在 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;
            }
        }
    }
};

在這個類中，有一個建構函式和另外兩個成員函式來插入和顯示列表節點。