C++ 中的循环双向链表

C++ 2周前 10

本文将演示如何在 C++ 中实现循环双向链表。

C++ 中从头开始的循环双向链表数据结构

双向链表是一种数据结构，其中每个节点都存储指向下一个和前一个节点的指针。这使其成为实现 std::deque 类容器的最佳选择。最好制作一个双向链表循环，以便最后一个节点的 next 成员指向列表的开头，第一个节点也指向最后一个节点作为它的前一个节点。

首先，我们需要声明一个名为 ListNode 的 struct，用于构造一个列表。接下来，我们定义一个 CircularList 类，其中包含两个类型为 ListNode* 的数据成员和三个成员函数。

请注意，我们决定只包含一个接受 string 值并初始化第一个节点的构造函数，但这部分可以根据程序员的需要进行修改。两个数据成员 – head 和 end – 存储第一个和最后一个节点。我们还有单独的函数来在列表的每一侧添加元素。

#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 函数来显示列表内容，因为我们可能需要检查代码的正确性。请注意，在列表对象超出范围后，一定不要忘记释放所有内存。后一个函数是作为析构函数实现的。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布，任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站。本站所有源码与软件均为原作者提供，仅供学习和研究使用。如您对本站的相关版权有任何异议，或者认为侵犯了您的合法权益，请及时通知我们处理。

C++

C++ 中从头开始的循环双向链表数据结构

相关文章