C++
C++循环链表
admin SU @ 2025-6-9 21:10:16

循环链表基础概念

循环链表是一种特殊的链表结构，它和普通链表的区别在于尾节点的指针指向头节点，形成一个闭环。这样的结构让链表可以循环遍历，适合实现需要循环特性的场景，比如多人游戏中的玩家轮询、操作系统的任务调度等。

循环链表节点结构体设计

首先我们需要定义链表的基本单元——节点。每个节点包含两部分：数据域和指针域。

// 循环链表节点结构体
struct Node {
    int data;         // 数据域，存储节点的值
    Node* next;       // 指针域，指向下一个节点
    
    // 构造函数，方便节点初始化
    Node(int value) : data(value), next(nullptr) {}
};

循环链表的基本操作实现

下面是循环链表的核心操作实现，包含创建、插入、删除和遍历等功能。

#include <iostream>
using namespace std;

// 循环链表节点结构体（同上）
struct Node {
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

// 循环链表类，封装所有操作
class CircularLinkedList {
private:
    Node* head;  // 头指针，指向链表的第一个节点

public:
    // 构造函数，初始化空链表
    CircularLinkedList() : head(nullptr) {}

    // 判断链表是否为空
    bool isEmpty() {
        return head == nullptr;
    }

    // 在链表尾部添加新节点
    void append(int value) {
        Node* newNode = new Node(value);
        
        if (isEmpty()) {
            // 空链表的情况，新节点就是头节点，并且指向自己
            head = newNode;
            newNode->next = head;
        } else {
            // 非空链表，找到尾节点
            Node* tail = head;
            while (tail->next != head) {
                tail = tail->next;
            }
            // 插入新节点并更新尾指针
            tail->next = newNode;
            newNode->next = head;
        }
    }

    // 在链表头部插入新节点
    void prepend(int value) {
        Node* newNode = new Node(value);
        
        if (isEmpty()) {
            // 空链表的情况，新节点就是头节点，并且指向自己
            head = newNode;
            newNode->next = head;
        } else {
            // 非空链表，找到尾节点
            Node* tail = head;
            while (tail->next != head) {
                tail = tail->next;
            }
            // 插入新节点并更新头指针
            newNode->next = head;
            head = newNode;
            tail->next = head;  // 让尾节点指向新的头节点
        }
    }

    // 删除指定值的第一个节点
    void remove(int value) {
        if (isEmpty()) return;  // 空链表直接返回
        
        // 如果要删除的是头节点
        if (head->data == value) {
            // 如果链表只有一个节点
            if (head->next == head) {
                delete head;
                head = nullptr;
            } else {
                // 找到尾节点
                Node* tail = head;
                while (tail->next != head) {
                    tail = tail->next;
                }
                // 删除头节点并更新头指针
                Node* temp = head;
                head = head->next;
                tail->next = head;
                delete temp;
            }
            return;
        }
        
        // 查找要删除节点的前一个节点
        Node* prev = head;
        while (prev->next != head && prev->next->data != value) {
            prev = prev->next;
        }
        
        // 如果找到了要删除的节点
        if (prev->next != head) {
            Node* temp = prev->next;
            prev->next = temp->next;
            delete temp;
        }
    }

    // 遍历链表并打印所有节点的值
    void display() {
        if (isEmpty()) {
            cout << "链表为空" << endl;
            return;
        }
        
        Node* current = head;
        do {
            cout << current->data << " ";
            current = current->next;
        } while (current != head);  // 当回到头节点时结束循环
        cout << endl;
    }

