跳到主要内容

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时间。
  • 环形缓冲区:循环链表可以用于实现环形缓冲区,用于数据流的处理。

总结

循环链表是一种非常有用的数据结构,特别适用于需要循环访问的场景。通过本文的学习,你应该已经掌握了循环链表的基本概念、实现方法以及实际应用场景。

提示

建议你尝试自己实现一个循环链表,并编写一些操作函数,如插入、删除、遍历等,以加深对循环链表的理解。

附加资源

练习

  1. 编写一个函数,计算循环链表中节点的数量。
  2. 实现一个函数,将两个循环链表合并为一个。
  3. 尝试用循环链表解决约瑟夫问题。

通过完成这些练习,你将更好地掌握循环链表的使用和操作。