学完结构体、指针之后就来到数据结构第一个重点单向链表。 数组顺序存储内存连续链表是链式存储内存分散依靠指针把一个个节点串起来。 链表最大难点就是指针逻辑写代码很容易出现段错误、内存泄漏、指针指向错乱。一、基于链表的学生管理系统1.知识回顾节点结构带头结点单链表节点分为两部分数据域存放业务数据这里是学生信息姓名、年龄、分数指针域next存下一个节点的地址头节点不存放有效学生数据作为链表入口。首节点第一个存真实业务数据的节点尾节点next NULL代表链表结束空链表head-next NULLstruct stu { char name[20]; int age; float score; }; typedef struct stu data_t; typedef struct node { data_t data; //数据域学生信息 struct node *next; //指针域下一个节点地址 }node_t;链表基础操作清单创建空链表malloc 头节点头插、尾插节点判断链表是否为空遍历打印链表获取链表长度根据 key 查找节点修改节点数据删除节点菜单交互学生管理系统业务逻辑2.完整代码#include stdio.h #include stdlib.h #include string.h struct stu { char name[20]; int age; float score; }; typedef struct stu data_t; typedef struct node { data_t data; struct node *next; }node_t; //创建带头节点空链表 node_t * linklist_create(void) { node_t * head malloc(sizeof(node_t)); if (headNULL) { printf(linklist_create malloc fail\n); return NULL; } head-next NULL; return head; } //头插新节点 int linklist_insert_head(node_t *phead,data_t *data) { if (phead NULL) { return -1; } node_t *pnew malloc(sizeof(node_t)); if (pnewNULL) { return -1; } pnew-data *data; pnew-next phead-next; phead-next pnew; return 0; } //判断链表是否为空 int is_empty(node_t *phead) { if (phead NULL) { return -1; } return phead-next NULL; } //打印单个学生 void printStu(void *p) { data_t q ((node_t *)p)-data; printf(name %s\n,q.name); printf(age %d\n,q.age); printf(score %.2f\n,q.score); } //遍历打印全部链表 int linklist_print(node_t *phead,void (*pprint)(void *)) { if (phead NULL || is_empty(phead) 1) { return -1; } node_t *p phead-next; while (p!NULL) { pprint(p); p p-next; } putchar(\n); return 0; } //获取链表节点个数 int length(node_t *phead) { if (phead NULL) { return -1; } if (is_empty(phead) 1) { return 0; } int cnt 0; node_t *p phead-next; while (p!NULL) { cnt; p p-next; } return cnt; } //按key查找节点 node_t *linklist_find_key(node_t *phead,data_t key) { if (phead NULL || is_empty(phead) 1) { return NULL; } node_t *p phead-next; while (p! NULL) { if (memcmp(p-data,key,sizeof(data_t)) 0) { return p; } p p-next; } return NULL; } //更新节点数据 node_t *linklist_update(node_t *phead,data_t old,data_t new) { if (phead NULL || is_empty(phead) 1) { return NULL; } node_t *p phead-next; while (p! NULL) { if (memcmp(p-data,old,sizeof(data_t)) 0) { p-data new; return p; } p p-next; } return NULL; } //头删 int linklist_delete_head(node_t *phead) { if (phead NULL || is_empty(phead) 1) { return -1; } node_t *p phead-next; phead-next p-next; free(p); pNULL; return 0; } //打印菜单 void printMenu(void) { printf(-----------学生管理系统----------------\n); printf( 1.批量录入学生信息\n 2.打印学生信息\n 3.新增单个学生信息\n 4.删除头部学生信息\n 5.统计学生人数\n 6.退出\n); printf( ); } int main(int argc, const char *argv[]) { node_t *phead linklist_create(); while(1) { printMenu(); int op 0; scanf(%d,op); switch (op) { case 1: printf(Input stu nums:); int nums 0; scanf(%d,nums); int i 0; for (i 0; i nums; i) { data_t d; printf(Input name,age,score:); scanf(%s,d.name); scanf(%d,d.age); scanf(%f,d.score); linklist_insert_head(phead,d); } break; case 2: linklist_print(phead,printStu); break; case 3: printf(Input name,age,score:); data_t d; scanf(%s,d.name); scanf(%d,d.age); scanf(%f,d.score); linklist_insert_head(phead,d); break; case 4: linklist_delete_head(phead); break; case 5: printf(stu nums: %d\n,length(phead)); break; case 6: printf(---退出-----\n); goto exit; } } exit: return 0; }二、GDB 调试链表程序链表大量指针操作极易发生段错误 Segmentation fault肉眼很难看出来必须学会 GDB 调试。带调试符号编译必须加-g -O0-g生成调试符号-O0关闭编译器优化防止代码行号错乱gcc -g -O0 swap.c -o swap启动调试gdb ./stu_linklist出现(gdb)提示符代表进入调试器。GDB 高频命令速查表格命令 (缩写)功能r(run)从头运行程序c(continue)继续运行到下一个断点n(next)单步不进入函数s(step)单步进入函数内部finish执行完当前函数返回b(break) main在 main 函数打断点b 35在 35 行打断点info b查看全部断点p 变量名打印变量p/x 变量十六进制打印bt(backtrace)打印函数调用栈崩溃必用l(list)查看附近源代码watch p观察点变量被修改时停下排查指针异常神器q(quit)退出 gdb三、链表高频考点1. 找到链表的中间节点题目描述给定一条带头单向链表找出链表中间节点。 奇数个节点返回正中间偶数个节点返回中间第二个节点。 示例head-1-2-3-4-5-NULL中间节点是3head-1-2-3-4-5-6-NULL中间节点是4思路两种方案方案 1先遍历一遍统计链表总长度再遍历len/2次找到中点需要遍历 2 次链表。方案 2快慢指针推荐只遍历 1 次链表快指针 p一次走 2 步慢指针 q一次走 1 步 快指针走到末尾 NULL 时慢指针刚好停在中点。node_t *linklist_find_mid(node_t *phead) { //判断有效性 if (phead NULL) { return NULL; } node_t *p phead;//快指针一次走两步 node_t *q phead;//慢指针一次走一步 //循环条件链表元素为偶数p-nextNULL结束奇数pNULL结束 while (p-next ! NULL p ! NULL) { p p-next-next; q q-next; } return q; }2. 找到链表的倒数第 k 个节点题目描述找到链表倒数第 k 个节点。例如链表1-2-3-4-5-6k2倒数第 2 个节点是5。 要求只遍历链表一次。思路前后双指针p、q 两个指针都先指向头节点让 p 指针先走 k 步之后 p、q 同步向后一步一步走当 p 走到 NULL 的时候q 所在节点就是倒数第 k 个节点边界坑k 大于链表总节点数直接返回 NULL。node_t *linklist_find_behind_key(node_t *phead, int key) { if (phead 0 || is_empty(phead) 1) { return NULL; } node_t *p phead; node_t *q phead; //p先走key步 while (key 0) { p p-next; --key; } //p、q同步移动当pNULLq所在位置为倒数第key个 while (p ! NULL) { p p-next; q q-next; } return q; }3. 判断链表是否有环题目描述单向链表是否存在环。有环的链表尾节点不会指向 NULL会指向链表内部某个节点遍历会无限循环。思路快慢指针追击Floyd 判圈算法快指针 pf 一次走 2 步慢指针 ps 一次走 1 步如果链表无环快指针会率先走到 NULL直接返回 0如果链表存在环快慢指针一定会在环内相遇pf ps返回 1int linklist_is_circle(node_t *phead) { if (phead NULL || is_empty(phead) 1) { return -1; } node_t *p phead;//快指针一次走两步 node_t *q phead;//慢指针一次走一步 //考虑链表元素有奇数或偶数两种情况循环条件和找中间节点一样 while (p ! NULL p-next ! NULL) { p p-next-next; q q-next; if (p q)//快慢指针相遇说明有环 { return 1; } } //p走到NULL说明无环 if (p NULL || p-next NULL) { return 0; } }4. 链表的逆序倒置就地反转题目描述将带头单向链表原地反转不能新开链表。 原始head -1-2-3-4-NULL逆序后head -4-3-2-1-NULL思路头插法就地逆置p指向第一个有效节点p phead-next把头节点next置 NULL当成空链表依次取出 p 指向节点不断头插到 head 后面直到 p 遍历完毕int linklist_reverse(node_t *phead) { if (phead NULL || phead-next NULL) { return -1; } if (phead-next-next NULL)//链表中只有一个数据不进行逆序操作 { return 0; } node_t *p phead-next;//p指向首元素 phead-next NULL; //头节点变成空链表 node_t *q NULL; //q临时保存p的下一个节点 //头插法 while (p ! NULL) { q p-next; p-next phead-next; phead-next p; p q;//p向后移动 } return 1; }三指针法int linklist_reverse_threep(node_t*phead) { if (phead NULL || phead-next NULL) { return -1; } if (phead-next-next NULL) { return 0; } node_t *curr phead-next; node_t *prev NULL; node_t *next NULL; while (curr ! NULL) { next curr-next; curr-next prev; prev curr; curr next; } phead-next prev; return 1; }5. 链表排序选择排序题目描述对单向链表进行升序排序这里采用选择排序。数组选择排序思路每一轮找到未排序区间最小值放到当前确定位置。链表版本用指针实现不交换节点数据操作指针。思路用外层指针标记当前待填充位置内层遍历找到后面数据最小的节点交换节点数据简易版面试快速手写高级版本直接移动节点指针说明链表选择排序简易实现可以交换节点内部 data简化代码。int linklist_select_sort(node_t *phead) { if (phead NULL || phead-next NULL) { return -1; } if (phead-next-next NULL) { return 0; } node_t *p phead-next; node_t *q p-next; int data; while (p-next ! NULL) { while (q ! NULL) { if (p-data q-data) { data p-data; p-data q-data; q-data data; } q q-next; } p p-next; q p-next; } return 1; }刷题总结快慢指针是链表笔试的核心技巧找中点、判环都靠它一定要吃透。双指针前后指针专门解决倒数第 k 节点这类 “距离固定” 的问题。链表逆置是必背手写代码嵌入式 C 面试出现频率极高。链表操作最容易踩坑空指针判断每一个函数入口先校验指针有效性。写链表代码的好习惯画图方框代表节点箭头表示 next 指针指针逻辑一目了然。四、总结带头单向链表核心节点 数据域 指针域画图是理解链表最好的手段。不要光背代码画方框 箭头模拟指针变化。学生管理系统完整实践创建、插入、删除、遍历、统计长度熟悉链表整套流程。链表大量指针操作出现段错误不要瞎猜学会GDB 调试断点、单步、print 打印指针、bt 看调用栈快速定位 bug。笔试高频链表逆置、判环、删除节点、头插尾插等必须能手写。