每次作业截止前的那天晚上，我的邮箱或聊天窗口总会多出几封求助消息，内容出奇一致：“学长，我的代码编译能过，但运行结果不对，帮我看一眼？”这些同学交上来的数据结构上机作业，绝大多数不是算法不会，而是栽在了输入输出格式、边界条件、指针处理这些看似不起眼的地方。我当年也是从“抄代码→编译→提交→WA→通宵改”的循环里爬出来的，所以今天想把一套完整的数据结构上机作业从拿到题单到提交通过的全过程，结合具体案例和踩坑经历，拆开揉碎了讲一遍。这篇东西不教你背代码，而是告诉你如何高质量地完成一次数据结构上机作业，让你少走弯路。

1. 上机作业不是背代码：先把这三件事做在前面

很多人拿到上机题单的第一反应是：找代码、背代码、粘贴、编译、提交。但我的经验恰恰相反，花半小时做好下面三件事，比多写一晚上代码都值。

1.1 审题时盯住四个细节，而不是只看算法名字

数据结构上机题通常会把算法包装在一个具体场景里。比如“约瑟夫环”不会直接叫“约瑟夫环”，它可能叫“猴子选大王”“报数出列”之类的。审题时，请把注意力放在四个容易被忽略的地方：

第一，输入格式。是“每组数据占一行”还是“第一行为n，第二行为数据”？题目说“输入包含多组测试数据，以EOF结束”，那么你的代码就得用while(scanf(...) != EOF)或者while(cin >> n)这种循环结构，很多人只处理了一组数据就忙着交，结果只能过一个样例。

第二，输出格式。看起来最简单的部分往往最致命。题目要求“每个结果占一行”，你写成空格分隔；题目要求“输出编号之间用逗号分隔”，你漏了逗号，直接WA（Wrong Answer）。我见过太多人算法完全正确，就因为多打了一个空格或者少打了一个换行，白白扣分。

第三，数据范围。这一步直接决定你选择什么算法和数据结构。如果 n ≤ 10，冒泡排序也能过；如果 n = 10^6，你还写个 O(n²) 的排序，那结果必然是TLE（Time Limit Exceeded）。数据范围还影响变量的类型，别用 int 装 10^9 以上的数，溢出之后你会得到一个完全无法理解的负数。

第四，时间限制和内存限制。课程OJ平台通常给的时间比较宽裕，一般是1到2秒，内存128MB左右。但这不意味着你可以随便挥霍。递归层数太深导致爆栈、开一个 10000×10000 的 int 二维数组导致 MLE（Memory Limit Exceeded），都是我在判题记录里常看到的错误。

1.2 先写“测试用例”，再写代码

这个习惯我是吃了亏才养成的。以前我拿到题目直接开始写函数，写完再用题目给的样例去测，发现能过就觉得万事大吉，结果提交后WA。后来某导师跟我说了一句话：“题目给的样例是用来让你理解题意的，不是用来证明你代码对的。”

从那以后，我拿到每道题第一件事是手写一组自己的测试用例，覆盖下面这些情况：

把这些用例放在代码旁边，每写完一个函数就跑一遍。你不用一次全部测完，但至少保证在提交前都测过一遍。

1.3 先写核心API签名，再填充实现

这个技巧尤其适合“上机作业”这种限时任务。拿到题目后，不要急着写main函数里的业务逻辑，先想清楚这道题需要哪几个核心函数，每个函数的参数是什么、返回值是什么。

比如约瑟夫环，核心API就是void josephus(int n, int k, int m)；括号匹配，核心API就是bool isValid(const char *s)。先把这个架子搭好，再往里填代码，你会发现整个程序的逻辑清晰很多，面试笔试时也能直接复用这种思考方式。更重要的是，一旦核心API设计合理，你在写测试用例的时候根本不需要依赖完整的main函数，直接写个小驱动测试就行。

2. 线性表与栈的经典作业拆解：约瑟夫环和括号匹配到底想考你什么

数据结构课程的上机作业，线性表、栈、队列这几个模块几乎是必考的。绝大多数学校会从“约瑟夫环”“括号匹配”“多项式加减法”这类经典题目里出题。我用这两道最经典的题作为案例，详细拆一遍实现思路和深埋的坑。

2.1 约瑟夫环：循环链表只是“看起来”的正确答案

约瑟夫环的题目描述一般是这样的：n 个人编号从1到n，围成一圈，从第 k 个人开始从1报数，报到 m 的人出列，然后从下一个人重新从1报数。求完整的出列顺序。

