在 C++ 中對連結串列進行排序

Muhammad Husnain 2023年10月12日

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

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