迹忆客 专注技术分享

这个简单的编程教程演示了在 C++ 中对链表数据结构的排序操作的实现。

C++ 中的列表

列表或链表是一种线性数据结构，可以作为数据容器，将数据存储在内存中。与向量或数组不同，列表中的数据不需要连续的内存位置；相反，数据可以动态增长并分配到任意堆内存位置。

列表中的每个元素称为一个节点。列表中的每个节点都包含一个指向列表的下一个节点的指针。

在每个节点中包含指向下一个元素的指针可以促进线性链接，其中每个下一个元素都可以通过前一个节点访问。节点之间的这种线性链接是将此结构命名为链表的主要原因。

可以对链表执行多种 ADT（抽象数据类型）操作，例如插入、删除、搜索甚至排序。我们将从链表的基本结构实现开始，然后在该类中实现排序算法。

在 C++ 中实现链表

现在，我们将开始实现链表。为此，首先，我们需要为 Node 创建一个类，如下所示：

template <class T >
class Node
{
public:
    T data;
    Node<T>* next;
    Node ( ){
        next = 0;
    }
};

在这个类中，有两个成员，一个用于存储数据，即 info，另一个是该类的指针，用于存储下一个节点的地址。该类被模板化，以便可以创建任何数据类型的列表。

现在，我们将创建一个这样的链表类：

template <class T>
class LSLL
{
private:
    Node<T> * head;
public:
    LSLL ( ){
        head = 0;
    }
    void insertAtHead ( T val )
    {
        Node<T>* x = new Node<T>(val);
        x-> next = head;
        head = x;
    }
    void displayAll ( )
    {
        Node<T>* x = head;
        {
            while ( x != 0 )
            {
                cout<<x->info<<endl;
                x = x->next;
            }
        }
    }
};

在这个类中，有一个构造函数和另外两个成员函数来插入和显示列表节点。

在 C++ 中对链表进行排序

我们将实现最简单的排序算法，冒泡排序，以升序对链表进行排序。如果以未排序的顺序放置，此排序算法会重复交换相邻元素。

重复执行此操作，直到所有元素都处于正确的排序位置。这将按如下方式实施：

void sortLinkedList( ) {
   Node<T> *curr = head, *temp = NULL;
    int t;
    if (head == NULL) {
        return;
    }else {
        while (curr != NULL) {
            temp = curr->next;
            while (temp != NULL) {
            if (curr->info > temp->info) {
                t = curr->info;
                curr->info = temp->info;
                temp->info = t;
            }
            temp = temp->next;
        }
        curr = curr->next;
        }
    }
}

驱动程序将是：

int main ()
{
    LSLL<int> list;
    list.insertAtHead ( 50 );
    list.insertAtHead ( 45 );
    list.insertAtHead ( 16 );
    cout<<"Before sorting"<<endl;
    list.displayAll();
    cout<<"After Sorting: "<<endl;
    list.sortLinkedList();
    list.displayAll();
    return 0;
}

输出：

Before sorting
43
65
13
After Sorting:
13
43
65