C++实现双向循环链表：创建、查询与删除

本文提供了一个使用C++编写的双向循环链表示例，包括创建、查询和删除操作，并对每个函数进行详细讲解。cpp#include

typedef struct Node { int data; struct Node* prev; struct Node* next;} DoublyCircularLinkedList;

// 创建双向循环链表DoublyCircularLinkedList* createDoublyCircularLinkedList() { int n; std::cout << '请输入节点数目: '; std::cin >> n;

DoublyCircularLinkedList* head = nullptr;    DoublyCircularLinkedList* prevNode = nullptr;

for (int i = 0; i < n; i++) {        int value;        std::cout << '请输入第 ' << i+1 << ' 个节点的值: ';        std::cin >> value;

    DoublyCircularLinkedList* newNode = new DoublyCircularLinkedList;        newNode->data = value;

    if (head == nullptr) {            head = newNode;        } else {            prevNode->next = newNode;            newNode->prev = prevNode;        }

    prevNode = newNode;    }

// 将最后一个节点的next指向head，并将head的prev指向最后一个节点，形成循环链表    prevNode->next = head;    head->prev = prevNode;

return head;}

// 查询双向循环链表void searchDoublyCircularLinkedList(DoublyCircularLinkedList* head, int target) { if (head == nullptr) { std::cout << '链表为空' << std::endl; return; }

DoublyCircularLinkedList* current = head;    bool found = false;

do {        if (current->data == target) {            found = true;            std::cout << '找到目标值 ' << target << std::endl;        }

    current = current->next;    } while (current != head);

if (!found) {        std::cout << '未找到目标值 ' << target << std::endl;    }}

// 删除双向循环链表中的节点void deleteNode(DoublyCircularLinkedList*& head, int target) { if (head == nullptr) { std::cout << '链表为空' << std::endl; return; }

DoublyCircularLinkedList* current = head;

// 遍历链表，找到目标节点    while (current->data != target) {        current = current->next;

    // 如果遍历回到了头节点，说明节点不存在        if (current == head) {            std::cout << '未找到目标节点 ' << target << std::endl;            return;        }    }

// 删除目标节点    if (current == head) {        // 如果目标节点是头节点，需要更新头节点的指针        head = head->next;    }

current->prev->next = current->next;    current->next->prev = current->prev;    delete current;

std::cout << '成功删除节点 ' << target << std::endl;}

// 打印双向循环链表void printDoublyCircularLinkedList(DoublyCircularLinkedList* head) { if (head == nullptr) { std::cout << '链表为空' << std::endl; return; }

DoublyCircularLinkedList* current = head;

do {        std::cout << current->data << ' ';        current = current->next;    } while (current != head);

std::cout << std::endl;}

// 释放双向循环链表的内存void releaseDoublyCircularLinkedList(DoublyCircularLinkedList*& head) { if (head == nullptr) { return; }

DoublyCircularLinkedList* current = head->next;    DoublyCircularLinkedList* temp;

while (current != head) {        temp = current;        current = current->next;        delete temp;    }

delete head;    head = nullptr;}

int main() { DoublyCircularLinkedList* head = createDoublyCircularLinkedList(); printDoublyCircularLinkedList(head);

int target;    std::cout << '请输入要查找的目标值: ';    std::cin >> target;    searchDoublyCircularLinkedList(head, target);

std::cout << '请输入要删除的节点值: ';    std::cin >> target;    deleteNode(head, target);    printDoublyCircularLinkedList(head);

releaseDoublyCircularLinkedList(head);

return 0;}

函数解析:

createDoublyCircularLinkedList(): 该函数用于创建双向循环链表。 - 首先，用户需要输入节点的数量和每个节点的值。 - 然后，函数动态分配内存创建新节点，并将节点值存储在data成员变量中。 - 函数通过prev和next指针将节点连接起来，并最终将最后一个节点的next指向头节点，将头节点的prev指向最后一个节点，形成循环链表。 - 函数返回链表的头结点。
searchDoublyCircularLinkedList(): 该函数用于查询双向循环链表中是否存在目标值。 - 首先，函数检查链表是否为空。 - 然后，函数遍历链表，并在找到目标值时输出信息。 - 如果遍历完整个链表都没有找到目标值，则输出未找到的信息。
deleteNode(): 该函数用于删除双向循环链表中的节点。 - 首先，函数检查链表是否为空。 - 然后，函数遍历链表，找到目标节点。 - 如果目标节点是头节点，需要更新头节点的指针。 - 最后，函数删除目标节点，并释放其内存空间。
printDoublyCircularLinkedList(): 该函数用于打印双向循环链表的所有节点值。 - 首先，函数检查链表是否为空。 - 然后，函数遍历链表，并打印每个节点的值。
releaseDoublyCircularLinkedList(): 该函数用于释放双向循环链表的内存。 - 首先，函数检查链表是否为空。 - 然后，函数遍历链表，并删除每个节点。 - 最后，函数将头节点指针设置为nullptr。

主函数

在主函数中，我们首先创建双向循环链表并打印它，然后询问用户要查找的目标值，并进行查询操作。接下来，询问用户要删除的节点值，并进行删除操作。最后，释放链表的内存。

这段代码提供了一个简单易懂的双向循环链表实现示例，可以帮助您更好地理解双向循环链表的概念和操作方法。