循环链表（Circular Linked List）是一种特殊类型的线性链表，其不同之处在于最后一个节点的next指针不是指向NULL，而是指向链表的头节点，从而形成一个环。循环链表常用于那些需要周期性遍历节点的应用，比如实现循环队列或者轮询任务。
循环链表节点结构体
循环链表的节点结构体与线性链表类似，只是最后一个节点的next指针指向头节点。
|
typedef struct CircularListNode { |
|
int data; // 数据域 |
|
struct CircularListNode *next; // 指针域，指向下一个节点 |
|
} CircularListNode; |
循环链表的基本操作
初始化循环链表
创建一个空的循环链表，头节点的next指针指向自己。
|
// 初始化循环链表 |
|
CircularListNode* InitCircularList() { |
|
CircularListNode *head = (CircularListNode *)malloc(sizeof(CircularListNode)); |
|
if (!head) { |
|
exit(1); // 内存分配失败 |
|
} |
|
head->next = head; // 指向自己，形成循环 |
|
return head; |
|
} |
插入节点
在循环链表中插入节点通常有两种情况：在头部插入和在尾部插入。这里我们实现一个在尾部插入节点的函数。
|
// 在循环链表尾部插入节点 |
|
void InsertAtTail(CircularListNode *head, int value) { |
|
CircularListNode *newNode = (CircularListNode *)malloc(sizeof(CircularListNode)); |
|
if (!newNode) { |
|
exit(1); // 内存分配失败 |
|
} |
|
newNode->data = value; |
|
|
|
CircularListNode *temp = head; |
|
while (temp->next != head) { // 找到最后一个节点 |
|
temp = temp->next; |
|
} |
|
temp->next = newNode; // 将新节点插入到尾部 |
|
newNode->next = head; // 新节点的next指向头节点，形成循环 |
|
} |
删除节点
在循环链表中删除节点需要先找到要删除的节点的前一个节点，然后修改其next指针。
|
// 删除循环链表中的指定值节点 |
|
void DeleteNode(CircularListNode *head, int value) { |
|
if (head == NULL || head->next == head) { |
|
return; // 空链表或只有一个节点的链表，无需删除 |
|
} |
|
|
|
CircularListNode *current = head->next; // 从头节点的下一个节点开始遍历 |
|
CircularListNode *prev = head; |
|
|
|
while (current != head && current->data != value) { // 查找要删除的节点 |
|
prev = current; |
|
current = current->next; |
|
} |
|
|
|
if (current == head) { |
|
return; // 未找到要删除的节点 |
|
} |
|
|
|
prev->next = current->next; // 跳过要删除的节点 |
|
free(current); // 释放要删除节点的内存 |
|
} |
遍历链表
遍历循环链表与遍历线性链表类似，只是不需要检查next是否为NULL。
|
// 遍历循环链表并打印元素 |
|
void PrintList(CircularListNode *head) { |
|
if (head == NULL || head->next == head) { |
|
return; // 空链表或只有一个节点的链表，无需打印 |
|
} |
|
|
|
CircularListNode *current = head->next; // 从头节点的下一个节点开始遍历 |
|
do { |
|
printf("%d ", current->data); |
|
current = current->next; |
|
} while (current != head); // 当回到头节点时停止遍历 |
|
printf("\n"); |
|
} |
释放循环链表内存
与线性链表一样，需要释放循环链表所占用的内存。
|
// 释放循环链表内存 |
|
void FreeList(CircularListNode *head) { |
|
if (head == NULL) { |
|
return; // 空链表无需释放 |
|
} |
|
|
|
CircularListNode *current = head; |
|
CircularListNode *temp; |
|
do { |
|
temp = current; |
|
current = current->next; |
|
free(temp); |
|
} while (current != head); // 当回到头节点时停止释放 |
|
head = NULL; // 将头节点指针设为NULL |
|
} |
main 函数示例
在main函数中，我们可以创建一个循环链表，执行插入、删除和打印操作。
|
int main() { |
|
CircularListNode *head = InitCircularList(); // 初始化循环链表 |
|
|
|
// 插入节点 |
|
InsertAtTail(head, 1); |
|
InsertAtTail(head, 2); |
|
InsertAtTail(head, 3); |
