尧图网页设计 
简介面向C语言与数据结构初学者的链表专题资料以PDF文档形式整理链表操作的完整实例代码涵盖创建、遍历、查询结点数、判空、冒泡排序、按值/按位查找、修改、头插/尾插/按位插/有序插入、头删/尾删/按位删/按值删、交换结点、删除整表等十九种操作适合正在学习单链表或准备算法笔试的读者对照练习。资源为1个PDF文件压缩包整体约57KB轻量易用下载后可直接阅读源码头注释与完整实现。已有734人学习下载内容结构清晰以函数模块划分便于按需查阅通过阅读该文档可快速理解链表结点结构、malloc动态分配、遍历与指针修改等关键知识点并积累常用链表操作的可复用代码片段。1. C 语言链表实例十九种操作到底在练什么很多人学数据结构 C 语言版时第一次被要求写一个“链表的实例”常常会拿到一张实验报告上面写着“实现单链表的基本操作实验”少则增删改查多则十九种操作一起上。别小看这十九种操作建表、遍历、查找、插入、删除、修改、排序、反转、合并、判环、约瑟夫环每加一种指针操作就深一层。它的本质不是背代码而是让“节点里存数据、节点间靠指针串起来”这件事变成肌肉记忆。C 语言链表的十九种操作解决的是几个被问烂但还是会翻车的问题头插法和尾插法什么时候用插入和删除要不要改前驱的 nextfree 之后指针还能不能碰边界条件是空链表还是单节点所以这篇笔记按“建链 → 读数据 → 改结构 → 避坑 → 验证”的思路把每类操作的关键代码和参数选择拆开讲新手能跟着敲熟手也能对照排查细节。2. 链表实例的骨架结构体定义与三种建链方式写链表前先定义好节点后面所有操作都建立在同一套结构上。常见的链表示例会让数据域用 typedef 重命名好处是将来把 int 换成 float 或结构体时只改一行。2.1 节点结构体与宏定义数据域、指针域、状态码#include stdio.h #include stdlib.h typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; } LNode, *LinkList; #define OK 1 #define ERROR 0逻辑说明data是数据域next是指针域struct Node *next的写法是因为在结构体内部还不能直接用LNode *next这种别名必须写完整的struct Node *。LNode用来表示节点类型LinkList用来表示链表头指针类型二者本质一样但语义不同看到LinkList时知道这是一个链表头看到LNode *时知道这是一个普通节点指针。参数说明ElemType是数据域类型的抽象若链表要存字符串可以把typedef int ElemType改成typedef char* ElemType但后续涉及比较、赋值、打印的地方也要跟着改。OK和ERROR是函数返回的状态码可能只是一个int但写出来的代码意图更清楚。2.2 头插法建立单链表新节点永远插在头节点之后头插法是最容易写错的建链方式因为它会把输入顺序反过来。代码实现是每次申请一个新节点然后把它挂到链表的头部。LinkList listHeadInsert(int arr[], int n) { LinkList L (LinkList)malloc(sizeof(LNode)); if (!L) return NULL; L-next NULL; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); if (!s) return NULL; s-data arr[i]; s-next L-next; L-next s; } return L; }逻辑说明申请头节点L让L-next NULL这样链表从空表开始。每读一个数组元素就生成一个节点ss-next L-next把新节点接到当前首元节点前面L-next s再让头节点指向新节点。由于后面的节点不断抢占链表头部最终数组的最后一个元素会排在最前面。参数说明arr[]是传入的原始数据n是元素个数。函数返回值是链表头指针。注意这里为了示例简洁没有做完整的内存释放处理如果malloc中途失败在真实工程里要把已申请的节点逐个释放不然会出现内存泄漏。2.3 尾插法建立单链表尾指针的意义尾插法保持数据的原始顺序代价是需要一个尾指针r始终指向最后一个节点。LinkList listTailInsert(int arr[], int n) { LinkList L (LinkList)malloc(sizeof(LNode)); if (!L) return NULL; L-next NULL; LNode *r L; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); if (!s) return NULL; s-data arr[i]; s-next NULL; r-next s; r s; } return L; }逻辑说明初始r L此时头节点也是尾节点。每创建一个新节点ss-next NULL然后r-next s把新节点挂在尾节点后面r s让r指向新的尾节点。这样插入顺序和数组顺序完全一致。参数说明如果不保存尾指针每次插入都要从L出发遍历到链表尾部插入 n 个元素的时间会变成 O(n²)。这里保留尾指针每次都是 O(1)。面试里经常问头插法和尾插法的区别头插法适合栈式数据尾插法适合队列式数据。2.4 用数组批量构造链表单元测试最常用的手段手工调用多次插入来建链表太慢我一般会用数组批量构造这样测试用例可以写得很紧凑。int main() { int arr[] {3, 1, 4, 1, 5}; int n sizeof(arr) / sizeof(arr[0]); LinkList L listTailInsert(arr, n); for (LNode *p L-next; p; p p-next) { printf(%d , p-data); } printf(\n); return 0; }逻辑说明sizeof(arr) / sizeof(arr[0])计算数组长度避免硬编码n。链表建立后从头节点的下一个节点开始遍历直到p NULL为止。输出结果是3 1 4 1 5说明尾插法没有改变数据顺序。参数说明数组批量构造适合长度固定、输入已知的测试场景。如果要在程序运行中动态输入就把arr[i]换成scanf读入的值。批量构造的一个坑是忘记处理malloc失败测试时数据量小可能没问题数据量一大就容易出事。建链方式数据顺序时间复杂度适用场景头插法逆序O(n)需要反转数据、构建栈结构尾插法原序O(n)保持输入顺序、队列结构数组批量构造原序或逆序O(n)单元测试、固定样例3. 遍历、查找与修改读操作先过关读操作是链表入门的第一道坎。遍历输出、求链表长度、按值查找、按位置查找看着简单实际写起来全是细节。3.1 遍历输出与求长度循环终止条件的差别遍历链表的终止条件有两种写法while (p ! NULL)和while (p-next ! NULL)。求长度和输出全部节点要用前者只处理到倒数第二个节点时才用后者。int listLength(LinkList L) { int len 0; LNode *p L-next; while (p ! NULL) { len; p p-next; } return len; } void listPrint(LinkList L) { for (LNode *p L-next; p ! NULL; p p-next) { printf(%d , p-data); } printf(\n); }逻辑说明len从 0 开始每经过一个节点自增一次。for循环的初始化和后继跳转集中在一起适合只读遍历。p p-next必须在打印完当前节点之后执行否则会跳过首元节点输出结果少一个。参数说明listLength的时间复杂度是 O(n)链表本身不记录长度。如果频繁需要长度可以在结构体里增加一个size字段每次插入删除时维护它但十九种操作的基础版一般不这么做。遍历时如果误用while (p-next ! NULL)长度会少算 1这种错误很难肉眼发现。3.2 按值查找与按位置查找返回值的两种设计按值查找从头节点之后开始找到第一个data x的节点。按位置查找需要约定下标起点常见的有从 0 开始和从 1 开始两种习惯实验报告里推荐从 1 开始因为教材上 i 表示第 i 个节点。LNode* locateByValue(LinkList L, ElemType x) { LNode *p L-next; while (p ! NULL p-data ! x) { p p-next; } return p; } LNode* getNodeByIndex(LinkList L, int i) { if (i 1) return NULL; LNode *p L-next; int j 1; while (p ! NULL j i) { p p-next; j; } return p; }逻辑说明locateByValue返回 NULL 表示没有找到。getNodeByIndex中j从 1 开始p一开始指向第 1 个节点当j i时不断后移直到p NULL说明 i 超出了链表长度。参数说明这两种查找返回的都是目标节点本身而不是它的前驱。做插入删除时返回前驱往往更实用因为光拿到目标节点无法知道它的前驱是谁。这也是链表和数组最大的差异数组按下标能直接访问链表必须顺着指针走。3.3 修改节点值与交换两个节点什么时候要动指针修改节点值最简单定位到节点后只改data不碰next。交换两个节点有两种思路交换值或者交换指针。链表操作里我最推荐交换值因为不动指针就不容易断链。int changeNodeValue(LinkList L, int i, ElemType newVal) { LNode *p getNodeByIndex(L, i); if (p NULL) return ERROR; p-data newVal; return OK; } int swapNodeData(LNode *a, LNode *b) { if (a NULL || b NULL) return ERROR; ElemType t a-data; a-data b-data; b-data t; return OK; }逻辑说明changeNodeValue先调用getNodeByIndex返回 NULL 就报错。swapNodeData只交换两个节点的data链接关系完全不变排序算法里经常这样用。参数说明如果一定要交换节点位置需要同时修改两个节点的前驱和它们的next还要处理相邻节点和头节点的情况非常容易翻车。所以我在链表排序时一律交换值不交换节点。3.4 逆序输出用递归还是用辅助栈不修改链表结构只要求从尾到头打印可以用递归或辅助栈。递归代码最少但栈深度跟链表长度成正比。void printListReverse(LNode *p) { if (p NULL) return; printListReverse(p-next); printf(%d , p-data); }逻辑说明递归调用先走到链尾回溯时再打印天然得到逆序输出。调用层次等于链表长度链表有几万个节点时可能栈溢出这时要用循环加辅助栈替代。参数说明辅助栈写法是先遍历链表把所有元素压栈再逐个出栈打印。空间复杂度都是 O(n)但递归写法代码更短适合实验报告里的“逆序输出单链表”小题。需要注意的是这个函数不修改链表入参是首元节点L-next如果传L会把头节点的垃圾值也打印出来。4. 插入、删除与排序写操作的关键切换读操作做熟了接下里就是改结构。插入、删除、排序、清空每一处都在考验指针顺序。写操作的核心口诀是先接后断先让新节点指向后继再让前驱指向新节点。4.1 在指定位置插入节点指针顺序是生死线在单链表的第 i 个位置插入元素 e实质是在第 i-1 个节点后面挂新节点。找到前驱是关键。int listInsert(LinkList L, int i, ElemType e) { if (i 1) return ERROR; LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) return ERROR; LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) return ERROR; s-data e; s-next p-next; p-next s; return OK; }逻辑说明p从L出发而不是从L-next出发这样i 1时p就是头节点可以在链表头部插入。while的终止条件同时检查p NULL避免插入位置超过了链表长度。插入的关键是s-next p-next先保存后继再p-next s更新前驱。顺序一旦写反p-next就被覆盖后半段链表丢失。参数说明i 从 1 开始计i 超出[1, 长度1]范围时返回 ERROR。malloc 失败也要返回 ERROR不要直接访问空指针。这里的头节点 L 是存在的所以暂不考虑不带头节点的写法。4.2 删除指定节点与按值删除free 前先接链删除第 i 个节点时同样要找到它的前驱。删除操作比插入多了一步释放被删节点的内存。int listDelete(LinkList L, int i, ElemType *e) { if (i 1) return ERROR; LNode *p L; int j 0; while (p-next ! NULL j i - 1) { p p-next; j; } if (p-next NULL) return ERROR; LNode *q p-next; p-next q-next; if (e ! NULL) { *e q-data; } free(q); return OK; }逻辑说明while条件必须判断p-next ! NULL因为我们要删除的是p-next它不能为空。q是被删节点先让前驱p-next指向q-next跳过q再free(q)。如果先 free(q)q-next 就再也拿不到了。参数说明e是出参用来带回被删除节点的值。如果只删除不取值可以传 NULL。这里函数返回 OK 或 ERROR不能只靠e判断。按值删除是另一个变体先找到第一个值等于 x 的节点的前驱再调用同样的删除逻辑。注意如果有多个重复值通常只删第一个。4.3 选择排序与冒泡排序的实现链表排序为什么不推荐相邻交换链表排序最简单的实现是选择排序每趟找到最小节点交换它的 data 到当前趟的起始位置。因为不需要随机访问遍历找最小节点很方便。void listSort(LinkList L) { for (LNode *p L-next; p ! NULL; p p-next) { LNode *min p; for (LNode *q p-next; q ! NULL; q q-next) { if (q-data min-data) { min q; } } if (min ! p) { ElemType t min-data; min-data p-data; p-data t; } } }逻辑说明外循环从首元节点开始内循环从p-next开始在未排序部分找最小值的节点。找到后交换两个节点的data节点顺序完全不变。这里用交换值而不是交换节点可以规避大量指针修改。参数说明时间复杂度是 O(n²)没有额外空间。链表做冒泡排序很别扭因为相邻节点交换后下一轮需要重新定位前驱代码会写得很长。链表的 O(n log n) 排序一般用归并排序但那属于进阶题。实验报告里要求冒泡排序时也可以用交换 data 的方式模拟相邻交换视觉上更好理解。4.4 清空与销毁保留头节点和不保留头节点的区别清空链表是删除所有数据节点但保留头节点。销毁链表是连同头节点一起释放并把链表头指针置为 NULL。void listClear(LinkList L) { LNode *p L-next; while (p ! NULL) { LNode *q p; p p-next; free(q); } L-next NULL; } void listDestroy(LinkList *L) { listClear(*L); free(*L); *L NULL; }逻辑说明清空时先保存当前节点q再让p指向q-next最后 free(q)。如果先free(p)再p p-next读到的就是已释放的内存行为不可预料。销毁要传二级指针LinkList *L因为函数内部要修改调用者的指针为 NULL。参数说明listDestroy接收L调用后原来的L变成 NULL后续再用L时会立刻发现空指针。如果不置 NULL就成了悬空指针这是很多代码“偶尔崩溃、偶尔不崩”的原因。5. 避坑链表实例里最常见的五个翻车点链表代码看着不长出错率却很高很多问题都出在“以为自己理解了指针”上面。这里把最常见的翻车点按“现象 → 原因 → 解决”写清楚。5.1 返回局部节点地址导致悬空指针现象链表函数返回了一个节点指针主函数一用就乱输出或者偶尔正常偶尔崩溃。原因在函数内部声明了一个局部LNode x然后return x;。局部变量在函数返回后就释放了返回的指针指向一块已经被收回的栈空间。这种情况在编译时通常没有报错运行行为像玄学。LNode* createNodeBad() { LNode x; x.data 1; x.next NULL; return x; // 错误返回局部变量地址 } LNode* createNodeGood(int val) { LNode *s (LNode*)malloc(sizeof(LNode)); s-data val; s-next NULL; return s; }解决节点必须用 malloc 在堆上申请不用时用 free 释放。函数返回的指针要么是 malloc 来的要么是链表里已有的节点地址绝不能是函数内部普通变量的地址。5.2 插入删除时指针顺序写反导致断链现象插入节点后链表只输出了前半段后半段凭空消失。原因在插入时先执行了p-next s;再执行s-next p-next;。此时p-next已经被改成ss-next指向了自己或 NULL原来的后继节点丢失。// 错误写法 s-next p-next; // 这两行顺序写反会导致断链 p-next s; // 正确写法 s-next p-next; p-next s;解决插入操作永远先让新节点指向旧后继再让前驱指向新节点。删除操作先让前驱跳过被删节点再 free。这个顺序没有例外写完后可以用单步调试或打印语句确认s-next的值。5.3 遍历带头节点链表时把头节点算进去现象链表的长度总是比实际多 1打印输出多了一个不确定的数字。原因遍历从L开始而不是从L-next开始。头节点不存数据它的data是个未初始化的野值打印出来难以理解。// 错误 int badLength(LinkList L) { int len 0; for (LNode *p L; p ! NULL; p p-next) { len; } return len; } // 正确 int goodLength(LinkList L) { int len 0; for (LNode *p L-next; p ! NULL; p p-next) { len; } return len; }解决所有遍历类操作都从L-next开始。只有插入和删除时为了让头节点能作为“前驱”才从L开始移动指针。这个规律可以当成规则来记读链表永远从第一个数据节点开始改链表才允许从头节点开始。5.4 free 之后不置 NULL 带来重复释放现象同一段链表被清理两次程序在第二次 free 时报错崩溃。原因第一次free(p)后p仍然指向那块已释放的内存但指针变量本身没有被置 NULL。第二次再free(p)就是对同一块内存执行 double free引发运行时错误。Node *p (Node*)malloc(sizeof(Node)); free(p); p NULL; // 释放后立即置空解决free 之后立即把指针置为 NULL尤其是在销毁链表时把链表头指针也置成 NULL。我习惯在写链表函数时遵循一条约束谁 malloc谁 freefree 完立刻置 NULL。这样悬空指针的概率会小很多。5.5 空链表、单节点、删除头节点时边界翻车现象对长度为 0 或 1 的链表执行插入、删除程序没问题对长度为 2 的链表删除第一个数据节点结果链表变成空指针或者少了一个节点。原因边界条件的判断不完整。删除第一个数据节点时前驱是头节点L执行L-next q-next没问题。但如果不写while (p-next ! NULL)而是只写while (p ! NULL)当p跑到最后一个节点时p-next是 NULL再访问p-next-next就会空指针崩溃。边界情况容易犯的错误处理方式空链表直接访问L-next的 next先判断 L NULL单节点删除节点后没把前驱置 NULL用p-next q-next统一处理删除头节点直接把L往后移丢头节点带头节点链表要改L-next不能改L解决写任何链表函数之前先列三个输入空链表、单节点链表、普通链表。分别跑一遍所有针对链表结构的操作都检查这两种极端情况。尤其注意带头节点的链表删除第一个数据节点时被修改的还是L-next而不是L本身。6. 用断言式测试和“最小链表”验证十九种操作链表操作写完不测试等于没写。我一般会用一个简单的测试宏把期望值和实际值对比失败时打印出错位置并退出。这个方法比用printf肉眼比对更高效也适合写实验报告里的测试截图。#include assert.h #define ASSERT_INT_EQ(actual, expected) do { \ if ((actual) ! (expected)) { \ fprintf(stderr, line %d: %d ! %d\n, \ __LINE__, (actual), (expected)); \ exit(1); \ } \ } while (0)用这个宏可以快速验证链表长度、查找结果、删除返回值。比如对长度为 3 的链表执行删除第 2 个节点期望剩余长度为 2期望第二个节点变成原来的第三个节点代码写出来就是void test_list() { int arr[] {1, 2, 3}; LinkList L listTailInsert(arr, 3); ASSERT_INT_EQ(listLength(L), 3); ElemType deleted 0; ASSERT_INT_EQ(listDelete(L, 2, deleted), OK); ASSERT_INT_EQ(deleted, 2); ASSERT_INT_EQ(listLength(L), 2); LNode *second getNodeByIndex(L, 2); ASSERT_INT_EQ(second-data, 3); listReverse(L); ASSERT_INT_EQ(getNodeByIndex(L, 1)-data, 3); ASSERT_INT_EQ(getNodeByIndex(L, 2)-data, 1); listDestroy(L); ASSERT_INT_EQ(L NULL, 1); }这段测试覆盖了建链表、长度、删除、取值、反转、销毁六类操作。剩下十三种操作可以继续往上叠每加一种操作就在测试函数里加两条断言。断言失败时错误信息直接指出是哪一行不满足省去了到处插打印语句的功夫。我自己的习惯是先构造一个长度为 3 的“最小链表”把插入、删除、反转都跑一遍再用长度为 0 和 1 的链表跑边界最后才用长度 5 以上的链表做压力验证。链表出问题多数不是算法没看懂而是某个边界条件没有覆盖到。把十九种操作当成一组可以互相调用的工具函数来写每种操作都保持入参明确、返回值一致最后用统一测试函数收口这样整套代码才算真正能交差。希望这些验证方法和踩坑经验能帮到你。本文还有配套的精品资源点击获取 C语言链表十九种操作详解：从建链到避坑实践
简介面向C语言与数据结构初学者的链表专题资料以PDF文档形式整理链表操作的完整实例代码涵盖创建、遍历、查询结点数、判空、冒泡排序、按值/按位查找、修改、头插/尾插/按位插/有序插入、头删/尾删/按位删/按值删、交换结点、删除整表等十九种操作适合正在学习单链表或准备算法笔试的读者对照练习。资源为1个PDF文件压缩包整体约57KB轻量易用下载后可直接阅读源码头注释与完整实现。已有734人学习下载内容结构清晰以函数模块划分便于按需查阅通过阅读该文档可快速理解链表结点结构、malloc动态分配、遍历与指针修改等关键知识点并积累常用链表操作的可复用代码片段。1. C 语言链表实例十九种操作到底在练什么很多人学数据结构 C 语言版时第一次被要求写一个“链表的实例”常常会拿到一张实验报告上面写着“实现单链表的基本操作实验”少则增删改查多则十九种操作一起上。别小看这十九种操作建表、遍历、查找、插入、删除、修改、排序、反转、合并、判环、约瑟夫环每加一种指针操作就深一层。它的本质不是背代码而是让“节点里存数据、节点间靠指针串起来”这件事变成肌肉记忆。C 语言链表的十九种操作解决的是几个被问烂但还是会翻车的问题头插法和尾插法什么时候用插入和删除要不要改前驱的 nextfree 之后指针还能不能碰边界条件是空链表还是单节点所以这篇笔记按“建链 → 读数据 → 改结构 → 避坑 → 验证”的思路把每类操作的关键代码和参数选择拆开讲新手能跟着敲熟手也能对照排查细节。2. 链表实例的骨架结构体定义与三种建链方式写链表前先定义好节点后面所有操作都建立在同一套结构上。常见的链表示例会让数据域用 typedef 重命名好处是将来把 int 换成 float 或结构体时只改一行。2.1 节点结构体与宏定义数据域、指针域、状态码#include stdio.h #include stdlib.h typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; } LNode, *LinkList; #define OK 1 #define ERROR 0逻辑说明data是数据域next是指针域struct Node *next的写法是因为在结构体内部还不能直接用LNode *next这种别名必须写完整的struct Node *。LNode用来表示节点类型LinkList用来表示链表头指针类型二者本质一样但语义不同看到LinkList时知道这是一个链表头看到LNode *时知道这是一个普通节点指针。参数说明ElemType是数据域类型的抽象若链表要存字符串可以把typedef int ElemType改成typedef char* ElemType但后续涉及比较、赋值、打印的地方也要跟着改。OK和ERROR是函数返回的状态码可能只是一个int但写出来的代码意图更清楚。2.2 头插法建立单链表新节点永远插在头节点之后头插法是最容易写错的建链方式因为它会把输入顺序反过来。代码实现是每次申请一个新节点然后把它挂到链表的头部。LinkList listHeadInsert(int arr[], int n) { LinkList L (LinkList)malloc(sizeof(LNode)); if (!L) return NULL; L-next NULL; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); if (!s) return NULL; s-data arr[i]; s-next L-next; L-next s; } return L; }逻辑说明申请头节点L让L-next NULL这样链表从空表开始。每读一个数组元素就生成一个节点ss-next L-next把新节点接到当前首元节点前面L-next s再让头节点指向新节点。由于后面的节点不断抢占链表头部最终数组的最后一个元素会排在最前面。参数说明arr[]是传入的原始数据n是元素个数。函数返回值是链表头指针。注意这里为了示例简洁没有做完整的内存释放处理如果malloc中途失败在真实工程里要把已申请的节点逐个释放不然会出现内存泄漏。2.3 尾插法建立单链表尾指针的意义尾插法保持数据的原始顺序代价是需要一个尾指针r始终指向最后一个节点。LinkList listTailInsert(int arr[], int n) { LinkList L (LinkList)malloc(sizeof(LNode)); if (!L) return NULL; L-next NULL; LNode *r L; for (int i 0; i n; i) { LNode *s (LNode*)malloc(sizeof(LNode)); if (!s) return NULL; s-data arr[i]; s-next NULL; r-next s; r s; } return L; }逻辑说明初始r L此时头节点也是尾节点。每创建一个新节点ss-next NULL然后r-next s把新节点挂在尾节点后面r s让r指向新的尾节点。这样插入顺序和数组顺序完全一致。参数说明如果不保存尾指针每次插入都要从L出发遍历到链表尾部插入 n 个元素的时间会变成 O(n²)。这里保留尾指针每次都是 O(1)。面试里经常问头插法和尾插法的区别头插法适合栈式数据尾插法适合队列式数据。2.4 用数组批量构造链表单元测试最常用的手段手工调用多次插入来建链表太慢我一般会用数组批量构造这样测试用例可以写得很紧凑。int main() { int arr[] {3, 1, 4, 1, 5}; int n sizeof(arr) / sizeof(arr[0]); LinkList L listTailInsert(arr, n); for (LNode *p L-next; p; p p-next) { printf(%d , p-data); } printf(\n); return 0; }逻辑说明sizeof(arr) / sizeof(arr[0])计算数组长度避免硬编码n。链表建立后从头节点的下一个节点开始遍历直到p NULL为止。输出结果是3 1 4 1 5说明尾插法没有改变数据顺序。参数说明数组批量构造适合长度固定、输入已知的测试场景。如果要在程序运行中动态输入就把arr[i]换成scanf读入的值。批量构造的一个坑是忘记处理malloc失败测试时数据量小可能没问题数据量一大就容易出事。建链方式数据顺序时间复杂度适用场景头插法逆序O(n)需要反转数据、构建栈结构尾插法原序O(n)保持输入顺序、队列结构数组批量构造原序或逆序O(n)单元测试、固定样例3. 遍历、查找与修改读操作先过关读操作是链表入门的第一道坎。遍历输出、求链表长度、按值查找、按位置查找看着简单实际写起来全是细节。3.1 遍历输出与求长度循环终止条件的差别遍历链表的终止条件有两种写法while (p ! NULL)和while (p-next ! NULL)。求长度和输出全部节点要用前者只处理到倒数第二个节点时才用后者。int listLength(LinkList L) { int len 0; LNode *p L-next; while (p ! NULL) { len; p p-next; } return len; } void listPrint(LinkList L) { for (LNode *p L-next; p ! NULL; p p-next) { printf(%d , p-data); } printf(\n); }逻辑说明len从 0 开始每经过一个节点自增一次。for循环的初始化和后继跳转集中在一起适合只读遍历。p p-next必须在打印完当前节点之后执行否则会跳过首元节点输出结果少一个。参数说明listLength的时间复杂度是 O(n)链表本身不记录长度。如果频繁需要长度可以在结构体里增加一个size字段每次插入删除时维护它但十九种操作的基础版一般不这么做。遍历时如果误用while (p-next ! NULL)长度会少算 1这种错误很难肉眼发现。3.2 按值查找与按位置查找返回值的两种设计按值查找从头节点之后开始找到第一个data x的节点。按位置查找需要约定下标起点常见的有从 0 开始和从 1 开始两种习惯实验报告里推荐从 1 开始因为教材上 i 表示第 i 个节点。LNode* locateByValue(LinkList L, ElemType x) { LNode *p L-next; while (p ! NULL p-data ! x) { p p-next; } return p; } LNode* getNodeByIndex(LinkList L, int i) { if (i 1) return NULL; LNode *p L-next; int j 1; while (p ! NULL j i) { p p-next; j; } return p; }逻辑说明locateByValue返回 NULL 表示没有找到。getNodeByIndex中j从 1 开始p一开始指向第 1 个节点当j i时不断后移直到p NULL说明 i 超出了链表长度。参数说明这两种查找返回的都是目标节点本身而不是它的前驱。做插入删除时返回前驱往往更实用因为光拿到目标节点无法知道它的前驱是谁。这也是链表和数组最大的差异数组按下标能直接访问链表必须顺着指针走。3.3 修改节点值与交换两个节点什么时候要动指针修改节点值最简单定位到节点后只改data不碰next。交换两个节点有两种思路交换值或者交换指针。链表操作里我最推荐交换值因为不动指针就不容易断链。int changeNodeValue(LinkList L, int i, ElemType newVal) { LNode *p getNodeByIndex(L, i); if (p NULL) return ERROR; p-data newVal; return OK; } int swapNodeData(LNode *a, LNode *b) { if (a NULL || b NULL) return ERROR; ElemType t a-data; a-data b-data; b-data t; return OK; }逻辑说明changeNodeValue先调用getNodeByIndex返回 NULL 就报错。swapNodeData只交换两个节点的data链接关系完全不变排序算法里经常这样用。参数说明如果一定要交换节点位置需要同时修改两个节点的前驱和它们的next还要处理相邻节点和头节点的情况非常容易翻车。所以我在链表排序时一律交换值不交换节点。3.4 逆序输出用递归还是用辅助栈不修改链表结构只要求从尾到头打印可以用递归或辅助栈。递归代码最少但栈深度跟链表长度成正比。void printListReverse(LNode *p) { if (p NULL) return; printListReverse(p-next); printf(%d , p-data); }逻辑说明递归调用先走到链尾回溯时再打印天然得到逆序输出。调用层次等于链表长度链表有几万个节点时可能栈溢出这时要用循环加辅助栈替代。参数说明辅助栈写法是先遍历链表把所有元素压栈再逐个出栈打印。空间复杂度都是 O(n)但递归写法代码更短适合实验报告里的“逆序输出单链表”小题。需要注意的是这个函数不修改链表入参是首元节点L-next如果传L会把头节点的垃圾值也打印出来。4. 插入、删除与排序写操作的关键切换读操作做熟了接下里就是改结构。插入、删除、排序、清空每一处都在考验指针顺序。写操作的核心口诀是先接后断先让新节点指向后继再让前驱指向新节点。4.1 在指定位置插入节点指针顺序是生死线在单链表的第 i 个位置插入元素 e实质是在第 i-1 个节点后面挂新节点。找到前驱是关键。int listInsert(LinkList L, int i, ElemType e) { if (i 1) return ERROR; LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) return ERROR; LNode *s (LNode*)malloc(sizeof(LNode)); if (s NULL) return ERROR; s-data e; s-next p-next; p-next s; return OK; }逻辑说明p从L出发而不是从L-next出发这样i 1时p就是头节点可以在链表头部插入。while的终止条件同时检查p NULL避免插入位置超过了链表长度。插入的关键是s-next p-next先保存后继再p-next s更新前驱。顺序一旦写反p-next就被覆盖后半段链表丢失。参数说明i 从 1 开始计i 超出[1, 长度1]范围时返回 ERROR。malloc 失败也要返回 ERROR不要直接访问空指针。这里的头节点 L 是存在的所以暂不考虑不带头节点的写法。4.2 删除指定节点与按值删除free 前先接链删除第 i 个节点时同样要找到它的前驱。删除操作比插入多了一步释放被删节点的内存。int listDelete(LinkList L, int i, ElemType *e) { if (i 1) return ERROR; LNode *p L; int j 0; while (p-next ! NULL j i - 1) { p p-next; j; } if (p-next NULL) return ERROR; LNode *q p-next; p-next q-next; if (e ! NULL) { *e q-data; } free(q); return OK; }逻辑说明while条件必须判断p-next ! NULL因为我们要删除的是p-next它不能为空。q是被删节点先让前驱p-next指向q-next跳过q再free(q)。如果先 free(q)q-next 就再也拿不到了。参数说明e是出参用来带回被删除节点的值。如果只删除不取值可以传 NULL。这里函数返回 OK 或 ERROR不能只靠e判断。按值删除是另一个变体先找到第一个值等于 x 的节点的前驱再调用同样的删除逻辑。注意如果有多个重复值通常只删第一个。4.3 选择排序与冒泡排序的实现链表排序为什么不推荐相邻交换链表排序最简单的实现是选择排序每趟找到最小节点交换它的 data 到当前趟的起始位置。因为不需要随机访问遍历找最小节点很方便。void listSort(LinkList L) { for (LNode *p L-next; p ! NULL; p p-next) { LNode *min p; for (LNode *q p-next; q ! NULL; q q-next) { if (q-data min-data) { min q; } } if (min ! p) { ElemType t min-data; min-data p-data; p-data t; } } }逻辑说明外循环从首元节点开始内循环从p-next开始在未排序部分找最小值的节点。找到后交换两个节点的data节点顺序完全不变。这里用交换值而不是交换节点可以规避大量指针修改。参数说明时间复杂度是 O(n²)没有额外空间。链表做冒泡排序很别扭因为相邻节点交换后下一轮需要重新定位前驱代码会写得很长。链表的 O(n log n) 排序一般用归并排序但那属于进阶题。实验报告里要求冒泡排序时也可以用交换 data 的方式模拟相邻交换视觉上更好理解。4.4 清空与销毁保留头节点和不保留头节点的区别清空链表是删除所有数据节点但保留头节点。销毁链表是连同头节点一起释放并把链表头指针置为 NULL。void listClear(LinkList L) { LNode *p L-next; while (p ! NULL) { LNode *q p; p p-next; free(q); } L-next NULL; } void listDestroy(LinkList *L) { listClear(*L); free(*L); *L NULL; }逻辑说明清空时先保存当前节点q再让p指向q-next最后 free(q)。如果先free(p)再p p-next读到的就是已释放的内存行为不可预料。销毁要传二级指针LinkList *L因为函数内部要修改调用者的指针为 NULL。参数说明listDestroy接收L调用后原来的L变成 NULL后续再用L时会立刻发现空指针。如果不置 NULL就成了悬空指针这是很多代码“偶尔崩溃、偶尔不崩”的原因。5. 避坑链表实例里最常见的五个翻车点链表代码看着不长出错率却很高很多问题都出在“以为自己理解了指针”上面。这里把最常见的翻车点按“现象 → 原因 → 解决”写清楚。5.1 返回局部节点地址导致悬空指针现象链表函数返回了一个节点指针主函数一用就乱输出或者偶尔正常偶尔崩溃。原因在函数内部声明了一个局部LNode x然后return x;。局部变量在函数返回后就释放了返回的指针指向一块已经被收回的栈空间。这种情况在编译时通常没有报错运行行为像玄学。LNode* createNodeBad() { LNode x; x.data 1; x.next NULL; return x; // 错误返回局部变量地址 } LNode* createNodeGood(int val) { LNode *s (LNode*)malloc(sizeof(LNode)); s-data val; s-next NULL; return s; }解决节点必须用 malloc 在堆上申请不用时用 free 释放。函数返回的指针要么是 malloc 来的要么是链表里已有的节点地址绝不能是函数内部普通变量的地址。5.2 插入删除时指针顺序写反导致断链现象插入节点后链表只输出了前半段后半段凭空消失。原因在插入时先执行了p-next s;再执行s-next p-next;。此时p-next已经被改成ss-next指向了自己或 NULL原来的后继节点丢失。// 错误写法 s-next p-next; // 这两行顺序写反会导致断链 p-next s; // 正确写法 s-next p-next; p-next s;解决插入操作永远先让新节点指向旧后继再让前驱指向新节点。删除操作先让前驱跳过被删节点再 free。这个顺序没有例外写完后可以用单步调试或打印语句确认s-next的值。5.3 遍历带头节点链表时把头节点算进去现象链表的长度总是比实际多 1打印输出多了一个不确定的数字。原因遍历从L开始而不是从L-next开始。头节点不存数据它的data是个未初始化的野值打印出来难以理解。// 错误 int badLength(LinkList L) { int len 0; for (LNode *p L; p ! NULL; p p-next) { len; } return len; } // 正确 int goodLength(LinkList L) { int len 0; for (LNode *p L-next; p ! NULL; p p-next) { len; } return len; }解决所有遍历类操作都从L-next开始。只有插入和删除时为了让头节点能作为“前驱”才从L开始移动指针。这个规律可以当成规则来记读链表永远从第一个数据节点开始改链表才允许从头节点开始。5.4 free 之后不置 NULL 带来重复释放现象同一段链表被清理两次程序在第二次 free 时报错崩溃。原因第一次free(p)后p仍然指向那块已释放的内存但指针变量本身没有被置 NULL。第二次再free(p)就是对同一块内存执行 double free引发运行时错误。Node *p (Node*)malloc(sizeof(Node)); free(p); p NULL; // 释放后立即置空解决free 之后立即把指针置为 NULL尤其是在销毁链表时把链表头指针也置成 NULL。我习惯在写链表函数时遵循一条约束谁 malloc谁 freefree 完立刻置 NULL。这样悬空指针的概率会小很多。5.5 空链表、单节点、删除头节点时边界翻车现象对长度为 0 或 1 的链表执行插入、删除程序没问题对长度为 2 的链表删除第一个数据节点结果链表变成空指针或者少了一个节点。原因边界条件的判断不完整。删除第一个数据节点时前驱是头节点L执行L-next q-next没问题。但如果不写while (p-next ! NULL)而是只写while (p ! NULL)当p跑到最后一个节点时p-next是 NULL再访问p-next-next就会空指针崩溃。边界情况容易犯的错误处理方式空链表直接访问L-next的 next先判断 L NULL单节点删除节点后没把前驱置 NULL用p-next q-next统一处理删除头节点直接把L往后移丢头节点带头节点链表要改L-next不能改L解决写任何链表函数之前先列三个输入空链表、单节点链表、普通链表。分别跑一遍所有针对链表结构的操作都检查这两种极端情况。尤其注意带头节点的链表删除第一个数据节点时被修改的还是L-next而不是L本身。6. 用断言式测试和“最小链表”验证十九种操作链表操作写完不测试等于没写。我一般会用一个简单的测试宏把期望值和实际值对比失败时打印出错位置并退出。这个方法比用printf肉眼比对更高效也适合写实验报告里的测试截图。#include assert.h #define ASSERT_INT_EQ(actual, expected) do { \ if ((actual) ! (expected)) { \ fprintf(stderr, line %d: %d ! %d\n, \ __LINE__, (actual), (expected)); \ exit(1); \ } \ } while (0)用这个宏可以快速验证链表长度、查找结果、删除返回值。比如对长度为 3 的链表执行删除第 2 个节点期望剩余长度为 2期望第二个节点变成原来的第三个节点代码写出来就是void test_list() { int arr[] {1, 2, 3}; LinkList L listTailInsert(arr, 3); ASSERT_INT_EQ(listLength(L), 3); ElemType deleted 0; ASSERT_INT_EQ(listDelete(L, 2, deleted), OK); ASSERT_INT_EQ(deleted, 2); ASSERT_INT_EQ(listLength(L), 2); LNode *second getNodeByIndex(L, 2); ASSERT_INT_EQ(second-data, 3); listReverse(L); ASSERT_INT_EQ(getNodeByIndex(L, 1)-data, 3); ASSERT_INT_EQ(getNodeByIndex(L, 2)-data, 1); listDestroy(L); ASSERT_INT_EQ(L NULL, 1); }这段测试覆盖了建链表、长度、删除、取值、反转、销毁六类操作。剩下十三种操作可以继续往上叠每加一种操作就在测试函数里加两条断言。断言失败时错误信息直接指出是哪一行不满足省去了到处插打印语句的功夫。我自己的习惯是先构造一个长度为 3 的“最小链表”把插入、删除、反转都跑一遍再用长度为 0 和 1 的链表跑边界最后才用长度 5 以上的链表做压力验证。链表出问题多数不是算法没看懂而是某个边界条件没有覆盖到。把十九种操作当成一组可以互相调用的工具函数来写每种操作都保持入参明确、返回值一致最后用统一测试函数收口这样整套代码才算真正能交差。希望这些验证方法和踩坑经验能帮到你。本文还有配套的精品资源点击获取