简介PTA“数据结构与算法”题目集的C解答合集面向正在刷题或备战期末考试的高校学生与自学者覆盖线性结构、二叉树、图论、排序及动态规划等核心考点。压缩包内共41个文件以38个cpp源码文件为主搭配2个头文件和1份说明文档整体仅有38KB便于快速下载和本地编译调试其中说明文档简要梳理了文件组织与题目来源。源码实现了Dijkstra、Floyd、Kruskal、Prim、拓扑排序、KMP、LCS、AVL树、Huffman编码等经典算法并包含最大子列和、是否同一棵二叉搜索树、一元多项式的乘法与加法运算等PTA原题的可运行代码注释清晰、变量命名直观适合对照题目逐行理解算法流程与边界处理。目前已有3008人学习下载尤其适合在考前集中刷题时对照验证思路是复习数据结构和准备上机考试的实用参考。1. 这份题集到底装了什么从“能跑”到“AC”之间隔着什么期末周拿到一份命名极简的“PTA-数据结构与算法题目集.zip”解压后是一堆按章节排好的 .c 文件很多人的第一反应是会心一笑——这不就是拼题A上那几百道经典题目的本地快照吗。PTAProgramming Teaching Assistant做的东西本质上是把数据结构与算法从纸面概念变成了一段段必须让机器点头的代码而这份题目集的价值恰好在于它不提供“一键刷题”的捷径反而是把最常见的线性表、树、图、排序、字符串匹配题目打包成你能反复折腾的原始素材。适合谁正在上数据结构课、被 OJ 判题搞得夜不能寐的本科生准备 408 统考想找密集训练场的考研党以及蓝桥杯这类竞赛前想把自己从“会看答案”逼成“能默写”的备赛者。开局先泼一盆冷水这份题集不会直接给你 AC它只给了你一个机会让你弄清自己到底哪里没搞懂。2. 拆开压缩包之前的准备工作本地环境、目录规划与三种最常见的打开方式2.1 用 GCC 和 GDB 搭一个能放心翻车的本地工作区我拿到任何OJ题目集合的第一件事永远是先把本地编译环境弄到“报错信息肉眼可读”的程度。PTA 判题机使用的是 Linux 环境下的 GCC 编译器标准一般是 C11所以本地用 MinGW-w64 或者 WSL 里的 GCC 都行不挑。核心是把“编译-运行-对比”这个循环做到三秒以内否则你根本没耐心去追一个野指针。我会在解压后先建一个这样的目录结构:pta-workspace/ ├── 01-linear-list/ │ ├── 1001-reverse-list.c │ ├── 1002-merge-lists.c │ └── Makefile ├── 02-tree/ ├── 03-graph/ ├── 04-sorting/ ├── input.txt # 手工构造的测试输入 └── build.sh # 一键编译全部题目的脚本这个build.sh是给你省时间用的内容不长作用却很实在。它遍历每个子目录的 .c 文件逐个编译成同名可执行文件编译选项里开-Wall全量警告:#!/bin/bash # 逐个编译所有题目遇到语法错误立刻停止 for dir in */; do for src in $dir*.c; do gcc $src -o ${src%.c}.out -Wall -Wextra -g -O0 2error.log if [ $? -ne 0 ]; then echo 编译失败: $src cat error.log exit 1 fi done done逻辑说明这个脚本替你省掉了手动敲几十次 GCC 命令的体力活-g开启调试信息让 GDB 能定位到源代码行-O0关闭优化避免调试时变量被优化掉导致你怀疑人生。参数上要注意PTA 判题机默认不开启-Wextra这一档警告但本地开着你才能提前抓住那些“隐式类型转换”“未使用的参数”之类的问题。提示不要把线上判题当编译器用。本地 GDB 能看到数组越界的崩溃现场OJ 只给你一个冷冰冰的“Runtime Error”。能本地看核心转储就别去网上猜。2.2 读题先从 Input 下手逆向推断数据规模与边界条件打开任意一道题的 .c 文件前我建议你先找题目描述里关于输入格式和数据范围的那几行。PTA 题目的特征非常鲜明——数据规模几乎总是明写在题干里比如“N ≤ 10^5”。这几个字决定了你能用 O(N^2) 的暴力算法还是必须上 O(N log N) 的优化解法。更关键的是它直接告诉你数组该开多大、递归深度会不会爆栈。题目集里那道经典的“两个有序链表序列的合并”如果你只看到“递增序列”就开练忽略了 N 可能等于 0 的空表情况你会在期末的夜半时分体会到什么叫“玄学”。我习惯先用纸笔把输入样例跑一遍把程序当人脑模拟器用。比如链表反转题目输入可能是“1 2 3 4 5”加一个反转位置段这时候我会在草稿纸上画出每个节点 next 指针的指向变化标注出 prev、curr、next 三个指针在循环里分别指向谁。这个习惯会在你调指针题时救你一命因为大部分指针 bug 不是语法错误而是逻辑上“某一步的赋值顺序写反了”。2.3 把“能在本地跑”和“能在 PTA 上 AC”当成两件事验证我一直强调一个观点本地输出正确只是及格线PTA 判题比你想象得更严格。它的 Special Judge 程序会检查输出格式的空格、换行、行尾空格甚至输出的浮点数精度。所以拿到这个题目集时你的目标不是“让样例通过”而是“让所有边界条件通过”。建一个input.txt专门存放你自己构造的边界用例——空数组、单元素数组、全是相同元素的数组、已经排好序的数组——这比反复提交 OJ 等判题结果效率高十倍相当于你在本地给自己做了一次完整的冒烟测试。3. 从暴力枚举到剪枝与 KMPPTA 字符与数组题目里的套路拆解3.1 暴力枚举不是笨办法它是你调试算法的基准线题目集里有一批“看起来很简单”的题比如字符串逆序输出、复数四则运算、找两个点之间最近的距离。这类题对新手最容易踩的坑是上来就想优化结果优化代码写得比暴力还慢。我自己的习惯是第一版永远写最直白的思路能过的样例先过掉复杂度分析放后面。拿“字符串逆序”这道典型题来说PTA 的常用考法是给一个带空格的整行字符串要求单词逆序而不是字符逆序。第一版我会用双指针做整个字符串反转然后再逐个反转单词——这是标准的两次反转法时间复杂度 O(N)空间复杂度 O(1):#include stdio.h #include string.h // 工具函数反转 str 中 [left, right] 区间的字符 void reverse_range(char *str, int left, int right) { while (left right) { char tmp str[left]; str[left] str[right]; str[right] tmp; left; right--; } } int main() { char str[100005]; // PTA 题面说过输入可能包含空格所以必须用 gets 或 fgets fgets(str, sizeof(str), stdin); // fgets 会把换行符也读进来先去掉它 int len strlen(str); if (len 0 str[len - 1] \n) str[len - 1] \0; int n strlen(str); // 第一遍整体反转 reverse_range(str, 0, n - 1); // 第二遍逐个单词再反转回来 int i 0; while (i n) { // 跳过单词间的空格 while (i n str[i] ) i; int start i; while (i n str[i] ! ) i; reverse_range(str, start, i - 1); } printf(%s\n, str); return 0; }逻辑说明整个算法的核心是两个指针 i 和 startstart 记录每个单词的起点i 一直往前扫描直到遇空格或字符串结尾然后对这段区间做一次区间反转。内外两层循环加起来每个字符最多被访问两次所以是线性时间。参数上要注意fgets会把\n一起读入第一遍整体反转时如果没去掉这个换行符你反转后的字符串开头会多出一个空行这正是很多人在本地跑得好好的、一提交就是格式错误的原因。3.2 KMP 算法为什么 next 数组的构建是字符串匹配题的命门题目集里一旦出现“模式匹配”相关的题十有八九是让你实现 KMP 算法或者用 KMP 思想解决重复子串问题。这里有一个 PTA 特别喜欢埋的坑他们不会直接告诉你“请用 KMP”而是给一个看似朴素的“找子串位置”的题面可数据规模 N10^6暴力匹配必定超时。这时候你需要的不是背代码而是搞懂 next 数组到底在干嘛。next[i] 的含义是“当模式串第 i 位失配时跳回到模式串的哪个位置继续匹配”它本质上是模式串自身的最长相等前后缀长度。一个常见的错误是背错了 next 数组的递推公式把next[j] next[next[j]]当成口诀念但完全不理解为什么失配时要跳到 next[next[j]]——因为下一步要拿模式串更短的前缀去对齐主串里已经扫过的位置。PTA 里那道“病毒追踪”变种题就是把 KMP 的 next 数组当成一个循环节检测器用判断一个字符串是否由某个子串重复构成。3.3 剪枝不是高深技术它是让暴力枚举活下来的最后一根稻草题目集里那些搜索类问题比如求子集、排列、组合的计数很多新手一上来就想用 DFS 全排列硬搜。对 N8 的小数据没问题但一旦 N 到 20全排列的 20! 足以让你怀疑 PTA 的服务器是不是在故意针对你。这时你需要的是剪枝——在递归搜索树的每一层提前判断“这条路继续走是否有意义”。剪枝最常见的三种手段是可行性剪枝当前部分解已经不满足约束条件直接返回、最优性剪枝当前累计长度已经超过已知最优解直接返回、重复性剪枝同一层不选重复元素。这三种手段在题目集里的应用场景截然不同但核心逻辑完全一致减少无效的递归调用。在“N 皇后问题”这类经典题目里最朴素的判断是同列和对角线冲突而高效的写法是用三个布尔数组分别记录列、主对角线、副对角线的占用情况。这里有个剪枝参数上的细节主对角线编号是 row - col N副对角线编号是 row col加 N 是为了把索引偏移到非负数区间不理解这个偏移你的数组下标大概率会越界。4. 线性表与树的 C 语言实现从单链表反转到二叉堆的调整函数4.1 链表题先画图再写码反转、合并、去重的指针边界PTA 题目集里线性表部分最劝退新手的题莫过于带头结点的单链表反转。这道题考的不是“你能不能反转”而是“你在反转过程中是否会丢节点”。很多人的第一版代码长这样用 p 指向当前节点q 指向下一个节点然后直接把 p-next 改成前驱。听起来没问题但指针一旦改链原本 q 的下一个节点就找不到了这就是“断链”。我的建议是动手前一定在草稿纸上画出三指针模型。pre、cur、next 三个指针分别指向前驱、当前、后继每次循环先把 next 保存下来再让 cur 指向 pre然后三个指针同时向后挪一位。循环结束后头结点的 next 要指向原来的尾节点。这个过程中最容易翻车的动作是“让头结点的 next 置空”——因为如果不带头结点反转后的链表尾节点的 next 必须指向 NULL否则你遍历时会越界。4.2 堆排序与建堆操作向上调整和向下调整别搞反题目集里的排序章节堆排序几乎从不缺席。这里有一个非常普遍的认知误区把建堆过程记成“从最后一个非叶节点开始向下调整”却忘了实际代码里的堆是用数组实现的。PTA 里典型的堆操作题会要求你输出建堆过程中每次调整后的数组状态这逼着你必须理解下沉sift down和上浮sift up两个函数的区别。建堆用的是向下调整因为从最后一个父节点开始把每个父节点和它的两个孩子比较如果父节点不是最大就交换然后继续向下递归调整。而往堆里插入一个新元素时用的是向上调整新元素放在数组末尾然后和父节点比较并一路向上替换。一个必踩的坑是数组下标问题——堆结构常从下标 1 开始存储这样父节点 i 的左孩子是 2i右孩子是 2i1如果你写代码时图省事从 0 开始存那么左右孩子的下标公式就变成了 2i1 和 2i2这个偏差会导致你的调整函数访问越界。4.3 双端队列与循环数组front 和 rear 的追赶游戏双端队列在 PTA 里常以数组实现为考点考的其实是你对环形队列下标管理和取模运算的掌握程度。这个题的坑特别典型当你用 front 和 rear 两个指针来标记队列头和尾时需要决定 rear 是指向最后一个元素还是指向下一个空位。题目集里的惯用做法是 rear 指向下一个空位这样队列为空的判断条件是 front rear队列满的判断条件是 (rear 1) % capacity front但这种做法会浪费一个存储单元——因为你要留一个位置来区分空和满。我之前在这个问题上吃过亏原因是把容量设为和最大元素数一致的数结果当插入到最后一个位置时(rear1) % capacity 正好等于 front被判为“满”可实际上队列里还有一个空位没用上。这里的心法是如果你不想浪费那个存储单元就必须额外引入一个 size 字段来记录当前元素数量用 size 0 判空用 size capacity 判满代价是每次插入删除都要维护这个变量。5. PTA 题目集避坑清单从编译报错到超时的七个血泪现场5.1 数组开小了OJ 报“段错误”不一定是野指针也可能是栈溢出现象本地测试样例全部通过提交到 PTA 后立刻 Runtime Error没有任何多余提示。老手会告诉你先检查数组大小而不是去追指针。原因是你把题面的“N ≤ 10^6”当成了最大规模却忽略了题目可能还有多组测试数据。比如每轮处理一个长度为 10^6 的数组如果总共要处理 10 组你的数组却只按单组最大长度申请第二轮就溢出。解决办法非常机械数组大小按最大数据规模加一个足够大的冗余量直接写 1000005、1000006 这样的值别精确到刚好够用。另外如果你在函数内部声明了超大数组比如int arr[1000000]这个数组占的是栈空间Linux 默认栈大小只有 8MB很容易爆。这时候把数组声明成全局变量或者用malloc分配到堆上问题立刻消失。5.2 scanf 读字符串的截断问题带空格的行怎么读现象用scanf(%s, str)读输入遇到“hello world”这种带空格的字符串只读到了“hello”后续处理全部错乱。原因很简单%s碰到空格或换行就会停止读取。解决方案是分场景用fgets(str, MAX_LEN, stdin)配合手动去掉末尾换行符或者用scanf(%[^\n], str)这种正则读法。但要注意fgets会保留换行符而%[^\n]不会消耗输入流里的换行符这会导致下一次读入时就拿到一个空行。所以%[^\n]后面要手动加一个getchar()来吞掉换行。判断一道题该用哪种读法标准只有一个题目描述里写“字符串可能包含空格”的一律 fgets。5.3 递归深度过深导致栈溢出DFS 不是万能的现象树或图的深度优先遍历在大数据下直接崩溃报错信息是 Segmentation Fault。排查后发现递归深度达到了 10^5 层每次递归调用压栈的局部变量加上返回地址把系统栈彻底撑爆。这不是算法错误而是系统资源限制。解法通常有两种把递归改成显式的栈用数组模拟压栈弹栈或者检查你的递归函数里有没有不必要的局部变量——比如在递归里声明一个 100 字节的临时数组这会成倍放大栈消耗。我见过最离谱的写法是在 DFS 函数内部声明了一个几百 KB 的缓冲导致递归到第 100 层时就爆了。记住递归函数的局部变量越少越好循环用的下标都尽量复用全局变量。5.4 Presentation Error输出格式的魔鬼细节现象代码逻辑完全正确所有样例输出都对但 PTA 退回 PE提示“输出格式错误”。原因方向有很多最常见的三个行尾多了一个空格、最后一行缺换行符、空行的数量不对。PTA 的输出比较是逐字符进行的多一个空格都算错。我个人的习惯是把所有输出都用一个数组暂存最后一次性printf拼接好的字符串输出。这样能保证格式统一可控。另外题目说“每个测试数据之间用空行隔开”时最后一行不该再输出空行这个判断条件要特别留意。5.5 浮点数精度比较输出差 0.000001 就被判 WA现象一道几何题本机测试多次输出都是 1.732提交后判答错误再仔细看题面要求输出保留三位小数你的 1.732 和标准答案的 1.732 之间表面上没有差别但 PTA 的 Special Judge 可能做的是绝对误差或相对误差判断。解法是用printf(%.3lf, ans)精确控制输出精度而不是用double默认的 6 位有效数字。如果题目没有指定精度但你的结果涉及浮点运算建议输出比要求多一到两位小数给判题机留出容差空间。5.6 多组输入的处理没写循环读到 EOF现象题目说“输入包含多个测试用例每组数据以……开头”你却只处理了一组就输出并退出了。典型的错误是用了scanf但不检查返回值。正确处理方式是while (scanf(%d, n) ! EOF)这种循环结构注意scanf返回的是成功匹配的参数个数不是读取的值本身。所以判断条件写成 1比! EOF更严格——如果你在读两个整数scanf(%d%d, a, b)返回 2 才能说明两个都读成功了。这个细节在输入行末尾有多余空格或空行时尤其重要因为scanf会跳过空白字符继续读取下一个有效值。5.7 全局变量和局部变量的初始化零值不是默认保证现象程序在本地反复测试正确提交后出现随机性的错误输出。排查了所有逻辑后发现某个数组用作计数器你只初始化了前 N 个元素而第 N1 个元素在全局静态区会自动清零看起来没问题但如果你把这个数组声明在函数内部栈上它的初值就是不确定的。解决办法是养成习惯任何数组声明后第一件事就是memset清零。特别是结构体数组不要假设内存里的值是 0memset(buf, 0, sizeof(buf))一行代码能省掉你半夜三小时。另外calloc和malloc的区别就在这里——calloc分配内存时自动清零但速度比malloc慢一点做竞赛题时我会优先用memset而不是calloc原因是大数组清零的场景里calloc会引入额外的页错误开销。6. 最后这一步很关键把本地验证脚本做成你刷题体系的一部分这一章教你怎么给自己的解题过程加一道“后悔药”写一个自动对比脚本把本地运行结果和标准输出文件做 diff。步骤很简单你在解压后的题目集目录里建一个test.sh内容是把每个题目的输入样例喂给编译好的可执行文件然后把输出重定向到out.txt再用diff和标准答案文件比对。这个脚本最大的作用不是帮你找答案而是让你在改动一个参数后迅速确认“没有破坏原有的正确性”——这在做堆排序调整函数时特别实用因为你经常会在优化一个分支时不小心影响另一个分支。#!/bin/bash # 自动测试脚本遍历所有题目运行并对比输出 for exe in */**.out; do base$(basename $exe .out) if [ -f testcases/$base.in ]; then ./$exe testcases/$base.in testcases/$base.myout if diff -q testcases/$base.out testcases/$base.myout /dev/null; then echo $base: PASS else echo $base: FAIL fi fi done逻辑说明这个脚本的执行逻辑非常直白但它是你整个调试循环里真正能救命的环节。diff -q只报告文件是否相同不输出详细差异所以你的终端只会干净利落地显示 PASS 或 FAIL。每个题目的输入样例需要你手动放在testcases目录下命名规范是题目名.in和题目名.out这是我个人的命名约定也推荐你这么做因为base变量会从可执行文件名自动提取题目前缀不会搞混。参数上要注意的是**这个通配符需要 bash 开启 globstar 选项如果你用的是 sh 或者没开这个选项要改成*.out这样的单星形式。关于内存调试我还有一个压箱底的习惯在编译选项里加上-fsanitizeaddress这是 GCC 提供的地址消毒器能当场定位数组越界、使用已释放内存这类 C 程序最常见的致命伤。这个选项在 OJ 里不能用但在本地调试时是你的第一道防线。需要注意的是开启这个选项编译出来的程序会明显变慢内存占用也大几倍所以它只用于调试版最终提交前的版本一定要用普通选项重新编译否则你可能会因为性能差异而误判自己的算法复杂度。最后说说我个人的教训拿到任何题目集我都会先花半小时搭测试框架再花两小时刷题。顺序一旦反了后续所有调参和修正都会陷入混乱。把这套脚本固化下来之后你其实已经把自己的刷题流程变成了一个小型 CI 系统——每次改动代码后跑一遍全绿了就提交 PTA。用这套流程吃透一份这样的题目集比盲目刷十份没反馈的题更有意义。希望帮到你。本文还有配套的精品资源点击获取