HOWTO · 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;
}
}
}
};
在這個類中，有一個建構函式和另外兩個成員函式來插入和顯示列表節點。
在 C++ 中對連結串列進行排序
我們將實現最簡單的排序演算法，氣泡排序，以升序對連結串列進行排序。如果以未排序的順序放置，此排序演算法會重複交換相鄰元素。
重複執行此操作，直到所有元素都處於正確的排序位置。這將按如下方式實施：
-
建立一個新節點
temp供以後使用，並使head成為curr節點。 -
如果
head為 NULL，則返回。 -
否則，進行迴圈，直到到達
end節點（即 NULL）。 -
每次重複都應重複步驟 5-6。
-
在
temp中，儲存curr節點的下一個節點。 -
檢查
curr節點的資料是否大於下一個節點的資料。如果較大，則交換curr和temp。
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
