1. 项目概述循环单链表一个被低估的“环形”数据结构在初学数据结构时我们接触的第一个动态结构往往是单链表。它解决了数组需要预先分配连续空间、插入删除效率低的问题。但你是否想过单链表有一个“天生”的缺陷当你遍历到链表末尾想快速回到链表头部时只能从头再来或者依赖一个额外的头指针。这在某些需要“循环”或“轮转”处理的场景下就显得不那么优雅和高效了。今天要聊的循环单链表就是为解决这个问题而生的。它把单链表的“线性”首尾相连形成一个环让遍历操作可以无缝地循环往复。简单来说循环单链表就是最后一个节点的指针域不再指向NULL而是指向了头节点或第一个数据节点从而形成一个闭环。这个看似微小的改动却带来了应用逻辑上的巨大便利。比如在操作系统的进程时间片轮转调度、多人游戏的玩家回合制循环、数据缓冲区的循环利用环形缓冲区等场景中循环单链表都是非常自然且高效的数据模型。对于C语言学习者而言亲手实现一个循环单链表不仅能巩固指针和动态内存管理的核心知识更能深刻理解“结构决定用途”的设计思想。接下来我将以一个从业者的视角带你从零开始用C语言构建一个功能完整、鲁棒性强的循环单链表并分享那些教科书上不会写的“踩坑”心得。2. 核心设计如何为“循环”而生实现一个数据结构首先要明确它的“形态”和“规则”。循环单链表的核心设计决策主要集中在如何表示这个“环”以及如何处理边界情况这直接决定了后续所有操作的复杂度和正确性。2.1 节点结构定义万变不离其宗链表的基石是节点。循环单链表的节点结构与普通单链表完全一致这体现了数据结构设计的继承性。每个节点需要包含两部分数据域和指针域。typedef int ElemType; // 为方便起见假设数据元素为整型实际可替换为任意复杂类型 typedef struct LNode { ElemType data; // 数据域存放节点数据 struct LNode *next; // 指针域指向下一个节点 } LNode, *LinkList;这里用了typedef定义了两种类型LNode强调这是一个节点结构体LinkList强调这是一个指向节点的指针通常用作链表的头指针或尾指针。这种定义在后续的函数参数传递时能让代码意图更清晰LinkList L表示“一个链表”LNode *p表示“一个指向节点的指针”。注意数据域ElemType应根据实际需求定义。如果是学生信息可能是一个包含学号、姓名、成绩的结构体。这里用int是为了简化示例聚焦于链表结构本身的操作。2.2 循环的基石尾指针 vs 头指针这是实现循环单链表的第一个关键抉择。普通单链表通常用一个头指针指向第一个节点。在循环单链表中我们有两种主流方案带头节点的循环单链表使用头指针引入一个不存储实际数据的“头节点”其next指向第一个数据节点最后一个数据节点的next指向这个头节点。头指针L始终指向这个头节点。优点统一了空表和非空表的操作。无论链表是否为空头节点的next域都指向某个节点空表时指向自己这使得插入、删除第一个数据节点的操作与操作中间节点在代码逻辑上完全一致简化了判断。缺点多占用了一个节点的内存。要找到链表尾部需要遍历。不带头节点的循环单链表使用尾指针这是更符合“循环”直觉、也往往更高效的方案。我们维护一个尾指针rear它直接指向链表中的最后一个节点。那么最后一个节点的next就指向第一个节点而rear-next就是第一个节点。优点插入到链表尾部的操作是O(1)时间复杂度因为直接修改rear及其next即可。合并两个循环链表异常高效只需交换几个指针也是O(1)时间。逻辑直观rear-next就是头形成了一个完美的环。缺点空表的表示和操作需要特殊处理rear为NULL且删除第一个节点时需要更新rear-next稍微麻烦一点。我的选择与理由在大多数需要循环特性的实际场景中如缓冲区、轮询队列频繁的尾部插入和链表合并操作更为常见。因此我将采用“不带头节点、使用尾指针”的方案来实现。这不仅性能更优也能让我们更纯粹地体会“循环”的精髓。空表状态用一个NULL指针表示我们在初始化、插入和删除时仔细处理这个边界条件即可。2.3 核心操作的设计思路基于尾指针的设计我们来规划核心操作初始化创建一个空链表即*rear NULL。创建尾插法依次在尾部插入新节点并始终更新rear指向新的尾节点。注意处理第一个节点插入时的成环操作。遍历从rear-next即第一个节点开始依次访问直到再次回到这个节点为止。需要小心处理空表情况。插入头部插入新节点插入在rear-next之前并可能需要更新rear-next如果链表原为空则还需更新rear。尾部插入新节点插入在rear之后并更新rear为新节点。这是最方便的操作。中间插入先找到前驱节点然后修改指针。删除需要找到待删除节点的前驱节点。特别注意删除第一个或最后一个节点时对rear指针的影响。查找遍历环比对数据。销毁依次释放所有节点内存最后将rear置为NULL。遍历时需注意避免无限循环。3. 核心细节与避坑指南纸上得来终觉浅绝知此事要躬行。理论设计清晰后真正的挑战在于代码实现中的各种细节和边界条件。下面这些“坑”是我在无数次调试中总结出来的。3.1 空链表的判断与操作统一这是使用尾指针方案最需要小心的地方。一个空链表意味着rear NULL。此时rear-next是非法访问会导致程序崩溃。插入第一个节点时这个节点既是头也是尾其next要指向自己同时rear要指向它。解决方案在所有涉及rear-next的操作前必须先判断rear是否为NULL。例如在遍历函数中void TraverseList(LinkList rear) { if (rear NULL) { printf(The list is empty.\n); return; } LNode *p rear-next; // 从第一个节点开始 do { printf(%d , p-data); p p-next; } while (p ! rear-next); // 回到起点则结束 printf(\n); }这里使用了do...while循环确保即使链表只有一个节点此时p rear也能正确打印一次。如果用while循环就需要更复杂的初始条件判断。3.2 指针修改的顺序不可逆转的法则在链表操作中修改指针的顺序至关重要一旦顺序错误就会丢失节点引用导致内存泄漏或链表断裂。有一个基本原则先搭新桥再拆旧桥。以在节点p之后插入新节点s为例s-next p-next;// 新节点s指向p原来的后继p-next s;// 节点p指向新节点s绝对不能颠倒如果先执行p-next s那么p原来的后继节点就丢失了再也找不回来。在循环链表中如果p是尾节点rear插入后还需要更新rear s。这个更新操作放在两步指针修改之后即可。3.3 尾指针的维护谁是真正的“尾”在删除操作中维护尾指针rear的正确性是难点。考虑两种情况删除尾节点如果删除的节点恰好是rear指向的节点那么在删除它之后必须将rear更新为它的前驱节点。这就要求我们在删除前必须找到前驱节点。链表只剩一个节点这是上面情况的特例。删除这个唯一的节点后链表变为空rear必须被设为NULL。因此一个健壮的删除函数通常需要先遍历找到待删除节点的前驱节点pre。即使你知道要删除的节点指针p你也需要pre来修改链表结构并判断p是否是尾节点。// 假设已知要删除节点p我们需要找到它的前驱pre LNode *pre rear; while (pre-next ! p) { // 在循环链表中寻找p的前驱 pre pre-next; if (pre rear pre-next ! p) { // 绕了一圈没找到说明p不在链表中 // 错误处理 return; } } // 执行删除 pre-next p-next; // 维护rear if (p rear) { if (pre rear) { // 链表只有一个节点 rear NULL; } else { rear pre; // 更新rear为新的尾节点 } } free(p);3.4 遍历的终止条件防止无限循环在普通单链表中遍历以p ! NULL为条件。在循环单链表中遍历以p ! 起始点为条件。这带来了一个微妙的问题如何确定起始点对于带头指针的链表起始点是头节点或第一个数据节点。对于我们的尾指针链表起始点是rear-next。关键技巧在遍历开始前用一个变量start保存起始点的地址然后移动指针p当p再次回到start时停止。一定要使用do...while或确保初始p被正确设置否则可能一次都不执行对于while循环或无法处理单节点情况。4. 完整代码实现与逐行解析下面我将给出一个采用尾指针rear、不带头节点的循环单链表的完整C语言实现。每一部分都配有详细注释和逻辑解释。#include stdio.h #include stdlib.h // 定义节点类型和链表类型 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; // LinkList 是指向LNode的指针此处我们用它表示尾指针 // 1. 初始化链表传入尾指针的地址 void InitList(LinkList *rear) { *rear NULL; // 空链表尾指针为NULL } // 2. 采用尾插法创建循环单链表 void CreateList_R(LinkList *rear, int n) { printf(Please enter %d elements: , n); for (int i 0; i n; i) { LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) { perror(Memory allocation failed); exit(EXIT_FAILURE); } scanf(%d, (s-data)); if (*rear NULL) { // 链表为空插入第一个节点 s-next s; // 自己指向自己形成环 *rear s; // 尾指针指向这唯一的节点 } else { // 链表非空插入到尾部 s-next (*rear)-next; // 新节点指向原头节点 (*rear)-next s; // 原尾节点指向新节点 *rear s; // 更新尾指针为新节点 } } } // 3. 遍历打印链表 void TraverseList(LinkList rear) { if (rear NULL) { printf(The list is empty.\n); return; } LNode *p rear-next; // p指向第一个节点 printf(List elements: ); do { printf(%d , p-data); p p-next; } while (p ! rear-next); // 再次回到起点时结束 printf(\n); } // 4. 在链表头部插入元素 void InsertAtHead(LinkList *rear, ElemType e) { LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) exit(EXIT_FAILURE); s-data e; if (*rear NULL) { // 空表插入 s-next s; *rear s; } else { // 非空表插入到rear-next之前 s-next (*rear)-next; (*rear)-next s; // rear指针不变因为插入在头部尾部没变 } } // 5. 在链表尾部插入元素效率最高 void InsertAtTail(LinkList *rear, ElemType e) { LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) exit(EXIT_FAILURE); s-data e; if (*rear NULL) { // 空表插入 s-next s; *rear s; } else { s-next (*rear)-next; // 新节点指向头 (*rear)-next s; // 原尾节点指向新节点 *rear s; // 更新尾指针 } } // 6. 在指定位置第i个元素从1开始计数之后插入元素 int InsertAfter(LinkList *rear, int i, ElemType e) { if (i 0 || *rear NULL) return 0; // 位置非法或空表 LNode *p (*rear)-next; // 从第一个节点开始找 int count 1; // 寻找第i个节点 while (p ! *rear count i) { p p-next; count; } if (count ! i) { // 没找到第i个节点 return 0; } LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) exit(EXIT_FAILURE); s-data e; s-next p-next; p-next s; if (p *rear) { // 如果在尾节点后插入需要更新尾指针 *rear s; } return 1; } // 7. 按值查找节点 LNode* LocateElem(LinkList rear, ElemType e) { if (rear NULL) return NULL; LNode *p rear-next; do { if (p-data e) return p; p p-next; } while (p ! rear-next); return NULL; // 未找到 } // 8. 删除第i个节点从1开始计数 int DeleteNode(LinkList *rear, int i, ElemType *e) { if (i 1 || *rear NULL) return 0; // 位置非法或空表 LNode *p (*rear)-next; // p初始指向第一个节点最终指向待删除节点 LNode *pre *rear; // pre初始指向尾节点最终指向p的前驱 // 处理删除第一个节点的特殊情况因为pre初始就是它的前驱尾节点 if (i 1) { // 要删除的节点是p } else { // 寻找第i个节点及其前驱 int count 1; while (p ! *rear count i) { pre p; p p-next; count; } if (count ! i) { // 没找到第i个节点 return 0; } } // 执行删除 pre-next p-next; if (p *rear) { // 如果删除的是尾节点 if (pre p) { // 链表只有一个节点 *rear NULL; } else { *rear pre; // 更新尾指针为前驱 } } else if (p (*rear)-next) { // 如果删除的是第一个节点且链表节点数1 // rear指针不需要改变因为尾部没变但头变了这个变化已由pre-next p-next体现 } if (e ! NULL) *e p-data; free(p); return 1; } // 9. 获取链表长度 int GetLength(LinkList rear) { if (rear NULL) return 0; int len 0; LNode *p rear-next; do { len; p p-next; } while (p ! rear-next); return len; } // 10. 销毁链表释放所有内存 void DestroyList(LinkList *rear) { if (*rear NULL) return; LNode *p (*rear)-next; // 从第一个节点开始 LNode *q; (*rear)-next NULL; // 打破环变成普通单链表以便遍历释放 while (p ! NULL) { q p-next; // 保存下一个节点 free(p); // 释放当前节点 p q; // 移动到下一个节点 } *rear NULL; // 最后将尾指针置空 } // 主函数测试所有功能 int main() { LinkList rear; // 尾指针 InitList(rear); printf(1. Create a list with 5 elements.\n); CreateList_R(rear, 5); TraverseList(rear); printf(Length: %d\n, GetLength(rear)); printf(\n2. Insert 100 at head.\n); InsertAtHead(rear, 100); TraverseList(rear); printf(\n3. Insert 200 at tail.\n); InsertAtTail(rear, 200); TraverseList(rear); printf(\n4. Insert 300 after the 3rd element.\n); if (InsertAfter(rear, 3, 300)) { TraverseList(rear); } else { printf(Insert failed.\n); } printf(\n5. Search for element 200.\n); LNode *found LocateElem(rear, 200); if (found) { printf(Found node with data: %d\n, found-data); } else { printf(Not found.\n); } printf(\n6. Delete the 2nd element.\n); ElemType deletedValue; if (DeleteNode(rear, 2, deletedValue)) { printf(Deleted element: %d\n, deletedValue); TraverseList(rear); } else { printf(Delete failed.\n); } printf(\n7. Destroy the list.\n); DestroyList(rear); printf(After destruction, list is: ); TraverseList(rear); return 0; }代码解析与关键点函数参数LinkList *rear因为我们需要修改调用者手中的尾指针例如初始化置空、插入后更新所以必须传递尾指针的地址二级指针。这是C语言修改外部指针的标准做法。CreateList_R尾插法的核心。每次插入新节点s后都将其设为新的尾节点并保证s-next指向头维持循环。TraverseList使用do...while是处理循环链表遍历的经典模式能正确处理单节点情况。DeleteNode这是最复杂的函数。它巧妙地用pre初始指向尾节点来处理删除第一个节点的情况。删除后需要仔细判断并更新rear指针。DestroyList在释放内存前先将尾节点的next置为NULL打破循环从而可以将一个循环链表的释放转化为一个普通单链表的释放简化了操作。5. 常见问题与调试技巧实录即使有了完整的代码在实际编写和调试时你依然可能会遇到下面这些问题。我把它们和解决方法记录下来希望能帮你节省时间。5.1 程序崩溃访问空指针或野指针症状程序运行中突然崩溃调试器提示Segmentation fault或访问了0x0地址。常见原因对NULL指针进行了解引用操作例如rear-next当rear为NULL时。释放内存后再次使用该指针use after free。指针未初始化就使用。排查技巧防御性编程在任何使用rear或p-next之前先判断其是否为NULL。尤其是在TraverseList,Insert,Delete等函数的开头。画图辅助在纸上画出链表操作前后的指针指向变化。对于复杂的插入删除画图能极大降低出错概率。使用调试器在关键函数处设置断点单步执行观察指针变量的值是否与预期一致。5.2 内存泄漏分配的内存未释放症状程序长时间运行后内存占用不断增长对于小程序可能不明显但习惯很重要。原因使用malloc分配了节点内存但在删除节点或销毁链表时没有调用free释放。解决确保DeleteNode和DestroyList函数中每一个malloc都有对应的free。在DestroyList中使用临时指针q保存下一个节点的地址再释放当前节点这是一个安全的内存释放模式。可以使用如ValgrindLinux或Dr. MemoryWindows等工具来检测内存泄漏。5.3 逻辑错误遍历陷入死循环或提前结束症状遍历函数停不下来或者该打印的元素没打全。原因循环终止条件错误。死循环在while(p ! NULL)这样的条件下遍历循环链表因为永远没有NULL所以死循环。提前结束在while(p ! rear)的条件下遍历如果链表只有一个节点p rear则一次都不会执行。解决牢记循环链表的遍历范式do { ... } while (p ! start_point);。务必在循环开始前正确记录起始点start_point rear-next。5.4 合并两个循环链表的“魔术”这是一个展示循环单链表尾指针表示法优势的经典操作。合并两个链表La和Lb要求时间复杂度为O(1)。// 假设La和Lb都是非空的循环单链表的尾指针 LinkList Connect(LinkList La, LinkList Lb) { if (La NULL) return Lb; if (Lb NULL) return La; LNode *head_a La-next; // La的头节点 LNode *head_b Lb-next; // Lb的头节点 La-next head_b; // La的尾节点指向Lb的头 Lb-next head_a; // Lb的尾节点指向La的头此时Lb-next已不是原来的头但Lb指针本身仍指向原Lb的尾 // 新的尾指针是Lb原第二个链表的尾 // 因为La现在是中间节点了而Lb指向合并后链表的最后一个节点 // 实际上也可以返回La取决于你想把哪个链表的尾作为新链表的尾 return Lb; }这段代码像变魔术一样只通过几次指针赋值就完成了合并。其核心思想是交换两个链表的“头尾连接”。理解它的最好方式就是在纸上画出合并前后的指针变化图。5.5 关于“头节点”的再思考虽然我们这次实现选择了不带头节点但带头节点的设计在“简化边界操作”上确有优势。例如在带头节点的循环链表中空链表是一个头节点自己指向自己的环。插入和删除第一个数据节点不需要特殊判断rear是否为空或是否更新rear如果使用头指针。这使代码更统一。选择哪种方式取决于你的具体需求和个人偏好。在面试或考试中务必先明确题目要求或与面试官确认。
1. 项目概述循环单链表一个被低估的“环形”数据结构在初学数据结构时我们接触的第一个动态结构往往是单链表。它解决了数组需要预先分配连续空间、插入删除效率低的问题。但你是否想过单链表有一个“天生”的缺陷当你遍历到链表末尾想快速回到链表头部时只能从头再来或者依赖一个额外的头指针。这在某些需要“循环”或“轮转”处理的场景下就显得不那么优雅和高效了。今天要聊的循环单链表就是为解决这个问题而生的。它把单链表的“线性”首尾相连形成一个环让遍历操作可以无缝地循环往复。简单来说循环单链表就是最后一个节点的指针域不再指向NULL而是指向了头节点或第一个数据节点从而形成一个闭环。这个看似微小的改动却带来了应用逻辑上的巨大便利。比如在操作系统的进程时间片轮转调度、多人游戏的玩家回合制循环、数据缓冲区的循环利用环形缓冲区等场景中循环单链表都是非常自然且高效的数据模型。对于C语言学习者而言亲手实现一个循环单链表不仅能巩固指针和动态内存管理的核心知识更能深刻理解“结构决定用途”的设计思想。接下来我将以一个从业者的视角带你从零开始用C语言构建一个功能完整、鲁棒性强的循环单链表并分享那些教科书上不会写的“踩坑”心得。2. 核心设计如何为“循环”而生实现一个数据结构首先要明确它的“形态”和“规则”。循环单链表的核心设计决策主要集中在如何表示这个“环”以及如何处理边界情况这直接决定了后续所有操作的复杂度和正确性。2.1 节点结构定义万变不离其宗链表的基石是节点。循环单链表的节点结构与普通单链表完全一致这体现了数据结构设计的继承性。每个节点需要包含两部分数据域和指针域。typedef int ElemType; // 为方便起见假设数据元素为整型实际可替换为任意复杂类型 typedef struct LNode { ElemType data; // 数据域存放节点数据 struct LNode *next; // 指针域指向下一个节点 } LNode, *LinkList;这里用了typedef定义了两种类型LNode强调这是一个节点结构体LinkList强调这是一个指向节点的指针通常用作链表的头指针或尾指针。这种定义在后续的函数参数传递时能让代码意图更清晰LinkList L表示“一个链表”LNode *p表示“一个指向节点的指针”。注意数据域ElemType应根据实际需求定义。如果是学生信息可能是一个包含学号、姓名、成绩的结构体。这里用int是为了简化示例聚焦于链表结构本身的操作。2.2 循环的基石尾指针 vs 头指针这是实现循环单链表的第一个关键抉择。普通单链表通常用一个头指针指向第一个节点。在循环单链表中我们有两种主流方案带头节点的循环单链表使用头指针引入一个不存储实际数据的“头节点”其next指向第一个数据节点最后一个数据节点的next指向这个头节点。头指针L始终指向这个头节点。优点统一了空表和非空表的操作。无论链表是否为空头节点的next域都指向某个节点空表时指向自己这使得插入、删除第一个数据节点的操作与操作中间节点在代码逻辑上完全一致简化了判断。缺点多占用了一个节点的内存。要找到链表尾部需要遍历。不带头节点的循环单链表使用尾指针这是更符合“循环”直觉、也往往更高效的方案。我们维护一个尾指针rear它直接指向链表中的最后一个节点。那么最后一个节点的next就指向第一个节点而rear-next就是第一个节点。优点插入到链表尾部的操作是O(1)时间复杂度因为直接修改rear及其next即可。合并两个循环链表异常高效只需交换几个指针也是O(1)时间。逻辑直观rear-next就是头形成了一个完美的环。缺点空表的表示和操作需要特殊处理rear为NULL且删除第一个节点时需要更新rear-next稍微麻烦一点。我的选择与理由在大多数需要循环特性的实际场景中如缓冲区、轮询队列频繁的尾部插入和链表合并操作更为常见。因此我将采用“不带头节点、使用尾指针”的方案来实现。这不仅性能更优也能让我们更纯粹地体会“循环”的精髓。空表状态用一个NULL指针表示我们在初始化、插入和删除时仔细处理这个边界条件即可。2.3 核心操作的设计思路基于尾指针的设计我们来规划核心操作初始化创建一个空链表即*rear NULL。创建尾插法依次在尾部插入新节点并始终更新rear指向新的尾节点。注意处理第一个节点插入时的成环操作。遍历从rear-next即第一个节点开始依次访问直到再次回到这个节点为止。需要小心处理空表情况。插入头部插入新节点插入在rear-next之前并可能需要更新rear-next如果链表原为空则还需更新rear。尾部插入新节点插入在rear之后并更新rear为新节点。这是最方便的操作。中间插入先找到前驱节点然后修改指针。删除需要找到待删除节点的前驱节点。特别注意删除第一个或最后一个节点时对rear指针的影响。查找遍历环比对数据。销毁依次释放所有节点内存最后将rear置为NULL。遍历时需注意避免无限循环。3. 核心细节与避坑指南纸上得来终觉浅绝知此事要躬行。理论设计清晰后真正的挑战在于代码实现中的各种细节和边界条件。下面这些“坑”是我在无数次调试中总结出来的。3.1 空链表的判断与操作统一这是使用尾指针方案最需要小心的地方。一个空链表意味着rear NULL。此时rear-next是非法访问会导致程序崩溃。插入第一个节点时这个节点既是头也是尾其next要指向自己同时rear要指向它。解决方案在所有涉及rear-next的操作前必须先判断rear是否为NULL。例如在遍历函数中void TraverseList(LinkList rear) { if (rear NULL) { printf(The list is empty.\n); return; } LNode *p rear-next; // 从第一个节点开始 do { printf(%d , p-data); p p-next; } while (p ! rear-next); // 回到起点则结束 printf(\n); }这里使用了do...while循环确保即使链表只有一个节点此时p rear也能正确打印一次。如果用while循环就需要更复杂的初始条件判断。3.2 指针修改的顺序不可逆转的法则在链表操作中修改指针的顺序至关重要一旦顺序错误就会丢失节点引用导致内存泄漏或链表断裂。有一个基本原则先搭新桥再拆旧桥。以在节点p之后插入新节点s为例s-next p-next;// 新节点s指向p原来的后继p-next s;// 节点p指向新节点s绝对不能颠倒如果先执行p-next s那么p原来的后继节点就丢失了再也找不回来。在循环链表中如果p是尾节点rear插入后还需要更新rear s。这个更新操作放在两步指针修改之后即可。3.3 尾指针的维护谁是真正的“尾”在删除操作中维护尾指针rear的正确性是难点。考虑两种情况删除尾节点如果删除的节点恰好是rear指向的节点那么在删除它之后必须将rear更新为它的前驱节点。这就要求我们在删除前必须找到前驱节点。链表只剩一个节点这是上面情况的特例。删除这个唯一的节点后链表变为空rear必须被设为NULL。因此一个健壮的删除函数通常需要先遍历找到待删除节点的前驱节点pre。即使你知道要删除的节点指针p你也需要pre来修改链表结构并判断p是否是尾节点。// 假设已知要删除节点p我们需要找到它的前驱pre LNode *pre rear; while (pre-next ! p) { // 在循环链表中寻找p的前驱 pre pre-next; if (pre rear pre-next ! p) { // 绕了一圈没找到说明p不在链表中 // 错误处理 return; } } // 执行删除 pre-next p-next; // 维护rear if (p rear) { if (pre rear) { // 链表只有一个节点 rear NULL; } else { rear pre; // 更新rear为新的尾节点 } } free(p);3.4 遍历的终止条件防止无限循环在普通单链表中遍历以p ! NULL为条件。在循环单链表中遍历以p ! 起始点为条件。这带来了一个微妙的问题如何确定起始点对于带头指针的链表起始点是头节点或第一个数据节点。对于我们的尾指针链表起始点是rear-next。关键技巧在遍历开始前用一个变量start保存起始点的地址然后移动指针p当p再次回到start时停止。一定要使用do...while或确保初始p被正确设置否则可能一次都不执行对于while循环或无法处理单节点情况。4. 完整代码实现与逐行解析下面我将给出一个采用尾指针rear、不带头节点的循环单链表的完整C语言实现。每一部分都配有详细注释和逻辑解释。#include stdio.h #include stdlib.h // 定义节点类型和链表类型 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; // LinkList 是指向LNode的指针此处我们用它表示尾指针 // 1. 初始化链表传入尾指针的地址 void InitList(LinkList *rear) { *rear NULL; // 空链表尾指针为NULL } // 2. 采用尾插法创建循环单链表 void CreateList_R(LinkList *rear, int n) { printf(Please enter %d elements: , n); for (int i 0; i n; i) { LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) { perror(Memory allocation failed); exit(EXIT_FAILURE); } scanf(%d, (s-data)); if (*rear NULL) { // 链表为空插入第一个节点 s-next s; // 自己指向自己形成环 *rear s; // 尾指针指向这唯一的节点 } else { // 链表非空插入到尾部 s-next (*rear)-next; // 新节点指向原头节点 (*rear)-next s; // 原尾节点指向新节点 *rear s; // 更新尾指针为新节点 } } } // 3. 遍历打印链表 void TraverseList(LinkList rear) { if (rear NULL) { printf(The list is empty.\n); return; } LNode *p rear-next; // p指向第一个节点 printf(List elements: ); do { printf(%d , p-data); p p-next; } while (p ! rear-next); // 再次回到起点时结束 printf(\n); } // 4. 在链表头部插入元素 void InsertAtHead(LinkList *rear, ElemType e) { LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) exit(EXIT_FAILURE); s-data e; if (*rear NULL) { // 空表插入 s-next s; *rear s; } else { // 非空表插入到rear-next之前 s-next (*rear)-next; (*rear)-next s; // rear指针不变因为插入在头部尾部没变 } } // 5. 在链表尾部插入元素效率最高 void InsertAtTail(LinkList *rear, ElemType e) { LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) exit(EXIT_FAILURE); s-data e; if (*rear NULL) { // 空表插入 s-next s; *rear s; } else { s-next (*rear)-next; // 新节点指向头 (*rear)-next s; // 原尾节点指向新节点 *rear s; // 更新尾指针 } } // 6. 在指定位置第i个元素从1开始计数之后插入元素 int InsertAfter(LinkList *rear, int i, ElemType e) { if (i 0 || *rear NULL) return 0; // 位置非法或空表 LNode *p (*rear)-next; // 从第一个节点开始找 int count 1; // 寻找第i个节点 while (p ! *rear count i) { p p-next; count; } if (count ! i) { // 没找到第i个节点 return 0; } LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) exit(EXIT_FAILURE); s-data e; s-next p-next; p-next s; if (p *rear) { // 如果在尾节点后插入需要更新尾指针 *rear s; } return 1; } // 7. 按值查找节点 LNode* LocateElem(LinkList rear, ElemType e) { if (rear NULL) return NULL; LNode *p rear-next; do { if (p-data e) return p; p p-next; } while (p ! rear-next); return NULL; // 未找到 } // 8. 删除第i个节点从1开始计数 int DeleteNode(LinkList *rear, int i, ElemType *e) { if (i 1 || *rear NULL) return 0; // 位置非法或空表 LNode *p (*rear)-next; // p初始指向第一个节点最终指向待删除节点 LNode *pre *rear; // pre初始指向尾节点最终指向p的前驱 // 处理删除第一个节点的特殊情况因为pre初始就是它的前驱尾节点 if (i 1) { // 要删除的节点是p } else { // 寻找第i个节点及其前驱 int count 1; while (p ! *rear count i) { pre p; p p-next; count; } if (count ! i) { // 没找到第i个节点 return 0; } } // 执行删除 pre-next p-next; if (p *rear) { // 如果删除的是尾节点 if (pre p) { // 链表只有一个节点 *rear NULL; } else { *rear pre; // 更新尾指针为前驱 } } else if (p (*rear)-next) { // 如果删除的是第一个节点且链表节点数1 // rear指针不需要改变因为尾部没变但头变了这个变化已由pre-next p-next体现 } if (e ! NULL) *e p-data; free(p); return 1; } // 9. 获取链表长度 int GetLength(LinkList rear) { if (rear NULL) return 0; int len 0; LNode *p rear-next; do { len; p p-next; } while (p ! rear-next); return len; } // 10. 销毁链表释放所有内存 void DestroyList(LinkList *rear) { if (*rear NULL) return; LNode *p (*rear)-next; // 从第一个节点开始 LNode *q; (*rear)-next NULL; // 打破环变成普通单链表以便遍历释放 while (p ! NULL) { q p-next; // 保存下一个节点 free(p); // 释放当前节点 p q; // 移动到下一个节点 } *rear NULL; // 最后将尾指针置空 } // 主函数测试所有功能 int main() { LinkList rear; // 尾指针 InitList(rear); printf(1. Create a list with 5 elements.\n); CreateList_R(rear, 5); TraverseList(rear); printf(Length: %d\n, GetLength(rear)); printf(\n2. Insert 100 at head.\n); InsertAtHead(rear, 100); TraverseList(rear); printf(\n3. Insert 200 at tail.\n); InsertAtTail(rear, 200); TraverseList(rear); printf(\n4. Insert 300 after the 3rd element.\n); if (InsertAfter(rear, 3, 300)) { TraverseList(rear); } else { printf(Insert failed.\n); } printf(\n5. Search for element 200.\n); LNode *found LocateElem(rear, 200); if (found) { printf(Found node with data: %d\n, found-data); } else { printf(Not found.\n); } printf(\n6. Delete the 2nd element.\n); ElemType deletedValue; if (DeleteNode(rear, 2, deletedValue)) { printf(Deleted element: %d\n, deletedValue); TraverseList(rear); } else { printf(Delete failed.\n); } printf(\n7. Destroy the list.\n); DestroyList(rear); printf(After destruction, list is: ); TraverseList(rear); return 0; }代码解析与关键点函数参数LinkList *rear因为我们需要修改调用者手中的尾指针例如初始化置空、插入后更新所以必须传递尾指针的地址二级指针。这是C语言修改外部指针的标准做法。CreateList_R尾插法的核心。每次插入新节点s后都将其设为新的尾节点并保证s-next指向头维持循环。TraverseList使用do...while是处理循环链表遍历的经典模式能正确处理单节点情况。DeleteNode这是最复杂的函数。它巧妙地用pre初始指向尾节点来处理删除第一个节点的情况。删除后需要仔细判断并更新rear指针。DestroyList在释放内存前先将尾节点的next置为NULL打破循环从而可以将一个循环链表的释放转化为一个普通单链表的释放简化了操作。5. 常见问题与调试技巧实录即使有了完整的代码在实际编写和调试时你依然可能会遇到下面这些问题。我把它们和解决方法记录下来希望能帮你节省时间。5.1 程序崩溃访问空指针或野指针症状程序运行中突然崩溃调试器提示Segmentation fault或访问了0x0地址。常见原因对NULL指针进行了解引用操作例如rear-next当rear为NULL时。释放内存后再次使用该指针use after free。指针未初始化就使用。排查技巧防御性编程在任何使用rear或p-next之前先判断其是否为NULL。尤其是在TraverseList,Insert,Delete等函数的开头。画图辅助在纸上画出链表操作前后的指针指向变化。对于复杂的插入删除画图能极大降低出错概率。使用调试器在关键函数处设置断点单步执行观察指针变量的值是否与预期一致。5.2 内存泄漏分配的内存未释放症状程序长时间运行后内存占用不断增长对于小程序可能不明显但习惯很重要。原因使用malloc分配了节点内存但在删除节点或销毁链表时没有调用free释放。解决确保DeleteNode和DestroyList函数中每一个malloc都有对应的free。在DestroyList中使用临时指针q保存下一个节点的地址再释放当前节点这是一个安全的内存释放模式。可以使用如ValgrindLinux或Dr. MemoryWindows等工具来检测内存泄漏。5.3 逻辑错误遍历陷入死循环或提前结束症状遍历函数停不下来或者该打印的元素没打全。原因循环终止条件错误。死循环在while(p ! NULL)这样的条件下遍历循环链表因为永远没有NULL所以死循环。提前结束在while(p ! rear)的条件下遍历如果链表只有一个节点p rear则一次都不会执行。解决牢记循环链表的遍历范式do { ... } while (p ! start_point);。务必在循环开始前正确记录起始点start_point rear-next。5.4 合并两个循环链表的“魔术”这是一个展示循环单链表尾指针表示法优势的经典操作。合并两个链表La和Lb要求时间复杂度为O(1)。// 假设La和Lb都是非空的循环单链表的尾指针 LinkList Connect(LinkList La, LinkList Lb) { if (La NULL) return Lb; if (Lb NULL) return La; LNode *head_a La-next; // La的头节点 LNode *head_b Lb-next; // Lb的头节点 La-next head_b; // La的尾节点指向Lb的头 Lb-next head_a; // Lb的尾节点指向La的头此时Lb-next已不是原来的头但Lb指针本身仍指向原Lb的尾 // 新的尾指针是Lb原第二个链表的尾 // 因为La现在是中间节点了而Lb指向合并后链表的最后一个节点 // 实际上也可以返回La取决于你想把哪个链表的尾作为新链表的尾 return Lb; }这段代码像变魔术一样只通过几次指针赋值就完成了合并。其核心思想是交换两个链表的“头尾连接”。理解它的最好方式就是在纸上画出合并前后的指针变化图。5.5 关于“头节点”的再思考虽然我们这次实现选择了不带头节点但带头节点的设计在“简化边界操作”上确有优势。例如在带头节点的循环链表中空链表是一个头节点自己指向自己的环。插入和删除第一个数据节点不需要特殊判断rear是否为空或是否更新rear如果使用头指针。这使代码更统一。选择哪种方式取决于你的具体需求和个人偏好。在面试或考试中务必先明确题目要求或与面试官确认。
