简介本资源是面向计算机专业学生、考研复试考生及校招求职者的《数据结构》核心算法实战手册紧密配套严蔚敏《数据结构C语言版》教材覆盖课程全部主干章节解决理论理解难、代码动手弱、机试刷题无系统方案等痛点。文档为单个Word文件.docx共162KB结构清晰、注释完整所有算法均以可独立编译运行的C语言代码实现含顺序表字符统计、多项式相加、稀疏矩阵转置、栈与队列行编辑器、后缀表达式求值、双向队列、查找排序二分查找、哈希表、八大经典排序、字符串匹配BF与KMP、树二叉树遍历、哈夫曼编码、前中序建树及图邻接矩阵/表的BFS、最小生成树等模块每节附带说明与关键注解。已有1391人学习下载适合作为期末复习、ACM训练、考研机试强化及面试算法速查的高实用性参考资料。1. 为什么你抄了严蔚敏书上的链表代码却跑不通——C语言实现数据结构算法不是“翻译”而是“重写”你手头那份《数据结构C语言版》严蔚敏教材翻到第28页的单链表插入操作照着抄完ListInsert_L函数编译通过一运行就段错误或者更糟——程序不报错但插入后遍历只输出第一个节点后面全丢。这不是你手抖漏了个-next也不是编译器抽风。这是典型的数据结构 C 实现「纸面正确、内存崩坏」陷阱教材代码是教学精简模型省略了内存分配失败处理、头结点初始化细节、指针有效性校验而真实 C 环境下malloc可能返回NULLL-next可能未初始化为NULLp-next s前s若未malloc就直接解引用——黑匣子瞬间炸开。本篇不讲抽象概念只聚焦「如何用标准 CC99 兼容在 Linux/macOS/Windows MinGW 下稳定复现线性表、栈、队列、树、图五大模块共 32 个核心算法」覆盖王道408 考纲全部必背代码、严蔚敏教材全部经典实现并给出每段代码的可验证输入输出样例、内存泄漏检查命令、GDB 断点设置位置。适合正在啃《数据结构实验报告》的本科生、备考 408 的考研党、以及需要把算法嵌入单片机固件注意单片机无malloc文中会单独标注替代方案的嵌入式工程师。所有代码均经 GCC 11.4 Clang 16 实测拒绝伪代码、拒绝截图、拒绝“读者自补”。2. 线性表从顺序表到静态链表三类实现必须分清适用场景严蔚敏教材中线性表实现常被混为一谈但实际工程中顺序表、动态链表、静态链表三者内存模型、时间复杂度、适用约束完全不同。盲目套用会导致考试扣分、嵌入式系统宕机、竞赛超时。本章逐个击破给出可直接编译运行的最小完整示例。2.1 顺序表用数组模拟但必须手动管理长度与容量顺序表本质是带长度计数器的动态数组。教材常忽略「容量扩容」逻辑导致插入超限时静默失败。以下为严格遵循 C99 标准、支持自动扩容的实现#include stdio.h #include stdlib.h #include string.h typedef int ElemType; typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配容量 } SqList; // 初始化顺序表初始容量为10 Status InitList_Sq(SqList *L) { L-elem (ElemType*)malloc(10 * sizeof(ElemType)); if (!L-elem) return ERROR; // 内存分配失败 L-length 0; L-listsize 10; return OK; } // 在第i个位置插入ei从1开始 Status ListInsert_Sq(SqList *L, int i, ElemType e) { if (i 1 || i L-length 1) return ERROR; // 位置非法 if (L-length L-listsize) { // 空间满需扩容 ElemType *newbase (ElemType*)realloc(L-elem, (L-listsize 10) * sizeof(ElemType)); if (!newbase) return ERROR; // 扩容失败 L-elem newbase; L-listsize 10; } // 移动元素从后往前避免覆盖 for (int j L-length; j i; j--) { L-elem[j] L-elem[j-1]; } L-elem[i-1] e; // 插入注意数组下标从0开始 L-length; return OK; }关键参数说明listsize是已分配内存单元数length是实际有效元素数二者必须分离管理否则无法判断是否需扩容realloc后必须重新赋值L-elem旧指针失效插入位置i从 1 开始教材约定但数组索引i-1这是初学者最易写反的边界移动方向必须从后往前j--若从前向后j则L-elem[j]被覆盖。2.2 动态单链表头结点是刚需不是可选项教材中“带头结点的单链表”常被简化为“头指针”但实际调试中无头结点链表的插入/删除操作需对首节点特殊处理极易漏判L NULL。以下为带明确头结点的标准实现typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; // 初始化带头结点的单链表 Status InitList_L(LinkList *L) { *L (LinkList)malloc(sizeof(LNode)); // 分配头结点 if (!*L) return ERROR; (*L)-next NULL; // 头结点指针域置空 return OK; } // 在第i个位置插入ei从1开始插入到头结点后第i个位置 Status ListInsert_L(LinkList L, int i, ElemType e) { LinkList p L, s; int j 0; while (p j i-1) { // 查找第i-1个结点 p p-next; j; } if (!p || j ! i-1) return ERROR; // i值不合法i1 或 iL-length1 s (LinkList)malloc(sizeof(LNode)); if (!s) return ERROR; s-data e; s-next p-next; p-next s; return OK; }为什么必须带头结点删除首节点时p-next s-next统一适用无需if (L s)特判L永远指向头结点其地址不变便于函数传参避免二级指针遍历时p L-next直接进入首元结点逻辑清晰。2.3 静态链表用数组模拟指针专治单片机内存受限场景单片机无malloc但需链表逻辑用静态链表游标实现。核心是用int next替代struct LNode *next所有节点存于固定数组中#define MAXSIZE 100 typedef struct { ElemType data; int next; // 游标指向下一个元素下标 } component; typedef struct { component space[MAXSIZE]; int length; int avail; // 空闲链表头下标 } SLinkList; // 初始化静态链表将所有节点链成空闲链 void InitSpace_SL(SLinkList *L) { for (int i 0; i MAXSIZE-1; i) { L-space[i].next i 1; // 0-1-2-...-98-99 } L-space[MAXSIZE-1].next 0; // 循环链表尾连头 L-avail 0; // 空闲链表头为0号单元 L-length 0; } // 分配一个空闲节点类似malloc int Malloc_SL(SLinkList *L) { int i L-avail; if (i) { L-avail L-space[i].next; // 取出首节点更新空闲链头 } return i; }单片机适配要点MAXSIZE编译期确定无运行时内存申请Malloc_SL返回数组下标非地址避免指针运算avail是整型游标非指针节省 RAM此结构可直接烧录进 STM32 的 64KB RAM 中运行。3. 栈与队列循环队列的模运算陷阱与共享栈的冲突检测栈和队列看似简单但循环队列的判空判满、共享栈的溢出检测是历年 408 真题高频雷区。教材公式rear front判空、(rear1)%MAXSIZE front判满若未理解其推导过程调试时会陷入玄学。3.1 循环队列牺牲一个存储单元换取判别唯一性标准循环队列用front和rear指针但front rear既可表示空也可表示满。解决方案约定满队列时rear指向的位置不存数据即实际容量为MAXSIZE-1。#define MAXQSIZE 100 typedef struct { ElemType *base; // 动态分配存储数组 int front; // 头指针指向队头元素 int rear; // 尾指针指向队尾元素的下一个位置 int queuesize; // 当前已分配容量 } SqQueue; Status InitQueue_Sq(SqQueue *Q) { Q-base (ElemType*)malloc(MAXQSIZE * sizeof(ElemType)); if (!Q-base) return ERROR; Q-front Q-rear 0; // 初始空队列 Q-queuesize MAXQSIZE; return OK; } Status EnQueue_Sq(SqQueue *Q, ElemType e) { if ((Q-rear 1) % MAXQSIZE Q-front) // 队满(rear1)%M front return ERROR; Q-base[Q-rear] e; Q-rear (Q-rear 1) % MAXQSIZE; // rear循环前进 return OK; } Status DeQueue_Sq(SqQueue *Q, ElemType *e) { if (Q-front Q-rear) return ERROR; // 队空 *e Q-base[Q-front]; Q-front (Q-front 1) % MAXQSIZE; // front循环前进 return OK; }模运算本质rear指向下一个待插入位置故插入后rear (rear1)%M判满条件(rear1)%M front表示若再插入rear将走到front位置与空队列状态冲突实际可用单元数 MAXQSIZE - 1这是硬性约束不可绕过。3.2 共享栈两栈相向增长溢出检测必须双向判断将两个栈共享同一数组stack1从0开始向上增长stack2从MAXSIZE-1开始向下增长。溢出发生在top1 1 top2时#define MAXSIZE 100 typedef struct { ElemType data[MAXSIZE]; int top1; // 栈1栈顶指针初始为-1 int top2; // 栈2栈顶指针初始为MAXSIZE } ShareStack; Status Push_Share(ShareStack *S, ElemType e, int stackNumber) { if (S-top1 1 S-top2) return ERROR; // 两栈相遇溢出 if (stackNumber 1) { S-data[S-top1] e; // 栈1先加top再存 } else if (stackNumber 2) { S-data[--S-top2] e; // 栈2先减top再存 } return OK; }双向溢出检测逻辑top1从-1开始top2从MAXSIZE开始确保初始不重叠top1 1 top2是唯一溢出条件不能只判top1 top2此时已重叠Push操作中栈1用top1前缀栈2用--top2前缀保证指针始终指向栈顶元素。3.3 链队列头尾指针缺一不可否则入队变 O(n)链队列若只保存front指针每次入队需遍历至队尾时间复杂度退化为 O(n)。必须同时维护rear指针typedef struct { LinkList front, rear; // 队头、队尾指针 } LinkQueue; Status InitQueue_L(LinkQueue *Q) { Q-front Q-rear (LinkList)malloc(sizeof(LNode)); if (!Q-front) return ERROR; Q-front-next NULL; // 头结点 return OK; } Status EnQueue_L(LinkQueue *Q, ElemType e) { LinkList s (LinkList)malloc(sizeof(LNode)); if (!s) return ERROR; s-data e; s-next NULL; Q-rear-next s; // 尾插 Q-rear s; // 更新尾指针 return OK; }为什么必须双指针Q-rear-next s直接连接O(1)若无rear需while(p-next) pp-nextO(n)Q-rear s保证下次入队仍为 O(1)这是链队列设计铁律。4. 树与二叉树递归遍历的终止条件与线索化二叉树的前驱后继定位二叉树是数据结构难点但核心只有两点递归终止条件必须精准线索化必须区分左右孩子与线索标志。教材常将if (T)作为唯一终止条件但实际需区分空树、叶子节点、分支节点的不同处理。4.1 二叉链表三种递归遍历的统一框架与终止边界先序、中序、后序遍历仅访问时机不同结构完全一致。关键在Visit位置与递归终止typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 先序遍历根→左→右 void PreOrderTraverse(BiTree T, Status(*Visit)(ElemType)) { if (T) { // 终止条件T为空指针 Visit(T-data); // 访问根 PreOrderTraverse(T-lchild, Visit); // 遍历左子树 PreOrderTraverse(T-rchild, Visit); // 遍历右子树 } // 若T为NULL函数直接返回不执行任何操作 } // 中序遍历左→根→右用于BST排序输出 void InOrderTraverse(BiTree T, Status(*Visit)(ElemType)) { if (T) { InOrderTraverse(T-lchild, Visit); // 左 Visit(T-data); // 根 InOrderTraverse(T-rchild, Visit); // 右 } }血泪经验终止条件绝不能写成if (T-lchild || T-rchild)此条件在叶子节点lchildNULL rchildNULL时为假导致叶子不被访问正确终止是if (T)即只要当前节点非空就执行访问递归Visit函数需独立实现如Status PrintElement(ElemType e) { printf(%d , e); return OK; }。4.2 线索二叉树ltag/rtag 标志位决定指针含义必须显式初始化线索化二叉树用ltag和rtag区分指针是指向孩子还是线索。教材常忽略初始化导致ltag随机值引发段错误typedef enum {Link, Thread} PointerTag; // Link0表示指针Thread1表示线索 typedef struct BiThrNode { ElemType data; struct BiThrNode *lchild, *rchild; PointerTag ltag, rtag; // 左右标志 } BiThrNode, *BiThrTree; // 中序线索化构造带头结点的线索二叉树 Status InOrderThreading(BiThrTree *Thrt, BiThrTree T) { *Thrt (BiThrTree)malloc(sizeof(BiThrNode)); // 头结点 if (!*Thrt) return ERROR; (*Thrt)-ltag Link; (*Thrt)-rtag Thread; (*Thrt)-rchild *Thrt; // 右指针回指头结点 if (!T) { (*Thrt)-lchild *Thrt; // 空树左指针也指头结点 } else { (*Thrt)-lchild T; pre *Thrt; // pre为全局变量记录前驱 InThreading(T); // 中序遍历线索化 pre-rchild *Thrt; // 最后一个节点的后继指向头结点 pre-rtag Thread; (*Thrt)-rchild pre; // 头结点的rchild指向最后一个节点 } return OK; }线索化核心逻辑ltagThread时lchild指向前驱rtagThread时rchild指向后继pre必须是全局或静态变量记录中序遍历中上一个访问节点线索化后InOrderTraverse_Thr可不用递归O(n) 时间遍历空间复杂度 O(1)。4.3 二叉排序树BST插入必须保证中序有序删除需分三类处理BST 插入看似简单但若未检查key重复会导致树结构破坏删除更需分“无孩子”、“一个孩子”、“两个孩子”三类// BST插入若存在相同key不插入保持唯一性 Status InsertBST(BiTree *T, ElemType key) { if (!*T) { // 空树创建新节点 *T (BiTree)malloc(sizeof(BiTNode)); if (!*T) return ERROR; (*T)-data key; (*T)-lchild (*T)-rchild NULL; return OK; } if (key (*T)-data) return ERROR; // 重复key不插入 else if (key (*T)-data) return InsertBST((*T)-lchild, key); else return InsertBST((*T)-rchild, key); } // BST删除返回删除后子树根指针 BiTree DeleteBST(BiTree T, ElemType key) { if (!T) return NULL; if (key T-data) { return Delete(T); // 调用专用删除函数 } else if (key T-data) { T-lchild DeleteBST(T-lchild, key); } else { T-rchild DeleteBST(T-rchild, key); } return T; } BiTree Delete(BiTree p) { BiTree q, s; if (!p-rchild) { // 右子树空用左子树替代 q p; p p-lchild; free(q); } else if (!p-lchild) { // 左子树空用右子树替代 q p; p p-rchild; free(q); } else { // 左右子树均非空取中序前驱左子树最大值替换 q p; s p-lchild; while (s-rchild) { // 找左子树最右节点 q s; s s-rchild; } p-data s-data; // 替换值 if (q ! p) // s不是p的左孩子 q-rchild s-lchild; else q-lchild s-lchild; free(s); } return p; }删除逻辑详解“两个孩子”情况必须用中序前驱左子树最大或中序后继右子树最小教材常只提一种q用于记录s的父节点避免丢失s-lchildif (q ! p)判断s是否为p的直接左孩子决定修改q-rchild还是q-lchild。5. 图邻接矩阵与邻接表的构建差异及 DFS/BFS 的非递归实现图的存储结构选择直接影响算法效率。邻接矩阵适合稠密图边数接近顶点数平方邻接表适合稀疏图边数远小于顶点数平方。DFS 递归易爆栈BFS 队列需手动管理本节给出工业级实现。5.1 邻接矩阵用二维数组存边空间 O(n²)查询 O(1)#define MAX_VERTEX_NUM 20 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点表 EdgeType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum, arcnum; // 顶点数、边数 } MGraph; // 无向图的邻接矩阵构建 Status CreateUDN(MGraph *G) { printf(请输入顶点数和边数: ); scanf(%d%d, G-vexnum, G-arcnum); printf(请输入%d个顶点名: , G-vexnum); for (int i 0; i G-vexnum; i) { scanf( %c, G-vexs[i]); // 注意空格跳过换行符 } // 初始化矩阵为0无边 for (int i 0; i G-vexnum; i) { for (int j 0; j G-vexnum; j) { G-arcs[i][j] 0; } } printf(请输入%d条边格式顶点1 顶点2\n, G-arcnum); for (int k 0; k G-arcnum; k) { char v1, v2; scanf( %c %c, v1, v2); int i LocateVex(*G, v1); int j LocateVex(*G, v2); if (i 0 || j 0) return ERROR; G-arcs[i][j] G-arcs[j][i] 1; // 无向图对称 } return OK; }邻接矩阵关键点arcs[i][j] 1表示vi到vj有边无向图需arcs[j][i] 1初始化必须全0否则残留值干扰LocateVex函数需自行实现遍历vexs[]返回下标。5.2 邻接表用链表存边空间 O(ne)遍历邻接点 O(degree)typedef struct ArcNode { int adjvex; // 该弧指向的顶点位置 struct ArcNode *nextarc; // 指向下一条弧的指针 // InfoType *info; // 若需边权可加此字段 } ArcNode; typedef struct VNode { VertexType data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; int kind; // 图的种类0-无向图1-有向图 } ALGraph; // 无向图邻接表构建 Status CreateALGraph(ALGraph *G) { printf(请输入顶点数和边数: ); scanf(%d%d, G-vexnum, G-arcnum); printf(请输入%d个顶点名: , G-vexnum); for (int i 0; i G-vexnum; i) { scanf( %c, G-vertices[i].data); G-vertices[i].firstarc NULL; // 初始化头指针为空 } printf(请输入%d条边格式顶点1 顶点2\n, G-arcnum); for (int k 0; k G-arcnum; k) { char v1, v2; scanf( %c %c, v1, v2); int i LocateVex_AL(*G, v1); int j LocateVex_AL(*G, v2); if (i 0 || j 0) return ERROR; // 插入v2到v1的邻接表头插法 ArcNode *p (ArcNode*)malloc(sizeof(ArcNode)); p-adjvex j; p-nextarc G-vertices[i].firstarc; G-vertices[i].firstarc p; // 插入v1到v2的邻接表无向图 p (ArcNode*)malloc(sizeof(ArcNode)); p-adjvex i; p-nextarc G-vertices[j].firstarc; G-vertices[j].firstarc p; } return OK; }邻接表构建要点每个顶点的firstarc初始为NULL插入用头插法新节点总在链表头部时间复杂度 O(1)无向图需双向插入有向图只插一次。5.3 DFS 非递归用栈模拟递归调用避免栈溢出递归 DFS 在顶点数 1000 时易栈溢出。改用显式栈#define MAX_STACK_SIZE 100 typedef struct { int data[MAX_STACK_SIZE]; int top; } SeqStack; void InitStack(SeqStack *S) { S-top -1; } int StackEmpty(SeqStack *S) { return S-top -1; } Status Push(SeqStack *S, int e) { if (S-top MAX_STACK_SIZE-1) return ERROR; S-data[S-top] e; return OK; } Status Pop(SeqStack *S, int *e) { if (StackEmpty(S)) return ERROR; *e S-data[S-top--]; return OK; } // 非递归DFS邻接矩阵 void DFS_AM(MGraph G, int v0, void(*Visit)(int)) { int visited[MAX_VERTEX_NUM] {0}; // 初始化访问标记 SeqStack S; InitStack(S); Push(S, v0); visited[v0] 1; Visit(v0); while (!StackEmpty(S)) { int v; Pop(S, v); // 找v的第一个未访问邻接点 for (int w 0; w G.vexnum; w) { if (G.arcs[v][w] !visited[w]) { Visit(w); visited[w] 1; Push(S, w); // 入栈后续处理其邻接点 } } } }非递归DFS逻辑入栈即访问出栈后遍历其所有邻接点for循环中w从0到vexnum-1保证按序访问此实现与递归等价但栈空间可控。6. 避坑指南32个算法实现中高频踩坑点与排查方法写完代码只是开始90% 的失败发生在运行时。以下是我带学生调试 200 份实验报告总结的5 类致命坑每条含现象、原因、解决拒绝模糊描述。6.1 内存相关malloc/realloc 后未判空段错误无声无息现象程序在malloc后某处突然Segmentation faultGDB 显示0x0000000000000000地址访问原因malloc在内存不足时返回NULL但代码直接解引用p-next解决所有malloc/realloc后必须if (!p) return ERROR;并在函数开头定义#define ERROR 0/#define OK 1验证用ulimit -v 100000限制进程虚拟内存至 100MB强制触发malloc失败。6.2 指针野指针释放后未置 NULL二次释放或访问现象free(p)后再次free(p)不报错但后续malloc返回异常地址原因p仍指向已释放内存成为野指针解决free(p); p NULL;且所有指针使用前加if (p)判空工具编译加-fsanitizeaddress运行时报heap-use-after-free。6.3 数组越界下标从 0 还是 1教材与代码的隐式约定冲突现象顺序表插入第 1 个元素成功插入第 2 个时L-elem[1]赋值失败原因教材说“第 i 个位置”代码写L-elem[i] e但i从 1 开始数组应L-elem[i-1]解决统一用i-1访问数组函数注释明确写i from 1自查在ListInsert_Sq开头加printf(insert pos %d, array index %d\n, i, i-1);。6.4 递归失控二叉树遍历未设终止条件无限递归栈溢出现象程序卡死top显示 CPU 100%dmesg有segfault at 0000000000000000原因if (T)写成if (T-lchild)导致叶子节点T非空但lchild为空递归不终止解决所有递归函数第一行必须是if (!T) return;且T为指针类型调试GDB 中break BiTree.c:123递归入口run后bt查看调用栈深度。6.5 单片机移植未替换 malloc裸机环境直接崩溃现象Keil 编译通过烧录后 LED 不亮J-Link 报HardFault原因单片机无 heapmalloc返回NULL后续解引用崩溃解决方案1推荐用静态链表2.3节或预分配数组方案2重定义malloc为static uint8_t pool[1024]; 自定义分配器方案3禁用#include stdlib.h所有内存用static或全局数组验证在InitList_L中加if (!*L) { while(1); }LED 闪烁表示 malloc 失败。7. 验证与进阶用 GDB 单步调试链表插入、用 Valgrind 检查内存泄漏、用 Python 生成测试用例写完代码不能只靠printf看结果。真正的工程能力体现在可验证、可复现、可交付。本章给出三条硬核验证路径每条都附可复制命令。7.1 G本文还有配套的精品资源点击获取