C++ 循环链表删除结点前驱函数 rcl_delete_pre

本文介绍使用 C++ 编写的函数 void rcl_delete_pre(chainList &p)，用于删除循环链表中结点 p 的直接前驱。

#include <iostream>

struct Node {
    int data;
    Node* next;
};

typedef Node* chainList;

void rcl_delete_pre(chainList &p) {
    if (p == nullptr || p->next == nullptr) {
        std::cout << "Error: Invalid node or empty list!\n";
        return;
    }

    chainList pre = p;
    while (pre->next->next != p) {
        pre = pre->next;
    }

    chainList temp = pre->next;
    pre->next = p;
    delete temp;
}

int main() {
    // 创建循环链表示例
    chainList list = new Node;
    list->data = 1;

    chainList node2 = new Node;
    node2->data = 2;

    chainList node3 = new Node;
    node3->data = 3;

    chainList node4 = new Node;
    node4->data = 4;

    list->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = list;

    // 删除结点的直接前驱
    std::cout << "Before deletion: ";
    chainList curr = list;
    do {
        std::cout << curr->data << " ";
        curr = curr->next;
    } while (curr != list);
    std::cout << "\n";

    rcl_delete_pre(node3);

    std::cout << "After deletion: ";
    curr = list;
    do {
        std::cout << curr->data << " ";
        curr = curr->next;
    } while (curr != list);
    std::cout << "\n";

    // 释放内存
    delete node4;
    delete node3;
    delete node2;
    delete list;

    return 0;
}

在上面的代码中，我们首先定义了结点的结构体 Node，然后使用 typedef 将 Node* 命名为 chainList，作为链表的别名。

函数 rcl_delete_pre 的实现如下：

1. 首先，检查链表是否为空或结点 p 的下一个结点为 nullptr，这些情况下无法删除直接前驱，输出错误信息并返回。
2. 创建一个指针 pre，指向结点 p。
3. 通过循环找到结点 p 的直接前驱 pre，即 pre 的下一个结点的下一个结点为 p。
4. 创建一个指针 temp，指向 pre 的下一个结点。
5. 将 pre 的下一个结点指向 p，即删除了直接前驱。
6. 删除 temp 指向的结点。

在主函数中，我们创建一个循环链表示例并展示删除前后的链表。最后，我们释放了动态分配的内存以避免内存泄漏。

请注意，此代码仅删除了直接前驱，如果需要删除任意结点的前驱，可以稍作修改。

代码解释

1. 首先，定义了 Node 结构体，其中包含 data 和 next 两个成员。data 用于存储结点的数据，next 指向下一个结点。
2. 使用 typedef 将 Node* 命名为 chainList，方便代码编写和阅读。
3. 函数 rcl_delete_pre 接受一个 chainList 类型的参数 p，该参数指向要删除其前驱的结点。
4. 函数首先检查链表是否为空或结点 p 的下一个结点为 nullptr，如果为空，则输出错误信息并返回。
5. 创建一个指针 pre，指向结点 p。
6. 使用 while 循环找到结点 p 的直接前驱 pre，即 pre 的下一个结点的下一个结点为 p。
7. 创建一个指针 temp，指向 pre 的下一个结点。
8. 将 pre 的下一个结点指向 p，即删除了 pre 的下一个结点（即 temp 指向的结点）。
9. 删除 temp 指向的结点，释放内存。

使用方法

1. 创建一个循环链表。
2. 调用 rcl_delete_pre 函数，传入要删除其前驱的结点。

注意

1. 此函数只删除了直接前驱，如果需要删除任意结点的前驱，可以稍作修改。
2. 在使用此函数之前，请确保链表不为空且传入的结点有效。
3. 删除结点后，需要释放内存以避免内存泄漏。