C++ 环形双向链表删除元素算法详解

问题描述:

构造一个环形双向链表，节点中存储的值为正整数，用这个链表进行删除操作。链表中的元素均不超过 100000。

输入格式:

多行输入，从第一行开始，每行一个正整数代表链表中的元素，直到遇到 -1，之后每行一个正整数 'x' 代表要删除的元素。若删除的元素在链表中存在，则将链表中所有的 'x' 全部删去，若不存在，则输出 -1。输入再次遇到 -1 结束，最后将链表中剩余的元素输出。

输出格式:

输出若干行，每行若干个整数。对于每个要删除的元素，若删除失败，输出 -1，最后输出链表的剩余元素。

C++ 代码示例:

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node* prev;
};

// 创建一个新的节点
Node* createNode(int val) {
    Node* newNode = new Node;
    newNode->val = val;
    newNode->next = newNode;
    newNode->prev = newNode;
    return newNode;
}

// 将一个新节点插入到环形链表中
void insert(Node*& head, int val) {
    Node* newNode = createNode(val);
    if (head == nullptr) {
        head = newNode;
        return;
    }
    newNode->next = head;
    newNode->prev = head->prev;
    head->prev->next = newNode;
    head->prev = newNode;
}

// 删除环形链表中的指定节点
void deleteNode(Node*& head, int val) {
    if (head == nullptr) {
        return;
    }
    Node* cur = head;
    bool found = false;
    do {
        if (cur->val == val) {
            found = true;
            if (cur == head && cur->next == cur) {
                head = nullptr;
            } else {
                cur->prev->next = cur->next;
                cur->next->prev = cur->prev;
                if (cur == head) {
                    head = cur->next;
                }
            }
            delete cur;
            cur = head;
        } else {
            cur = cur->next;
        }
    } while (cur != head);
    if (!found) {
        cout << '-1' << endl;
    }
}

// 打印环形链表
void printList(Node* head) {
    if (head == nullptr) {
        return;
    }
    Node* cur = head;
    do {
        cout << cur->val << ' ';
        cur = cur->next;
    } while (cur != head);
    cout << endl;
}

int main() {
    Node* head = nullptr;
    int val;
    cin >> val;
    while (val != -1) {
        insert(head, val);
        cin >> val;
    }
    cin >> val;
    while (val != -1) {
        deleteNode(head, val);
        cin >> val;
    }
    printList(head);
    return 0;
}

代码解释:

结构体 Node: 定义了链表节点的结构，包含节点值 val，下一个节点 next 和上一个节点 prev 的指针。
createNode 函数: 创建一个新的节点，并将其初始化为一个环形链表，其中 next 和 prev 指向自身。
insert 函数: 将一个新节点插入到环形链表中。首先判断链表是否为空，若为空，则将新节点设为头节点。否则，将新节点插入到头节点之前，并将头节点的前一个节点指向新节点。
deleteNode 函数: 删除环形链表中的指定节点。首先判断链表是否为空，若为空则直接返回。否则，遍历链表，找到要删除的节点，并将该节点的前一个节点的 next 指针指向该节点的下一个节点，以及该节点的下一个节点的 prev 指针指向该节点的前一个节点。最后，删除该节点。如果遍历完整个链表没有找到要删除的节点，则输出 -1。
printList 函数: 打印环形链表的所有节点。
main 函数: 读取用户输入的元素，构建环形链表，并进行删除操作，最后输出剩余的元素。

注意事项:

此代码仅供参考，可根据具体需求进行修改。
在使用完链表后，需要释放所有节点的内存空间，避免内存泄漏。
在实际应用中，需要考虑对输入数据的合法性进行验证，例如判断输入的元素是否为正整数。

总结:

本文介绍了如何使用 C++ 构建一个环形双向链表，并实现删除指定元素的功能。该算法简单易懂，且效率较高，适合处理各种数据结构问题。