单向循环链表(Circular Linked List)
一、基本概念
循环链表是一种特殊的链表,其末尾节点的后继指针指向头结点,形成一个闭环。
循环链表的操作与普通链表基本一致,但需注意循环特性的处理。
二、代码实现
clList.h
#ifndef _CLLIST_H #define _CLLIST_H #include <stdio.h> #include <stdlib.h> #include <string.h> //定义节点数据的类型 typedef int DATA; //定义一个单向循环链表的节点 typedef struct node { DATA data; //节点数据域 struct node *next; //指针域,指向后继节点 }NODE; //函数原型的声明 /** * 创建链表 * @param head 待操作的链表 * @param data 待插入的数据 * @return 成功返回0,否则返回-1 */ extern int cllist_create(NODE **head, DATA data); /** * 在循环链表插入新节点(把新节点插入到头节点之前) * @param head 待操作的链表(默认是头节点) * @param data 待插入的数据 * @return 成功返回0,否则返回-1 */ extern int cllist_insert(NODE **head, DATA data); /** * 实现无头节点的头插法(插入在头节点之前) * @param head 待操作的链表(默认是头节点) * @param data 待插入的数据 * @return 成功返回0,否则返回-1 */ extern int cllist_insertAthead(NODE **head, DATA data); /** * 遍历链表数据 * @param head 待遍历的链表 * @return 成功返回0,否则返回-1 */ extern int cllist_showAll(const NODE *head); /** * 根据data返回查找对应的节点 * @param head 待操作的链表 * @param data 需要查找的节点数据 * @return 查找到的节点 */ extern NODE *cllist_find(const NODE *head, DATA data); /** * 根据newdata修改old对应的节点数据 * @param head 待操作的链表 * @param old 待修改的原数据 * @param newdata 待修改的新数据 * @return 成功返回0,否则返回-1 */ extern int cllist_update(const NODE *head, DATA old, DATA newdata); /** * 根据data删除对应的节点 * @param head 待操作的链表 * @param data 待删除的节点数据 * @return 成功返回0,否则返回-1 */ extern int cllist_delete(NODE **head, DATA data); /** * 销毁整个链表 * @param head 待销毁的链表 */ extern void cllist_destroy(NODE **head); #endif //_CLLIST_H
clList.c
#include "clList.h" //函数原型的声明 /** * 创建链表 * @param head 待操作的链表(head是指向头节点指针的地址) * @param data 待插入的数据 * @return 成功返回0,否则返回-1 */ int cllist_create(NODE **head, DATA data) { //如果链表存在,就无需创建 if(*head) { //打印错误信息到标准错误流(避免影响正常输出) fprintf(stderr, "链表已存在,无需创建!\n"); return -1; } //单向循环链表 //创建一个新节点 NODE *p = (NODE*)malloc(sizeof(NODE)); //校验新节点是否创建成功 if(!p) return -1; //初始化新节点 p->data = data; p->next = p; //循环特性:单个节点的next指向自身(即使单个节点也形成环) //设置头指针 *head = p; //将头指针设置为自己 } /** * 实现无头节点的头插法(插入在头节点之前) * @param head 待操作的链表(默认是头节点) * @param data 待插入的数据 * @return 成功返回0,否则返回-1 */ int cllist_insertAthead(NODE **head, DATA data) { //创建一个新节点 NODE *pNew = (NODE*)malloc(sizeof(NODE)); if(!pNew) { fprintf(stderr, "创建新节点失败!\n"); return -1; } //初始化新节点的数据域,指针域暂不赋值 pNew->data = data; NODE *p = *head; //创建一个遍历指针用来遍历链表寻找尾节点 //如果是空链表 if(!p) { pNew->next = pNew; *head = pNew; return 0; } //非空链表 pNew->next = *head; //新节点的next指向原头节点 //查找尾节点(原链表的最后一个节点) while(p->next != *head) //单向循环链表的尾节点next永远指向头节点(非NULL) { p = p->next; }//此时p是尾节点 p->next = pNew; *head = pNew; return 0; } /** * 在循环链表插入新节点(把新节点插入到头节点之前) * @param head 待操作的链表(默认是头节点) * @param data 待插入的数据 * @return 成功返回0,否则返回-1 */ int cllist_insert(NODE **head, DATA data) { //创建新节点 NODE *p = (NODE*)malloc(sizeof(NODE)); //校验节点是否创建成功 if(!p) return -1; //初始化新节点 p->data = data; p->next = p; //此时创建的新节点与链表还无关 //情景1:若待插入的链表是空链表 if(*head == NULL) { *head = p; //设置头指针,相当于创建了一个新链表 return 0; } //情景2:若待插入的链表是非空链表(在头节点和头节点的next之间插入,头节点不变) p->next = (*head)->next; //新节点指向原头节点的下一个节点 (*head)->next = p; //头节点指向新节点 } /** * 遍历链表数据 * @param head 待遍历的链表 * @return 成功返回0,否则返回-1 */ int cllist_showAll(const NODE *head) { //创建临时指针用于遍历(保持头指针不变) const NODE *p = head; //p指向当前遍历的节点 //空链表 if(!p) { fprintf(stderr, "空链表,没有数据!\n"); return -1; } //遍历列表 do //使用do—while保证至少执行依次(应对单节点循环链表) { printf("%d\t", p->data); p = p->next; }while(p != head); //循环终止条件:回到起始节点 printf("\n"); return 0; } /** * 根据data返回查找对应的节点 * @param head 待操作的链表 * @param data 需要查找的节点数据 * @return 查找到的节点 */ NODE *cllist_find(const NODE *head, DATA data) { //使用const指针避免意外修改节点 const NODE *p = head; //空链表 if(!head) return NULL; //遍历列表(确保至少执行一次) do { if(memcmp(&(p->data), &data, sizeof(DATA)) == 0) { return (NODE*)p; //强转,避免类型不匹配 } p = p->next; }while(p != head); return NULL; } /** * 根据newdata修改old对应的节点数据 * @param head 待操作的链表 * @param old 待修改的原数据 * @param newdata 待修改的新数据 * @return 成功返回0,否则返回-1 */ int cllist_update(const NODE *head, DATA old, DATA newdata) { NODE *p = cllist_find(head, old); if(!p) { fprintf(stderr, "数据未找到!\n"); return -1; } //找到旧数据的节点更新为新数据 p->data = newdata; return 0; } /** * 根据data删除对应的节点 * @param head 待操作的链表 * @param data 待删除的节点数据 * @return 成功返回0,否则返回-1 */ int cllist_delete(NODE **head, DATA data) { //尾随法(p为当前节点,q为前驱节点) NODE *p = *head, *q = NULL; //空链表 if(!*head) return -1; //遍历节点 while(p) { //找到要删除数据的位置 if(memcmp(&(p->data), &data, sizeof(DATA)) == 0) { //若要删除的节点是头节点 if(q == NULL) //指针还没有进行尾随,证明是头节点 { q = p->next; //获取头节点的下一个节点 //如果此头节点是唯一的头节点(p的next执行自身--头节点) if(p->next == *head) { //链表置空 *head = NULL; } else //链表中除了要删除的头节点还有其他节点 { //替换法(复制下一节点的数据并删除下一节点) p->data = q->data; //用头节点的后续节点数据替换头节点的数据,删除后续节点 p->next = q->next; free(q); } return 0; } //如果要删除的节点是非头节点 q->next = p->next; //前驱节点跳过当前节点 free(p); //释放当前节点 return 0; } q = p; p = p->next; //因为是循环链表,所以要想办法终结循环链表 if(p == *head) break; } return -1; } /** * 销毁整个单向循环链表 * @param head 待销毁的链表 */ void cllist_destroy(NODE **head) { //空链表 if(!*head) return; //在链表中找节点就用指针尾随法 NODE *p = *head, *q = NULL; //p指向当前节点,q用于保存待释放节点 while(p) { q = p; p = p->next; free(q); //解除循环链表 if(p == *head) break; } *head = NULL; //将头节点置空,不然会产生野指针 }
app.c
#include "clList.h" int main(int argc,char *argv[]) { NODE *head = NULL; //测试创建和插入 cllist_create(&head, 111); //创建头节点 cllist_insert(&head, 222); cllist_insert(&head, 333); cllist_insert(&head, 444); cllist_showAll(head); //111 444 333 222 cllist_insertAthead(&head, 222); cllist_insertAthead(&head, 333); cllist_insertAthead(&head, 444); cllist_showAll(head); //444 333 222 111 444 333 222 //测试更新 cllist_update(head, 333, 3333); cllist_showAll(head); //444 3333 222 111 444 333 222 //测试删除 cllist_delete(&head, 444); cllist_showAll(head); //3333 222 111 444 333 222 //销毁链表 cllist_destroy(&head); cllist_showAll(head); //空链表,没有数据 return 0; }
三、优缺点总结
优点
动态内存:无需预分配固定大小,适合数据量不确定的场景。
高效操作
头插/头删:O(1)时间复杂度
尾插:O(1)(维护尾指针时)或O(n)
中间插入:O(1)(定位后)
循环特性:适合周期性访问场景(如:轮询调度、循环缓冲区)
内存效率:按需分配,无扩容浪费
缺点:
随机访问 :必须遍历,时间复杂度O(n)
存储开销 :每个节点需额外存储指针
循环陷阱 :未正确处理终止条件会导致死循环
缓存不友好 :节点内存不连续,访问速度低于数组。
边界处理 :需特殊处理头尾节点的指针更新。
四、常见问题
1、数据结构的应用场景
所有编程领域都会涉及,例如
链表:内存管理、任务队列
树/图:数据库索引、路径规划
哈希表:高速缓存、字典实现
2、面试题--单次遍历找到倒数第50个节点
解法:使用双指针技术
初始化指针
fast
和slow
指向头节点fast
先移动50步然后
fast
和slow
同步移动,当fast
到达末尾时,slow
即指向倒数第50个节点
//单链表找倒数第k节点 NODE *findLastKth(NODE *head, int k) { NODE *fast = head, *slow = head; //先让快指针前进k步 for(int i = 0; i < k; i++) { //若快指针提前变空,说明链表长度不足k if(!fast) return NULL; fast = fast->next; } while(fast != NULL) { //循环链表终止条件 fast = fast->next; slow = slow->next; } return slow; }
//循环链表找倒数第k节点 NODE *findLastKth_Circular(NODE *head, int k) { if(!head || k <= 0) return NULL; NODE *fast = head, *slow = head; //快指针先快走n步 for(int i = 0; i < k; i++) { if(fast == head) return NULL; fast = fast->next; } //同步移动直到fast回到起点 while(fast != head) { fast = fast->next; slow = slow->next; } return slow; }
时间复杂度O(n),空间复杂度O(1)
练习题
【1】(单向链表)
题目:建立一个包含若干整数的单向链表,比如: 1,2,3,4,51,2,3,4,5
通过某些算法将其中各个节点逆转,比如: 5,4,3,2,15,4,3,2,1
分析:(约瑟夫环、单向循环链表)主要分析如何将链表倒转
代码:
/ #include <stdio.h> #include <stdlib.h> #define MAX_LENGHT 20 // 链表节点结构体 typedef struct ListNode { int data; // 节点数据域 struct ListNode *next; // 指向下一节点的指针 } Node; //尾插法创建链表 Node* createList(int arr[], int size) { if (size == 0) return NULL; Node *head = NULL, *tail = NULL; for (int i = 0; i < size; i++) { Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = NULL; if (head == NULL) { // 链表为空时初始化头尾指针 head = tail = newNode; } else { // 尾插法维护尾指针 tail->next = newNode; tail = newNode; } } return head; } //迭代反转法(三指针法) Node* reverseByIteration(Node *head) { Node *prev = NULL, *current = head, *next = NULL; while (current) { next = current->next; // 保存下一节点指针 current->next = prev; // 反转指针方向 prev = current; // 前驱指针后移 current = next; // 当前指针后移 } return prev; // 新头节点是原链表尾节点 } //头插法反转 Node* reverseByHeadInsert(Node *head) { Node *newHead = NULL, *current = head; while (current) { Node *next = current->next; // 保存下一节点 current->next = newHead; // 头插操作 newHead = current; // 更新新头节点 current = next; // 移动当前指针 } return newHead; } //递归反转法 Node* reverseByRecursion(Node *current, Node *prev) { if (!current) return prev; // 递归终止条件 Node *next = current->next; // 保存下一节点 current->next = prev; // 反转指针方向 return reverseByRecursion(next, current); // 递归调用 } //打印链表 void printList(Node *head) { Node *current = head; while (current) { printf("%d\t", current->data); current = current->next; } printf("\n"); } //释放内存 void freeList(Node *head) { Node *current = head; while (current) { Node *temp = current; current = current->next; free(temp); } } int main(int argc,char *argv[]) { //动态分配数组 int *arr = (int*)malloc(MAX_LENGHT * sizeof(int)); int n; printf("Please enter the number of digits you want to reverse:>"); scanf("%d", &n); printf("Please enter %d numbers:>\n", n); for(int i = 0; i < n; i++) { scanf("%d", &arr[i]); } // 创建原始链表 Node *original = createList(arr, n); printf("原链表: "); printList(original); // 迭代反转测试 Node *reversed1 = reverseByIteration(original); printf("迭代反转: "); printList(reversed1); // 头插法反转测试 Node *reversed2 = reverseByHeadInsert(reversed1); printf("头插法反转: "); printList(reversed2); // 递归反转测试 Node *reversed3 = reverseByRecursion(reversed2, NULL); printf("递归反转: "); printList(reversed3); freeList(reversed3); return 0; }
【2】约瑟夫环问题
题目:罗马人占领乔塔帕特后,犹太人与 Josephus 及他的朋友躲到一个洞中,族人决定宁愿死 也不要被敌人找到,于是决定了一个自杀方式,所有人排成一个圆圈,由第 1 个人开始报数, 每报数到第 3 人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。
然而Josephus和他的朋友并不想死,Josephus要他的朋友先假装遵从,他将朋友与自己安排在两个 特殊的位置,于是逃过了这场死亡游戏。
现在假设有n个人形成一个单向循环链表,求最后剩余的两个节点。
解析:主要是分析有头结点和没有头结点,对本题的影响。一般情况下链表带头结点是比较方便的,但是 对于本题,约瑟夫环问题,带上头结点的链表反而不利于操作,画图讲解。
约瑟夫环问题(Josephus Problem)是一个精度的数学与数据结构问题,其核心在于通过特定规则在循环队列中淘汰元素(删除元素),最终找到幸存者的位置
基本设定:
n个人围成一个环形队列,编号通常为1到n(或0到n-1)
从第一个人开始报数,每次数到m(或动态变化的密码值)时,该人出列
从出列者的下一位重新开始报数,每次数到m(或动态变化的密码值)时,该人出列
目标:确定幸存者的初始编号
使用循环链表模拟环形队列,每次遍历到第m个节点时删除该节点
代码:
//yuesefu.h #ifndef _YUESEFU_H #define _YUESEFU_H #include <stdio.h> #include <stdlib.h> #include <string.h> //创建节点结构体 typedef struct node { int number; //人员编号(1~n) struct node *next; //指针域 }NODE; //创建无头循环链表 NODE *createCircle(int n); //约瑟夫环淘汰逻辑 void joseph(NODE **head, int m); #endif //_YUESEFU_H
//yuesefu.c #include "yuesefu.h" //创建无头循环链表 NODE *createCircle(int n) { //定义头指针和前驱节点指针(初始化为空) NODE *head = NULL, *prev = NULL; //循环创建n个节点,人员编号从1开始递增 for(int i = 1; i <= n; i++) { //创建新节点 NODE *new_node = (NODE*)malloc(sizeof(NODE)); //检查节点是否创建成功 if(!new_node) return NULL; //设置节点编号 new_node->number = i; //如果链表为空则将新节点设为头节点 if(!head) { //头指针执行新节点 head = new_node; //头指针指向自身,形成单个节点的循环结构 head->next = head; } //非空链表(尾插法插入元素) else { //将新节点插入到prev节点之后 prev->next = new_node; //前驱节点连接新节点 new_node->next = head; //新节点指向头节点形成闭环 } //更新前驱节点为当前新节点 prev = new_node; } return head; } //约瑟夫环淘汰逻辑 void joseph(NODE **head, int m) { //指针尾随法寻找待删除节点 NODE *p = *head, *q = NULL; //当剩余节点数>2时循环 while(p->next->next != p) { //移动m-1次寻找待删除节点 for(int i = 1; i < m; i++) { q = p; p = p->next; } //删除当前节点 q->next = p->next; //跳过当前节点 printf("处死:%d\n", p->number); //释放被淘汰节点的内存 free(p); //从下一节点继续 p = q->next; } //输出最后两个幸存者 printf("幸存者1:%d\t幸存者2:%d\n", p->number, p->next->number); }
//app.c #include "yuesefu.h" int main() { //经典的约瑟夫问题参数 int n = 41, m = 3; NODE *p = createCircle(n); joseph(&p, m); //释放最后两个节点 free(p->next); free(p); return 0; }