尧图网站建设 
简介这是一份用于课程复习与备考的《数据结构与算法》PPT覆盖线性表、链表、栈、队列、字符串等核心知识点并配有典型例题与代码分析适合计算机专业学生巩固基础、准备考试。资源为单个PPT演示文稿压缩包大小1.73MB内容组织以章节为单位包含知识结构、考点提示、代码片段和习题讲解便于按需查看。已有253人学习使用。课件从逻辑结构与物理结构入手深入讲解顺序表、单链表、双向链表、循环链表及有序链表合并操作并对时间复杂度、抽象数据类型、循环队列与栈的应用等高频考点做了归纳可帮助读者快速建立知识框架并掌握常见题型解题思路。1. 数据结构与算法期末复习这份 PPT 到底把考点圈到了什么程度数据结构与算法这门课很多人是考前一周才开始翻书。但教材那么厚从线性表翻到图再翻到排序根本来不及。这份《数据结构与算法PPT》就是冲着这个痛点来的——它把每章的知识点、考核范围、典型例题和易错点全按目录页整理好了甚至连哪些章节不考都直接给你标出来。我拿到之后第一反应是这不就是一份带答案的考前划重点手册吗。它不是教材替代品而是帮你把教材压缩成“考点清单代码题模板”的复习资源适合期末冲刺、考研 408 数据结构部分复习以及想快速回顾数据结构核心概念的从业者。2. 先看全局这份 PPT 的知识结构和考核范围到底怎么用2.1 从目录页能读出什么每章考什么、不考什么PPT 第 2 页就是目录页分成了“温习知识点、知识结构、考试、训练、答疑”几个板块。第 3 页交代了计算机世界的研究问题建模 算法 实现数据结构的研究视角是逻辑结构和物理结构抽象数据类型由数据、数据间联系、数据上的操作集合构成。第 4 页最实用——直接列出了不属于考核范围的内容Chapter 2 的 2.5、2.6Chapter 3 的 3.3Chapter 6 的 6.2Chapter 7 的 7.4、7.5、7.6Chapter 9 的 9.5.2、9.6、9.7还有整个 Chapter 10。这意味着你复习的时候可以先把这些章节跳过去把时间花在真正会考的内容上。对于两周内要考完这门课的人来说这一页就值回下载时间了。2.2 每个 Chapter 的知识点密度从第 1 章的 O() 到第 5 章的哈夫曼树PPT 把每个 Chapter 的知识点都浓缩成了“考点地图”。第 1 章是数据结构和算法的基础逻辑结构分线性结构线性、树型、集合、图存储结构分顺序、链接、散列、索引算法性能评价看时间复杂度和空间复杂度用 O() 表示。第 2 章是线性表逻辑结构上的前驱后继、抽象数据类型的插入删除物理结构上的顺序表和链接表还有几个必问题——头结点的用途、带头结点单链表的判空条件、顺序表和链接表的优缺点对比。第 5 章是二叉树基本术语、完全二叉树和满二叉树的性质、父结点和孩子结点编号对应关系、度为 0 和度为 2 的结点数量关系、三种深度优先遍历、线索二叉树的空指针数目、哈夫曼树构造和 WPL 计算。如果需要给这些考点做一个优先级排序我会这么排优先级考点理由P0必考时间复杂度计算、链表插入删除、栈和队列特性、二叉树遍历每个学校期末卷基本都出P1高频顺序表地址计算、循环队列判满判空、哈夫曼树构造与 WPL考研 408 反复考P2选考有序链表合并、线索二叉树、字符串匹配看具体试卷风格3. 线性表考点拆解顺序表、链表和有序合并代码逐行看3.1 顺序表和链表对比从“平均移动多少个元素”说起PPT 第 7 页抛出一个经典问题顺序存储的线性表插入或删除一个元素平均移动多少个元素答案是 n/2。为什么因为插入到第 i 个位置需要移动 n-i1 个元素所有位置等概率时平均移动次数是 (n1)/2近似 n/2。这个考点几乎每个学校都考形式可能是一道选择题也可能是一道简答题。顺序表的优点是随机访问 O(1)缺点是插入删除要移动元素。链表反过来插入删除只要改指针 O(1)前提是已经定位到目标位置但随机访问是 O(n)。PPT 第 10-11 页还给出了 P168 第 16 题两个带头结点的有序升序单链表合并为一个升序链表要求在原表基础上合并。这是一道非常典型的链表操作综合题考察的是指针操作基本功。3.2 mergeList 函数逐段拆解为什么这样写PPT 第 11 页给出的合并代码是这样的//升序合并为升序 PList mergeList(PList list1, PList list2){ PList p1list1, p2list2, headNULL, tailNULL, temp; if(p1-valuep2-value){ headp1; tailp1; p1p1-next; tail-nextNULL; }else{ headp2; tailp2; p2p2-next; tail-nextNULL; } while((p1!NULL)(p2!NULL)){ if(p1-valuep2-value){ tempp2-next; tail-nextp2; tailp2; tail-nextNULL; p2temp; }else{ tempp1-next; tail-nextp1; tailp1; tail-nextNULL; p1temp; } } if(p1!NULL) tail-nextp1; if(p2!NULL) tail-nextp2; return head; }这段代码的思路是先比较两个链表第一个结点把较小者作为合并后链表的头结点然后用 tail 指针维护合并链表的尾部。循环里每次比较 p1 和 p2 当前指向的结点值把较小的那个接到 tail 后面同时把对应链表的指针往后移。注意一个细节每接一个结点tail-next 都被置为 NULL这是为了让合并后的链表尾部干净避免残留原来的 next 指向。循环结束后把还没遍历完的链表剩余部分直接接到 tail 后面。我一般会提醒学生注意两个坑。第一个坑是初始比较时if(p1-valuep2-value)用的是小于号这意味着如果两个链表第一个结点值相等会走 else 分支选择 list2 的结点作为头结点。这本身没问题但如果你希望合并后结点来源保持某种确定性这里就需要改成。第二个坑是 while 循环里if(p1-valuep2-value)用的是大于号等于的情况走了 else 分支接 p1 的结点逻辑上是自洽的但如果你把这两个比较符号搞混合并结果就会出现乱序或者丢失结点。3.3 升序转降序一个改动点就能实现PPT 里有一句追问升序转降序如何实现其实很简单把合并过程中的比较符号反过来就行。升序合并是每次取较小的结点降序合并是每次取较大的结点。但要注意两个原始链表是升序的如果你直接改成“每次取较大结点”得到的是降序结果头结点会是第一个较大者。实际写的时候把if(p1-valuep2-value)改成if(p1-valuep2-value)把 while 里的if(p1-valuep2-value)改成if(p1-valuep2-value)就完成了降序合并。这是最容易出分的改动题考试时遇到别慌。4. 栈、队列和循环链表应用题从概念到代码实现4.1 栈的经典考题入栈序列 1,2,3,…,np1n 时 pi 是多少PPT 第 14 页有一道经典题已知栈的入栈序列是 1, 2, 3, …, n输出序列是 p1, p2, p3, …, pn若 p1n则 pi 是多少答案是 Cn-i1。逻辑是第一个出栈的是 n说明前 n-1 个元素都已经全部压栈了剩下的只能按 n-1, n-2, …, 1 的顺序依次弹出所以第 i 个出栈的元素就是 n-i1。这类题考察的是对栈 FILO 特性的理解而且不需要模拟整个过程只要抓住“第一个弹出的是 n 就意味着所有元素都已入栈”这个关键结论就行。很多人在这道题上翻车是因为没有意识到 p1n 这个条件已经把入栈序列卡死了——它不是让你随便选一个出栈序列而是给定第一个出栈元素反推整个序列。4.2 循环单链表作为队列初始化和插入的代码逻辑PPT 第 18 页给出了用循环单链表只有尾指针 tail实现队列的代码typedef struct QueueElement{ int value; struct QueueElement *next; }QueueElement; typedef QueueElement *PQueue; PQueue initQueue(){ PQueue queueTail; queueTail(PQueue)malloc(sizeof(QueueElement)); queueTail-value-1; queueTail-nextqueueTail; return queueTail; } PQueue insertElement(PQueue queueTail, int v){ QueueElement *q(QueueElement *)malloc(sizeof(QueueElement)); q-valuev; q-nextqueueTail-next; queueTail-nextq; queueTailq; return queueTail; }这段代码里initQueue 创建了一个头结点value 设为 -1 作为哨兵值next 指向自己表示空队列。insertElement 是尾插法新结点的 next 指向原队列的第一个结点queueTail-next再把原尾结点的 next 指向新结点最后把 tail 指针移到新结点上。为什么要返回 queueTail因为 tail 指针变化了调用方需要接收新的尾指针。PPT 问删除操作如何实现循环单链表队列只有一个尾指针 tail那么队头元素就是 tail-next因为 tail 指向最后一个元素tail-next 指向第一个元素。删除操作是这样的// 循环单链表队列的出队操作 PQueue deleteElement(PQueue queueTail){ if(queueTail-next queueTail){ printf(队列为空无法删除\n); return queueTail; } QueueElement *front queueTail-next; if(front queueTail){ // 只有一个元素时删除后变成空队列 free(front); queueTail-next queueTail; return queueTail; } queueTail-next front-next; free(front); return queueTail; }这段删除操作要处理三种情况空队列tail-next 等于 tail 自己、只有一个结点的队列删除后 tail 仍然是头结点但 next 指回自己、多个结点的队列tail-next 跳过第一个结点指向第二个。如果删的是唯一的那个元素你必须把 tail 的 next 重新指向 tail 自己不然队列就断了。4.3 三种状态图为什么“只有尾指针”是考点PPT 第 16-17 页反复出现同一个问题采用循环单链表作为队列只有尾指针 tail画出三种状态下的结构。这三种状态分别是空队列tail 的 next 指向自己、插入一个元素后tail 指向刚插入的元素tail-next 指向头结点、插入多个元素后tail 指向最后一个元素tail-next 指向第一个元素。为什么这个考点反复出现因为它考察的是你能否在“只有一个指针”约束下正确理解循环链表的结构。很多人画图会画错是因为下意识里把 tail 当成了队头。实际上 tail 指向的是队尾而队头是 tail-next这是循环单链表队列最反直觉的地方。理解了这一点删除操作的实现就水到渠成。5. 二叉树高频失分点术语、编号、哈夫曼树与避坑排查5.1 必须背下来的二叉树性质和编号关系PPT 第 19-20 页列了二叉树的核心术语和性质。其中最容易考到的是这几个结点的层数从 0 开始计根结点层数为 0树的高度是最大层数加 1完全二叉树中父结点编号为 i 时左孩子编号为 2i1如果根结点编号为 0或 2i如果根结点编号为 1二叉树中度为 0 的结点数等于度为 2 的结点数加 1深度为 k 的二叉树最少有 k1 个结点每层至少一个最多有 2^(k1)-1 个结点满二叉树。PPT 还问了三个需要动笔的问题只有三个结点的二叉树有多少种不同形态答案是 5 种——这是卡特兰数的经典应用C35。n 个结点的二叉链表中有多少个空指针答案是 n1 个。为什么因为每个结点有两个指针域共 2n 个实际使用的非空指针是 n-1 个树有 n-1 条边所以空指针是 2n-(n-1)n1。这个推导过程一定要写熟考试时直接用公式容易被判没有推导过程扣分。5.2 哈夫曼树的构造和 WPL 计算步骤和参数哈夫曼树最优二叉树的构造步骤是固定的把 n 个权值看成 n 棵只有根结点的树每次选出两个权值最小的树合并新结点的权值是两个子结点权值之和重复直到只剩一棵树。WPL带权路径长度等于每个叶子结点的权值乘以它到根结点的路径长度边数之和。PPT 问的是“如何构造哈夫曼树和计算 WPL”我一般建议按固定格式作答第一步写出初始森林第二步每轮合并写明选中的两个最小权值和新权值第三步画出最终树形并逐项计算 WPL。具体计算时有一个常见翻车点哈夫曼树要求每次合并后把新结点放回森林重新排序很多人为了省事直接从左到右合并结果构造出来的不是最优树WPL 也偏大。5.3 避坑排查五个高频失分点坑 1完全二叉树编号起点搞混。现象是计算父结点和孩子结点编号时结果差 1。原因是教材和真题有的从 0 开始编号、有的从 1 开始编号你没看题目条件直接套公式。解决方法是先确认题目给出的根结点编号是 0 还是 1再决定用 2i1/2i2 还是 2i/2i1。坑 2线索二叉树的空指针数目算错。现象是题目问“n 个结点的二叉链表有多少空指针”你写成 n 或者 n-1。原因是你把二叉链表的空指针和线索二叉树加了线索后的指针混为一谈。解决方法是记住普通二叉链表空指针是 n1线索二叉树里这些空指针被用来指向前驱和后继数量本身没有变化。坑 3哈夫曼树合并顺序不重新排序。现象是构造出来的树 WPL 比标准答案大。原因是每次合并后没有把新结点放回森林重新选择最小值。解决方法是每合并一轮就把新权值插回森林再选两个最小的不要人肉凭感觉合并。坑 4度为 0 的结点数和度为 2 的结点数关系记成相等。现象是填空题直接写成 n0 n2。原因是没记住 1 是哪个方向。解决方法是记住一个推导锚点一棵只有 3 个结点的二叉树根 两个孩子n02n21所以 n0n21。坑 5遍历结果反推二叉树时忽略空子树占位。现象是由先序和中序还原二叉树时把只有一个孩子的结点误判成两个孩子。原因是先序序列里没有显式标出空子树位置。解决方法是手动补一个空标记比如用 # 表示空结点写出带空结点的先序序列再去还原。6. 把复习题变成验证代码一个训练习惯让考点不再抽象PPT 里的代码题看懂了是一回事能自己写出来是另一回事。我自己的习惯是每复习完一章就把 PPT 里出现的代码题在编辑器里重新敲一遍用真实输入验证输出。比如第 3 章的 mergeList光看代码觉得懂了但自己从头写的时候经常会漏掉tail-next NULL这一步导致合并后的链表末尾残留旧指针。跑一次测试就暴露了。// 验证用构造两个有序链表并合并 #include stdio.h #include stdlib.h typedef struct Node { int value; struct Node *next; } Node, *PList; // 创建一个带头结点的升序链表 {1, 3, 5} PList createList1() { PList head (PList)malloc(sizeof(Node)); head-next NULL; PList tail head; int vals[] {1, 3, 5}; for(int i 0; i 3; i) { PList p (PList)malloc(sizeof(Node)); p-value vals[i]; p-next NULL; tail-next p; tail p; } return head; } // 创建一个带头结点的升序链表 {2, 4, 6} PList createList2() { PList head (PList)malloc(sizeof(Node)); head-next NULL; PList tail head; int vals[] {2, 4, 6}; for(int i 0; i 3; i) { PList p (PList)malloc(sizeof(Node)); p-value vals[i]; p-next NULL; tail-next p; tail p; } return head; } PList mergeList(PList list1, PList list2) { // 跳过头结点从第一个元素结点开始合并 PList p1 list1-next, p2 list2-next, head NULL, tail NULL, temp; // 处理第一个结点 if(p1-value p2-value) { head p1; tail p1; p1 p1-next; tail-next NULL; } else { head p2; tail p2; p2 p2-next; tail-next NULL; } while((p1 ! NULL) (p2 ! NULL)) { if(p1-value p2-value) { temp p2-next; tail-next p2; tail p2; tail-next NULL; p2 temp; } else { temp p1-next; tail-next p1; tail p1; tail-next NULL; p1 temp; } } if(p1 ! NULL) tail-next p1; if(p2 ! NULL) tail-next p2; return head; } int main() { PList list1 createList1(); PList list2 createList2(); PList merged mergeList(list1, list2); PList p merged; while(p ! NULL) { printf(%d , p-value); p p-next; } printf(\n); return 0; }注意这份验证代码和 PPT 原版代码有个差别PPT 的 mergeList 直接拿 list1 和 list2 当作头结点存放数据而我的验证代码把 list1 和 list2 定义为带头结点的链表mergeList 里手动跳过了头结点。这个改动的意义在于更接近真实工程场景——带头结点便于统一判空逻辑。运行结果应该输出1 2 3 4 5 6如果你拿到的输出有乱序或丢值说明 while 循环里的比较符号和指针移动步骤写错了。第 4 章的循环队列删除操作也值得补全跑一遍。用随机插入几个元素再全部删除的方式验证重点看删除到最后一个元素时是否还能正确判空。如果你在那个分支上忘了重置queueTail-next queueTail删除最后一个元素后队列状态就坏了再执行插入操作会出现两个结点互相指向的死循环。从那以后我每次复习完一套数据结构资料都强制自己走一遍“看题 → 手写代码 → 构造输入验证输出”的流程而不是只看不练。这份 PPT 帮我省掉了整理考点的力气但代码手感必须自己练出来。希望这些坑和拆解能帮到你少走点弯路。本文还有配套的精品资源点击获取 数据结构与算法考前冲刺：考点圈定与链表二叉树代码避坑
简介这是一份用于课程复习与备考的《数据结构与算法》PPT覆盖线性表、链表、栈、队列、字符串等核心知识点并配有典型例题与代码分析适合计算机专业学生巩固基础、准备考试。资源为单个PPT演示文稿压缩包大小1.73MB内容组织以章节为单位包含知识结构、考点提示、代码片段和习题讲解便于按需查看。已有253人学习使用。课件从逻辑结构与物理结构入手深入讲解顺序表、单链表、双向链表、循环链表及有序链表合并操作并对时间复杂度、抽象数据类型、循环队列与栈的应用等高频考点做了归纳可帮助读者快速建立知识框架并掌握常见题型解题思路。1. 数据结构与算法期末复习这份 PPT 到底把考点圈到了什么程度数据结构与算法这门课很多人是考前一周才开始翻书。但教材那么厚从线性表翻到图再翻到排序根本来不及。这份《数据结构与算法PPT》就是冲着这个痛点来的——它把每章的知识点、考核范围、典型例题和易错点全按目录页整理好了甚至连哪些章节不考都直接给你标出来。我拿到之后第一反应是这不就是一份带答案的考前划重点手册吗。它不是教材替代品而是帮你把教材压缩成“考点清单代码题模板”的复习资源适合期末冲刺、考研 408 数据结构部分复习以及想快速回顾数据结构核心概念的从业者。2. 先看全局这份 PPT 的知识结构和考核范围到底怎么用2.1 从目录页能读出什么每章考什么、不考什么PPT 第 2 页就是目录页分成了“温习知识点、知识结构、考试、训练、答疑”几个板块。第 3 页交代了计算机世界的研究问题建模 算法 实现数据结构的研究视角是逻辑结构和物理结构抽象数据类型由数据、数据间联系、数据上的操作集合构成。第 4 页最实用——直接列出了不属于考核范围的内容Chapter 2 的 2.5、2.6Chapter 3 的 3.3Chapter 6 的 6.2Chapter 7 的 7.4、7.5、7.6Chapter 9 的 9.5.2、9.6、9.7还有整个 Chapter 10。这意味着你复习的时候可以先把这些章节跳过去把时间花在真正会考的内容上。对于两周内要考完这门课的人来说这一页就值回下载时间了。2.2 每个 Chapter 的知识点密度从第 1 章的 O() 到第 5 章的哈夫曼树PPT 把每个 Chapter 的知识点都浓缩成了“考点地图”。第 1 章是数据结构和算法的基础逻辑结构分线性结构线性、树型、集合、图存储结构分顺序、链接、散列、索引算法性能评价看时间复杂度和空间复杂度用 O() 表示。第 2 章是线性表逻辑结构上的前驱后继、抽象数据类型的插入删除物理结构上的顺序表和链接表还有几个必问题——头结点的用途、带头结点单链表的判空条件、顺序表和链接表的优缺点对比。第 5 章是二叉树基本术语、完全二叉树和满二叉树的性质、父结点和孩子结点编号对应关系、度为 0 和度为 2 的结点数量关系、三种深度优先遍历、线索二叉树的空指针数目、哈夫曼树构造和 WPL 计算。如果需要给这些考点做一个优先级排序我会这么排优先级考点理由P0必考时间复杂度计算、链表插入删除、栈和队列特性、二叉树遍历每个学校期末卷基本都出P1高频顺序表地址计算、循环队列判满判空、哈夫曼树构造与 WPL考研 408 反复考P2选考有序链表合并、线索二叉树、字符串匹配看具体试卷风格3. 线性表考点拆解顺序表、链表和有序合并代码逐行看3.1 顺序表和链表对比从“平均移动多少个元素”说起PPT 第 7 页抛出一个经典问题顺序存储的线性表插入或删除一个元素平均移动多少个元素答案是 n/2。为什么因为插入到第 i 个位置需要移动 n-i1 个元素所有位置等概率时平均移动次数是 (n1)/2近似 n/2。这个考点几乎每个学校都考形式可能是一道选择题也可能是一道简答题。顺序表的优点是随机访问 O(1)缺点是插入删除要移动元素。链表反过来插入删除只要改指针 O(1)前提是已经定位到目标位置但随机访问是 O(n)。PPT 第 10-11 页还给出了 P168 第 16 题两个带头结点的有序升序单链表合并为一个升序链表要求在原表基础上合并。这是一道非常典型的链表操作综合题考察的是指针操作基本功。3.2 mergeList 函数逐段拆解为什么这样写PPT 第 11 页给出的合并代码是这样的//升序合并为升序 PList mergeList(PList list1, PList list2){ PList p1list1, p2list2, headNULL, tailNULL, temp; if(p1-valuep2-value){ headp1; tailp1; p1p1-next; tail-nextNULL; }else{ headp2; tailp2; p2p2-next; tail-nextNULL; } while((p1!NULL)(p2!NULL)){ if(p1-valuep2-value){ tempp2-next; tail-nextp2; tailp2; tail-nextNULL; p2temp; }else{ tempp1-next; tail-nextp1; tailp1; tail-nextNULL; p1temp; } } if(p1!NULL) tail-nextp1; if(p2!NULL) tail-nextp2; return head; }这段代码的思路是先比较两个链表第一个结点把较小者作为合并后链表的头结点然后用 tail 指针维护合并链表的尾部。循环里每次比较 p1 和 p2 当前指向的结点值把较小的那个接到 tail 后面同时把对应链表的指针往后移。注意一个细节每接一个结点tail-next 都被置为 NULL这是为了让合并后的链表尾部干净避免残留原来的 next 指向。循环结束后把还没遍历完的链表剩余部分直接接到 tail 后面。我一般会提醒学生注意两个坑。第一个坑是初始比较时if(p1-valuep2-value)用的是小于号这意味着如果两个链表第一个结点值相等会走 else 分支选择 list2 的结点作为头结点。这本身没问题但如果你希望合并后结点来源保持某种确定性这里就需要改成。第二个坑是 while 循环里if(p1-valuep2-value)用的是大于号等于的情况走了 else 分支接 p1 的结点逻辑上是自洽的但如果你把这两个比较符号搞混合并结果就会出现乱序或者丢失结点。3.3 升序转降序一个改动点就能实现PPT 里有一句追问升序转降序如何实现其实很简单把合并过程中的比较符号反过来就行。升序合并是每次取较小的结点降序合并是每次取较大的结点。但要注意两个原始链表是升序的如果你直接改成“每次取较大结点”得到的是降序结果头结点会是第一个较大者。实际写的时候把if(p1-valuep2-value)改成if(p1-valuep2-value)把 while 里的if(p1-valuep2-value)改成if(p1-valuep2-value)就完成了降序合并。这是最容易出分的改动题考试时遇到别慌。4. 栈、队列和循环链表应用题从概念到代码实现4.1 栈的经典考题入栈序列 1,2,3,…,np1n 时 pi 是多少PPT 第 14 页有一道经典题已知栈的入栈序列是 1, 2, 3, …, n输出序列是 p1, p2, p3, …, pn若 p1n则 pi 是多少答案是 Cn-i1。逻辑是第一个出栈的是 n说明前 n-1 个元素都已经全部压栈了剩下的只能按 n-1, n-2, …, 1 的顺序依次弹出所以第 i 个出栈的元素就是 n-i1。这类题考察的是对栈 FILO 特性的理解而且不需要模拟整个过程只要抓住“第一个弹出的是 n 就意味着所有元素都已入栈”这个关键结论就行。很多人在这道题上翻车是因为没有意识到 p1n 这个条件已经把入栈序列卡死了——它不是让你随便选一个出栈序列而是给定第一个出栈元素反推整个序列。4.2 循环单链表作为队列初始化和插入的代码逻辑PPT 第 18 页给出了用循环单链表只有尾指针 tail实现队列的代码typedef struct QueueElement{ int value; struct QueueElement *next; }QueueElement; typedef QueueElement *PQueue; PQueue initQueue(){ PQueue queueTail; queueTail(PQueue)malloc(sizeof(QueueElement)); queueTail-value-1; queueTail-nextqueueTail; return queueTail; } PQueue insertElement(PQueue queueTail, int v){ QueueElement *q(QueueElement *)malloc(sizeof(QueueElement)); q-valuev; q-nextqueueTail-next; queueTail-nextq; queueTailq; return queueTail; }这段代码里initQueue 创建了一个头结点value 设为 -1 作为哨兵值next 指向自己表示空队列。insertElement 是尾插法新结点的 next 指向原队列的第一个结点queueTail-next再把原尾结点的 next 指向新结点最后把 tail 指针移到新结点上。为什么要返回 queueTail因为 tail 指针变化了调用方需要接收新的尾指针。PPT 问删除操作如何实现循环单链表队列只有一个尾指针 tail那么队头元素就是 tail-next因为 tail 指向最后一个元素tail-next 指向第一个元素。删除操作是这样的// 循环单链表队列的出队操作 PQueue deleteElement(PQueue queueTail){ if(queueTail-next queueTail){ printf(队列为空无法删除\n); return queueTail; } QueueElement *front queueTail-next; if(front queueTail){ // 只有一个元素时删除后变成空队列 free(front); queueTail-next queueTail; return queueTail; } queueTail-next front-next; free(front); return queueTail; }这段删除操作要处理三种情况空队列tail-next 等于 tail 自己、只有一个结点的队列删除后 tail 仍然是头结点但 next 指回自己、多个结点的队列tail-next 跳过第一个结点指向第二个。如果删的是唯一的那个元素你必须把 tail 的 next 重新指向 tail 自己不然队列就断了。4.3 三种状态图为什么“只有尾指针”是考点PPT 第 16-17 页反复出现同一个问题采用循环单链表作为队列只有尾指针 tail画出三种状态下的结构。这三种状态分别是空队列tail 的 next 指向自己、插入一个元素后tail 指向刚插入的元素tail-next 指向头结点、插入多个元素后tail 指向最后一个元素tail-next 指向第一个元素。为什么这个考点反复出现因为它考察的是你能否在“只有一个指针”约束下正确理解循环链表的结构。很多人画图会画错是因为下意识里把 tail 当成了队头。实际上 tail 指向的是队尾而队头是 tail-next这是循环单链表队列最反直觉的地方。理解了这一点删除操作的实现就水到渠成。5. 二叉树高频失分点术语、编号、哈夫曼树与避坑排查5.1 必须背下来的二叉树性质和编号关系PPT 第 19-20 页列了二叉树的核心术语和性质。其中最容易考到的是这几个结点的层数从 0 开始计根结点层数为 0树的高度是最大层数加 1完全二叉树中父结点编号为 i 时左孩子编号为 2i1如果根结点编号为 0或 2i如果根结点编号为 1二叉树中度为 0 的结点数等于度为 2 的结点数加 1深度为 k 的二叉树最少有 k1 个结点每层至少一个最多有 2^(k1)-1 个结点满二叉树。PPT 还问了三个需要动笔的问题只有三个结点的二叉树有多少种不同形态答案是 5 种——这是卡特兰数的经典应用C35。n 个结点的二叉链表中有多少个空指针答案是 n1 个。为什么因为每个结点有两个指针域共 2n 个实际使用的非空指针是 n-1 个树有 n-1 条边所以空指针是 2n-(n-1)n1。这个推导过程一定要写熟考试时直接用公式容易被判没有推导过程扣分。5.2 哈夫曼树的构造和 WPL 计算步骤和参数哈夫曼树最优二叉树的构造步骤是固定的把 n 个权值看成 n 棵只有根结点的树每次选出两个权值最小的树合并新结点的权值是两个子结点权值之和重复直到只剩一棵树。WPL带权路径长度等于每个叶子结点的权值乘以它到根结点的路径长度边数之和。PPT 问的是“如何构造哈夫曼树和计算 WPL”我一般建议按固定格式作答第一步写出初始森林第二步每轮合并写明选中的两个最小权值和新权值第三步画出最终树形并逐项计算 WPL。具体计算时有一个常见翻车点哈夫曼树要求每次合并后把新结点放回森林重新排序很多人为了省事直接从左到右合并结果构造出来的不是最优树WPL 也偏大。5.3 避坑排查五个高频失分点坑 1完全二叉树编号起点搞混。现象是计算父结点和孩子结点编号时结果差 1。原因是教材和真题有的从 0 开始编号、有的从 1 开始编号你没看题目条件直接套公式。解决方法是先确认题目给出的根结点编号是 0 还是 1再决定用 2i1/2i2 还是 2i/2i1。坑 2线索二叉树的空指针数目算错。现象是题目问“n 个结点的二叉链表有多少空指针”你写成 n 或者 n-1。原因是你把二叉链表的空指针和线索二叉树加了线索后的指针混为一谈。解决方法是记住普通二叉链表空指针是 n1线索二叉树里这些空指针被用来指向前驱和后继数量本身没有变化。坑 3哈夫曼树合并顺序不重新排序。现象是构造出来的树 WPL 比标准答案大。原因是每次合并后没有把新结点放回森林重新选择最小值。解决方法是每合并一轮就把新权值插回森林再选两个最小的不要人肉凭感觉合并。坑 4度为 0 的结点数和度为 2 的结点数关系记成相等。现象是填空题直接写成 n0 n2。原因是没记住 1 是哪个方向。解决方法是记住一个推导锚点一棵只有 3 个结点的二叉树根 两个孩子n02n21所以 n0n21。坑 5遍历结果反推二叉树时忽略空子树占位。现象是由先序和中序还原二叉树时把只有一个孩子的结点误判成两个孩子。原因是先序序列里没有显式标出空子树位置。解决方法是手动补一个空标记比如用 # 表示空结点写出带空结点的先序序列再去还原。6. 把复习题变成验证代码一个训练习惯让考点不再抽象PPT 里的代码题看懂了是一回事能自己写出来是另一回事。我自己的习惯是每复习完一章就把 PPT 里出现的代码题在编辑器里重新敲一遍用真实输入验证输出。比如第 3 章的 mergeList光看代码觉得懂了但自己从头写的时候经常会漏掉tail-next NULL这一步导致合并后的链表末尾残留旧指针。跑一次测试就暴露了。// 验证用构造两个有序链表并合并 #include stdio.h #include stdlib.h typedef struct Node { int value; struct Node *next; } Node, *PList; // 创建一个带头结点的升序链表 {1, 3, 5} PList createList1() { PList head (PList)malloc(sizeof(Node)); head-next NULL; PList tail head; int vals[] {1, 3, 5}; for(int i 0; i 3; i) { PList p (PList)malloc(sizeof(Node)); p-value vals[i]; p-next NULL; tail-next p; tail p; } return head; } // 创建一个带头结点的升序链表 {2, 4, 6} PList createList2() { PList head (PList)malloc(sizeof(Node)); head-next NULL; PList tail head; int vals[] {2, 4, 6}; for(int i 0; i 3; i) { PList p (PList)malloc(sizeof(Node)); p-value vals[i]; p-next NULL; tail-next p; tail p; } return head; } PList mergeList(PList list1, PList list2) { // 跳过头结点从第一个元素结点开始合并 PList p1 list1-next, p2 list2-next, head NULL, tail NULL, temp; // 处理第一个结点 if(p1-value p2-value) { head p1; tail p1; p1 p1-next; tail-next NULL; } else { head p2; tail p2; p2 p2-next; tail-next NULL; } while((p1 ! NULL) (p2 ! NULL)) { if(p1-value p2-value) { temp p2-next; tail-next p2; tail p2; tail-next NULL; p2 temp; } else { temp p1-next; tail-next p1; tail p1; tail-next NULL; p1 temp; } } if(p1 ! NULL) tail-next p1; if(p2 ! NULL) tail-next p2; return head; } int main() { PList list1 createList1(); PList list2 createList2(); PList merged mergeList(list1, list2); PList p merged; while(p ! NULL) { printf(%d , p-value); p p-next; } printf(\n); return 0; }注意这份验证代码和 PPT 原版代码有个差别PPT 的 mergeList 直接拿 list1 和 list2 当作头结点存放数据而我的验证代码把 list1 和 list2 定义为带头结点的链表mergeList 里手动跳过了头结点。这个改动的意义在于更接近真实工程场景——带头结点便于统一判空逻辑。运行结果应该输出1 2 3 4 5 6如果你拿到的输出有乱序或丢值说明 while 循环里的比较符号和指针移动步骤写错了。第 4 章的循环队列删除操作也值得补全跑一遍。用随机插入几个元素再全部删除的方式验证重点看删除到最后一个元素时是否还能正确判空。如果你在那个分支上忘了重置queueTail-next queueTail删除最后一个元素后队列状态就坏了再执行插入操作会出现两个结点互相指向的死循环。从那以后我每次复习完一套数据结构资料都强制自己走一遍“看题 → 手写代码 → 构造输入验证输出”的流程而不是只看不练。这份 PPT 帮我省掉了整理考点的力气但代码手感必须自己练出来。希望这些坑和拆解能帮到你少走点弯路。本文还有配套的精品资源点击获取