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

Muhammad Husnain 2023年1月30日 2022年6月21日

C++ C++ Sorting

C++ 中的列表
在 C++ 中实现链表
在 C++ 中对链表进行排序

这个简单的编程教程演示了在 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;
            }
        }
    }
};

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