    // 析构函数，释放链表内存
    ~CircularLinkedList() {
        if (isEmpty()) return;
        
        Node* current = head;
        Node* nextNode;
        
        // 先断开循环，便于释放内存
        Node* tail = head;
        while (tail->next != head) {
            tail = tail->next;
        }
        tail->next = nullptr;
        
        // 逐个释放节点
        while (current != nullptr) {
            nextNode = current->next;
            delete current;
            current = nextNode;
        }
    }
};

使用示例

下面是如何使用上述循环链表类的示例代码：

int main() {
    CircularLinkedList cll;
    
    // 添加节点
    cll.append(10);
    cll.append(20);
    cll.append(30);
    cout << "添加节点后: ";
    cll.display();  // 输出: 10 20 30
    
    // 在头部插入节点
    cll.prepend(5);
    cout << "头部插入节点后: ";
    cll.display();  // 输出: 5 10 20 30
    
    // 删除节点
    cll.remove(20);
    cout << "删除节点20后: ";
    cll.display();  // 输出: 5 10 30
    
    return 0;
}

关键知识点总结

结构特点：循环链表的尾节点指针指向头节点，形成闭环。
操作注意事项：
- 插入和删除操作需要特别处理头尾节点的连接关系
- 遍历时需要使用do-while循环确保头节点也被访问到
- 空链表的处理需要单独判断
适用场景：适合需要循环访问数据的场景，如游戏轮询、任务调度等。

通过以上代码和解释，你应该对循环链表有了基本的理解。可以尝试运行示例代码，并根据自己的需求扩展更多功能，比如查找节点、获取链表长度等。

admin SU @ 2025-6-9 21:12:23

C++ 循环链表教程

循环链表是一种链式数据结构，与普通单向链表不同的是，它的最后一个节点指向第一个节点，形成一个环。这种结构非常适合需要循环遍历的场景。

一、定义结构体

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct Node {
    int data;        // 节点中存储的数据
    Node* next;      // 指向下一个节点的指针
};

二、创建新节点函数

// 创建新节点的函数
Node* createNode(int value) {
    Node* newNode = new Node();  // 动态分配内存
    newNode->data = value;       // 设置节点数据
    newNode->next = nullptr;     // 初始化下一个节点指针
    return newNode;
}

三、插入节点函数

在末尾插入节点

// 在循环链表末尾插入节点
void insertAtEnd(Node*& tail, int value) {
    Node* newNode = createNode(value);  // 创建新节点
    
    if (tail == nullptr) {  // 如果链表为空
        tail = newNode;     // 新节点就是尾节点
        newNode->next = tail;  // 形成自环
    } else {
        // 插入到尾节点后面
        newNode->next = tail->next;  // 新节点指向头节点
        tail->next = newNode;        // 原来的尾节点指向新节点
        tail = newNode;              // 更新尾节点
    }
}

四、删除节点函数

// 删除指定值的节点
void deleteNode(Node*& tail, int value) {
    if (tail == nullptr) {
        cout << "链表为空，无法删除" << endl;
        return;
    }

    Node* current = tail->next;  // 从头节点开始查找
    Node* prev = tail;           // 前一个节点

    do {
        if (current->data == value) {
            if (current == current->next) {  // 只有一个节点的情况
                delete current;
                tail = nullptr;
                return;
            }
            
            if (current == tail) {  // 如果要删除的是尾节点
                tail = prev;        // 更新尾节点
            }
            
            prev->next = current->next;  // 断开当前节点
            delete current;              // 释放内存
            return;
        }
        
        prev = current;
        current = current->next;
    } while (current != tail->next);  // 遍历完整个链表
    
    cout << "未找到要删除的值：" << value << endl;
}

五、遍历打印链表函数

// 打印循环链表
void printList(Node* tail) {
    if (tail == nullptr) {
        cout << "链表为空" << endl;
        return;
    }

    Node* temp = tail->next;  // 从头节点开始
    
    do {
        cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != tail->next);  // 直到回到头节点
    
    cout << "循环回起点" << endl;
}

六、主函数测试

int main() {
    Node* tail = nullptr;  // 初始为空链表
    
    // 插入一些节点
    insertAtEnd(tail, 10);
    insertAtEnd(tail, 20);
    insertAtEnd(tail, 30);
    insertAtEnd(tail, 40);
    
    // 打印链表
    cout << "初始链表：" << endl;
    printList(tail);
    
    // 删除一个节点
    cout << "\n删除20后的链表：" << endl;
    deleteNode(tail, 20);
    printList(tail);
    
    // 删除不存在的节点
    cout << "\n尝试删除50：" << endl;
    deleteNode(tail, 50);
    
    // 删除所有节点
    cout << "\n删除所有节点：" << endl;
    while (tail != nullptr) {
        deleteNode(tail, tail->next->data);
    }
    printList(tail);
    
    return 0;
}

程序输出示例：

初始链表：
10 -> 20 -> 30 -> 40 -> 循环回起点

删除20后的链表：
10 -> 30 -> 40 -> 循环回起点

尝试删除50：
未找到要删除的值：50

删除所有节点：
链表为空

总结

这个教程展示了如何使用C++中的结构体和指针实现循环链表的基本操作：

使用结构体定义链表节点
创建新节点
在末尾插入节点
删除指定节点
遍历并打印链表

循环链表的关键在于最后一个节点的next指针要指向第一个节点，这使得我们可以在不使用额外变量的情况下循环遍历整个链表。

admin SU @ 2025-6-9 21:11:05

在循环链表中插入节点有多种情况，主要分为在链表头部插入、尾部插入以及指定位置插入。以下是这些插入操作的详细实现：

1. 在链表尾部插入节点

// 在链表尾部添加新节点
void append(int value) {
    Node* newNode = new Node(value);
    
    if (isEmpty()) {
        // 空链表的情况，新节点就是头节点，并且指向自己
        head = newNode;
        newNode->next = head;
    } else {
        // 非空链表，找到尾节点
        Node* tail = head;
        while (tail->next != head) {
            tail = tail->next;
        }
        // 插入新节点并更新尾指针
        tail->next = newNode;
        newNode->next = head;
    }
}

2. 在链表头部插入节点

// 在链表头部插入新节点
void prepend(int value) {
    Node* newNode = new Node(value);
    
    if (isEmpty()) {
        // 空链表的情况，新节点就是头节点，并且指向自己
        head = newNode;
        newNode->next = head;
    } else {
        // 非空链表，找到尾节点
        Node* tail = head;
        while (tail->next != head) {
            tail = tail->next;
        }
        // 插入新节点并更新头指针
        newNode->next = head;
        head = newNode;
        tail->next = head;  // 让尾节点指向新的头节点
    }
}

3. 在指定位置插入节点

// 在指定位置（位置索引从0开始）插入新节点
void insertAt(int position, int value) {
    if (position < 0) return;  // 位置不能为负数
    
    Node* newNode = new Node(value);
    
    if (isEmpty()) {
        // 空链表只能插入到位置0
        if (position == 0) {
            head = newNode;
            newNode->next = head;
        }
        return;
    }
    
    if (position == 0) {
        // 在头部插入（等同于prepend操作）
        Node* tail = head;
        while (tail->next != head) {
            tail = tail->next;
        }
        newNode->next = head;
        head = newNode;
        tail->next = head;
        return;
    }
    
    // 找到插入位置的前一个节点
    Node* current = head;
    int count = 0;
    while (count < position - 1 && current->next != head) {
        current = current->next;
        count++;
    }
    
    // 如果位置超出链表长度，插入到尾部
    if (current->next == head) {
        current->next = newNode;
        newNode->next = head;
    } else {
        // 正常插入操作
        newNode->next = current->next;
        current->next = newNode;
    }
}

插入操作的关键点

空链表处理：空链表插入时，新节点需要自己形成循环（next指向自身）。
头尾节点更新：
- 头部插入时，需要更新尾节点的next指针指向新头节点
- 尾部插入时，需要更新新节点的next指针指向头节点
插入位置：
- 插入位置的合法性检查（如位置不能为负）
- 位置超出链表长度时的处理（通常插入到尾部）

通过上述函数，你可以在循环链表的不同位置灵活插入新节点。实际应用中，根据具体需求选择合适的插入方式即可。

C++循环链表

循环链表基础概念

循环链表节点结构体设计

循环链表的基本操作实现

使用示例

关键知识点总结

2 条评论

C++ 循环链表教程

一、定义结构体

二、创建新节点函数

三、插入节点函数

在末尾插入节点

四、删除节点函数

五、遍历打印链表函数

六、主函数测试

程序输出示例：

总结

1. 在链表尾部插入节点

2. 在链表头部插入节点

3. 在指定位置插入节点

插入操作的关键点

状态

开发

支持

C++循环链表

循环链表基础概念

循环链表节点结构体设计

循环链表的基本操作实现

使用示例

关键知识点总结

2 条评论

C++ 循环链表教程

一、定义结构体

二、创建新节点函数

三、插入节点函数

在末尾插入节点

四、删除节点函数

五、遍历打印链表函数

六、主函数测试

程序输出示例：

总结

1. 在链表尾部插入节点

2. 在链表头部插入节点

3. 在指定位置插入节点

插入操作的关键点

状态

开发

支持

还没有账户？

登录