算法竞赛阶段二-数据结构（37）数据结构循环链表模拟实现

之前单链表中，数组全初始化为0，末尾最后一个next 存的就是0，指向的就是头节点

循环链表的基本概念

循环链表是一种特殊的链表，其尾节点的指针域指向头节点，形成一个闭环。与普通单链表相比，循环链表的遍历需要额外注意终止条件，避免无限循环。

循环链表的节点结构

循环链表的节点与普通链表节点相同，包含数据域和指针域。以C语言为例：

typedef struct Node { int data;  // 数据域 struct Node *next; // 指针域，指向下一个节点} Node;

循环链表的初始化

初始化时，头节点的指针域指向自身，形成空循环链表：

Node* initList() { Node *head = (Node*)malloc(sizeof(Node)); if (head != NULL) { head->next = head; // 头节点指向自身 } return head;}

循环链表的插入操作

头插法

新节点插入到头节点之后：

void insertAtHead(Node *head, int data) { Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->next = head->next; head->next = newNode;}

尾插法

新节点插入到尾节点之后（需先遍历到尾节点）：

void insertAtTail(Node *head, int data) { Node *current = head; while (current->next != head) { current = current->next; } Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->next = head; current->next = newNode;}

循环链表的删除操作

删除指定值的节点：

void deleteNode(Node *head, int data) { Node *current = head; while (current->next != head) { if (current->next->data == data) { Node *temp = current->next; current->next = temp->next; free(temp); return; } current = current->next; }}

循环链表的遍历

遍历时需检查是否回到头节点：

void traverseList(Node *head) { Node *current = head->next; while (current != head) { printf(\"%d \", current->data); current = current->next; } printf(\"\\n\");}

循环链表的销毁

释放所有节点内存，避免内存泄漏：

void destroyList(Node *head) { Node *current = head->next; while (current != head) { Node *temp = current; current = current->next; free(temp); } free(head);}

注意事项

1. 终止条件：循环链表的遍历和操作需明确终止条件（如current != head），否则会陷入无限循环。
2. 边界处理：空链表时需确保头节点指向自身。
3. 内存管理：动态分配的内存需及时释放。

通过上述方法，可以完整实现循环链表的基本操作。