尧图网站建设 
简介这份PTA-数据结构与算法题目集压缩包面向正在刷题备考或复习数据结构的本科生与考研人群集中整理了浙江大学PTA平台中常见的算法实现与解题模板。包内共41个文件以38个C源文件为主辅以2个头文件和1个说明文档覆盖图论、树、排序、字符串匹配等经典专题如Dijkstra、Floyd、Prim、Kruskal、拓扑排序、AVL树、堆、KMP、LCS等每个文件对应一道题目的完整可运行解答便于对照思路或直接调试。压缩包仅38KB轻量便携可快速下载使用。目前已有3008人学习下载是PTA刷题者积累代码模板、查漏补缺的实用参考尤其适合需要系统梳理算法实现细节的读者。1. 拿到PTA数据结构题目集先别急着敲代码这份压缩包该怎么用PTAProgramming Teaching Assistant是高校计算机课程常用的在线评测系统数据结构与算法题目集则是里面流传最广的一份训练包。很多人从老学长手里拷贝到PTA-数据结构与算法题目集.zip解压后看到一堆.c/.cpp文件和题面文档误以为这是答案包或题库源码其实它是一个可以当作本地题库、对拍器和模板仓库的宝贵资源。这篇笔记想帮你把它变成真正能提升数据结构和算法能力的训练工具而不是躺在硬盘里的僵尸文件。适合正在上数据结构课、准备考研408或天梯赛的C/C学习者也适合辅导学生刷题的一线教师。压缩包里的题目大多是函数实现题和编程题混合刷法与LeetCode完全不同下面从考点、流程、避坑到复用逐步拆开。2. 题目集里的高频考点线性表、树与图怎么刷才能不白费2.1 线性表题型链表操作与数组下标的取舍数据结构题目集里线性表占了近三分之一。常见题型有求链式表的表长、带头结点链表的就地逆置、两个有序链表的合并。这些题在OJ上的输入往往是一串整数第一行给N第二行给N个元素。但PTA有个特点很多题目要求你补全函数而不是写完整程序。比如带头结点的单链表就地逆置它给的是下面这样的函数签名void ReverseList(List L);你需要直接操作链表L把next指针倒过来。这里有个常见坑题目给的链表可能带头结点也可能不带头函数内部要自己判断。我一般这么写带头结点版本void ReverseList(List L) { if (L NULL || L-Next NULL) return; List p L-Next, q NULL, next; L-Next NULL; // 断开头结点与第一个数据结点 while (p) { next p-Next; p-Next q; q p; p next; } L-Next q; }逻辑说明p指向当前要处理的原第一个结点q保存已逆置链表的头部每次把p拆下来挂到q的前面最后让头结点的Next指向新的首结点。参数方面ReverseList只接收一个头结点指针所以空链表和单结点链表必须先return否则后面p-Next会空指针访问。测试时如果发现本地样例通过但提交段错误先检查有没有判空。遇到两个有序链表合并我通常会先用数组模拟练一遍再用链表实现一遍。数组模拟的归并逻辑直观能帮你快速确认边界链表实现要特别小心尾指针的更新。PTA里不少题会同时出现输入序列为空的测试点合并函数返回NULL时很多人会漏判空链表。建议写合并时给两个链表都加一个哑结点dummy node这个技巧能把各种空链表分支收敛成统一处理。线性表题型的本质是指针操作边界覆盖所以不需要背太多算法但必须把指针改写的每一步画清楚。2.2 树的题目三种遍历和同构判断的套路树的题目集里最经典的三道是还原二叉树、树的同构、列出叶结点。这些题有个共同点输入给的不是指针而是结点编号和左右孩子编号甚至用字符表示结点比如A、B。你要自己建一个静态结构体数组typedef struct { char data; int left, right; } Node; Node trees[10];通过输入构造两棵二叉树然后判断同构。所谓同构就是可以通过左右孩子互换得到另一棵树。判断函数的核心思路是如果两个结点都为空返回真一个空一个非空返回假数据不同返回假然后递归判断四种交换组合。我习惯写成int Isomorphic(int r1, int r2) { if (r1 -1 r2 -1) return 1; if ((r1 -1 r2 ! -1) || (r1 ! -1 r2 -1)) return 0; if (trees[r1].data ! trees[r2].data) return 0; if (Isomorphic(trees[r1].left, trees[r2].left) Isomorphic(trees[r1].right, trees[r2].right)) return 1; if (Isomorphic(trees[r1].left, trees[r2].right) Isomorphic(trees[r1].right, trees[r2].left)) return 1; return 0; }逻辑说明前两个分支过滤结构不对称的情况第三个分支比较根数据后面两个分支分别对应未交换和交换左右子树两种同构路径。很多初学者会漏掉第二个交换分支导致样例过了但提交只有部分正确。参数方面-1代表空结点所以递归入口要传入两个根下标。这题刷完后树的遍历题基本就通了先序、中序、后序三套递归要背到默写层序遍历用队列实现基于这些可以衍生出求树高、找叶结点、镜像反转、判断完全二叉树。在题目集里遇到由先序和中序构造二叉树本质就是递归切分区间区间索引的偏移量是最容易算错的地方我一般会在纸上画一行数组测试一下边界。2.3 图的题目遍历、最短路和最小生成树的模板该怎么背图在PTA数据集里以列出连通集、六度空间、最短路径问题的改装版等形式出现。列连通集要求用DFS和BFS各输出一次遍历序列。这题建议邻接矩阵版和邻接表版各写一遍。PTA的六度空间题目数据规模常到1000用邻接矩阵做BFS会很慢邻接表加队列才能稳过。void BFS(int start, int n) { int q[MAXN], head 0, tail 0, visited[MAXN] {0}; q[tail] start; visited[start] 1; while (head tail) { int v q[head]; printf(%d , v); for (int i 0; i n; i) { if (adj[v][i] !visited[i]) { visited[i] 1; q[tail] i; } } } }这里用数组模拟队列主要是为了可控和可移植PTA部分旧编译器对STL队列也能用但数组队列在性能上更稳定。注意visited标记必须在入队时置位不能在出队时置位否则同一结点可能被重复入队导致层数统计混乱。参数说明start是起始结点编号n是总结点数adj是全局邻接矩阵。如果换邻接表版内层遍历改成for (int i head[v]; i ! -1; i edge[i].next)复杂度降为O(NE)。最短路和最小生成树建议把Dijkstra、Floyd、Prim、Kruskal整理成固定模板。PTA常考的交通咨询类题经常给N≤500、M≤10000的稀疏图用Dijkstra堆优化最合适。重点是把dist数组初始化为无穷大松弛时用dist[u] w dist[v]判断如果要输出路径就额外开一个pre数组在松弛时更新。Kruskal的并查集模板也值得背用路径压缩加按秩合并能应对绝大多数题。排序调用stdlib里的qsort即可但要注意qsort比较函数的参数类型是const void*这个细节很多同学第一次写会编译报错。图的模板背下来之后题目集里大多数图论题都能套进去难的是识别题目在考哪个模型比如判断是否有回路其实是在考并查集或拓扑排序。3. 把题目集跑通的最小流程从解压到本地评测3.1 解压后先整理目录再动手写代码拿到PTA-数据结构与算法题目集.zip后不要急着点开某个.c文件。先看目录结构通常有按章节分的子文件夹比如02-线性结构、03-树、04-图每个文件夹里有题面txt和若干.c文件。这些.c可能是别人提交的答案、半成品或损坏文件。我的建议是新建一个自己的代码目录把题面单独复制出来把别人的答案移入_bak备份目录和你的代码分开。因为PTA代码文件命名往往是2-1.c这样的数字混在一起三天后就分不清哪个是自己写的。然后做一遍最基础的编译冒烟测试找一题最简单的比如求链式表的表长用gcc编译gcc -stdc11 -Wall -o test 02-1.c注意PTA题目集的代码大多基于C/C用-Wall能提前抓到变量未初始化、函数声明缺失等问题。PTA的GCC版本比较老不支持C11的某些新特性所以我本地用-stdc11而不是gnu11避免用了VLA变长数组后本地通过但OJ编译失败。编译通过后先跑一下题目给的样例能过说明基本语法没问题。这一步虽然简单但能筛掉大量低级错误不要跳过。3.2 用输入输出重定向模拟判题PTA判题时你的程序从标准输入读数据往标准输出写结果。本地手动测试最直接的方法是把样例存成in.txt然后这样运行./test in.txt out.txt再把out.txt和题目给定的输出对比。如果样例没过先在关键位置加printf打印中间值确认是哪一步和预期不符。这里有个血泪经验本地调试时加freopen很方便但提交前一定要注释掉。// 本地调试时打开下面一行提交时注释掉 // freopen(in.txt, r, stdin);我也在提交时忘注释结果OJ上找不到in.txt直接运行时错误。为了记住这茬我会在freopen那行后面写一个TODO注释提交前搜索TODO或者freopen检查。如果你用脚本编译可以在编译命令里顺便执行一个grep检测代码里是否含有freopen有就停下来警告这样能彻底杜绝这个坑。3.3 三个必调参数时间限制、内存限制和输出格式PTA每题都有时间限制常见400ms/1000ms和内存限制64MB或128MB。看题面时先看这两个数字。如果时间限制是400ms说明这题不能靠暴力枚举应对最坏情况要么优化复杂度要么预处理。内存限制64MB就不能开太大的全局数组比如1000×1000的int矩阵是4MB开几个还行10000×10000就是400MB直接超限。如果题目数据规模达到10000图论题就要用邻接表而不是邻接矩阵。输出格式是PTA最挑剔的地方。行尾是否允许多余空格题目里通常写得很清楚。每个元素后面有一个空格意味着最后可以留空格元素之间用一个空格分隔意味着行尾不能有多余空格。我建议封装一个输出函数void print_arr(int a[], int n) { for (int i 0; i n; i) { if (i) putchar( ); printf(%d, a[i]); } putchar(\n); }这函数能解决一半的格式错误。另一个输出坑是调试信息没删比如printf(请输入n: )这在OJ上属于多余输出会直接判答案错误。所以提交前的检查清单里永远有一项代码里不能有任何非题面要求的输出。4. 避坑PTA判题系统的常见问题与排查方法4.1 段错误八成是数组越界或空指针现象提交后显示运行时错误或段错误本地跑样例完全正常。原因最常见三个。数组开太小题面N最大100000你开了10000递归层数太深比如树退化成链DFS递归深度达到NC语言默认栈空间会爆指针操作访问了NULL比如链表或者树遍历时节点为空还继续访问成员。解决先在本地用最大规模数据测试N取题面上限。全局数组普通场景开N5有哨兵需求开N10。递归深度大的题改用非递归遍历用显式栈模拟。链表操作里每次p p-Next之前先判p养成拿到指针先判空的习惯。最有效的排查办法是打开地址消毒器AddressSanitizer编译时加-fsanitizeaddress本地一跑就能告诉你越界发生在第几行。4.2 答案错误先怀疑输入输出格式再怀疑算法现象样例通过提交判答案错误且错误点从小规模到大规模都有。原因PTA每个测试点侧重不同边界。比如二分查找函数题可能会测key小于所有元素、key大于所有元素、数组只有一个元素三种情况。你的程序如果只处理了key存在于数组的场景就会挂。另一类答案错误是输出多余内容比如freopen留下的调试输出、printf提示符OJ比较的是整个stdout。解决把题目描述里提到如果未找到返回0这类条件全部列出来逐一核对。用Python写一个小生成器专门构造边界数据。输出格式错误和答案错误的提示不同如果提示格式错误重点检查空格、换行、行末空格如果提示答案错误则先确认算法逻辑对标准样例的覆盖度再看是否有多余输出。一个非常隐蔽的点是全局变量未初始化PTA的多次调用会复用全局状态函数题里尤其容易踩。4.3 运行超时递归转迭代排序别手写现象提交显示运行超时本地跑最大数据时明显卡顿。原因算法复杂度过高。N10000时O(N²)勉强够N100000时O(N²)基本超时。PTA里的超时还常见于两类递归实现的DFS在链状树上爆栈并超时输入输出用了cin/cout且没关同步比scanf/printf慢数倍。解决先看题目规模估算复杂度。排序直接用qsort不要自己写快排除非题目指定要求手写。递归改循环中序、后序的非递归用栈层序用队列。暴力枚举题如果超时要加剪枝超过当前最优解就return或者排序后提前终止。输入输出方面C语言用scanf/printfC用cin.tie(0); ios::sync_with_stdio(false);或者直接用scanf读整数。极个别题目数据量特别大还可以用自己实现的快读函数但对PTA题目集来说多数题没必要。4.4 编译错误PTA的GCC版本和本地不一致现象本地编译通过提交显示编译错误错误信息指向标准库或某些语法。原因PTA在线编译器通常是GCC 4.8/4.9对C11支持较好但个别标准库特性不完整。比如std::regex在GCC 4.8中容易出问题C11的某些头文件也不全。解决提交前把语言切换成Cgcc而不是Cg很多函数题用C更稳。如果必须用C避免用C11之后的新特性比如auto可以但结构化绑定、可变参数模板慎用。可以在本地装一个稍老的GCC做交叉验证或者统一用gcc -stdc11编译C代码。另一个经验是不要滥用全局宏比如#define int long long在PTA某些编译器上可能引发奇怪错误。4.5 内存超限邻接矩阵换邻接表全局变量别乱开现象提交显示内存超限本地内存够用但OJ有限制。原因图论题里开了一个10001×10001的int邻接矩阵直接400MB。数据结构题常见的内存陷阱是递归栈溢出但这报段错误更多真正的内存超限几乎都是静态数组开太大。解决遇到稀疏图边数远小于N²邻接表是唯一选择。邻接表可以用vector[100010]也可以手写边数组后者在PTA上更可控。如果必须用矩阵用bool代替int可以节省四分之三内存再不够就用bitset。另外局部变量不要开大数组局部大数组在栈上分配可能直接压爆栈改成全局数组最稳妥。动态分配不free不会在OJ上造成问题但频繁malloc/free可能带来性能损耗题目集里能用数组的尽量不用动态结构。5. 把题目集变成本地题库数据生成、对拍与单元测试5.1 用Python生成边界数据覆盖PTA隐藏测试点PTA的测试点设计很刁钻常见的有空输入、单元素、最大N、重复元素、全同元素、元素已经有序升序或降序、负数、大数、浮点精度。任何一道题都要生成这样一组数据自测。下面是一个针对排序题的生成脚本import random # 生成最坏输入完全逆序 n 100000 print(n) print( .join(str(i) for i in range(n, 0, -1)))这个脚本输出n100000的逆序序列专门检验排序算法在逆序输入下的性能。如果你写的是冒泡排序这个数据会直接暴露问题。参数说明range(n, 0, -1)生成从n到1的递减序列join把列表转成字符串print末尾自带换行正好匹配PTA的输入格式。树题要构造退化链每个结点只有一个孩子让树变成一条链递归遍历会爆栈。图题要生成极端稠密和极端稀疏两种以及自环和重边检查你的最短路模板是否处理了重复边。数据生成脚本的核心是刻意制造麻烦而不是随机噪音。我一般会写一个gen.py接受一个参数控制数据规模然后用循环生成多组。对于链式表的题生成整个链表为空、只有一个节点、两个节点的情况就够了。对于树同构题要生成两棵结构相同但数据不同的树以及一棵树的左右子树交换后的输入。这些边界数据往往就是PTA隐藏测试点的思路你提前覆盖了提交时就不慌。5.2 对拍脚本用暴力解法验证你的高效解法对拍是本地验证的黄金方法。跑通样例只证明程序能跑对拍能证明结果正确。常规配置你的解法sol.c、一个暴力解法bf.c、一个数据生成器gen.py。用shell循环不断生成数据比较两个程序的输出#!/bin/bash for i in $(seq 1 1000); do python3 gen.py in.txt ./sol in.txt out_sol.txt ./bf in.txt out_bf.txt if ! diff -q out_sol.txt out_bf.txt /dev/null; then echo Wrong at iteration $i cat in.txt break fi done echo Done这个脚本的逻辑说明seq 1 1000循环生成1000组随机数据sol和bf分别编译成可执行文件diff比较两个输出-q表示只报告不同如果不同打印当前输入并退出。参数说明sol和bf的二进制文件名与源文件名对应如果你用C编译命令要改成对应的ggen.py生成的数据范围必须满足题目约束否则对拍的结果没有意义。对拍的价值在于几分钟内发现隐蔽bug。比如求链表的倒数第K个元素暴力解法可以先把链表存到数组再取倒数第K个然后和你的双指针解法对比小数据下暴力结果一定是正确的。一旦发现不一致用最小复现的输入去调试通常很快定位。我经常在考试前一天对拍一晚上把所有模板题的边界都过一遍。注意对拍脚本要放在题目集目录之外防止被自己误删。5.3 按知识点分组整理模板形成自己的PTA做题手册题目集里的题很多是同一个模板的不同形态。把代码按知识点重组建立以下模板文件会很有价值linked_list.c反转、合并、找中间结点、删除指定结点tree_traversal.c先序、中序、后序、层序递归与非递归graph_basic.c邻接矩阵/邻接表构建DFS、BFS、连通块计数shortest_path.cDijkstra朴素堆优化、Floyd、Bellman-Fordmst.cPrim和Kruskalstring_match.c朴素匹配、KMP的next数组、改进nextsort_utils.cqsort比较函数、归并、堆排、快排固定写法每个文件顶部写一段注释注明适用题型、复杂度、坑位。比如在linked_list.c顶部写反转带头结点链表时先断开头结点合并用哑结点减少判空分支。这套模板在期末考、考研408、天梯赛刷题时能省大量时间。数据结构与算法分析教材里的代码很多是伪代码不能直接提交你需要对照模板改成PTA能接受的完整函数。串的模式匹配题在PTA里经常单独成题KMP的next数组是高频易错点单独建一个string_match.c非常划算。6. 从刷题到考试用这招把PTA成绩变成期末分数6.1 用PTA题目集针对性刷考研408的算法题考研408的算法题分值不高但区分度高常见出题点是线性表、二叉树和排序。PTA题目集里正好覆盖这些片段比如求两个有序序列的中位数是408真题变形还原二叉树就是408常考的由遍历序列构造二叉树。刷的时候不要把题目集当成题库而是当成题型模板库。我备考时会把PTA里所有树的题目刷两遍第一遍完整写代码第二遍只写核心递归函数然后默写。每次默写后对比自己的模板文件找出漏掉的边界。408算法题一般只需要写出算法思路和关键函数PTA的函数题天然适合这种训练边刷边用笔写下复杂度和边界条件考试时就会很从容。6.2 考试前快速复习路线图如果时间仓促临时抱佛脚建议按这个优先级线性表链式操作反转、合并——必考且代码量小树的三种遍历与二叉搜索树的插入删除图的DFS/BFS以及Dijkstra模板排序中的qsort与二分查找边界。每天花半小时用题目集里的题自测重点看最近做错的题。我自己的习惯是考前把避坑清单重新过一遍freopen注释掉了吗数组多开5个了吗行末空格处理了吗变量初始化了吗这四句话救了我很多场考试。这都是血泪经验换来的。PTA题目集不是一个需要膜拜的答案包而是一面照出算法盲区的镜子。希望这篇笔记里的套路和踩坑记录能让你少走弯路刷题时更有底气祝你在PTA和期末里都拿到想要的分数。本文还有配套的精品资源点击获取 PTA数据结构题目集实战攻略：从函数题刷到考试高分
简介这份PTA-数据结构与算法题目集压缩包面向正在刷题备考或复习数据结构的本科生与考研人群集中整理了浙江大学PTA平台中常见的算法实现与解题模板。包内共41个文件以38个C源文件为主辅以2个头文件和1个说明文档覆盖图论、树、排序、字符串匹配等经典专题如Dijkstra、Floyd、Prim、Kruskal、拓扑排序、AVL树、堆、KMP、LCS等每个文件对应一道题目的完整可运行解答便于对照思路或直接调试。压缩包仅38KB轻量便携可快速下载使用。目前已有3008人学习下载是PTA刷题者积累代码模板、查漏补缺的实用参考尤其适合需要系统梳理算法实现细节的读者。1. 拿到PTA数据结构题目集先别急着敲代码这份压缩包该怎么用PTAProgramming Teaching Assistant是高校计算机课程常用的在线评测系统数据结构与算法题目集则是里面流传最广的一份训练包。很多人从老学长手里拷贝到PTA-数据结构与算法题目集.zip解压后看到一堆.c/.cpp文件和题面文档误以为这是答案包或题库源码其实它是一个可以当作本地题库、对拍器和模板仓库的宝贵资源。这篇笔记想帮你把它变成真正能提升数据结构和算法能力的训练工具而不是躺在硬盘里的僵尸文件。适合正在上数据结构课、准备考研408或天梯赛的C/C学习者也适合辅导学生刷题的一线教师。压缩包里的题目大多是函数实现题和编程题混合刷法与LeetCode完全不同下面从考点、流程、避坑到复用逐步拆开。2. 题目集里的高频考点线性表、树与图怎么刷才能不白费2.1 线性表题型链表操作与数组下标的取舍数据结构题目集里线性表占了近三分之一。常见题型有求链式表的表长、带头结点链表的就地逆置、两个有序链表的合并。这些题在OJ上的输入往往是一串整数第一行给N第二行给N个元素。但PTA有个特点很多题目要求你补全函数而不是写完整程序。比如带头结点的单链表就地逆置它给的是下面这样的函数签名void ReverseList(List L);你需要直接操作链表L把next指针倒过来。这里有个常见坑题目给的链表可能带头结点也可能不带头函数内部要自己判断。我一般这么写带头结点版本void ReverseList(List L) { if (L NULL || L-Next NULL) return; List p L-Next, q NULL, next; L-Next NULL; // 断开头结点与第一个数据结点 while (p) { next p-Next; p-Next q; q p; p next; } L-Next q; }逻辑说明p指向当前要处理的原第一个结点q保存已逆置链表的头部每次把p拆下来挂到q的前面最后让头结点的Next指向新的首结点。参数方面ReverseList只接收一个头结点指针所以空链表和单结点链表必须先return否则后面p-Next会空指针访问。测试时如果发现本地样例通过但提交段错误先检查有没有判空。遇到两个有序链表合并我通常会先用数组模拟练一遍再用链表实现一遍。数组模拟的归并逻辑直观能帮你快速确认边界链表实现要特别小心尾指针的更新。PTA里不少题会同时出现输入序列为空的测试点合并函数返回NULL时很多人会漏判空链表。建议写合并时给两个链表都加一个哑结点dummy node这个技巧能把各种空链表分支收敛成统一处理。线性表题型的本质是指针操作边界覆盖所以不需要背太多算法但必须把指针改写的每一步画清楚。2.2 树的题目三种遍历和同构判断的套路树的题目集里最经典的三道是还原二叉树、树的同构、列出叶结点。这些题有个共同点输入给的不是指针而是结点编号和左右孩子编号甚至用字符表示结点比如A、B。你要自己建一个静态结构体数组typedef struct { char data; int left, right; } Node; Node trees[10];通过输入构造两棵二叉树然后判断同构。所谓同构就是可以通过左右孩子互换得到另一棵树。判断函数的核心思路是如果两个结点都为空返回真一个空一个非空返回假数据不同返回假然后递归判断四种交换组合。我习惯写成int Isomorphic(int r1, int r2) { if (r1 -1 r2 -1) return 1; if ((r1 -1 r2 ! -1) || (r1 ! -1 r2 -1)) return 0; if (trees[r1].data ! trees[r2].data) return 0; if (Isomorphic(trees[r1].left, trees[r2].left) Isomorphic(trees[r1].right, trees[r2].right)) return 1; if (Isomorphic(trees[r1].left, trees[r2].right) Isomorphic(trees[r1].right, trees[r2].left)) return 1; return 0; }逻辑说明前两个分支过滤结构不对称的情况第三个分支比较根数据后面两个分支分别对应未交换和交换左右子树两种同构路径。很多初学者会漏掉第二个交换分支导致样例过了但提交只有部分正确。参数方面-1代表空结点所以递归入口要传入两个根下标。这题刷完后树的遍历题基本就通了先序、中序、后序三套递归要背到默写层序遍历用队列实现基于这些可以衍生出求树高、找叶结点、镜像反转、判断完全二叉树。在题目集里遇到由先序和中序构造二叉树本质就是递归切分区间区间索引的偏移量是最容易算错的地方我一般会在纸上画一行数组测试一下边界。2.3 图的题目遍历、最短路和最小生成树的模板该怎么背图在PTA数据集里以列出连通集、六度空间、最短路径问题的改装版等形式出现。列连通集要求用DFS和BFS各输出一次遍历序列。这题建议邻接矩阵版和邻接表版各写一遍。PTA的六度空间题目数据规模常到1000用邻接矩阵做BFS会很慢邻接表加队列才能稳过。void BFS(int start, int n) { int q[MAXN], head 0, tail 0, visited[MAXN] {0}; q[tail] start; visited[start] 1; while (head tail) { int v q[head]; printf(%d , v); for (int i 0; i n; i) { if (adj[v][i] !visited[i]) { visited[i] 1; q[tail] i; } } } }这里用数组模拟队列主要是为了可控和可移植PTA部分旧编译器对STL队列也能用但数组队列在性能上更稳定。注意visited标记必须在入队时置位不能在出队时置位否则同一结点可能被重复入队导致层数统计混乱。参数说明start是起始结点编号n是总结点数adj是全局邻接矩阵。如果换邻接表版内层遍历改成for (int i head[v]; i ! -1; i edge[i].next)复杂度降为O(NE)。最短路和最小生成树建议把Dijkstra、Floyd、Prim、Kruskal整理成固定模板。PTA常考的交通咨询类题经常给N≤500、M≤10000的稀疏图用Dijkstra堆优化最合适。重点是把dist数组初始化为无穷大松弛时用dist[u] w dist[v]判断如果要输出路径就额外开一个pre数组在松弛时更新。Kruskal的并查集模板也值得背用路径压缩加按秩合并能应对绝大多数题。排序调用stdlib里的qsort即可但要注意qsort比较函数的参数类型是const void*这个细节很多同学第一次写会编译报错。图的模板背下来之后题目集里大多数图论题都能套进去难的是识别题目在考哪个模型比如判断是否有回路其实是在考并查集或拓扑排序。3. 把题目集跑通的最小流程从解压到本地评测3.1 解压后先整理目录再动手写代码拿到PTA-数据结构与算法题目集.zip后不要急着点开某个.c文件。先看目录结构通常有按章节分的子文件夹比如02-线性结构、03-树、04-图每个文件夹里有题面txt和若干.c文件。这些.c可能是别人提交的答案、半成品或损坏文件。我的建议是新建一个自己的代码目录把题面单独复制出来把别人的答案移入_bak备份目录和你的代码分开。因为PTA代码文件命名往往是2-1.c这样的数字混在一起三天后就分不清哪个是自己写的。然后做一遍最基础的编译冒烟测试找一题最简单的比如求链式表的表长用gcc编译gcc -stdc11 -Wall -o test 02-1.c注意PTA题目集的代码大多基于C/C用-Wall能提前抓到变量未初始化、函数声明缺失等问题。PTA的GCC版本比较老不支持C11的某些新特性所以我本地用-stdc11而不是gnu11避免用了VLA变长数组后本地通过但OJ编译失败。编译通过后先跑一下题目给的样例能过说明基本语法没问题。这一步虽然简单但能筛掉大量低级错误不要跳过。3.2 用输入输出重定向模拟判题PTA判题时你的程序从标准输入读数据往标准输出写结果。本地手动测试最直接的方法是把样例存成in.txt然后这样运行./test in.txt out.txt再把out.txt和题目给定的输出对比。如果样例没过先在关键位置加printf打印中间值确认是哪一步和预期不符。这里有个血泪经验本地调试时加freopen很方便但提交前一定要注释掉。// 本地调试时打开下面一行提交时注释掉 // freopen(in.txt, r, stdin);我也在提交时忘注释结果OJ上找不到in.txt直接运行时错误。为了记住这茬我会在freopen那行后面写一个TODO注释提交前搜索TODO或者freopen检查。如果你用脚本编译可以在编译命令里顺便执行一个grep检测代码里是否含有freopen有就停下来警告这样能彻底杜绝这个坑。3.3 三个必调参数时间限制、内存限制和输出格式PTA每题都有时间限制常见400ms/1000ms和内存限制64MB或128MB。看题面时先看这两个数字。如果时间限制是400ms说明这题不能靠暴力枚举应对最坏情况要么优化复杂度要么预处理。内存限制64MB就不能开太大的全局数组比如1000×1000的int矩阵是4MB开几个还行10000×10000就是400MB直接超限。如果题目数据规模达到10000图论题就要用邻接表而不是邻接矩阵。输出格式是PTA最挑剔的地方。行尾是否允许多余空格题目里通常写得很清楚。每个元素后面有一个空格意味着最后可以留空格元素之间用一个空格分隔意味着行尾不能有多余空格。我建议封装一个输出函数void print_arr(int a[], int n) { for (int i 0; i n; i) { if (i) putchar( ); printf(%d, a[i]); } putchar(\n); }这函数能解决一半的格式错误。另一个输出坑是调试信息没删比如printf(请输入n: )这在OJ上属于多余输出会直接判答案错误。所以提交前的检查清单里永远有一项代码里不能有任何非题面要求的输出。4. 避坑PTA判题系统的常见问题与排查方法4.1 段错误八成是数组越界或空指针现象提交后显示运行时错误或段错误本地跑样例完全正常。原因最常见三个。数组开太小题面N最大100000你开了10000递归层数太深比如树退化成链DFS递归深度达到NC语言默认栈空间会爆指针操作访问了NULL比如链表或者树遍历时节点为空还继续访问成员。解决先在本地用最大规模数据测试N取题面上限。全局数组普通场景开N5有哨兵需求开N10。递归深度大的题改用非递归遍历用显式栈模拟。链表操作里每次p p-Next之前先判p养成拿到指针先判空的习惯。最有效的排查办法是打开地址消毒器AddressSanitizer编译时加-fsanitizeaddress本地一跑就能告诉你越界发生在第几行。4.2 答案错误先怀疑输入输出格式再怀疑算法现象样例通过提交判答案错误且错误点从小规模到大规模都有。原因PTA每个测试点侧重不同边界。比如二分查找函数题可能会测key小于所有元素、key大于所有元素、数组只有一个元素三种情况。你的程序如果只处理了key存在于数组的场景就会挂。另一类答案错误是输出多余内容比如freopen留下的调试输出、printf提示符OJ比较的是整个stdout。解决把题目描述里提到如果未找到返回0这类条件全部列出来逐一核对。用Python写一个小生成器专门构造边界数据。输出格式错误和答案错误的提示不同如果提示格式错误重点检查空格、换行、行末空格如果提示答案错误则先确认算法逻辑对标准样例的覆盖度再看是否有多余输出。一个非常隐蔽的点是全局变量未初始化PTA的多次调用会复用全局状态函数题里尤其容易踩。4.3 运行超时递归转迭代排序别手写现象提交显示运行超时本地跑最大数据时明显卡顿。原因算法复杂度过高。N10000时O(N²)勉强够N100000时O(N²)基本超时。PTA里的超时还常见于两类递归实现的DFS在链状树上爆栈并超时输入输出用了cin/cout且没关同步比scanf/printf慢数倍。解决先看题目规模估算复杂度。排序直接用qsort不要自己写快排除非题目指定要求手写。递归改循环中序、后序的非递归用栈层序用队列。暴力枚举题如果超时要加剪枝超过当前最优解就return或者排序后提前终止。输入输出方面C语言用scanf/printfC用cin.tie(0); ios::sync_with_stdio(false);或者直接用scanf读整数。极个别题目数据量特别大还可以用自己实现的快读函数但对PTA题目集来说多数题没必要。4.4 编译错误PTA的GCC版本和本地不一致现象本地编译通过提交显示编译错误错误信息指向标准库或某些语法。原因PTA在线编译器通常是GCC 4.8/4.9对C11支持较好但个别标准库特性不完整。比如std::regex在GCC 4.8中容易出问题C11的某些头文件也不全。解决提交前把语言切换成Cgcc而不是Cg很多函数题用C更稳。如果必须用C避免用C11之后的新特性比如auto可以但结构化绑定、可变参数模板慎用。可以在本地装一个稍老的GCC做交叉验证或者统一用gcc -stdc11编译C代码。另一个经验是不要滥用全局宏比如#define int long long在PTA某些编译器上可能引发奇怪错误。4.5 内存超限邻接矩阵换邻接表全局变量别乱开现象提交显示内存超限本地内存够用但OJ有限制。原因图论题里开了一个10001×10001的int邻接矩阵直接400MB。数据结构题常见的内存陷阱是递归栈溢出但这报段错误更多真正的内存超限几乎都是静态数组开太大。解决遇到稀疏图边数远小于N²邻接表是唯一选择。邻接表可以用vector[100010]也可以手写边数组后者在PTA上更可控。如果必须用矩阵用bool代替int可以节省四分之三内存再不够就用bitset。另外局部变量不要开大数组局部大数组在栈上分配可能直接压爆栈改成全局数组最稳妥。动态分配不free不会在OJ上造成问题但频繁malloc/free可能带来性能损耗题目集里能用数组的尽量不用动态结构。5. 把题目集变成本地题库数据生成、对拍与单元测试5.1 用Python生成边界数据覆盖PTA隐藏测试点PTA的测试点设计很刁钻常见的有空输入、单元素、最大N、重复元素、全同元素、元素已经有序升序或降序、负数、大数、浮点精度。任何一道题都要生成这样一组数据自测。下面是一个针对排序题的生成脚本import random # 生成最坏输入完全逆序 n 100000 print(n) print( .join(str(i) for i in range(n, 0, -1)))这个脚本输出n100000的逆序序列专门检验排序算法在逆序输入下的性能。如果你写的是冒泡排序这个数据会直接暴露问题。参数说明range(n, 0, -1)生成从n到1的递减序列join把列表转成字符串print末尾自带换行正好匹配PTA的输入格式。树题要构造退化链每个结点只有一个孩子让树变成一条链递归遍历会爆栈。图题要生成极端稠密和极端稀疏两种以及自环和重边检查你的最短路模板是否处理了重复边。数据生成脚本的核心是刻意制造麻烦而不是随机噪音。我一般会写一个gen.py接受一个参数控制数据规模然后用循环生成多组。对于链式表的题生成整个链表为空、只有一个节点、两个节点的情况就够了。对于树同构题要生成两棵结构相同但数据不同的树以及一棵树的左右子树交换后的输入。这些边界数据往往就是PTA隐藏测试点的思路你提前覆盖了提交时就不慌。5.2 对拍脚本用暴力解法验证你的高效解法对拍是本地验证的黄金方法。跑通样例只证明程序能跑对拍能证明结果正确。常规配置你的解法sol.c、一个暴力解法bf.c、一个数据生成器gen.py。用shell循环不断生成数据比较两个程序的输出#!/bin/bash for i in $(seq 1 1000); do python3 gen.py in.txt ./sol in.txt out_sol.txt ./bf in.txt out_bf.txt if ! diff -q out_sol.txt out_bf.txt /dev/null; then echo Wrong at iteration $i cat in.txt break fi done echo Done这个脚本的逻辑说明seq 1 1000循环生成1000组随机数据sol和bf分别编译成可执行文件diff比较两个输出-q表示只报告不同如果不同打印当前输入并退出。参数说明sol和bf的二进制文件名与源文件名对应如果你用C编译命令要改成对应的ggen.py生成的数据范围必须满足题目约束否则对拍的结果没有意义。对拍的价值在于几分钟内发现隐蔽bug。比如求链表的倒数第K个元素暴力解法可以先把链表存到数组再取倒数第K个然后和你的双指针解法对比小数据下暴力结果一定是正确的。一旦发现不一致用最小复现的输入去调试通常很快定位。我经常在考试前一天对拍一晚上把所有模板题的边界都过一遍。注意对拍脚本要放在题目集目录之外防止被自己误删。5.3 按知识点分组整理模板形成自己的PTA做题手册题目集里的题很多是同一个模板的不同形态。把代码按知识点重组建立以下模板文件会很有价值linked_list.c反转、合并、找中间结点、删除指定结点tree_traversal.c先序、中序、后序、层序递归与非递归graph_basic.c邻接矩阵/邻接表构建DFS、BFS、连通块计数shortest_path.cDijkstra朴素堆优化、Floyd、Bellman-Fordmst.cPrim和Kruskalstring_match.c朴素匹配、KMP的next数组、改进nextsort_utils.cqsort比较函数、归并、堆排、快排固定写法每个文件顶部写一段注释注明适用题型、复杂度、坑位。比如在linked_list.c顶部写反转带头结点链表时先断开头结点合并用哑结点减少判空分支。这套模板在期末考、考研408、天梯赛刷题时能省大量时间。数据结构与算法分析教材里的代码很多是伪代码不能直接提交你需要对照模板改成PTA能接受的完整函数。串的模式匹配题在PTA里经常单独成题KMP的next数组是高频易错点单独建一个string_match.c非常划算。6. 从刷题到考试用这招把PTA成绩变成期末分数6.1 用PTA题目集针对性刷考研408的算法题考研408的算法题分值不高但区分度高常见出题点是线性表、二叉树和排序。PTA题目集里正好覆盖这些片段比如求两个有序序列的中位数是408真题变形还原二叉树就是408常考的由遍历序列构造二叉树。刷的时候不要把题目集当成题库而是当成题型模板库。我备考时会把PTA里所有树的题目刷两遍第一遍完整写代码第二遍只写核心递归函数然后默写。每次默写后对比自己的模板文件找出漏掉的边界。408算法题一般只需要写出算法思路和关键函数PTA的函数题天然适合这种训练边刷边用笔写下复杂度和边界条件考试时就会很从容。6.2 考试前快速复习路线图如果时间仓促临时抱佛脚建议按这个优先级线性表链式操作反转、合并——必考且代码量小树的三种遍历与二叉搜索树的插入删除图的DFS/BFS以及Dijkstra模板排序中的qsort与二分查找边界。每天花半小时用题目集里的题自测重点看最近做错的题。我自己的习惯是考前把避坑清单重新过一遍freopen注释掉了吗数组多开5个了吗行末空格处理了吗变量初始化了吗这四句话救了我很多场考试。这都是血泪经验换来的。PTA题目集不是一个需要膜拜的答案包而是一面照出算法盲区的镜子。希望这篇笔记里的套路和踩坑记录能让你少走弯路刷题时更有底气祝你在PTA和期末里都拿到想要的分数。本文还有配套的精品资源点击获取