C++ 中的迴圈雙向連結串列

Jinku Hu 2021年10月2日
C++ 中的迴圈雙向連結串列

本文將演示如何在 C++ 中實現迴圈雙向連結串列。

C++ 中從頭開始的迴圈雙向連結串列資料結構

雙向連結串列是一種資料結構,其中每個節點都儲存指向下一個和前一個節點的指標。這使其成為實現 std::deque 類容器的最佳選擇。最好製作一個雙向連結串列迴圈,以便最後一個節點的 next 成員指向列表的開頭,第一個節點也指向最後一個節點作為它的前一個節點。

首先,我們需要宣告一個名為 ListNodestruct,用於構造一個列表。接下來,我們定義一個 CircularList 類,其中包含兩個型別為 ListNode* 的資料成員和三個成員函式。

請注意,我們決定只包含一個接受 string 值並初始化第一個節點的建構函式,但這部分可以根據程式設計師的需要進行修改。兩個資料成員 - headend - 儲存第一個和最後一個節點。我們還有單獨的函式來在列表的每一側新增元素。

#include <iostream>
#include <string>
#include <vector>

using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;

struct ListNode {
    struct ListNode *next = nullptr;
    struct ListNode *prev = nullptr;
    string data;
} typedef ListNode;

class CircularList {
public:
    explicit CircularList(string data) {
        head = new ListNode;
        head->next = head;
        head->prev = head;
        head->data = std::move(data);
        end = head;
    };

    ListNode *insertNodeEnd(string data);
    ListNode *insertNodeHead(string data);
    void printNodes();

    ~CircularList();
private:
    ListNode *head = nullptr;
    ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
    auto new_node = new ListNode;
    new_node->next = head;
    new_node->prev = end;
    new_node->data = std::move(data);

    head->prev = new_node;
    end->next = new_node;
    end = end->next;
    return end;
}

ListNode *CircularList::insertNodeHead(string data) {
    auto new_node = new ListNode;
    new_node->next = head;
    new_node->prev = end;
    new_node->data = std::move(data);

    head->prev = new_node;
    end->next = new_node;
    head = new_node;
    return head;
}

CircularList::~CircularList() {
    while (head != end) {
        auto tmp = head;
        head = head->next;
        delete tmp;
    }
    delete head;
}

void CircularList::printNodes() {
    auto count = 0;
    auto tmp = head;
    while (tmp != end){
        cout << "node " << count << " - data: " << tmp->data << endl;
        tmp = tmp->next;
        count++;
    }
    cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
    CircularList clist("Xenial");

    clist.insertNodeHead("Saucy");
    clist.insertNodeEnd("Quantal");

    clist.printNodes();
    cout << " ----------------------------------- " << endl;

    clist.insertNodeHead("Bionic");
    clist.printNodes();

    return EXIT_SUCCESS;
}

輸出:

node 0 - data: Saucy
node 1 - data: Xenial
node 2 - data: Quantal
 -----------------------------------
node 0 - data: Bionic
node 1 - data: Saucy
node 2 - data: Xenial
node 3 - data: Quantal

元素插入的一般演算法需要分配一個新的 ListNode 物件,將相應的節點指標分配給其成員,然後根據需要修改 head/end 成員。我們還包括一個 printNodes 函式來顯示列表內容,因為我們可能需要檢查程式碼的正確性。請注意,在列表物件超出範圍後,一定不要忘記釋放所有記憶體。後一個函式是作為解構函式實現的。

Author: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn

相關文章 - C++ Data Structure