💡 这一部分最值得回味的是题6-12，是关于二叉搜索/排序树的。
| 编号 | 题目链接 | 我的题解 | 主要思路 | 易错点 |
|---|---|---|---|---|
| 6-1 | 链表逆转 | DS-6-1.c | 顺序遍历链表节点。每遍历到一个节点，就将当前节点接到前一个节点的前面 | 注意输入链表为空或者只有一个链表节点的情况！ |
| 6-2 | 顺序表操作集 | DS-6-2.c | 数据结构顺序表的基本四类操作 | 进行删除和插入操作时注意操作位置P是否合法。在进行删除、插入操作后不要忘了改变指向最后元素下标的变量Last |
| 6-3 | 求链式表的表长 | DS-6-3.c | 遍历链表进行计数 | 无 |
| 6-4 | 链式表的按序号查找 | DS-6-4.c | 遍历链表找到对应序号的元素 | 无 |
| 6-5 | 链式表操作集 | DS-6-5.c | 针对链表的增删查操作 | 注意表头指针的变动，也不要忘了操作位置的前一个节点 |
| 6-6 | 带头结点的链式表操作集 | DS-6-6.c | 针对链表的增删查操作(带头节点) | 注意循环终止条件的写法。 |
| 6-7 | 在一个数组中实现两个堆栈 | DS-6-7.c | 两个栈的栈顶下标移动方向相反 | PTA的裁判程序要求栈顶下标必须是对应栈顶元素的。 |
| 6-8 | 求二叉树高度 | DS-6-8.c | 递归遍历二叉树，采用贪心策略，每次都找最高的子树的高度进行累积。 | 无 |
| 6-9 | 二叉树的遍历 | DS-6-9.c | 二叉树的几种基本遍历方法，前中后序遍历是DFS，而层序遍历是BFS | 无 |
| 6-10 | 二分查找 | DS-6-10.c | 二分查找顺序表(数组) | 注意本题元素是从下标1开始储存的 |
| 6-11 | 先序输出叶结点 | DS-6-11.c | 先序遍历二叉树，输出所有叶节点 | 无 |
| 6-12 | 二叉搜索树的操作集 | DS-6-12.c | 每一棵树的左子树放比根节点小的数据，右子树放比根节点大的数据，以此构造二叉树 | 一定要注意删除结点的写法，细节点很多。 |
| 编号 | 题目链接 | 我的题解 | 关键思路 | 值得玩味 |
|---|---|---|---|---|
| 7-1 | 最大子列和问题 | DS-7-1.cpp | 枚举子序列长度，多次求和运算中找出拥有最大和的子序列。利用数组缓存求出的连续子序列和，用于后序子序列求和运算，用空间换时间。 | |
| 7-1 | 最大子列和问题 | DS-7-1-optimal.cpp | (最优解)只关心序列中能求出的最大和是多少，一遍循环找出部分序列累加的最大和即可。 | √ |
| 7-2 | 一元多项式的乘法与加法运算 | DS-7-2.cpp | 多项式乘法的结果中的项要按指数降序排列。加法得益于输入项是按指数降序排列的，可以用两个指针来寻找同类项。 | 0.5√ |
| 7-3 | 树的同构 | DS-7-3.cpp | 采用DFS思想，同时遍历两棵树，比对每个子树根节点下的左孩子和右孩子，必要时交换后再比对 | |
| 7-4 | 是否同一棵二叉搜索树 | AC: DS-7-4.cpp MLE: DS-7-4-MLE.cpp |
树的每个结点中新增一个标记位，通过标记位实现两棵树的比较。在每次比较过后，所有标记位要归位为0 | √ |
| 7-5 | 堆中的路径 | AC: DS-7-5.cpp 自下而上建堆: DS-7-5-SiftDown.cpp |
要AC的话得采用自顶向下建堆法，具体实现是对每个插入尾部的节点进行上滤操作 | |
| 7-6 | 列出连通集 | DS-7-6.cpp | 考察无向图的储存，以及图的DFS,BFS遍历 | |
| 7-7 | 六度空间 | DS-7-7.cpp | 采用无向图的BFS遍历，值得玩味的地方在于记录每个顶点所在层数 | 0.5√ |
| 7-8 | 哈利·波特的考试 | DS-7-8.cpp 完全图生成工具: completeGraph.js |
求无向图的单源最短路径，Dijkstra算法的写法很值得回味(本题我采用的是暴力Dijkstra写法) | √ |
| 7-9 | 旅游规划 | DS-7-9.cpp | 求无向图的两点间最短路径，采用优先队列辅助的Dijkstra算法(本题我手写实现了基于小根堆的优先队列) | √ |
| 7-10 | 公路村村通 | Prim(AC): DS-7-10.cpp Kruskal(AC,并查集): DS-7-10-Kruskal.cpp Kruskal(TLE): DS-7-10-Kruskal-TLE.cpp Dijkstra(错误思路): DS-7-10-WA-Dijkstra.cpp |
求无向图的最小生成树的权，有Prim和Kruskal实现 | √ |
| 7-11 | 关键活动 | DS-7-11.cpp 随机AOE网生成工具: randomAOE.js |
通过拓扑排序序列求AOE网(无环有向图)的关键活动。本题考察的点非常全面，涵盖到了关键路径这一块的所有内容。个人感觉出的很好，很适合查漏补缺。 | √√ |
| 7-12 | 排序 | DS-7-12.cpp | 常用的排序算法我都尝试写了一遍，适合复习。 | √√ |
| 7-13 | 统计工龄 | DS-7-13.cpp | 简单题，利用直接定址哈希表对相应工龄的员工数进行统计 | |
| 7-14 | 电话聊天狂人 | DS-7-14.cpp | 利用哈希表对大规模数据进行统计工作，采用位与取余法，并利用链地址法处理哈希碰撞。位与取余 被除数 & (除数-1)的公式值得记忆，不过这里的除数必须是2的N次方 |
|
| 7-15 | QQ帐户的申请与登陆 | DS-7-15.cpp | 利用哈希表存取账号信息，哈希表实现几乎和题7-14一致。 | |
| 7-16 | 一元多项式求导 | DS-7-16.cpp | 入门题，边输入边处理边输出，无需任何其他辅助空间 | |
| 7-17 | 汉诺塔的非递归实现 | DS-7-17.cpp 【递归实现: DS-7-17-recursive.cpp】 【咱写的汉诺塔演示工具】 |
经典递归问题-汉诺塔问题的非递归实现。借助栈和循环进行实现。适合用于回味递归思想。 | √ |
| 7-18 | 银行业务队列简单模拟 | DS-7-18.cpp | 利用个队列结构模拟两个窗口的处理过程 | |
| 7-19 | 求链式线性表的倒数第K项 | DS-7-19.cpp | 采用队列储存数字序列的倒数K个数字，只需要取队头数字即可找到倒数第K项 | |
| 7-20 | 表达式转换 | DS-7-20.cpp | 采用栈将中缀表达式转换为后缀表达式。本题AC要求十分严苛，包括输出不能有多余空格，负数，小数等情况，考察全面，十分适合用于复习。 | √√ |
| 7-21 | 求前缀表达式的值 | DS-7-21.cpp 按字符串读入的写法: DS-7-21-string.cpp |
采用栈计算前缀表达式的值。关于前缀表达式能否被正确计算的判断是本题的核心坑点。 | √ |
| 7-22 | 堆栈模拟队列 | DS-7-22.cpp | 利用容量不同的两个栈实现一个队列。两个栈分为入队栈和出队栈，队列的所有元素并不是都要储存在入队栈中，入队栈满时借助出队栈也可以储存一些元素。较小的那个栈决定了队列容量的上限。 | |
| 7-23 | 还原二叉树 | DS-7-23.cpp | 利用先序遍历序列和中序遍历序列还原二叉树并求得高度。其中先序序列用于确定根结点，而随后的中序序列用于确定左子树和右子树各自包含的结点。程序实现采用递归，操作是求字符串的子串。本题利于理解二叉树的遍历序列，值得回顾。 | √ |
| 7-24 | 树种统计 | DS-7-24.cpp | 利用C++ STL中的map容器即可快速解决。map容器底层的红黑树是有序的，其中自动对字符串键按字典序排了序。 | |
| 7-25 | 朋友圈 | DS-7-25.cpp | 本题考察并查集的合并操作，解题思路是将独立、互不相交的学生集合根据俱乐部的关系合并成朋友圈集合。合并过程中需要对集合元素数量进行统计，最后扫描并查集森林中所有根节点，找到计数最大的朋友圈集合，即为结果。 这是我第一次遇到考察并查集的题目，很值得回顾 |
√ |
| 7-26 | Windows消息队列 | DS-7-26.cpp | 本题比较直白地考察了优先队列。本题的优先队列采用小根堆实现，在插入/弹出元素时，利用上滤和下滤两个基本方法进行维护。 | |
| 7-27 | 家谱处理 | DS-7-27.cpp 随机测试数据生成工具: genogram.js |
归纳得出本题只需要储存各节点的父子关系，因此采用了类似于并查集的parents数组。然而要注意，这里的树根节点的父节点最好单独标记，而不是设置为根结点本身，以免判断兄弟节点时出错。 |
0.5√ |
| 7-28 | 搜索树判断 | DS-7-28.cpp | 把先序序列的元素依次插入BST，然后对BST(如果有必要还要对镜像BST)进行先序遍历，比对先序序列即可。本题中所有遍历采用堆栈+循环实现。 | |
| 7-29 | 修理牧场 | DS-7-29.cpp | 不妨反着看切割的过程: 每次由两个小木块组成一块大木头。采用霍夫曼贪心算法，在序列中每次选择最小的两块木板来组成大木板，大木板的长度就是单次切割的花费，选择过程类似于霍夫曼树的构造。这题一定程度上能锻炼算法思维，值得回顾 | 0.5√ |
| 7-30 | 目录树 | DS-7-30.cpp | 本题比较基础，考察多叉树的构建与遍历。多叉树节点中后继节点的指针用数组来储存。题目要求按字典序输出，因此本题咱还用到了algorithm库的sort函数。 |
|
| 7-31 | 笛卡尔树 | DS-7-31.cpp | 本题考察对是否是二叉搜索树和是否是小根堆的判断。值得回顾的是对二叉搜索树的判断，因为BST的中序遍历序列是呈升序的，因此如果题目给的二叉树的中序遍历序列递增，这棵树就是二叉搜索树的特性。 | 0.5√ |
| 7-32 | 哥尼斯堡的“七桥问题” | DS-7-32.cpp | 考察对无向图中是否有欧拉回路的判断。无向图中如果有欧拉回路，那么图中所有顶点都是连通的，且每个顶点的度数都是偶数。判断连通性时用到了并查集。 | √ |
| 7-33 | 地下迷宫探索 | DS-7-33.cpp | 本题采用深度优先搜索遍历DFS即可解决，需要注意的是，本题还需要打印出遍历中回溯的路径。 | |
| 7-34 | 任务调度的合理性 | DS-7-34.cpp / 栈辅助拓扑排序: DS-7-34-withStack.cpp |
本题需要判断一张图是不是AOV网，也就是要判断是不是无环的有向图。我采用了卡恩拓扑排序算法，也就是比较常用的“拆0入度顶点”的方法。// 值得注意的是，拓扑排序可以用栈辅助储存所有0入度的顶点以优化运行时间。 | |
| 7-35 | 城市间紧急救援 | DS-7-35.cpp | 和题7-9一样是采用Djikstra算法，但更进一步。不仅有涉及两个因素的最短路径的取舍，同时还考察了最短路径的记录与输出以及对等长最短路径条数的统计。 ------ 其中最值得回味的是统计最短路径条数: 额外借助一个数组 pathNum，用pathNum[i]标记从起点到顶点i的最短路径条数。当更新最短路径长时，对顶点最短路径条数进行赋值；而出现等长最短路径时，就得对顶点最短路径条数进行累加。 |
√ |
| 7-36 | 社交网络图中结点的“重要性”计算 | DS-7-36.cpp | 常规的最短路径题，可以用Dijkstra高效求解。本题给出的是一张无权无向图，因此我默认所有边的权为1。 |
|
| 7-37 | 模拟EXCEL排序 | DS-7-37.cpp | 选择一种排序算法(稳定性无所谓)来对包含多字段的元组进行排序。这里我采用了STL的priority_queue，辅以运算符重载实现了堆排序。快速排序更快(像STL的sort函数就有快排实现)，但我还没完全理解。稍后理解了我会在排序题7-12中写一下。 |
|
| 7-38 | 寻找大富翁 | DS-7-38.cpp | 从题目看是比较明显的“TopK”问题，也就是从可能的大规模序列中找出前K个最大的数值，适合用堆排序。我的解法是维护一个存放K个最大数的小根堆(优先队列)。具体维护方法是: 读入数值时如果遇到比堆顶元素还大的数就弹出堆顶，将新数值加入堆中。 | |
| 7-39 | 魔法优惠券 | DS-7-39.cpp | 分别且成对计算负值优惠券和商品以及正值优惠券和商品所得总回报，不一定要用完所有优惠券，回避所有“倒贴”的情况。具体解题上可以借助快排或者堆排序进行解决。 | |
| 7-40 | 奥运排行榜 | DS-7-40.cpp | 本质是考察排序的题，但对于并列排名的处理值得琢磨。我的解法是把每个国家的每种计算方式下的排名都算出来，并进行并列处理。在最后查询国家排名时，只需要从国家每种计算方式下的排名中选出最小的排名即可。 这题是我不擅长的重复项处理题，之前类似的题有多项式合并。 |
0.5√ |
| 7-41 | PAT排名汇总 | DS-7-41.cpp 测试数据生成脚本: randomRank7-41.js |
题7-40的升级版，仍然考察的是排序+并列排名处理。先对每个分区进行排序，算出每个分区内考生的排名，然后再对全部考生进行排序，算出总排名即可。 | |
| 7-42 | 整型关键字的散列映射 | DS-7-42.cpp | 哈希表的简单实现，哈希碰撞的解决方法是开放定址法。 | |
| 7-43 | 字符串关键字的散列映射 | DS-7-43.cpp | 字符串哈希表的实现。字符串哈希常用的方法就是将字符串看作某种进制的数，并将其转换为十进制数再进行哈希。 本题采用的碰撞处理方法是平方探测法，值得注意的是向前探测的时候小心下标越界。 |
√ |
| 7-44 | 基于词频的文件相似度 | DS-7-44.cpp | 考察字符串哈希和大规模数据的文件比对。 在读入数据的时候，首先要对单词进行去重，这里我采用了哈希表对已经加入文件的单词进行标记。在比对文件单词的时候，同样要用到哈希表对存在于其中一个文件的单词进行标记，从而找出两个文件中共有的单词数。本题我巩固了一下字符串哈希表的实现，挺值得回味的。 |
√ |
| 7-45 | 航空公司VIP客户查询 | DS-7-45.cpp | 仍然考察字符串哈希。本题要计算哈希值的字符串是一串身份证号，实际上只需要提取身份证号中的一部分来计算哈希即可。这个题解中我提取的是身份证号的前6位和后4位。 | |
| 7-46 | 新浪微博热门话题 | DS-7-46.cpp | 仍然考察字符串哈希，不过本题更注重分词的处理，同时本题还比较类似题7-44，需要对同一段文本的相同关键词进行去重操作。 做好了分词/去重这两步，剩下只需要遍历哈希表元素统计出结果即可。 |
0.5√ |
| 7-47 | 打印选课学生名单 | DS-7-47.cpp | 排序题，有点类似桶排序。每个课程就像一个桶，而题目指定了哪些学生该放在哪些桶里，最后只需要对每个桶进行字典序排序即可。 | |
| 7-48 | 银行排队问题之单窗口“夹塞”版 | DS-7-48.cpp 测试数据生成脚本: randomQueue7-48.js |
这题我觉得是挺综合的，考验对细节和临界情况的把握。 这里我先利用哈希表对每位顾客进行编号，然后利用并查集来储存顾客之间的朋友关系，最后用链表维护顾客排队形成的队列，依此解决问题。 解题核心代码实际上是围绕着链表的，因此还要注意指针变量的管理。 |
√ |
| 7-49 | 打印学生选课清单 | DS-7-49.cpp | 普通的字符串哈希题。用字符串作为键来访问哈希表，表中储存每个学生的选课信息即可。 | |
| 7-50 | 畅通工程之局部最小花费问题 | DS-7-50.cpp | 考察最小生成树算法，本题我采用的是Kruskal算法。 值得注意的是本题有坑——有些路已经事先建好了，也就是说，在用Kruskal算法之前，要先把所有已经建好的路(边)加入到图中。 ！！！不要把事先已经存在的边交给最小生成树算法处理！！！ |
√ |
| 7-51 | 两个有序链表序列的合并 | DS-7-51.cpp | 本题的核心思路十分类似于归并排序的序列合并过程，只不过本题的数据是储存在链表中的。 值得回味的地方是，在扫描两条链表时，如果有一条链表已经为空，可以直接把另一条链表的剩余节点接到结果中。 |
0.5√ |
| 7-52 | 两个有序链表序列的交集 | DS-7-52.cpp | 和7-51题一样是维护两个指针变量，分别对两个链表进行扫描，适时移动指针，找到相同值的元素即可。 注：这里的“交集”允许有重复元素出现。 |
|
| 7-53 | 两个有序序列的中位数 | DS-7-53.cpp | 题目给的仍然是两个有序序列。这里因为需要直接访问中位数，因此采用可随机存取的数组来作为储存结构。 合并两个有序序列的方式和归并排序中的完全一致。 |
当我脑袋过载的时候，往往找不出我写的代码到底错在哪了。为了方便快速找出错误，我写了一些辅助脚本来辅助我调试。
注: 这些脚本我是没有任何维护计划的，因此写的很随心所欲，能跑就行。
注: 这是一个
bash脚本。
./compare.sh <程序1执行指令> <程序2执行指令> <测试文件刷新脚本> <测试数据文件路径>
- 程序1和程序2的顺序可以调换，只是影响最后的比对展示。
- 其中一个程序是错误题解的代码编译出来的，另一个则是正解代码编译出来的。
- 测试文件刷新脚本是用来生成测试数据的脚本，我写的主要是
JavaScript脚本。 - 测试数据文件路径是测试数据文件的路径，我写的脚本一般会输出到同目录下的
testdata.txt。
举例:
./compare.sh ./DS-7-41-WA.exe ./DS-7-41-AC.exe 'node randomRank7-41.js 10 5' ./testdata.txt
- 脚本会不停调用
node randomRank7-41.js 10 5生成测试数据 - 生成的测试数据会被作为输入传入
./DS-7-41-WA.exe和./DS-7-41-AC.exe中 - 然后比对两个程序的输出，如果不一致，就会输出不同的地方；如果一致就继续生成新的测试数据，直到两个程序的输出不一致为止。
咱写了测试数据生成脚本的几题: