简介数据结构与算法基础青岛大学-王卓是一套系统讲解数据结构与算法核心内容的配套学习资源覆盖绪论、线性表、栈和队列、串与数组、树和二叉树、图、查找、排序共8章适合高校学生及初入职场软件工程师自学巩固。压缩包共80个文件大小8.16MB包含43张原理示意图、24个C示例程序、9个Markdown章节笔记、2个说明文档及2个头文件图文与代码结合便于理解抽象概念。资源中配有各章节的习题解答与算法设计练习代码如Chapter3Exe、Chapter5Exe等二叉树遍历、平衡调整、哈希查找、经典排序等内容均有示意图辅助说明可帮助读者从逻辑结构、存储实现到算法复杂度分析形成完整知识链。已有115人学习使用对于希望系统建立数据结构与算法基础、备考或准备机试的人群是一份轻量且实用的学习材料。1. 王卓版数据结构资源包一份以图和代码为主的自学配套材料如果你正在准备408考研或数据结构期末考手头又有青岛大学王卓老师的《数据结构与算法基础》视频那这个zip大概率是你在网盘里见过但没拆开的配套资源。它不包含讲课视频却把课程里最容易画错的图全部整理成了PNGAVL树的LL/RR/LR/RL调整前后对比、线索二叉树、散列表查找流程图外加Chapter3Exe和Chapter5Exe里的十几份算法设计C源码。一句话概括这是把“听懂”变成“看图能复述、看码能运行”的辅助材料。适合期末考本科生、408考研复习者以及想快速补数据结构短板的初级工程师。下文按第2章到第8章的知识顺序拆解最后给出在Windows下的编译验证方法。2. 线性表与栈队列顺序表选型边界、双栈设计以及两段可直接编译的C代码这一章从资源包的第二章、第三章里挑出三个关键图形和代码文件顺序表和链表的比较、栈的应用、双栈结构。它们是整个数据结构课程里第一个分水岭搞不清“什么时候用链表什么时候用数组”后面树和图的所有存储选择都会跟着出错。2.1 顺序表和链表的比较图几个容易忽略的决策点资源包里Chapter2 LinearList目录下有一张“顺序表和链表的比较.png”以及一张“单链表、循环链表和双向链表的时间效率比较.png”。很多初学者把这两张图当概念背诵但真正做课程设计或笔试面试时选型判断经常是反过来的。我先给一张对比表再把图上没写透的边界条件讲清楚。维度顺序表链表随机访问第k个元素O(1)O(n)已知位置插入/删除O(n)需要搬移元素O(1)只需改指针存储空间预分配扩容时整体搬移按需分配每个结点多存一个指针缓存局部性连续内存遍历快结点分散缓存命中率低这里有一个容易翻车的点链表“插入O(1)”是有前提的前提是已经找到了插入位置。如果要从头查找第i个结点再插入那总代价仍然是O(n)只是查找和插入各占一段而已。顺序表的插入删除看起来也是O(n)但实际操作上表尾插入是O(1)表头插入才是O(n)所以工程里“尾部频繁追加”的场景顺序表一点不虚。再看循环链表和双向链表。循环链表的尾结点next指针不再指向NULL而是指向头结点这让“从尾部回到头部”变成O(1)操作适合环形队列、约瑟夫环这类场景。双向链表每个结点多一个prior指针删除指定结点时不需要从头找前驱但代价是插入/删除时要维护四个指针而不是两个。资源里的时间效率对比图把这三类链表的查找、插入、删除列得很清楚我建议把这几个数字抄在笔记首页单链表找前驱O(n)双链表O(1)循环链表遍历整表仍O(n)。选型结论可以浓缩成三句话读多写少且表长稳定用顺序表写多读少且表长不确定用链表需要倒序遍历或频繁删除指定结点优先考虑双向链表。这些结论不是背出来的是在课程设计里改过两版代码才会真的记住。2.2 栈的经典应用进制转换与括号匹配的C实现Chapter3 StackAndQueue目录里有“栈的操作.png”“进制转换.png”“括号匹配.png”三张图Chapter3Exe目录里则有一组AlgoDesignExe*.cpp和AlgoDesignStack.h/.cpp。我建议学习顺序是先看“栈的操作.png”理解入栈出栈的指针变化再读源码最后自己敲一遍。下面这段是我从课程配套代码里提炼出的顺序栈头文件去掉了与核心逻辑无关的细节。// AlgoDesignStack.h - 顺序栈的简化定义 #ifndef ALGO_DESIGN_STACK_H #define ALGO_DESIGN_STACK_H #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; // 栈的存储区 int top; // 栈顶下标-1 表示空栈 } SeqStack; void InitStack(SeqStack S); // 初始化top 置为 -1 bool Push(SeqStack S, int x); // 入栈top 先加 1 再存数据 bool Pop(SeqStack S, int x); // 出栈先取数据 top 再减 1 bool IsEmpty(SeqStack S); // 判空top -1 #endif这个头文件的关键设计是top的初始值。top取-1表示空栈入栈时先自增再写入出栈时先读取再自减。如果初始化时把top置为0那判空条件就要相应改成top 0逻辑上也能成立但两种写法不能混用。我见过不少初学同学把网课的代码抄混栈一会是top-1一会是top0调试半天才发现是初始值不一致。基于这个栈进制转换是最直观的应用。十进制数不断除以进制数取余数余数先算出来的是低位最后算出来的是高位正好和栈的后进先出特性相反——或者说栈天然适合把“先得到的低位”压到栈底最后弹出来变成高位。// 十进制转二进制利用栈逆序输出余数 #include cstdio #include AlgoDesignStack.h void DecimalToBinary(int n) { SeqStack S; InitStack(S); if (n 0) { printf(0\n); return; } while (n 0) { Push(S, n % 2); // 余数 0 或 1 入栈 n n / 2; // 缩小规模直到 0 } while (!IsEmpty(S)) { int bit; Pop(S, bit); // 后进先出最后的高位先弹出 printf(%d, bit); } printf(\n); }这个函数的时间复杂度是O(log n)因为循环次数等于二进制位数。注意n0这个边界如果不加if判断while(n 0)不会进入结果什么也不输出看起来像程序死掉。这是所有进制转换代码都容易漏的边界。括号匹配是栈的另一个经典应用也是Chapter3Exe里AlgoDesignExe系列的常见题目。规则很简单遇到左括号入栈遇到右括号弹出栈顶检查类型是否匹配。最容易出错的是“栈空时遇到右括号”和“全部扫描完栈里还有左括号”两种场景。// 括号匹配判定支持 () [] {} 三种括号 #include cstdio #include AlgoDesignStack.h bool IsBracketMatch(const char *expr) { SeqStack S; InitStack(S); for (int i 0; expr[i] ! \0; i) { char c expr[i]; if (c ( || c [ || c {) { Push(S, c); // 左括号直接入栈 } else if (c ) || c ] || c }) { if (IsEmpty(S)) { // 右括号来了栈却是空的 return false; // 说明右括号多余 } int topChar; Pop(S, topChar); if ((c ) topChar ! () || (c ] topChar ! [) || (c } topChar ! {)) { return false; // 类型不匹配 } } } return IsEmpty(S); // 结束后栈里还有左括号则失败 }这里Push和Pop接收的是int型参数字符类型会自动转为ASCII码所以存(和存40在栈层面没有区别。判断匹配时比较的是topChar和当前字符c是否属于同一对括号。我遇到过最隐蔽的错误是字符串里有中文字符的括号“”它和ASCII括号长得几乎一样但编码完全不同程序当然判不匹配。这类问题在调试时很难发现建议先检查输入编码。提示Chapter3Exe目录下的AlgoDesignExe*.cpp是相互独立的小程序大部分文件自带main函数。如果编译器提示重复定义main请只编译其中一个Exe文件不要把所有Exe文件一起放进g命令行。2.3 双栈结构一个数组从两端向中间生长Chapter3 StackAndQueue目录里有一张“双栈结构的表示.png”画的是两个栈共享同一段连续内存的布局栈1从数组下标0向右生长栈2从数组最大下标向左生长。这种结构在程序里很实用比如一个表达式求值器中需要同时维护操作数栈和运算符栈两个栈的数据总量有上限但各自波动很大用双栈共享数组就能避免“栈1溢出但栈2还很空”的浪费。双栈的核心判断条件是栈顶指针的关系。假设数组下标从0到MAX_SIZE-1top1初始为-1top2初始为MAX_SIZE。栈1入栈时top1栈2入栈时top2--。栈满的条件是top1 1 top2也就是两个栈顶挨在一起数组中间没有剩余空间。这种设计下两个栈都不会出现“明明整体还有空间但单个栈已满”的假满现象。// 双栈共享数组的入栈操作 #define MAX_SIZE 100 int dualStack[MAX_SIZE]; int top1 -1; // 左栈栈顶 int top2 MAX_SIZE; // 右栈栈顶 bool DualPush(int stackNo, int x) { if (top1 1 top2) { return false; // 两个栈中间没有空位整体满 } if (stackNo 1) { dualStack[top1] x; } else if (stackNo 2) { dualStack[--top2] x; } else { return false; // 非法栈编号 } return true; }这段代码里最容易被忽略的是DualPush的失败处理。如果考试或面试里写双栈最好先声明“返回bool表示是否成功”而不是用“如果满了就覆盖”的写法。实际使用时还要配合一个判断stackNo1时要求top11top2stackNo2时同样要求top11top2两个方向共用同一个满条件写起来非常对称。配合旁边的“栈的操作.png”一起看把入栈出栈的指针移动方向画一遍比背十遍结论都管用。3. 树和二叉树五种形态、三种遍历与线索化用图把递归看清楚树这一章是很多人从“线性思维”切换到“递归思维”的转折点。资源里的Chapter5目录下图片最密集从树和线性结构的比较一直画到线索二叉树说明这些概念几乎没有能凭直觉猜对的地方必须靠图辅助推导。3.1 二叉树的五种基本形态递归定义的图形化表达资源里Chapter5 TreeAndBianryTree目录下有两张图“二叉树的五种形态.png”和“二叉树的五种基本形态.png”内容完全一致但文件重复了可能是课程打包时的冗余。这一点倒是顺手提醒了使用者这份资料是教学过程中积累的不是出版社精编教材文件名和章节号有重复是正常的不影响使用。二叉树的第一条性质是“递归定义”二叉树要么是空树要么由根结点、左子树和右子树组成而左子树和右子树本身又各是一棵二叉树。基于这个定义任何一棵非空二叉树都可以归入五种基本形态之一空树、只有根结点、只有左子树、只有右子树、左右子树都有。空树是最容易被忽略的一种很多同学画图时默认二叉树至少有一个结点结果在递归程序里空指针判断漏掉直接解引用空指针崩溃。这五种形态的价值在于它们是递归程序的终止条件和分支条件。写先序遍历时第一个if判断就是“结点是否为空”为空直接返回这对应空树形态接着访问根对应只有根结点的形态再递归遍历左子树和右子树对应剩余三种有子树的形态。所以把这张图理解成“递归分支图”而不是“形状分类图”看代码时会更顺。资源里还有一张“树结构和线性结构的比较.png”对比的是线性表与树的区别线性结构里每个结点最多只有一个直接前驱和一个直接后继树结构里每个结点可以有多个孩子但只有一个双亲。这个“一对多”的性质直接决定了树的存储设计——每个结点都得考虑怎么存孩子关系这就引出了双亲表示法、孩子表示法和孩子兄弟表示法。3.2 三种遍历方法先序、中序、后序的递归展开“遍历方法区别.png”这张图把先序、中序、后序印在同一棵树上直观展示了三种顺序的差异。先序遍历是“根-左-右”中序遍历是“左-根-右”后序遍历是“左-右-根”。以一棵小树为例假设根是AA的左孩子是BB有左孩子D、右孩子EA的右孩子是CC有左孩子F、右孩子G。那三种遍历结果是先序A B D E C F G中序D B E A F C G后序D E B F G C A我学的时候有个血泪经验光靠口诀“根左右、左根右、左右根”只能应付简单树一旦树深超过三层就会绕晕。正确做法是直接画递归展开过程——每到一个结点先决定要不要访问根再决定往左还是往右跳。下面是递归遍历的标准写法。// 二叉链表结点定义 struct BiTNode { int data; BiTNode *lchild, *rchild; }; // 中序遍历左-根-右 void InOrder(BiTNode *root) { if (root NULL) return; // 空树或空子树直接返回 InOrder(root-lchild); // 先递归整棵左子树 printf(%d , root-data); // 再访问根结点 InOrder(root-rchild); // 最后递归整棵右子树 }三种遍历的代码只有printf那一行的位置不同但效果差别很大。先序适合复制一棵二叉树因为先创建根结点再递归创建左右子树结构自然成立中序在二叉搜索树里会输出有序序列这是“BST中序有序”结论的来源后序适合释放整棵树因为先释放子树再释放根不会出现释放根之后还去访问子树的悬空指针。这三种应用场景是在写二叉树代码时最常用的三个判断依据。遍历序列还有一个高频笔试结论给定先序序列和中序序列可以唯一确定一棵二叉树给定后序和中序同样可以但只给先序和后序不行。原因是先序和后序都能确定根但无法区分左子树和右子树的分界线分界线必须靠中序序列提供。3.3 线索二叉树用空链域存前驱和后继资源里的“先序线索二叉树.png”和“后序线索二叉树.png”画的是线索化后的链式结构。线索二叉树的出发点是一个反直觉的事实n个结点的二叉链表里共有2n个指针域真正用来指向孩子的只有n-1个不含根的那条边所以有n1个指针域是空的。这些空指针闲着浪费不如用来指向遍历序列里的前驱和后继。中序线索二叉树是最常用的。一个结点的lchild如果原本为空就改为指向中序序列的前驱rchild如果原本为空就改为指向中序序列的后继。为了区分“指针指向孩子”还是“指针指向线索”每个结点要增加两个标志位ltag和rtag0表示孩子指针1表示线索。// 中序线索二叉树的结点定义 struct ThreadNode { int data; ThreadNode *lchild, *rchild; int ltag, rtag; // 0 孩子指针1 线索 }; // 查找中序线索二叉树中某结点的后继 ThreadNode* NextInOrder(ThreadNode *p) { if (p-rtag 1) { return p-rchild; // rchild 直接存的是后继线索 } // rtag 0p 有右孩子后继是右子树最左下结点 ThreadNode *q p-rchild; while (q ! NULL q-ltag 0) { q q-lchild; } return q; }这段代码里的NextInOrder是线索二叉树最核心的查询操作。rtag为1时rchild指向的就是后继一步到位rtag为0时p有右子树中序后继是右子树里最左下角的结点。这个“找最左下”的逻辑是理解线索二叉树的关键——线索只加速了空指针的利用非空的孩子关系仍然靠原有的二叉树结构。教材里会说线索化能够把中序遍历从递归O(n)栈空间降到O(1)辅助空间但实际工程里用得不多因为它牺牲了两个标志位。真正值得掌握的是“空指针利用”这个思想当你发现一个结构里有大量闲置字段时可以像线索二叉树一样把它们改造为辅助信息这在嵌入式场景的链表设计里很常见。3.4 树的存储表示双亲表示法的空间账“树的双亲表示法.png”画的是一个数组每个元素存结点的数据和孩子的parent下标。用双亲表示法存储一棵树时查找任意结点的父节点是O(1)的因为只取parent字段但要查找某结点的所有孩子就得遍历整个数组逐个判断parent是否等于该结点下标复杂度O(n)。这和邻接矩阵“判断存在性快、枚举邻居慢”的性质恰好相反。资源里还有一张“树结构和线性结构的比较.png”讲到树的存储时也可以带孩子表示法一起对比孩子表示法把每个结点的孩子串成链表查找孩子快但查找父节点慢双亲表示法反过来孩子兄弟表示法用“第一孩子下一兄弟”两个指针把任意树转成二叉树形式方便复用二叉树的遍历算法。这三者的适用场景不同笔试里常见的问题是“给一个操作需求选最合适的存储表示”。判断依据就一句话频繁查父亲用双亲表示法频繁查孩子用孩子表示法需要统一树和二叉树处理用孩子兄弟表示法。4. 图与查找邻接表选型、AVL四种旋向判断、散列查找完整链路图论和查找放在一起讲是因为这两个主题的共有特点是“存储结构决定算法难度”。资源里的Chapter6只有一张存储结构分析图Chapter7却堆了十几张AVL调整和散列查找的图——找一张对的图比看十遍文字定义更能解决旋转方向这种细节。4.1 图的存储结构分析邻接矩阵与邻接表的各自适用面Chapter6 Graph目录下的“图的存储结构分析.png”把邻接矩阵和邻接表放在同一张图里对比。邻接矩阵用n×n的二维数组存储顶点间的边关系判断两个顶点是否相邻只需O(1)访问matrix[i][j]但空间固定是O(n^2)。邻接表把每个顶点的邻接点串成链表存储空间是O(ne)n个顶点带头结点、e条边对应e个边结点空间效率在稀疏图里远优于矩阵。“图的存储结构分析”这张图里其实还有一层容易被忽略的含义邻接矩阵适合稠密图邻接表适合稀疏图选择依据是e和n^2的数量关系。判断一个图是“稀疏”还是“稠密”一般可以看e是否远小于n^2。工程里常见的是稀疏图比如社交网络的好友关系、地图的路网e和n大致同数量级用邻接表是默认选择。但如果图特别小比如顶点数不超过50邻接矩阵的简单性和随机访问优势更明显。邻接矩阵和邻接表在“找某个顶点的全部邻接点”上也有差别。邻接矩阵需要扫描一整行O(n)邻接表直接沿着链表走O(该顶点度)。这个差异在DFS/BFS、拓扑排序的实现里会直接变成性能瓶颈。另外网图带权图的存储只是把边表元素从“存在标记”换成“权值”判断标准不变。4.2 AVL平衡调整四种类型LL、RR、LR、RL的旋向判断Chapter7 Search目录下存放了大量AVL调整的图片图6到图13覆盖LL、RR、LR、RL四种失衡类型的前后状态对比。这块内容是查找章节里最能拉开分差的知识点也是初学者最容易画反旋转方向的地方。先把四种失衡的类型判断讲清楚。失衡判断的步骤是固定的插入新结点后从插入位置向上找第一个平衡因子绝对值大于1的结点把它当作失衡结点然后看新结点在失衡结点的哪一侧、以及在这一侧子树的哪一侧。如果新结点在失衡结点左孩子的左子树就是LL型在左孩子的右子树就是LR型在右孩子的右子树就是RR型在右孩子的左子树就是RL型。调整口诀也很对称LL右旋、RR左旋、LR先左后右、RL先右后左。口诀好背但真正画图时容易绕我建议把四种类型记成“插入位置决定的旋转序列”。失衡类型新结点位置调整操作LL失衡结点左孩子的左子树失衡结点右旋一次RR失衡结点右孩子的右子树失衡结点左旋一次LR失衡结点左孩子的右子树先对左孩子左旋再对失衡结点右旋RL失衡结点右孩子的左子树先对右孩子右旋再对失衡结点左旋资源里的LL型和RR型各配了三张图调整前状态、调整后结果、前后对比示意图。跟着图走一遍会发现LL型右旋的本质是“把失衡结点的左孩子提上来当新根失衡结点降为右孩子”RR型左旋则是镜像对称把右孩子提上来当新根。LR型和RL型都要旋转两次第一次先把“孙子”转成“儿子”的形态第二次才完成平衡。下面以RR型为例写一段左旋代码这是四类里最典型的一类单旋。// AVL树结点定义 struct AVLNode { int data; int height; // 以该结点为根的高度 AVLNode *left, *right; }; // RR型对失衡结点 root 做左旋 AVLNode* LeftRotate(AVLNode *root) { AVLNode *newRoot root-right; // 右孩子成为新根 root-right newRoot-left; // 新根的左子树过继给原根 newRoot-left root; // 原根降为左孩子 // 重新计算高度必须先更新原根再更新新根 root-height max(Height(root-left), Height(root-right)) 1; newRoot-height max(Height(newRoot-left), Height(newRoot-right)) 1; return newRoot; // 返回新子树根 }这段代码里有两个细节值得注意。第一root-right newRoot-left这一步必须在newRoot-left root之前执行否则会把新根的左子树弄丢。第二高度更新必须先更新原根再更新新根因为新根的高度依赖原根的新高度。这个顺序问题我在科目代码里踩过坑先更新newRoot再更新root算出来高度差一插入第三个结点后又失衡排查了半天。LR型和RL型的双旋实现就是“先旋转孩子再旋转失衡结点”的两次拼接。以LR型为例先对失衡结点的左孩子做左旋让平衡因子挂到外侧结构变成LL型再对整个失衡结点做右旋。代码上调用两次旋转函数就行但这里有一个常见误区——两次旋转的返回值要接回原位置很多同学的代码把第一次旋转的返回值丢掉了。4.3 散列查找ASL定义与查找流程图的完整链路Chapter7 Search目录下有“图1平均查找长度定义.png”“图2查找效率.png”“图3查找方法比较.png”和“图14散列表查找流程图.png”。散列表的查找流程和二分查找完全不同二分查找每次比较后大概率缩小一半范围散列则是“一次定位冲突处理”。平均查找长度ASL的定义是Σ(比较次数×概率)散列表的ASL只和装填因子α有关α表中记录数/表容量。α越大冲突概率越高ASL越大。把“图14散列表查找流程图.png”翻译成文字流程是这样的第一步计算hash(key)得到初始位置第二步检查该位置是否为空为空说明记录不存在查找失败如果不为空比较key值相等就查找成功不相等则按冲突处理方法线性探测、平方探测、链地址法计算下一个位置回到第二步继续直到遇到空位置或者绕回起始位置此时判定失败。散列表最常考的冲突处理对比是开放定址法和链地址法。开放定址法所有记录都存在表内ASL和删除操作要特别小心链地址法把同义词挂成链表装填因子可以大于1查找时先在表头定位再链表内查找。资源里的流程图是按开放定址法画的线性探测找下一个位置就是下标加1后对表长取模。这个取模运算容易被忽略导致数组越界。4.4 查找方法比较顺序、二分、散列的适用边界Chapter7里的“图3查找方法比较.png”把三种典型查找的效率放在同一张图里。顺序查找适合无序表平均查找长度O(n)实现最简单二分查找要求顺序表且关键字有序单次查找O(logn)但插入删除要维护有序性代价很高散列查找平均接近O(1)但需要额外空间、处理冲突删除还要注意标记。实际做题时把一个“频繁插入偶尔查询”的需求套进二分查找答案大概率是错的因为每次插入都要搬移元素。这类题考的是“查找算法和数据结构的匹配边界”而不是单纯背ASL公式。资源里那张比较图建议自己重新画一遍把“是否要求有序、能否链式存储、插入删除代价”三列补上比盯着图看半小时有效。5. 排序算法与避坑排查八种排序的复杂度对照和四个容易翻车的现场记录排序是考研408和面试里出镜率最高的主题也是背了又忘的重灾区。资源里的Chapter8把八种排序分成了四类再用三张图做对比正好适合按“先分类、再对比、后填坑”的顺序来掌握。5.1 排序方法的分类与比较图01到图03的信息量Chapter8 Sorting目录下有三张图图01排序方法的分类、图02主要学习内容、图03排序方法比较。八种排序按策略可以分为四类插入类包含直接插入和希尔排序交换类包含冒泡和快速排序选择类包含简单选择和堆排序外加归并排序。这张分类图的价值在于它说明排序算法不是孤立的知识点而是“插入、交换、选择、归并”四种基本策略的变体。排序算法最需要记牢的是稳定性和时间复杂度这是笔试和面试里最高频的考点。先把结论给全直接插入、冒泡、归并是稳定的希尔、快排、简单选择、堆不稳定。时间复杂度的关键数据是直接插入最好O(n)最坏O(n^2)冒泡最好O(n)最坏O(n^2)快排平均O(nlogn)最坏O(n^2)堆和归并稳定在O(nlogn)简单选择稳定O(n^2)但比较次数不随数据有序性变化。堆排序和简单选择的比较次数不随初始有序性变化这一点是初学者的认知盲区。堆排序无论输入是否有序都要经历建堆和n-1次堆调整简单选择每趟都要扫描未排序区间找最小值也不受有序性影响。反过来直接插入和冒泡在输入基本有序时能提前结束或减少移动这类“最好情况表现好”的算法适合近乎有序的数据。快排比较特殊平均情况最好但最坏情况退化到O(n^2)退化原因是枢轴选得不好。5.2 四个高频坑现象、原因、解决第一个坑是快速排序在“数组已经有序”时递归深度爆掉。现象对一个升序数组跑快排程序运行特别慢数据量大时栈溢出。原因很多教材默认选第一个元素当枢轴数组实际已有序时每次划分都有一边为空递归深度变成n而不是logn。解决枢轴不要固定取第一个改成三数取中首、中、尾三个元素取中位数或者随机选一个位置和第一个交换再继续常规划分。第二个坑是堆排序在交换堆顶和末尾元素后忘记缩小堆范围。现象排序结果部分正确前半段有序后半段混乱。原因执行“堆顶和末尾交换”后正确做法是把参与调整的堆大小减1让已排序的末尾元素不再参与下调有些实现漏掉这一步把刚归位的元素又调回堆里。解决用一个变量heapSize记录当前堆长度交换后heapSize减1所有下沉操作只在[0, heapSize)范围内进行。第三个坑是归并排序的空间复杂度记混。现象面试被问“归并排序的空间复杂度”回答了O(1)被面试官追问后才发现错了。原因标准二路归并需要一个和原数组等长的辅助数组用来暂存合并结果空间复杂度是O(n)。原地归并虽然存在但实现复杂度远高于标准写法不是教材默认方案。解决默认答案写O(n)如果提到原地归并要能解释它通过交换元素实现合并但仍需要用额外空间做旋转或缓存不能做到严格的O(1)辅助空间。第四个坑是散列表开放定址法删除记录后查找失败。现象删掉一个冲突链上的记录后原本能查到的另一个记录突然查不到了。原因开放定址法的探测序列依赖表中已有记录的位置直接删除会把探测链截断后面本应经过该位置的查找路径提前遇到空槽误判为不存在。解决删除时在槽位上做标记比如置为“已删除”状态查找时遇到已删除标记继续探测而不是返回失败只有遇到真正的空槽才停止。这个坑在链地址法里不存在链地址法删除就是普通的链表删除。5.3 配合资源的章节使用顺序这份资料的阅读顺序建议按课程原章节走Chapter2线性表、Chapter3栈和队列、Chapter4串和数组、Chapter5树、Chapter6图、Chapter7查找、Chapter8排序。每章先看README.md了解这一章的脉络再盯住该章的PNG图理解结构最后打开对应Exe目录的C源码做验证。Chapter5Exe和Chapter3Exe是代码密集区大部分文件是算法设计练习题建议每道题都自己重写一遍再对照。串章节里的next[j].png讲的是KMP算法的next数组推导这章在考研里出题频率高也是最容易看“懂”但写不对的章节。我的做法是把next数组的递推过程完全手动推一遍长度为8以上的模式串再用代码验证。查找章节里的散列流程图和AVL调整图是同一类难点都需要“看图→手画→写码验证”三步走。6. 把Chapter3Exe的代码在Windows下跑起来从g编译到括号匹配验证资源包面向Windows用户里面放的是cpp源码不能双击运行需要先确认机器上有g。在命令行输入g --version能输出版本号说明环境就绪。如果没有需要先安装MinGW-w64安装时把bin目录加入系统PATH装完重新打开命令行再试。以括号匹配为例把AlgoDesignStack.h、AlgoDesignStack.cpp和某个包含main函数的Exe文件放在同一目录执行下面的命令编译再运行。如果文件里使用了非标准语法或者include路径用了相对引用编译会报错需要按提示修正。g -o bracket AlgoDesignStack.cpp AlgoDesignExe3.cpp ./bracket运行后输入{(ab)*[c-d]}程序应该输出匹配再输入{(ab)*[c-d}少一个右括号应该输出不匹配。如果第一次编译就报错先看是不是头文件路径问题——g默认不会到当前目录以外找头文件#include AlgoDesignStack.h必须保证文件在同一目录。这种验证方式不依赖IDE在任何Windows命令行都能做。如果你还没解压这份zip建议拿到后先按上面流程跑通一个示例再决定按哪个章节深入。从那以后我每次拿到一套新课程资源都会先强制走一遍“看目录、找图、读源码、本地编译”的流程四步走完才算真正落地而不是只让它在网盘里躺灰。希望帮到你。本文还有配套的精品资源点击获取