》实战解读：从线性表到算法模板)
简介严蔚敏与吴伟民合著的《数据结构C语言版》是计算机专业经典教材面向本科教学、考研复习及自学入门。全书系统讲解线性表、栈与队列、串、树与二叉树、图、查找与排序等核心内容配合C语言实现代码帮助读者领会抽象数据类型的逻辑结构与存储实现。本次分享的是该书完整PDF文件共一个文件大小约29.15MB排版清晰、内容完整可直接在电脑、平板或手机上阅读。已有4032人学习下载口碑稳定适合需要系统梳理数据结构的读者。从顺序表、链表、栈与队列到树、图从查找排序到典型算法题目均配有细致讲解与示例对于备考期末、考研或求职笔试的读者利用这份PDF可快速定位链表反转、二叉树遍历、最短路径等高频考点对照书中的伪代码和C程序进行反复推演加深对时间复杂度和空间复杂度分析的理解。1. 严蔚敏吴伟民《数据结构(C语言版)》PDF为什么它值得细细啃而不是存了吃灰很多人的网盘里都躺着这本PDF严蔚敏、吴伟民合著的《数据结构(C语言版)》清华大学出版社二十多年重印了不知多少次。它不是速成教程而是把数据结构与算法讲得最克制的教材之一——不堆语法只讲数组、链表、栈、队列、树、图的逻辑结构、存储结构和运算这三件套。对初学者它是把C语言从“会写循环”带向“会设计程序”的摆渡船对考研党它是408和众多院校自命题的事实参考蓝本。这本书的代码是类C伪代码直接复制大概率跑不起来但把伪代码改写成能编译能运行的标准C本身就完成了数据结构的第一个学习闭环。这篇文章就把这条路走一遍顺便把路上的坑提前标出来。2. 把线性表写成能跑的C程序顺序表与链表的最小实现2.1 为什么线性表是整本书的地基严蔚敏把线性表放在第2章是有意的。后面的栈、队列、串本质上都是加了约束的线性表树和图里到处是线性表思维的影子。所以这一章值得死磕代码水平也主要看这一章的功力。书上对顺序表用的是ElemType和Status这类抽象类型纯C里得换成具体类型和int否则编译那关就过不去。我一般先固定三个约定ElemType用intStatus用intmalloc失败返回0。这样后面每一章的代码都能无缝对接。下面这段是能直接编译运行的顺序表我刻意用数组下标代替书上的指针移动逻辑等价但新手更容易在断点里看清每一次搬移。#include stdio.h #include stdlib.h #define INIT_SIZE 100 #define INCREMENT 10 typedef int ElemType; typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 } SqList; int InitList(SqList *L) { L-elem (ElemType *)malloc(INIT_SIZE * sizeof(ElemType)); if (!L-elem) return 0; L-length 0; L-listsize INIT_SIZE; return 1; } int ListInsert(SqList *L, int i, ElemType e) { // 书上的 i 是位序从 1 开始数组下标从 0 开始所以减 1 if (i 1 || i L-length 1) return 0; if (L-length L-listsize) { ElemType *newbase (ElemType *)realloc(L-elem, (L-listsize INCREMENT) * sizeof(ElemType)); if (!newbase) return 0; L-elem newbase; L-listsize INCREMENT; } for (int j L-length - 1; j i - 1; j--) L-elem[j 1] L-elem[j]; // 从尾部开始逐个后移 L-elem[i - 1] e; L-length; return 1; } void PrintList(SqList L) { for (int i 0; i L.length; i) printf(%d , L.elem[i]); printf(\n); } int main(void) { SqList list; if (!InitList(list)) return 1; for (int i 1; i 5; i) ListInsert(list, i, i * 10); PrintList(list); ListInsert(list, 3, 99); PrintList(list); return 0; }这段代码有三个必须理解的参数约定。第一插入位置i是位序允许等于length 1表示在末尾追加如果传成length最后一个元素就会被白白覆盖。第二扩容用realloc它会自动拷贝旧数据并释放旧空间前提是原内存必须由malloc分配。第三循环里的j i - 1是开区间和闭区间的边界写错成j i - 1会把目标位置前的一个元素漏掉这是个很隐蔽的错误单测不一定能查出来。2.2 单链表头插法和尾插法的指针操作链表是很多人第一次接触C语言指针的地方。书上对结点的定义是typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;这里的LinkList本质是struct LNode *的别名定义头结点指针专用。常见的血泪教训是把LNode和LinkList混用在函数参数里一会儿传值一会儿传指针最后编译能过运行直接段错误。下面这段尾插法建表是考研和工程里最常用的写法头结点不存数据让插入和删除逻辑对第一个位置和最后一个位置完全一致。#include stdio.h #include stdlib.h typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; LinkList CreateListTail(int n) { LinkList head (LinkList)malloc(sizeof(LNode)); if (!head) return NULL; head-next NULL; LinkList r head; // r 始终指向尾结点 for (int i 0; i n; i) { LinkList p (LinkList)malloc(sizeof(LNode)); if (!p) return head; scanf(%d, p-data); p-next NULL; // 新结点 next 置空否则会变成野指针 r-next p; r p; // 尾指针后移 } return head; } void PrintList(LinkList L) { LinkList p L-next; while (p) { printf(%d , p-data); p p-next; } putchar(\n); }两个参数细节值得单独记。第一head-next NULL必须一开始就做好很多翻车现场是忘了初始化头结点然后遍历时从随机地址开始读。第二p-next NULL要在挂链之前完成否则新结点带着malloc的随机残留值进链表PrintList的while(p)会一直往下走直到访问非法地址。头插法同理区别只是挂链顺序变成p-next head-next; head-next p;会让链表顺序和输入顺序相反。2.3 顺序表 vs 链表书里没写明的选型边界严蔚敏这章末尾有对比但写得克制。实际选型时下面这张表更直接维度顺序表单链表按位置访问第i个元素O(1)O(n)在已知位置插入/删除O(n) 需要搬移O(1) 只改指针空间分配预分配可能浪费或需扩容按需分配每个结点多一个指针缓存局部性好连续内存差结点分散适用场景读多写少、按下标访问写多读少、长度不确定工程里还有个容易被忽略的点顺序表的realloc扩容有成本频繁插入时反复扩容会让复杂度退化。所以实践中要么预分配足够大的容量要么改用链表。这个选择题书里的抽象描述是“顺序表适合随机访问链表适合频繁增删”到了408填空题里会变成“顺序表按位置访问的时间复杂度是O(1)链表是O(n)”本质是同一件事。3. 栈和队列的C落地从括号匹配到环形数组3.1 顺序栈栈顶指针的两种写法栈是线性表的特例只能在表尾插入和删除。书上的顺序栈用base和top两个指针top指向栈顶元素的下一个位置这个约定直接决定了Push和Pop的写法。很多初学者把top理解为“栈顶元素本身的位置”结果Push时先解引用再移动逻辑就拧了。下面是能直接跑的顺序栈核心函数配合后面的括号匹配用#include stdio.h #include stdlib.h #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int ElemType; typedef struct { ElemType *base; ElemType *top; int stacksize; } SqStack; int InitStack(SqStack *S) { S-base (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!S-base) return 0; S-top S-base; S-stacksize STACK_INIT_SIZE; return 1; } int Push(SqStack *S, ElemType e) { if (S-top - S-base S-stacksize) { // 栈满需要扩容 ElemType *newbase (ElemType *)realloc(S-base, (S-stacksize STACKINCREMENT) * sizeof(ElemType)); if (!newbase) return 0; S-base newbase; S-top S-base S-stacksize; // 重新定位 top S-stacksize STACKINCREMENT; } *S-top e; // 先放元素top 再上移 return 1; } int Pop(SqStack *S, ElemType *e) { if (S-top S-base) return 0; // 空栈 *e *--S-top; // top 先下移再取元素 return 1; }这里有一个所有教材都容易忽略的坑realloc之后top指针必须重新计算。realloc可能把整块内存搬到新地址旧top就成了悬垂指针。书上的代码同样犯了这个隐患因为它默认top跟随base同步更新实际工程里很容易漏写。这也是为什么我建议这类直接抄书上代码前先自己推一遍指针变化。3.2 括号匹配教科书案例在真实代码里的样子括号匹配是书上栈应用的经典第一例也是很多学校实验报告的必选题目。它的思路很简单遇到左括号入栈遇到右括号弹栈并检查配对。下面这个match函数可以直接抄进前面的栈代码里跑int match(const char *s) { SqStack S; InitStack(S); for (int i 0; s[i]; i) { if (s[i] ( || s[i] [ || s[i] {) { Push(S, s[i]); } else if (s[i] ) || s[i] ] || s[i] }) { ElemType top; if (!Pop(S, top)) return 0; // 栈空却遇到右括号 if (!((top ( s[i] )) || (top [ s[i] ]) || (top { s[i] }))) return 0; // 括号类型不匹配 } } return S.top S.base; // 栈空才算完全匹配 }参数细节最后一步return S.top S.base非常关键。如果只是开头设一个flag很容易漏掉“左括号比右括号多”的case比如输入(()循环走完没有遇到任何非法右括号但栈里还留着左括号逻辑上这组括号是不匹配的。用栈顶指针判断收尾一次把所有漏网情况兜住。3.3 循环队列判空判满的约定队列的顺序存储最大的问题是假溢出数组前面空着但rear已经走到末尾。书上的解法是循环队列用取模把数组首尾相接。判空和判满则是整个数据结构里最容易混淆的约定了。#define MAXQSIZE 6 // 实际上最多存放 MAXQSIZE-1 个元素 typedef struct { ElemType *base; int front; // 队头下标指向队头元素 int rear; // 队尾下标指向下一个入队位置 } SqQueue; int InitQueue(SqQueue *Q) { Q-base (ElemType *)malloc(MAXQSIZE * sizeof(ElemType)); if (!Q-base) return 0; Q-front Q-rear 0; return 1; } int EnQueue(SqQueue *Q, ElemType e) { if ((Q-rear 1) % MAXQSIZE Q-front) return 0; // 队满 Q-base[Q-rear] e; Q-rear (Q-rear 1) % MAXQSIZE; // 环形后移 return 1; } int DeQueue(SqQueue *Q, ElemType *e) { if (Q-front Q-rear) return 0; // 队空 *e Q-base[Q-front]; Q-front (Q-front 1) % MAXQSIZE; return 1; }为什么空和满都是front rear却要区分对待因为如果不做任何约定两者判断条件完全相同。书上的做法是牺牲一个存储单元当rear的下一个位置是front时认为队列已满。也就是说数组长度6时最多存5个元素多出来的那个格子是“警戒位”。这是理解循环队列的核心面试时经常被追问“怎么在不牺牲存储单元的情况下判满”方法是用length字段记录元素个数代价是多维护一个变量。3.4 什么时候用链栈书上的栈和队列都给了顺序和链式两种实现。实际选择时顺序栈在已知最大深度、且调用频繁的场景下更快因为连续内存对缓存友好链栈则在深度未知、需要频繁扩容的场景下更稳代价是每个结点多一个next指针。递归转非递归时比如二叉树的中序遍历用顺序栈更方便因为栈深度最多等于树的高度不会出现极端溢出。4. 树和图递归遍历与邻接表存储的接地气写法4.1 二叉树的递归终止条件写对遍历就不玄学树这一章是很多人第一次系统性接触递归。严蔚敏书上先讲二叉树的性质再讲遍历顺序是对的。但教材上的递归代码太简短初学者看着像黑匣子不知道递归为什么能自动结束。关键只有一句话每次递归调用都让子问题规模变小当遇到空指针时就回退。下面这段先序创建先序遍历是一个完整的最小可运行程序也是最常见的实验题模板#include stdio.h #include stdlib.h typedef char TElemType; typedef struct BiTNode { TElemType data; // 数据域 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; void CreateBiTree(BiTree *T) { char ch; scanf( %c, ch); // 前面的空格用于吸收换行和空白 if (ch #) { *T NULL; // # 表示空子树 } else { *T (BiTNode *)malloc(sizeof(BiTNode)); (*T)-data ch; CreateBiTree((*T)-lchild); CreateBiTree((*T)-rchild); } } void PreOrder(BiTree T) { if (T NULL) return; // 空子树是递归出口 printf(%c , T-data); PreOrder(T-lchild); PreOrder(T-rchild); }创建函数里有个让人翻车的细节scanf( %c, ch)必须加空格。因为scanf读字符时不会自动跳过换行符上一次输入后的回车会被当成有效字符读进来导致树的结构莫名其妙少一层。加了前导空格scanf会先跳过所有空白字符再读字符这个习惯在写C语言实验时特别重要。递归的出口是T NULL这一点要和“空树不是树”区分。很多初学者以为递归出口要判T-lchild NULL结果到了叶子结点再深入一层时没有出口直接栈溢出。实际上递归函数在每一层都先检查“我是不是空指针”是就返回不是就处理当前结点再钻进子树。每个结点被访问三次先序在第一次进入时打印中序和后续分别在第2、3次打印这个“三次路过”的理解比死记口诀有效得多。4.2 带空标记的先序序列建树上一节的CreateBiTree做了一件教材里不会明说的事用#补全所有空子树。为什么需要补全因为只给一个先序序列ABC无法确定这是“A的左孩子是BB的左孩子是C”还是“A的右孩子是BB的左孩子是C”。补上#后每个结点的左右孩子都被显式标注树的结构就唯一确定了。比如输入序列AB#C##D##对应的树是A的左孩子BB的右孩子CA的右孩子D。这里输入时字符之间不能有换行否则会被scanf的空格跳过规则搅乱。想要直观可以自己画一棵三层的树写出它的先序空标记序列再跑一次程序看到打印结果和原树一致递归就算真的理解了。4.3 图的邻接表头插法建图与遍历顺序的关系图这一章书上的代码量突然变大因为图的存储结构比树复杂。实操时邻接表是使用率最高的存储方式但建表代码里有几个和链表完全相同的坑比如头插法会让边表逆序。下面是有向图的邻接表建表代码骨架#define MAX_VERTEX_NUM 20 typedef struct ArcNode { int adjvex; // 该弧指向的顶点位置 struct ArcNode *nextarc; // 下一条弧 } ArcNode; typedef struct VNode { char data; // 顶点信息 ArcNode *firstarc; // 第一条弧 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; void CreateDG(ALGraph *G) { scanf(%d %d, G-vexnum, G-arcnum); for (int i 0; i G-vexnum; i) { scanf( %c, G-vertices[i].data); G-vertices[i].firstarc NULL; } for (int k 0; k G-arcnum; k) { int v1, v2; scanf(%d %d, v1, v2); // 顶点编号从 1 开始 ArcNode *p (ArcNode *)malloc(sizeof(ArcNode)); p-adjvex v2; p-nextarc G-vertices[v1].firstarc; // 头插法 G-vertices[v1].firstarc p; } } int visited[MAX_VERTEX_NUM]; void DFS(ALGraph *G, int v) { visited[v] 1; printf(%c , G-vertices[v].data); for (ArcNode *p G-vertices[v].firstarc; p; p p-nextarc) { if (!visited[p-adjvex]) DFS(G, p-adjvex); } }这里有一个容易踩坑的点头插法导致邻接表里的边顺序和输入顺序完全相反。如果输入1 2再输入1 3顶点1的邻接表里第一个结点是3第二个是2。做BFS或DFS时输出的遍历序列会和用邻接矩阵的结果不同但两种都属于合法遍历顺序。考试和实验报告里如果要求“按输入顺序输出遍历结果”就得把头插法改成尾插法或者建表时给顶点编号倒序。dfs递归里的visited数组是必须的否则无向图和有环图会死循环。很多人在二叉树上用递归用习惯了到图上直接套忘记图可能有环结果程序直接栈溢出。把visited[v] 1放在递归入口而不是放在循环里能保证每个顶点只处理一次。5. 严蔚敏版代码避坑5个让初学者翻车的细节5.1 引用参数在纯C编译器里直接报错现象把书上的ListInsert(L, i, e)原样敲进gcc编译直接报语法错误错误定位在附近。原因书上的函数形参大量使用int x这是C的引用语法ANSI C不支持。严蔚敏这本书的代码风格其实是“类C”介于C和C之间。解决把形参改成指针调用处传地址函数内部用*解引用。比如ListInsert(SqList *L, int i, ElemType e)函数体内一律用L-elem访问。这个转换没什么技术含量但能强制你弄清“值传递”和“地址传递”的区别反而是好事。5.2 位序从1开始数组下标从0开始现象向顺序表第5个位置插入元素结果发现第4个位置的元素被覆盖或者插入后打印出来的顺序不对。原因书上的i是位序从1数起数组下标从0数起。插入位置和数组操作之间差着一个1少算一个就错位。解决凡是和数组打的交道一律写成L-elem[i - 1]。这个转换要在心里默念三遍。更稳妥的做法是写一个小的调试宏打印插入前和插入后的全部元素跑一个插入用例亲眼看一下位移过程比背一百遍概念都管用。5.3 malloc返回类型与内存泄漏现象在C编译器里编译malloc返回的void*不能隐式转换成ElemType*报错在纯C里不报错但运行一段时间后内存占用持续上涨。原因malloc返回void*C要求强制转换纯C里虽然能隐式转换但很多人写了(ElemType*)malloc(...)却没配对的free链表结点、树结点、图结点一路malloc到底从不释放。解决统一写成(ElemType *)malloc(sizeof(ElemType))同时记住谁malloc谁free。严蔚敏书上几乎所有代码都忽略free因为教材要展示逻辑但工程实践里不释放就是内存泄漏。做实验时可以用valgrind检查有泄漏会直接标出来。5.4 链表尾插忘记置空next现象建立链表后用while(p)遍历打印程序要么停不下来一直打印乱码要么打印到中途直接段错误。原因新结点是malloc出来的next字段带着随机值。如果没有p-next NULL最后一个结点的next指向未知地址循环把野指针当成合法链表继续走直到访问到非法内存。解决每次创建结点后立即p-next NULL再执行挂链操作。这个顺序不能反。检查方法也很简单打印链表前先打一行“第一个结点地址”和“最后一个结点地址”看尾结点的next是否为NULL一眼就能定位。5.5 快速排序选第一个元素当基准现象对一个已经有序的数组执行快速排序耗时比冒泡排序还离谱递归深度大到栈溢出。原因快速排序选第一个元素当基准如果数组本来就有序每次分区极度不平衡一边空一边全量递归树退化成一条链时间复杂度从O(nlogn)退化到O(n²)。解决工程上选基准要随机化或者用三数取中。考研手写快排时书上教的“以第一个元素为基准”没问题因为考试的数组规模小但真实场景里这种退化是必须避免的。如果发现快排在接近有序的数据上性能骤降先怀疑轴点选择。6. 把这本书读薄三要素笔记法、复杂度速查表与一套必背代码模板6.1 用“逻辑结构-存储结构-运算”拆每一章我读这本书最有效的做法是每一章都画一张三列表格这章的数据结构逻辑结构是什么存储结构有哪几种基本运算有哪些。以树为例逻辑结构是一对多的层次结构存储结构有双亲表示法、孩子表示法、孩子兄弟表示法三种运算主要是遍历和查找。这个框架和王道408的总结方式完全一致先搭骨架再填细节比从头到尾抄笔记扎实得多。6.2 复杂度速查看到排序就条件反射排序这一章内容最多但考试和面试最终落在复杂度对比上。高频结论插入排序和冒泡排序是O(n²)归并排序稳定且最坏O(nlogn)堆排序和快速排序平均O(nlogn)二路归并需要O(n)辅助空间。表就一张背下来比反复看代码高效。6.3 必背代码模板快速排序快速排序是我建议每个人都默写一遍的算法十几行做完这件事分治和递归的体感会立刻上一个台阶void QuickSort(int a[], int low, int high) { if (low high) return; int i low, j high, pivot a[low]; while (i j) { while (i j a[j] pivot) j--; a[i] a[j]; while (i j a[i] pivot) i; a[j] a[i]; } a[i] pivot; QuickSort(a, low, i - 1); QuickSort(a, i 1, high); }记忆的时候只用记一句话挖坑填数。先存下基准然后从右往左找比基准小的填到左边从左往右找比基准大的填到右边最后把基准放进ij的坑里。我当年在这本PDF上最大的教训就是光看不敲看着看着以为自己会了真到实验课上代码一个字都写不出来。后来改成每天手写一个排序坚持了两周数据结构的后劲才真正长在身上。这本书适合反复读每次读都会有新东西希望帮到你。本文还有配套的精品资源点击获取
