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

Muhammad Husnain 2023年1月30日 2022年6月21日
  1. C++ 中的列表
  2. 在 C++ 中實現連結串列
  3. 在 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 節點的資料是否大於下一個節點的資料。如果較大,則交換 currtemp
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
Muhammad Husnain avatar Muhammad Husnain avatar

Husnain is a professional Software Engineer and a researcher who loves to learn, build, write, and teach. Having worked various jobs in the IT industry, he especially enjoys finding ways to express complex ideas in simple ways through his content. In his free time, Husnain unwinds by thinking about tech fiction to solve problems around him.

LinkedIn

相關文章 - C++ Sorting