教科书上给的经典解法是用循环链表模拟。思路没问题，但很多人的代码一跑就崩，或者结果不对，问题大多出在下面三个地方。

我写一个 C 语言版本，你对照着看：

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node* createCircle(int n) { Node *head = (Node*)malloc(sizeof(Node)); head->data = 1; head->next = NULL; Node *tail = head; for (int i = 2; i <= n; i++) { Node *p = (Node*)malloc(sizeof(Node)); p->data = i; p->next = NULL; tail->next = p; tail = p; } tail->next = head; return head; } void josephus(int n, int k, int m) { Node *prev = createCircle(n); Node *cur = prev->next; // cur 先指向头节点 // 找到编号为 k 的节点 for (int i = 1; i < k; i++) { // 只需要移动 k-1 次 prev = cur; cur = cur->next; } while (cur->next != cur) { for (int cnt = 1; cnt < m; cnt++) { prev = cur; cur = cur->next; } printf("%d ", cur->data); prev->next = cur->next; free(cur); cur = prev->next; } printf("%d\n", cur->data); free(cur); } int main() { int n, k, m; scanf("%d%d%d", &n, &k, &m); josephus(n, k, m); return 0; }

先说第一个坑：从第 k 个人开始报数，移动次数到底是 k 还是 k-1。很多人在这里出错。cur 初始指向 head，也就是编号1的节点。如果要从编号 k 开始，那么只需要让 cur 移动 k-1 次，因为它当前已经在编号1上了。你多移动一次，就会从 k 的下一个人开始，结果绕了一圈全错。

第二个坑是m=1 的情况。m=1 意味着报到1的人出列，也就是从当前人开始依次出列。上面的循环for (int cnt = 1; cnt < m; cnt++)一次都不会执行，于是直接把 cur 指向的人输出并删除，然后 cur 移到下一个人。这逻辑是对的。但很多人的写法是先移动 m-1 次，当 m=1 时确实没问题，如果他们把移动次数写成 m 次，m=1 时反而跳到了下一个人，逻辑就反了。

第三个坑是内存释放的顺序。删除节点时，你要先把prev->next指向cur->next，然后才能 free(cur)。顺序反了，cur 虽然还被 prev 指到，但cur->next的访问就变成了野指针操作，程序大概率会崩。这类问题用调试器很难查，因为它不是每次都崩，只在某些节点上崩。

再补充一点，约瑟夫环还有一种不需要链表的高效方案，用数组维护“下一个人的位置”，或者直接用公式法倒推存活者编号。如果题目只要求输出最后剩下的那个人的编号，你完全可以跳过模拟，直接用递推公式s = (s + m) % i去做。这个思路在数据量大、时间限制紧的时候非常管用。上机作业如果只要求最后存活编号，你还傻乎乎地建一个链表，那只能说明对数据结构的理解停留在“背答案”层面。

2.2 括号匹配：栈的几个“隐蔽”易错点

括号匹配也是经典中的经典。给定一个只包含()[]{}的字符串，判断所有括号是否正确配对。用栈实现的思路非常直观：遇到左括号就入栈，遇到右括号就和栈顶匹配，能匹配则弹出，不能匹配则说明整体不合法。

直接看代码：

#include <stdio.h> #include <string.h> char stack[1005]; int top = -1; int isMatching(char left, char right) { return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}'); } int isValid(const char *s) { top = -1; int len = strlen(s); for (int i = 0; i < len; i++) { char c = s[i]; if (c == '(' || c == '[' || c == '{') { stack[++top] = c; } else if (c == ')' || c == ']' || c == '}') { // 先判空栈，再取栈顶 if (top == -1 || !isMatching(stack[top], c)) { return 0; } top--; } // 其他字符跳过 } return top == -1; } int main() { char s[1005]; while (scanf("%s", s) != EOF) { printf("%s\n", isValid(s) ? "YES" : "NO"); } return 0; }

代码很简洁，但里面藏着三个高频错误：

第一个错误：取栈顶前不判空栈。如果字符串是")"，第一个字符就是右括号，此时top == -1。你如果直接写stack[top]，是会越界访问的。局部变量stack放在栈上，越界访问不一定崩溃，但可能读到随机值，于是程序输出一个看似合法的错误结果。正确写法就是用top == -1 ||做短路判断，先判空再取栈顶。

第二个错误：误把“匹配失败”当成“继续扫描”。判断括号匹配，只要出现一次不匹配，整个字符串就不合法，可以直接返回。但有些同学把if写成了if-else if的嵌套结构，变成“不匹配就跳过”，最后统计栈空不空，顶多丢一个括号，根本发现不了类型不匹配的问题。

第三个错误：忽略其他字符。题目如果明确说“只包含括号”，那没问题。但有些变种题会混入字母、数字、空格，你需要决定它们是跳过还是当作非法字符。我看到过一种很经典的变种：给定一段包含( ) [ ] { }和普通字符的代码，让你判断括号是否匹配。这时如果忽略其他字符，代码扫一遍即可，但如果把普通字母也入栈，整个栈结构就乱了。所以实现前必须确认题面约定。

栈这个数据结构本身不难，上机考你的其实是对“边界条件”的敏感度。isValid或者其他类似函数，我建议你手写测试时至少覆盖这些输入：空串""、单个左括号"("、单个右括号")"、"(]"、"([)]"、"{[]}"。尤其"([)]"这种交叉匹配很能测出“只计数不匹配类型”的错误实现。

3. 树与图的作业，真正的难点藏在“输入输出”和“存储结构”里

链表和栈只是热身。二叉树和图的作业才是很多人的分水岭。倒不是算法有多难，而是树的建树过程、图的存储方式太容易出错了。

3.1 二叉树的建树与层序遍历：输入格式决定你的代码写法

二叉树上机题里，最经典的一套操作是“给定二叉树的某种遍历序列，建树，然后输出层序遍历结果”。这里有一个关键问题：建树用的输入到底长什么样？

常见的有两种。第一种是按“扩展先序序列”输入，空节点用特殊符号#表示，例如ABD##E##C#F##，对应的树长这样：A 是根，B 是左孩子，D 是 B 的左孩子（无子节点），E 是 B 的右孩子，C 是 A 的右孩子，C 的左孩子为空，右孩子是 F。这种输入用递归建树非常方便：

#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { char val; struct TreeNode *left, *right; } TreeNode; char s[1005]; int idx = 0; TreeNode* buildTree() { char c = s[idx++]; if (c == '#') return NULL; TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = c; root->left = buildTree(); root->right = buildTree(); return root; }

这里有个反直觉的点：buildTree函数的参数需要变化，比如把idx作为指针传入，或者用全局变量，否则递归往返时索引会丢失。我见过很多人的代码，idx在递归里被反复覆盖，导致建出来的树结构完全是乱的。在递归参数设计上，我建议先想清楚“这个变量在递归过程中是每个栈帧各有一份，还是全局共享一份”。像idx必须在所有递归层次里共享，所以要么全局变量，要么传指针。

第二种输入是按“完全二叉树的层次序列”给出，空节点用-1或0占位，比如1 2 3 4 5 -1 6。这种输入用数组存树最合适，节点编号就是数组下标，左孩子是2*i+1，右孩子是2*i+2。很多同学明明拿到的是这种输入，非要用指针去建树，结果白写一大堆代码还容易错。选错存储结构，比选错算法更致命。

层序遍历的逻辑对很多新手来说有点别扭，因为它不是递進的，而是“一层一层扫”的。实现手段是队列：先让根节点入队，然后循环“出队一个节点，访问它，把它的左右孩子入队”。注意入队前要判空，否则空树的层序输出会变成NULL之类的东西。我自己写层序时，最常犯的错误是忘记了队列里存的是“指针”，读节点值要用front->data，而不是front.data，这属于用 STL 容器时的经典失误。

3.2 图的邻接表：头插法和尾插法直接影响输出顺序

图的上机作业里，常见的要求是“输入 n 个点、m 条边，求从某个起始点出发的深度优先遍历序列或广度优先遍历序列”。

这里真正容易翻车的地方，不在 DFS 或 BFS 算法本身，而在邻接表的“建立顺序”。

邻接表本质上是一个数组，每个元素是一条链表，链表中每个节点存储一个与当前点相邻的顶点编号。向链表里插入新邻接点，有两种策略：头插法和尾插法。

// 邻接表节点 typedef struct EdgeNode { int to; struct EdgeNode *next; } EdgeNode; EdgeNode *head[MAXN]; void addEdge(int u, int v) { // 头插法 EdgeNode *p = (EdgeNode*)malloc(sizeof(EdgeNode)); p->to = v; p->next = head[u]; head[u] = p; }

头插法的特点是：后加入的边排到链表前面，所以如果你按“输入顺序”往邻接表里插边，遍历邻接表时得到的邻接点顺序是“输入顺序的逆序”。很多题目要求输出“按编号从小到大遍历”或者“按输入顺序遍历”。如果题目明说了要按编号从小到大，你需要在插入后对每个顶点的邻接链表排一次序，或者用尾插法保持输入顺序，再统一排序。

我在某次模拟题里就栽过这个跟头：题目要求输出从 1 号点开始 DFS 的先序序列，邻接点按编号从小到大访问。我图省事用了头插法，结果邻接点顺序是反的，DFS 输出序列和标准答案差了一大截，找了一晚上 bug 才想起来是存储顺序的问题。

还有一个高频问题：无向图要加两条边。输入一条边u v，你得在 u 的邻接表里加 v，在 v 的邻接表里加 u。漏掉一条，整个遍历结果就不完整。这种错误在样例数据规模小、边少的时候极难察觉，等数据一大，某块区域直接访问不到。

3.3 递归改显式栈：DFS 爆栈的解决办法

二叉树用递归遍历是自然的，图用递归 DFS 也是自然的。但数据规模一大，递归层数会深得惊人。比如一条链状的图，有 10 万个节点，递归 DFS 很可能直接爆掉系统栈，程序崩溃。这在我当年的课程作业里真实发生过。

解决办法有两种。第一种是把递归改成显式栈模拟：

void dfsIterative(int start) { int stack[MAXN]; int top = 0; int visited[MAXN] = {0}; stack[top++] = start; while (top > 0) { int u = stack[--top]; if (visited[u]) continue; visited[u] = 1; printf("%d ", u); for (EdgeNode *p = head[u]; p; p = p->next) { if (!visited[p->to]) { stack[top++] = p->to; } } } }

这里要注意显式栈对遍历顺序的影响。递归 DFS 的顺序是“访问节点→递归第一个邻点→递归第二个邻点”，而显式栈实现会先把所有邻点入栈，再弹出最后一个邻点继续访问。如果你用“入栈 → 后进先出”的方式把所有邻点都压进去，最终的访问顺序会和递归版本不一样。想让顺序一致，可以从最后一个邻点往前入栈。先想清楚你要的顺序，再决定入栈的次序。

第二种办法是开大栈空间的编译指令或加线程属性，但课程 OJ 一般不支持，所以显式栈才是稳妥的方案。这也提醒我们，数据结构上机不只是考你“会不会背 DFS 模板”，而是在考你“能不能理解递归背后的栈结构”。理解了这一点，显式栈就是顺理成章的事。

4. 那些TLE和RE的深夜：时间复杂度和内存问题的真实教训

上机作业最常见的三个判题结果是：WA（结果错误）、TLE（超时）、RE（运行时错误）。WA 大多是逻辑边界问题，TLE 和 RE 则几乎都出在“对数据规模没有敬畏心”上。我挑三个亲历过的案例讲。

4.1 案例一：n=10^6 的排序，冒泡排序的代价到底有多大

某次上机题是给 n 个整数升序排序。某位 A 同学非常顺手写了个冒泡排序，本地测试的时候 n=10，秒出结果。提交后 TLE，他还很委屈：“我本地运行挺快的啊，不是应该过了吗？”

冒泡排序的复杂度是 O(n²)。n=10^6 时，基本操作次数大约是 5×10^11 次。一台普通的评测机器一秒钟大约能执行 10^8 次简单操作，5×10^11 意味着大概需要几十分钟。这还只是按理想情况估算。所以数据范围 10^6，你用 O(n²) 的算法，无论如何都不可能在一秒内跑完。

我当时给他的建议是：拿到题目先算一下数据规模对应的暴力复杂度是否可接受，再动手写代码。判断标准非常简单：假设每秒操作次数约 10^8，O(n²) 能接受的 n 大概在 10^4 到 3×10^4；O(n log n) 能接受的 n 可以到 10^6 甚至 10^7。这个估算不用很精确，能帮你避开绝大多数 TLE。

4.2 案例二：vector 反复扩容带来的隐藏性能损耗

C++ 里的std::vector非常方便，但很多人不知道它内部是怎么增长的。每次扩容，它会申请一块更大的内存，把旧数据全部拷贝过去，再释放旧内存。如果从小到大地频繁push_back，底层会发生多次拷贝，花费的时间比你想象的要多得多。

我的建议是：如果你事先知道大概要存多少个元素，直接用vector<int> v; v.reserve(n);把容量提前申请好。这一点点改动可能让一个原本 TLE 的代码直接压线通过。

类似的隐藏问题还有：频繁使用std::string::operator+拼接字符串，会产生大量临时对象和拷贝。在循环里拼接时，最好用ostringstream，或者在 C 语言里直接用char数组和sprintf/snprintf。上机题里的内存和时间的浪费，往往不是大算法错了，而是这些“小毛病”堆出来的。

4.3 案例三：递归太深导致 RE，不一定是数组越界

很多人看到 RE 第一反应是“数组越界”，这没错，但还有一个常见原因是函数调用栈溢出。递归深度过深会撑爆系统为每个进程分配的默认栈空间——通常在 8MB 左右。每次函数调用会占用栈帧空间，包括参数、局部变量、返回地址。深度达到几十万层时，栈空间很容易耗尽。

解决办法有这么几条：把递归改成循环或显式栈；如果递归深度很小但你还是 RE，那就要去查数组下标是否越界或者野指针。用调试器跑一遍，通常错误发生的那一行会直接标红。判断 RE 类型有一个技巧：如果错误程序输出了一部分内容之后崩溃，多半是越界访问；如果代码一进递归就崩，多半是栈溢出。

5. 交作业前两小时，按这张清单逐项检查

代码写了一晚上，终于所有样例都能过了。这时候是不是可以直接提交？我的建议是，交作业前两小时一定要留出来做最后的检查。下面这张清单是我自己吃过亏之后总结出来的，每条都对应真实翻车经历。

5.1 通过样例不等于通过全部：你要会“对拍”

对拍是 ACM 圈子里的常用技巧，对课程作业同样适用。思路是：写一个绝对正确但复杂度很高的暴力程序作为标准程序，再写一个随机数据生成器，然后不断生成随机数据，让暴力程序和你的优化程序分别跑一遍，比较输出是否一致。

对拍的步骤如下：

1. 写一个random.cpp，生成合法的随机输入数据。
2. 写一个brute.cpp，用最简单的思路保证输出正确。
3. 写一个solve.cpp，即你要提交的程序。
4. 用脚本循环运行：random生成数据 →brute跑一遍 →solve跑一遍 → 比对输出。

只要随机数据够多，你的程序的隐藏 bug 就会暴露出来。对拍脚本写起来不复杂，用 bash 或 bat 都能实现。对拍发现输出不一致后，把那一组输入数据保存下来，单步运行你的程序，定位 bug 就非常快了。

5.2 常见判题结果与问题定位对照表

如果你在本地运行正常，一交上去就 CE，大概率是头文件缺失或使用了非标准扩展。比如很多人用#include <bits/stdc++.h>在本地能过，但某些 OJ 的编译器版本可能不支持，建议老老实实写标准头文件。

5.3 别忽略内存释放和代码风格

课程上机作业和竞赛不一样，很多老师会要求你传递代码的同时，也会关注你是不是有内存泄漏。C 语言里用了malloc，最好在最外层调用里匹配free；C++ 里能不用裸指针就尽量不用，或者用unique_ptr管理。命名变量时尽量见名知意，不要全是tmp1、tmp2、tmp3。注释可以不必每行都写，但核心算法的关键步骤值得加一两行说明。这些细节在打分时常常成为区分“会写代码”和“只交作业”的关键。

还有一个小建议：如果你的代码特别长，提交前花十分钟从头到尾读一遍。重点关注所有数组下标和循环边界。我每次这么干，都能在提交前找出至少一个低级错误。有些错是当时写的时候脑子发热，事后一眼就能看出来的。

6. 最后再分享一点个人体会

从第一次上机作业的 WA 到后来能在限定时间内完整 AC，我最大的收获不是“某道题会做了”，而是养成了三个习惯。第一个习惯是动手前先估算时间和空间，这也让我在后续的数据结构课程设计和笔试面试里少踩了很多坑；第二个习惯是设计好测试用例再写代码，很多边界问题在写代码之前就已经被消灭了；第三个习惯是把每一次提交的失误记录下来——我会在笔记本上记下“这次 TLE 是因为没用快排，这次 RE 是因为递归爆栈”，下次遇到类似场景就能快速定位。

说到底，数据结构上机作业最能锻炼人的不是背会某个数据结构，而是让你在一次次调试中建立起“数据结构、算法、数据规模三者是绑定关系”的意识。把这份意识带进后续的学习和项目里，比多拿几个满分有用得多。