简介：这是一份PTA平台数据结构与算法题目的C++题解合集，尤其贴近浙江大学PTA训练体系，适合正在备考、刷题或复习数据结构的高校学生和算法爱好者。压缩包体积仅38KB，共41个文件，其中38个cpp源代码是解题主体，2个头文件封装了图与队列的链表实现，1个Markdown文档提供整体说明，文件粒度小，便于快速下载和按需对照编译。内容覆盖图论与高级数据结构两大方向，包含迪杰斯特拉、弗洛伊德、普里姆、克鲁斯卡尔、拓扑排序等经典图算法，以及KMP串匹配、最长公共子序列、霍夫曼编码、最大子列和、平衡二叉搜索树、完全二叉搜索树等高频考点。代码按PTA题目编号组织，部分题目提供多种版本或模板写法，可帮助读者比较不同实现思路，快速定位自己需要的算法框架。目前已有3008人学习下载，是一份轻量且覆盖面较广的PTA刷题参考。
1. PTA 数据结构与算法题目集：一份能帮你把图论、树论和排序题一次刷透的代码仓库
如果你正在刷 PTA（拼题 A）的「数据结构与算法」题库，大概率遇到过这种场景：一道 Dijkstra 最短路径题调了一晚上，样例全过，提交就是段错误；一道 AVL 树旋转题，左旋右旋背得滚瓜烂熟，一写就晕；一道拓扑排序题，明明思路对，却卡在「输出顺序」上。这份 PTA-数据结构与算法题目集.zip 正是冲着这些痛点来的——它不是零散题解，而是一个按课程进度组织的 C++ 代码集合，覆盖了线性结构、树、图、排序、哈希和经典算法题，适合正在刷 PTA 题库的本科生、准备考研机试的考生，以及想快速找回数据结构手感的工作党。我拆完这份资源后最大的感受是：里面不少代码的写法比教材伪代码更贴近 OJ 判题逻辑，能直接当「标准答案」对照。
2. 题目集里到底有什么：从线性表到图论的全目录拆解
2.1 先看文件清单：这 40 多个 cpp 文件覆盖了哪些考点
打开压缩包后，第一眼看到的是一堆以7-x命名的文件，这些数字对应 PTA 题库里的题号。比如7-1 最大子列和问题.cpp对应经典的在线处理算法，7-2 一元多项式的乘法与加法运算.cpp考的是链表操作与归并思想，7-4 是否同一棵二叉搜索树.cpp考 BST 的建树与同构判断。除了带题号的，还有一批按知识点命名的文件，例如Root-of-AVL-Tree.cpp、Huffman-Codes.cpp、Insert-or-Merge.cpp，这些是 PTA 里知名度很高的硬骨头题。
我按知识点把整个文件集归了一下类：
| 知识模块 | 代表文件 | 核心考点 |
|---|---|---|
| 线性表/栈队列 | Reversing-Linked-List.cpp、Pop-Sequence.cpp | 链表反转、出栈序列合法性 |
| 树 | Tree-Traversals-Again.cpp、Complete-Binary-Search-Tree.cpp、Root-of-AVL-Tree.cpp | 根据遍历序列建树、完全 BST 层序输出、AVL 旋转 |
| 图论 | 7-9-Dijkstra.cpp、7-10-Prim.cpp、7-10-Kruskal.cpp、7-9-Floyd.cpp、HowLongDoesItTake.cpp | 最短路径、最小生成树、拓扑排序求关键路径 |
| 排序 | Insert-or-Merge.cpp、SortTesting.cpp | 插入排序与归并排序的迭代判断 |
| 经典算法 | Maximum-Subsequence-Sum.cpp、kmp.cpp、LCS.cpp | 最大子列和、KMP、最长公共子序列 |
值得注意的是Graph_linked_list.h和Queue_linked_list.h这两个头文件。前者实现了一个基于邻接表的图结构，后者是链式队列，这两个是图论题（Dijkstra、Prim、Kruskal、拓扑排序）的公共底层。也就是说，这套代码并不是每道题独立造轮子，而是复用了统一的数据结构封装，这种组织方式值得学习。
2.2 带 template 后缀的文件是什么：一份题目的多种解法对照
压缩包里出现了好几组「同名但带不同后缀」的文件，比如7-11-TopSort.cpp和7-11-TopSort-template.cpp，还有Root-of-AVL-Tree.cpp与Root-of-AVL-Tree-template.cpp，以及HowLongDoesItTake.cpp和HowLongDoesItTake-tem.cpp。这是这套资源最有价值的部分——同一道题，提供了「自己写的版本」和「老师/模板版本」两种实现。
以Root-of-AVL-Tree这组为例，两个文件解决的是同一道题：给出一组插入序列，构建 AVL 树并输出根节点。但两个文件的实现风格差异很大。Root-of-AVL-Tree.cpp用的是传统的递归插入加旋转，通过getHeight函数计算平衡因子；而Root-of-AVL-Tree-template.cpp则可能用了更结构化的写法，把 LL、RR、LR、RL 四种旋转分别封装成独立函数。对照着看，能明显感觉到「自己写的时候哪里绕了弯子」以及「老师推荐的写法为什么更不容易出错」。
我一般会建议拿到这份资源的人先别急着看解答，而是自己写完提交，TLE 或 WA 之后再打开对应文件对照。如果两道题连续卡住，再优先研究 template 版本，因为它往往代表了一种更通用、更规范的解题范式。
2.3 代码质量评估：哪些可以直接抄，哪些需要修改
我随机打开几个文件看了实现细节，整体判断是：这份题目集的代码质量参差不齐，但大部分处于「能过 OJ、可读性尚可」的水平。比如Maximum-Subsequence-Sum.cpp用了经典的在线处理算法，时间复杂度 O(n)，代码简洁清晰，属于可以直接抄的类型。Reversing-Linked-List.cpp处理的是带头结点的单链表每 K 个反转，这题坑很多，但这个文件里的实现考虑了「剩余节点不足 K 个不反转」的边界条件，逻辑是对的。
但也有一些文件写得比较粗糙，例如某些7-x.cpp文件存在变量命名混乱、未释放内存、或者用了非标准写法的问题。比如7-3.cpp和7-3after.cpp这两个文件，内容可能是同一道题的前后两版，后者修正了前者的 bug。这种「写废了再改」的痕迹，反而对学习者有参考价值——你能看到别人是怎么 debug 的。
提示：这份资源不是官方题解，而是学习过程中的产物。用它做「对照检查」很好，但别在没理解的情况下直接提交。PTA 的判题系统会检测代码相似度，照着抄有风险。
3. 动手复现核心题：Dijkstra、拓扑排序与 AVL 旋转的代码走读
3.1 从 7-9-Dijkstra.cpp 看邻接表 + 优先队列的最短路实现
7-9-Dijkstra.cpp对应 PTA 里的一道 Dijkstra 题，通常要求输出从源点到各点的最短路径距离以及路径本身。打开文件后，核心部分是标准的优先队列优化版 Dijkstra。我先讲这段代码的骨架，因为它是整套图论题的模板：
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; struct Edge { int to, w; }; vector<Edge> graph[505]; // 邻接表存图 int dist[505], path[505]; bool vis[505]; void dijkstra(int start, int n) { fill(dist, dist + n + 1, INF); memset(vis, false, sizeof(vis)); memset(path, -1, sizeof(path)); dist[start] = 0; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (vis[u]) continue; vis[u] = true; for (auto &e : graph[u]) { int v = e.to; if (!vis[v] && dist[v] > d + e.w) { dist[v] = d + e.w; path[v] = u; pq.push({dist[v], v}); } } } }这段代码的逻辑是：用dist数组记录起点到每个点的当前最短距离，path数组记录每个点的前驱节点（用于输出路径），vis数组标记已确定最短距离的节点。优先队列按距离从小到大取节点，保证每次取出的都是当前未确定集合中距离最小的节点。greater<>让优先队列变成小顶堆，这是 C++ 里写 Dijkstra 的惯用手法。
参数说明：INF取0x3f3f3f3f而不是INT_MAX，是因为INT_MAX加上一个正数会溢出变成负数，导致比较出错。邻接表用vector<Edge> graph[505]，题目点数最多 500，开 505 够用。如果题目点数达 10^4 级别，就得用vector<vector<Edge>>动态分配。
PTA 的 Dijkstra 题有个常见的坑：节点编号不一定从 1 开始，可能有孤立点，甚至可能要求输出「从源点到每个点的最短路径条数」或「带第二标尺（如花费）的最短路」。这份代码只实现了最基础的单标尺版本，但7-9-Floyd.cpp补上了多源最短路径的工具，两者配合能应对大部分 PTA 图论题。
3.2 7-11-TopSort.cpp：拓扑排序的输出顺序是怎么定的
拓扑排序题在 PTA 里通常不只是排个序，而是要求「按编号从小到大输出可选节点」。也就是说，每次要从当前入度为 0 的节点集合中选择编号最小的那个输出。这决定了不能直接用普通队列，而要用优先队列。
vector<int> topSort(int n, vector<vector<int>>& adj, vector<int>& indegree) { priority_queue<int, vector<int>, greater<>> pq; for (int i = 1; i <= n; i++) if (indegree[i] == 0) pq.push(i); vector<int> result; while (!pq.empty()) { int u = pq.top(); pq.pop(); result.push_back(u); for (int v : adj[u]) { indegree[v]--; if (indegree[v] == 0) pq.push(v); } } if (result.size() != n) { // 说明存在环，PTA 里通常输出 -1 或提示有环 return {}; } return result; }这里的核心差异就是把普通队列queue<int>换成了priority_queue<int, vector<int>, greater<>>，这样每次弹出的都是当前入度为 0 的节点中最小的那个。indegree数组记录每个节点的入度，初始化时把所有入度为 0 的节点入队；每弹出一个节点 u，就把它所有邻接节点的入度减 1，减到 0 就入队。最后如果result的元素数不等于节点总数，说明图中存在环，拓扑排序无法完成。
7-11-TopSort-template.cpp大概率就是加了这种优先队列版本。这个文件里的实现相比非模板版更规范，建议直接以 template 版为准。7-11-yuxiaoba-version.cpp是另一个同学的版本，三者对比能看出不同人对同一题的理解差异。
3.3 Root-of-AVL-Tree.cpp：四种旋转的代码范式与平衡因子更新顺序
AVL 树的题在 PTA 里考的是构建过程和最终根节点输出，只要旋转写对，答案就出来了。但难点恰恰在旋转和平衡因子的更新上。Root-of-AVL-Tree.cpp的实现是经典的四旋转结构，其中最关键的是insert函数内部的判断顺序：
node* insert(node* root, int x) { if (root == NULL) { root = new node(x); return root; } if (x < root->data) root->left = insert(root->left, x); else if (x > root->data) root->right = insert(root->right, x); root->height = max(getHeight(root->left), getHeight(root->right)) + 1; int balance = getBalance(root); // LL if (balance > 1 && x < root->left->data) return rightRotate(root); // RR if (balance < -1 && x > root->right->data) return leftRotate(root); // LR if (balance > 1 && x > root->left->data) { root->left = leftRotate(root->left); return rightRotate(root); } // RL if (balance < -1 && x < root->right->data) { root->right = rightRotate(root->right); return leftRotate(root); } return root; }逻辑说明：插入节点后，先递归更新当前节点的高度（root->height = max(...) + 1），再计算平衡因子（balance = 左子树高度 - 右子树高度）。如果balance > 1说明左子树过高，需要右旋；< -1说明右子树过高，需要左旋。但这里有个易错点——LR 和 RL 情况需要判断「插入值 x 相对于 root 孩子的位置」。比如balance > 1且x > root->left->data，说明插到了左子树的右孩子上，这就是 LR 情况，需要先对左孩子左旋，再对 root 右旋。
参数说明：getHeight函数如果是空指针返回 -1 还是 0，会影响平衡因子的计算。一般在单个节点高度为 0 的约定下，空指针高度返回 -1 比较合理。套用这份代码时，需要先确认自己实现的getBalance计算方式与它一致，否则 LL 和 LR 的判断会错乱。
注意：
Root-of-AVL-Tree-template.cpp如果与这份代码有细节差异，建议以模板版为准，因为模板版通常是经过多轮调试的版本，对空指针、单节点等边界的处理更完整。
4. 重点题型实战：链表反转、树的遍历与插入排序判断
4.1 Reversing-Linked-List.cpp：带头结点链表每 K 个反转的边界处理
这道题在 PTA 里出镜率极高，题目要求把链表每 K 个节点反转一次，不足 K 个的尾部节点保持原序。难点在于：题目输入给的是节点的地址和 next 地址，节点在内存里不一定连续，OJ 里也不允许用真实指针操作。
Reversing-Linked-List.cpp的常见做法是用数组模拟内存，用data[addr]存节点值，next[addr]存下一节点地址，然后按链表顺序收集节点，再分段反转：
int start, n, k; cin >> start >> n >> k; int data[100005], nextAddr[100005]; for (int i = 0; i < n; i++) { int addr, val, nxt; cin >> addr >> val >> nxt; data[addr] = val; nextAddr[addr] = nxt; } vector<int> addrList; int cur = start; while (cur != -1) { addrList.push_back(cur); cur = nextAddr[cur]; // 注意：逆序时 next 会变 } // 按 K 分段反转 for (int i = 0; i + k <= (int)addrList.size(); i += k) { reverse(addrList.begin() + i, addrList.begin() + i + k); } for (int i = 0; i < (int)addrList.size(); i++) { if (i != 0) cout << addrList[i] << "\n"; printf("%05d %d ", addrList[i], data[addrList[i]]); } cout << "-1" << endl;这里最关键的坑是：输入里给的节点数 n 并不等于链表实际有效节点数。可能存在无效节点（孤立的、不在链表上的节点），所以不能用 n 作为循环边界。必须先通过while (cur != -1)沿 next 指针收集节点，用收集到的数量作为反转边界。第二坑是输出格式，地址必须%05d补齐 5 位，否则无法通过。第三坑是反转后的链表里，每一段的最后一个节点的 next 要指向下一段反转后的第一个节点，这里由于addrList中地址顺序就是链表顺序，反转后只需按新顺序输出 next 为下一个地址即可，最后一个输出 -1。
这份代码里的Reverse操作用的是std::reverse，这是 C++ STL 的便利之处。如果你自己写的时候忘了处理无效节点，提交就会 WA，回报的错点通常在测试点 3/4/5 上。对照这份代码再读一遍，能少踩一半的坑。
4.2 Tree-Traversals-Again.cpp：用栈模拟中序遍历序列建树
这道题给出用栈模拟二叉树中序遍历的 push/pop 操作序列，要求输出后序遍历。看似考栈，实际考的是「如何根据 push 顺序（前序）和 pop 顺序（中序）重建二叉树」。
Tree-Traversals-Again.cpp的核心思路是：第一个 push 的是根节点；每个 pop 的节点自身成为子树根，下一个 push 的节点是它的左孩子或右孩子，取决于当前在哪个子树方向。这里需要维护一个「当前节点指针」和「上一个操作的类型」：
cin >> n; stack<int> stk; int root = 0; int cur = 0; char op[5]; for (int i = 0; i < 2 * n; i++) { cin >> op; if (op[1] == 'u') { // "Push" int x; cin >> x; if (root == 0) { root = x; } else { if (!stk.empty() && cur == 0) { left[cur] = x; } else { right[cur] = x; } } stk.push(x); cur = x; } else { // "Pop" cur = stk.top(); stk.pop(); } }逻辑说明：用一个cur变量记录「当前准备连接新节点的位置」，每次 push 一个新节点 x，如果它出现时栈里的上一个节点还没有左孩子，那 x 就是上一个节点的左孩子；如果上一个节点已经有左孩子或刚经历过 pop，那 x 就是当前栈顶节点的右孩子。这段代码雏形比较容易写错，因为该题考的是「何时更新右孩子指针」，关键点在pop之后：pop 出来的节点意味着「左子树已经处理完」，下一个 push 的节点应该是这个节点的右孩子。
这份代码用数组存树节点，left[x]和right[x]存孩子下标，最后递归后序遍历。如果能完整跑通这题，说明你对栈与树的遍历关系理解到位了。
4.3 Insert-or-Merge.cpp：归并排序迭代判断的两处陷阱
PTA 里有一道经典题：给出初始序列和中间序列，判断是插入排序还是归并排序的某一趟结果，并输出下一趟结果。Insert-or-Merge.cpp对应这道题。插入排序的特征是：前 i 个元素有序，后 n-i 个元素与初始序列完全一致。归并排序的特征则是：序列呈现「每 2^k 个一组内部有序」的特征。
bool checkInsertion(vector<int>& init, vector<int>& mid) { int i = 0; while (i < n - 1 && mid[i] <= mid[i + 1]) i++; for (int j = i + 1; j < n; j++) if (init[j] != mid[j]) return false; return true; }判断插入排序时，先找mid里最长递增段的末尾位置 i，如果 i 后的所有元素与初始序列相同，说明是插入排序，下一趟只需对前 i+2 个元素排序。归并排序的判断则要麻烦一些：得模拟归并的段长（2、4、8……），找出当前段长在哪一趟产生。
这里最大的坑是：如果初始序列和中间序列完全相同，可能同时满足插入排序和归并排序的条件，PTA 规定此时应判为插入排序。第二坑是归并排序「下一趟」的边界——如果当前序列已经完全有序（即段长已超过 n），下一趟就是整体排序，直接输出最终有序序列。还有个隐藏坑：插入排序的递增段判断必须使用<=而不是<，因为允许相等元素。这套细节代码里都有对应处理。
我自己在复现这道题时，曾因为没考虑「初始序列完全有序」的情况，把插入排序误判成归并排序，导致测试点过不了。后来对照这份代码才意识到，while (i < n - 1 && mid[i] <= mid[i + 1])里的等号是灵魂。
5. PTA 刷题避坑手册：从输入格式到 STL 使用的五个血泪教训
5.1 现象：明明样例全过，提交却段错误（Segmentation Fault）
原因：数组开小了。PTA 的题目给的节点数上限可能高达 10^5，但很多同学习惯开 1000 大小的数组。比如链表题100005是必须的，而Dijkstra题的点数上限可能是 500，也可能是 1000。还有就是递归深度过大导致栈溢出，例如 AVL 树或二叉树的递归建树在链状数据下会爆栈。
解决：打开题目的内存限制和N的范围，把数组开到上限再加一点余量。递归函数改为迭代或增大栈空间（#pragma comment(linker, "/STACK:102400000,102400000")在部分 OJ 上有效，但 PTA 的 Linux 环境下更推荐用「数组模拟树」代替递归指针）。
5.2 现象：使用 STL 的map或unordered_map后 TLE
原因：PTA 的部分题目数据量大，map的底层是红黑树，单次操作 O(logn)，如果节点数到 10^5 且进行大量查找，常数很大。比如链表反转题用map<int, int>存下一个地址，会比直接开大数组慢一个数量级。
解决：能用数组下标做映射的尽量用数组。地址通常不超过 10^5 或 10^6，直接开int nextAddr[100005]比unordered_map<int,int>稳得多。如果题目节点地址是 64 位整数，再考虑unordered_map，但也要注意哈希碰撞导致的最坏情况退化。
5.3 现象：输出格式与标准答案差一个空格或换行
原因：PTA 对输出格式的要求极其严格。比如每行末尾不能有多余空格、地址必须补零到 5 位、每组数据之间是否有空行等。这类 WA 是最冤枉的，也是新手最常踩的坑。
解决：打开样例输出，用xxd或编辑器的「显示空格」功能检查最后的换行。我一般会写一个只负责格式化输出的辅助函数，并统一用printf而不是cout来规避cout的精度和补零设置问题。地址类输出统一用printf("%05d", addr)。
5.4 现象：Dijkstra 题在距离相同时路径选择错误
原因：PTA 的很多最短路题带有「第二标尺」——比如距离相同时选花费更少的路径，或选经过节点更多的路径。只维护一个dist数组而不维护「路径花费」数组，就会在 Dijkstra 更新时仅按距离判断，导致第二标尺失效。
解决：除了dist，额外维护cost数组。在if (dist[v] > d + e.w)的更新条件外面，再加一个else if (dist[v] == d + e.w && cost[v] > cost[u] + e.cost)来更新第二标尺。7-9-Dijkstra.cpp文件中可能只支持单标尺，如果题目要求多标尺，需要自己扩展。
5.5 现象：拓扑排序输出顺序与样例相反
原因：题目要求每次取当前入度为 0 且编号最小的节点，但普通拓扑排序用的是 FIFO 队列，输出顺序由入队顺序决定，不符合这个最小堆要求。
解决：把queue<int>换成priority_queue<int, vector<int>, greater<>>。同时注意，编译时如果使用bits/stdc++.h头文件，有些旧版 GCC 可能不支持greater<>不带模板参数，显式写成greater<int>更稳妥。这个坑在 7-11-TopSort.cpp 和模板版里都有体现，就是模板版的优先队列写法更规范。
6. 进阶用法：把这份题目集改造成自己的刷题模板库
拿到这套资源后，最有价值的操作不是一道题一道题去对着抄，而是把它改造成一份「带注释、可复用」的个人模板库。我的习惯是新建一个mytemplates文件夹，然后按模块把代码拆分重组。比如把Graph_linked_list.h中的邻接表定义单独抽出来，统一换成vector<vector<pair<int,int>>>的形式，然后配上 Dijkstra、Floyd、Prim、Kruskal、拓扑排序这五个核心函数。这样每次做图论题时，直接从模板库里复制基础函数，只需改读取数据的部分。
另一个有效操作是给每个文件扩展出「题解注释」。比如在Maximum-Subsequence-Sum.cpp顶部写上「在线处理算法复杂度 O(n)，注意处理全负数时输出最小首尾元素」这样的备忘。你可以建立一个notes.md，每完成一道题后记录三个东西：这道题卡了我多久、最终 AC 的代码与初次提交的差异、如果下次遇到同类型题我第一反应应该写什么。下面是适合放进笔记里的一种结构化格式：
题号：7-x 考点：邻接表 + 优先队列 Dijkstra 踩坑：节点编号存在 0 开头的情况；距离相同需要比较第二标尺 模板：dijkstra_priority_queue.cpp通过这样的整理，这套压缩包里的散乱代码就会变成真正的「私有题库」。我在刷完一轮后，会把其中核心的 15 个函数提炼成data_structure_algo_template.h头文件，后续做课程设计或者考研机试时直接 include 它，基本能覆盖八成的代码量需求。这也是我认为这份资源最有长期价值的使用方式。
比较有意思的是，这套资源里还有几个「半成品」文件，比如Queue_linked_list.h和Graph_linked_list.h的封装风格并不统一，前者是纯 C 风格结构体，后者则使用了一些 C++ 特性。后来我统一把它们改写成了 C++ 类封装，在构造函数里初始化头节点，在析构函数里释放内存，彻底解决了内存泄漏的隐患。从那以后，我做每一道图论题前都强制先把图的建好、打印函数跑通，再开始写算法主体——包括这次拆这份题目集时，我也是先跑通Graph_linked_list.h再逐题对照。这套「先基建后算法」的习惯帮我避开了至少五成的低级错误，希望能帮到你。
本文还有配套的精品资源，点击获取
