C 语言循环链表
介绍
循环链表是一种特殊的链表数据结构,它与普通链表的区别在于:循环链表的最后一个节点的指针指向链表的第一个节点,而不是指向 NULL
。这种结构使得链表形成一个闭环,可以在某些场景下提供更高效的操作。
循环链表可以是单向的,也可以是双向的。在本文中,我们将重点介绍单向循环链表。
循环链表的定义
循环链表的基本结构与普通链表类似,每个节点包含两个部分:
- 数据域:存储节点的数据。
- 指针域:存储指向下一个节点的指针。
与普通链表不同的是,循环链表的最后一个节点的指针指向链表的头节点,而不是 NULL
。
循环链表的实现
定义节点结构
首先,我们需要定义一个结构体来表示链表的节点:
c
struct Node {
int data; // 数据域
struct Node* next; // 指针域,指向下一个节点
};
创建循环链表
接下来,我们编写一个函数来创建一个简单的循环链表。假设我们要创建一个包含三个节点的循环链表:
c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void createCircularLinkedList() {
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// 分配内存
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
// 赋值
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = head; // 最后一个节点指向头节点,形成循环
// 打印链表
struct Node* current = head;
do {
printf("%d -> ", current->data);
current = current->next;
} while (current != head);
printf("HEAD\n");
}
int main() {
createCircularLinkedList();
return 0;
}
输出:
1 -> 2 -> 3 -> HEAD
备注
注意:在循环链表中,遍历时需要特别注意终止条件,通常使用 do-while
循环来确保至少遍历一次。
插入节点
在循环链表中插入节点的操作与普通链表类似,但需要特别注意处理头节点和尾节点的指针。
c
void insertNode(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (*head == NULL) {
*head = newNode;
newNode->next = newNode; // 只有一个节点时,指向自己
} else {
struct Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
newNode->next = *head;
}
}
删除节点
删除节点的操作也需要特别注意循环链表的特性,确保链表的闭环不被破坏。
c
void deleteNode(struct Node** head, int key) {
if (*head == NULL) return;
struct Node *current = *head, *prev = NULL;
// 查找要删除的节点
do {
if (current->data == key) {
break;
}
prev = current;
current = current->next;
} while (current != *head);
// 如果节点不存在
if (current->data != key) return;
// 如果链表只有一个节点
if (current->next == *head && prev == NULL) {
*head = NULL;
free(current);
return;
}
// 如果删除的是头节点
if (current == *head) {
prev = *head;
while (prev->next != *head) {
prev = prev->next;
}
*head = current->next;
prev->next = *head;
free(current);
} else {
prev->next = current->next;
free(current);
}
}
实际应用场景
循环链表在某些场景下非常有用,例如:
- 约瑟夫问题:循环链表可以用于解决经典的约瑟夫问题,即一群人围成一圈,每隔一定数量的人就被淘汰,直到最后剩下一个人。
- 轮询调度:在操作系统中,循环链表可以用于实现轮询调度算法,确保每个任务都能公平地获得CPU时间。
- 环形缓冲区:循环链表可以用于实现环形缓冲区,用于数据流的处理。
总结
循环链表是一种非常有用的数据结构,特别适用于需要循环访问的场景。通过本文的学习,你应该已经掌握了循环链表的基本概念、实现方法以及实际应用场景。
提示
建议你尝试自己实现一个循环链表,并编写一些操作函数,如插入、删除、遍历等,以加深对循环链表的理解。
附加资源
练习
- 编写一个函数,计算循环链表中节点的数量。
- 实现一个函数,将两个循环链表合并为一个。
- 尝试用循环链表解决约瑟夫问题。
通过完成这些练习,你将更好地掌握循环链表的使用和操作。