简介东北大学数据结构实验报告围绕约瑟夫环问题完整呈现了顺序表与链表两种存储结构下的线性表操作实现。报告面向计算机相关专业本科生及备考复习者详细记录了实验目的、存储结构选型、算法函数设计与时空复杂度分析并给出了调试过程中遇到的指针指向错误、循环链表成环时机等典型问题及改进方案便于读者对照理解链式存储动态分配和删除的机理。文档为单个docx文件共1份大小502KB已有293人学习下载。除核心代码外报告还包含随机多组测试验证、头结点特殊性的处理思路、实验结果总结等内容既能作为课程实验报告的参考范式也能帮助读者巩固循环链表、约瑟夫环出列顺序等知识点适合在实际编程练习或期末复习中配合使用。1. 这份数据结构实验报告合集四个实验把线性表、栈、排序、动态规划一次走完这份东北大学数据结构实验报告合集不是一份简单的作业存档而是把数据结构课里最常布置的四道题——约瑟夫环、括号匹配、广告归并排序、找零钱——用四种数据结构各实现了一遍的完整过程记录。实验一用循环链表解决约瑟夫环实验二用顺序栈做括号匹配实验三用非递归归并排序处理广告排序实验四用动态规划求解最少硬币数。每个实验都配有可以直接抄的源码、算法复杂度分析和调试记录连第一次写错的代码、跑挂的现象、后来怎么改的都写在里面。适合两类人一是正在写数据结构实验报告、需要参考完整步骤和代码的学生二是想快速过一遍链表、栈、归并、动态规划这四类经典代码、顺便看看别人怎么踩坑的入门开发者。这份报告最有价值的地方恰恰是那些翻车记录——网上能找到一堆标准答案但很少有人把指针断链、空栈访问这类问题写得这么具体。2. 约瑟夫环与循环链表可运行的完整代码和三个边界问题2.1 约瑟夫环为什么锁定了循环链表约瑟夫环的场景是 n 个人顺时针围坐一圈每人持一个正整数密码从第一个人开始报数报到 m 的人出列他的密码成为新的 m再从下一人重新报数直到全部出列。这个数据模型有三个关键特征围坐一圈、循环报数、动态删除。围坐一圈直接对应循环链表——最后一个节点的 next 指向第一个节点循环报数对应链表遍历时指针不断后移不需要处理数组下标越界回绕的问题动态删除对应链表的节点摘除只需改前驱的 next 指针不需要像数组那样移动大量元素。数组也能模拟约瑟夫环用一个 int 数组标记是否出列但每删除一个人就需要扫描整个数组代码逻辑更绕。链表的删除天然就是 O(1) 的指针操作删掉一个人只需要改一个 next 指针对。原报告选择链式存储结构的原因也是这两个物理位置上的邻接关系表达节点间的逻辑关系读代码时直观插入删除不需要移动大量节点可以动态分配空间。这个选型在思路上没有争议真正的坑在实现细节上。2.2 整理后的完整实现创建、显示、出列原报告的代码思路正确但有两个会导致程序跑挂的问题一是封环动作放在了插入循环内部导致第二个节点显示乱码二是出列循环里删除了节点却没有正确处理指针接续第二个人出列时程序就自动终止。下面是我按照原报告的抽象数据类型整理后的可运行版本修正了这两处问题。typedef int Datatype; typedef struct node { Datatype data; // 人的编号 int password; // 持有密码 struct node *next; } ListNode, *CLinkList;结构体定义与原报告一致data 存编号password 存密码next 指向下一个节点。这个定义是循环链表的基础后面的创建、显示、删除都基于它。CLinkList CreatList_CL(int n) { CLinkList head NULL, tail NULL; int pin; for (int i 0; i n; i) { printf(请输入第 %d 个人的密码, i 1); scanf(%d, pin); CLinkList p (CLinkList)malloc(sizeof(ListNode)); if (p NULL) { printf(内存分配失败\n); exit(1); } p-data i 1; p-password pin; p-next NULL; if (head NULL) { head p; // 第一个节点成为头 } else { tail-next p; // 接在链表尾部 } tail p; // tail 始终指向最后一个节点 } tail-next head; // 全部插入完成后封环 return head; }创建链表的时间复杂度是 O(n)n 次循环创建 n 个节点空间复杂度 O(n)。注意封环语句tail-next head放在整个循环外部这是原报告调试记录里的第一条修正经验如果在循环内部提前封环第二个节点的 next 会被错误改写显示链表内容时第二个节点输出乱码。这里用 head 和 tail 两个指针维护链表构建过程比原报告的哨兵节点写法更直观也避免了头结点带来的遍历问题。void Display(CLinkList head, int n) { CLinkList p head; for (int i 0; i n; i) { printf(编号%d 密码%d\n, p-data, p-password); p p-next; } }显示函数遍历 n 个节点时间复杂度 O(n)空间复杂度 O(1)。这里遍历 n 次而不是遍历到指针回到 head因为循环链表本身没有天然终止点用人数 n 控制循环次数最可靠。原报告在调试初期尝试过用p head判断结束但因为头结点处理不当导致遍历失败后来干脆不用头结点问题就解决了。void Delete_L(CLinkList *head, int n, int m) { CLinkList p *head; CLinkList q NULL; printf(\n出列顺序\n); while (n 0) { // 移动 m-1 步让 p 指向报数为 m 的人 for (int j 0; j m - 1; j) { q p; p p-next; } printf(编号%d 密码%d\n, p-data, p-password); m p-password; // 用出列者密码更新 m if (q NULL) { // 删除的是头结点更新头指针并重新封环 CLinkList tail p-next; if (tail p) { // 只剩最后一个节点 *head NULL; free(p); break; } while (tail-next ! p) tail tail-next; tail-next p-next; *head p-next; } else { q-next p-next; // 前驱跳过待删节点 } free(p); // 释放节点内存 p (q NULL) ? *head : q-next; // 从下一人继续报数 n--; } }出列核心逻辑先走 m-1 步找到报 m 的人输出编号和密码更新 m然后摘除节点。这里有两个原报告踩过坑的关键点。第一个是删除时要区分删除的是不是头结点原报告代码里 q 一直是 NULL删除第一个人后头指针没有更新第二个人出列时程序就崩了。第二个是先接链再释放——q-next p-next必须在free(p)之前执行否则 p 已经是一个野指针根本无法访问它的 next 字段。这个算法的时间复杂度是 O(mn) 的级别每次出列需要移动 m-1 步总共执行 n 次删除m 是当前密码值。原报告写的是 O(n²)建立在 m 恒定的假设上严格说不够准确——m 每次都会被出列者的密码替换密码可能很大所以写成 O(mn) 更严谨。空间复杂度 O(n)除了链表本身没有额外存储。2.3 出列逻辑的三个边界坑第一个坑是删除头结点。当被删除的节点恰好是 head 指向的节点时直接free(p)会让 head 变成野指针。原报告没有单独处理这个分支结果是第一个人正常出列后程序还能跑但第二次执行到删除时指针已经指向非法内存。解决方法是先找到尾节点 tail让tail-next p-next重新封环再更新*head p-next。第二个坑是 m 值为 1 的情况。for (int j 0; j m - 1; j)在 m1 时循环体一次都不执行q 保持 NULLp 指向当前节点。这个分支必须走上述删除头结点的逻辑否则会出错。m1 意味着直接删除当前指向的人不需要任何移动这在边界测试里是必测的用例。第三个坑是单个节点情况。当 n1 时循环链表只有一个节点头结点也是尾节点删除它之后链表为空。需要用tail p判断只剩一个节点的情况直接释放并退出否则后续的封环操作会访问已释放的内存。我的代码在if (tail p)分支里做了特殊处理这是原报告没有考虑到的情况。3. 括号匹配与顺序栈从设计到空栈访问修正3.1 括号匹配的需求模型与栈的对应关系题目要求检验表达式里的圆括号和中括号嵌套是否合法允许的括号只有( ) [ ]两种嵌套次序随意。这个问题的核心是检查括号的配对顺序一个右括号出现时它应该和最近的左括号配对——也就是最后一个未被匹配的左括号。这种「后出现的先被检验」的次序关系正是栈的 LIFO 特性所以选择顺序栈作为核心数据结构。我在读原报告时注意到一个细节报告里把栈的选型理由写得很清楚——栈是一个只能访问表尾端数据的数据结构先进后出的特点和括号匹配中检验顺序的需求相吻合。这个选型完全正确。括号匹配问题的处理流程从左到右扫描表达式遇到左括号就压栈遇到右括号就弹出栈顶元素检查是否配对最后看栈是否为空。栈空且字符串扫描完毕说明所有括号都找到了另一半栈不为空说明有左括号没被匹配。用数组实现顺序栈有好处如果使用链式结构存括号每个节点都需要 malloc 和 free纯属浪费——括号匹配只需要在栈顶操作数组的随机访问和紧凑存储完全够用。原报告也是这个思路先用 malloc 分配基地址空间再用 top 指针指示栈顶位置。3.2 顺序栈实现修正空栈访问和指针传参问题原报告的栈定义能正常编译但实现里有三个问题需要修正。第一个问题是push和pop函数用char *str作为参数但实际压栈的是一个字符传参时要用取地址写起来很别扭。第二个是 Match 函数里遇到右括号时直接访问*s-top如果此时栈是空的top 指向 base 位置读出来的是未定义数据。第三个是字符不匹配时执行s-top s-top - 1把栈顶指针往下移了一位这会破坏栈的结构导致后续判断全部错乱。下面是修正后的完整实现输入一行表达式输出括号是否匹配。#include stdio.h #include string.h #include stdlib.h #define STACK_SIZE 32 typedef struct { char *base; // 栈底指针 char *top; // 栈顶指针指向下一个可写入位置 int stacksize; // 当前栈容量 } SStack; void initStack(SStack *s) { s-base (char*)malloc(sizeof(char) * STACK_SIZE); if (s-base NULL) { printf(内存分配失败\n); exit(1); } s-top s-base; s-stacksize STACK_SIZE; } void push(SStack *s, char c) { // 栈满时动态扩容避免溢出 if (s-top - s-base s-stacksize) { int newSize s-stacksize * 2; char *newBase (char*)realloc(s-base, newSize); if (newBase NULL) { printf(栈扩容失败\n); exit(1); } s-top newBase (s-top - s-base); s-base newBase; s-stacksize newSize; } *s-top c; } int pop(SStack *s, char *c) { // 栈空时返回 0避免访问非法位置 if (s-top s-base) return 0; *c *--s-top; return 1; } int matchBrackets(const char *expr) { SStack s; initStack(s); int len strlen(expr); for (int i 0; i len; i) { char ch expr[i]; if (ch ( || ch [) { push(s, ch); } else if (ch ) || ch ]) { char topChar; if (!pop(s, topChar)) { // 栈为空却遇到右括号说明右括号多余 free(s.base); return 0; } if ((ch ) topChar ! () || (ch ] topChar ! [)) { // 左右括号类型不匹配 free(s.base); return 0; } } } int result (s.top s.base) ? 1 : 0; free(s.base); return result; } int main() { char expr[128]; printf(请输入表达式); scanf(%s, expr); if (matchBrackets(expr)) printf(括号匹配!\n); else printf(括号不匹配!\n); return 0; }这段代码的时间复杂度是 O(n)对表达式进行了一次线性扫描每个字符的入栈、出栈都是 O(1) 操作。空间复杂度 O(n)栈的容量会随表达式长度动态扩容。对比原报告的 Match 函数我做了一个关键修正原报告是两个循环分开处理——第一个循环把所有左括号入栈第二个循环再扫描右括号出栈这样等于遍历了两遍字符串而且第二遍扫描时遇到右括号判断栈顶元素如果栈为空就直接访问*s-top在 C 语言里这是未定义行为。我的做法是单次遍历处理遇到左括号入栈遇到右括号先检查栈是否为空、再弹出栈顶元素做类型匹配。这样只用一趟扫描且每个字符只处理一次逻辑上更紧凑。匹配失败时直接返回 0不需要像原报告那样用s-top s-top - 1去跳过字符——这种做法会破坏栈顶指针是原报告没有意识到的问题。3.3 测试用例设计括号匹配的正确性测试必须覆盖四类用例合法嵌套、不匹配类型、右括号多余、左括号多余。合法嵌套如([()])、([])返回匹配不匹配类型如([)]中)的栈顶是[类型不符返回不匹配右括号多余如()]扫描到]时栈已空返回不匹配左括号多余如(()扫描结束栈还剩下(返回不匹配。这个实验原报告的测试写在「随机给出表达式每次结果正确」上这个测试思路有一个隐含问题随机生成包含括号的合法数学表达式本身就容易偏向匹配正确的用例很难覆盖到右括号多余这类边界情况。用上述四类组合手动构造用例比随机测试更系统这也是我在做这类题时一直保留的习惯——先把每个边界写成一个测试用例再跑随机数据。4. 归并排序和动态规划广告排序与找零钱的落地代码4.1 广告排序的任务与选型实验三的任务是定义一个 Advertisement 类包含物品名称、数量、联系邮箱、开拍和关闭时间从 input.txt 读入广告信息由用户输入排序关键字用非递归归并排序对所有广告排序并输出到 output.txt。这个题目考查分治法的应用归并排序是分治思想的典型代表——把序列不断对半划分排序两个子序列再合并成一个有序序列。原报告选用了非递归归并排序这个选择很聪明。递归版本的归并排序虽然代码短但函数调用开销大递归深度接近 log n 虽然不算高但对初学者来说理解递归调用栈就不如迭代递推直观。非递归版本用 step 从 1 开始倍增每次将相邻的两个长度为 step 的有序序列合并step 翻倍直到超过 n彻底避开递归调用。时间复杂度方面归并排序无论数据初始状态如何都是 O(n log n)空间复杂度 O(n)因为合并过程需要一个临时数组存放合并结果。原报告里写「如果输入数据本来就是按非降次序排列的则根本不会进入 while 循环计算时间是 O(n)」这个说法其实不严谨——非递归归并的 while 循环以 step n 为条件数据有序只会影响比较次数不会跳过合并过程。这个细节我在下面的代码里会说明。4.2 非递归归并排序完整实现与参数说明原报告的算法用int* data排序一个整数数组但题目要求排序的是广告对象所以我整理了一个针对广告结构体的通用版本用函数指针做关键字的比较这样按名称、数量、邮箱排序都可以复用一个排序函数。#include stdio.h #include string.h #include stdlib.h typedef struct { char name[32]; // 物品名称 int count; // 数量 char email[32]; // 联系人邮箱 } Ad; // 比较函数返回 -1、0、1供排序函数调用 int compareByName(Ad a, Ad b) { return strcmp(a.name, b.name); } int compareByCount(Ad a, Ad b) { if (a.count b.count) return -1; if (a.count b.count) return 1; return 0; } // 合并两个有序区间 [L, M) 和 [M, R) void merge(Ad *arr, int L, int M, int R, int (*cmp)(Ad, Ad)) { int leftLen M - L; int rightLen R - M; Ad *temp (Ad*)malloc(sizeof(Ad) * (leftLen rightLen)); if (temp NULL) { printf(内存分配失败\n); exit(1); } int i 0, j 0, k 0; while (i leftLen j rightLen) { // 用 保持稳定性相同关键字时左边先放入 if (cmp(arr[L i], arr[M j]) 0) { temp[k] arr[L i]; i; } else { temp[k] arr[M j]; j; } } while (i leftLen) temp[k] arr[L i]; while (j rightLen) temp[k] arr[M j]; for (int t 0; t k; t) arr[L t] temp[t]; free(temp); } // 非递归归并排序主函数 void mergeSort(Ad *arr, int n, int (*cmp)(Ad, Ad)) { // step 是当前有序子序列的长度从 1 开始倍增 for (int step 1; step n; step * 2) { // 每轮把数组中相邻的两个长度为 step 的子序列合并 for (int i 0; i n - step; i 2 * step) { int R (i 2 * step) n ? i 2 * step : n; merge(arr, i, i step, R, cmp); } } } int main() { Ad ads[100]; int n 0; FILE *fin fopen(input.txt, r); if (fin NULL) { printf(无法打开 input.txt\n); return 1; } while (fscanf(fin, %s %d %s, ads[n].name, ads[n].count, ads[n].email) 3) n; fclose(fin); mergeSort(ads, n, compareByCount); FILE *fout fopen(output.txt, w); for (int i 0; i n; i) fprintf(fout, %d %s %d %s\n, i 1, ads[i].name, ads[i].count, ads[i].email); fclose(fout); printf(排序完成结果已写入 output.txt\n); return 0; }两个关键参数说明。第一个是外层循环变量step表示当前有序子序列的长度初始为 1。每轮循环结束后 step 翻倍——长度为 1 的相邻元素两两合并成有序序列长度变成 2下一轮 2 和 2 合并成 4以此类推。当 step n 时整个数组已经有序循环结束。这个倍增过程可以保证循环log2(n)次。第二个是内层循环的边界条件i n - step。当 i 后面的剩余元素不足一个 step 时不需要再合并。int R (i 2 * step) n ? i 2 * step : n这一行处理了末尾剩余元素不足一组的情况——左子序列是 [i, istep)右子序列是 [istep, R)R 取min(i 2*step, n)防止越界。 0的比较写法是为了稳定排序。原报告在调试记录里写「对于相同值的两个物品无法进行排序」就是因为比较函数里用了而不是导致数值相同的两个元素在合并时把后面的放到了前面。虽然结构体里没有额外下标标识但能保证左边序列的元素在相同值的情况下优先放入 temp等价于保持了元素的原始先后顺序。4.3 找零钱的动态规划与贪心的差别实验四的题目是找零钱问题有 n 种不同面值的硬币数量不限求找出钱数 j 所需的最少硬币个数输入为硬币面值数组 T[1:n] 和目标找钱数 L输出最少硬币数。原报告完整给出了动态规划的状态转移方程C(i, j) 表示只用前 i 种面值找 j 元的最少硬币数递推式是C(i, j) min(C(i-1, j), C(i, j-T[i]) 1)这是一个二维 DP 表。但有个地方要留意原报告附录里贴的代码片段是一个贪心算法——直接用 25、10、5、2、1 的面值逐级整除找零。贪心的思路是每次都用最大面值这个算法在硬币面值呈倍数关系时能得到最优解比如人民币的 25、10、5、2、1 这套组合每次取最大面值就是最优。但如果硬币面值是 3、4、7 这种不成倍数的组合贪心就可能翻车——比如找 6 元贪心会取一个 4 元加两个 1 元共 3 枚而最优解是两个 3 元共 2 枚。动态规划才是这道题的正解。我实现了一个一维滚动数组版本只用一个长度为 L1 的数组满足题目「算法中只允许用一个长度为 L 的数组」的约束。#include stdio.h #include stdlib.h #include string.h #define INF 0x3f3f3f3f // coins 为硬币面值数组n 为面值种类数money 为要找的钱数 int minCoins(int coins[], int n, int money) { int *dp (int*)malloc(sizeof(int) * (money 1)); for (int i 0; i money; i) dp[i] INF; dp[0] 0; // 找 0 元需要 0 枚硬币 for (int i 1; i money; i) { for (int j 0; j n; j) { if (coins[j] i dp[i - coins[j]] ! INF) { // 用一枚面值 coins[j] 的硬币加上剩余金额的最优解 if (dp[i - coins[j]] 1 dp[i]) dp[i] dp[i - coins[j]] 1; } } } int result (dp[money] INF) ? -1 : dp[money]; free(dp); return result; } int main() { int n; printf(请输入硬币面值种类数 n (n13)); scanf(%d, n); int coins[13]; printf(请输入 %d 种硬币的面值, n); for (int i 0; i n; i) scanf(%d, coins[i]); int money; printf(请输入要找的钱数 j); scanf(%d, money); int result minCoins(coins, n, money); if (result -1) printf(无法用这些硬币凑出 %d 元\n, money); else printf(最少需要 %d 枚硬币\n, result); return 0; }这个算法的时间复杂度是 O(nL)外层循环遍历 1 到 L 每个金额内层遍历 n 种面值空间复杂度 O(L)只保留一个一维数组。核心思想是 dp[i] 表示找 i 元所需的最少硬币数它等于所有dp[i - coins[j]] 1中的最小值——先用一枚面值 coins[j] 的硬币剩余金额 i - coins[j] 的最优解已经在之前的迭代中算好。从小到大填表保证了子问题先于父问题求解。5. 避坑五个从调试记录里翻出来的典型问题5.1 链表显示乱码封环动作塞进了插入循环里现象创建循环链表之后用 Display 显示链表内容第一个人的编号和密码正常第二个人开始输出乱码后面的数据也全不对。原因原报告在创建链表的 for 循环内部执行了q-next (*L)-next也就是每插入一个节点就执行一次封环操作。插入第二个节点时第一个节点还处于链表中间位置它背后的封环逻辑把第二个节点的指针错误指向了头结点导致第二个节点从链接关系中脱链。这种现象的本质是封环动作的执行时机不对——环形链表必须在所有节点都插入完成后才能封环中途封环等于把链表提前截断。解决把封环语句tail-next head移动到整个插入循环的外部先构建一个单向链表等 n 个节点全部插入完成后再把最后一个节点的 next 指向头结点。排错技巧写链表相关代码时先把逻辑在草稿纸上画出来标出每一步指针的指向再对照代码逐行检查乱码的问题就能一眼定位。5.2 第二个人出列时程序崩溃删除节点后指针没接上现象运行约瑟夫环程序第一个人能正常出列显示编号和密码程序继续执行到第二个人的时候直接卡死或弹出运行时错误终止运行。原因删除第一个节点后代码没有正确更新链表头指针和指向前驱的指针。原报告代码里q始终是 NULL删除节点只执行了free(p)没有让前驱节点的 next 指向 p 的下一个节点。free 之后 p 变成野指针第二次循环访问 p-next 拿到的是一个已经不可用的地址程序自然崩溃。解决删除前先摘链——q-next p-next然后释放节点并把指针挪到被删节点的下一个位置。另外要注意删除头结点时必须有单独的处理分支更新*head p-next同时重新保证尾节点指向新头。从那以后我再写链表删除第一件事就是问自己谁还指着这个节点它现在的 next 应该指向哪5.3 括号匹配遇到右括号就报错没有先判栈空现象用括号匹配程序测试一个右括号开头或右括号多于左括号的表达式程序直接崩溃或者返回一个莫名其妙的结果。原因Match 函数遇到)或]时直接访问栈顶元素*s-top没有先判断栈是否为空。栈为空时 top 指向 base此时读取*s-top读到的是一块未初始化的内存行为未定义——可能是一个随机值也可能触发访问违规。解决在访问栈顶之前先检查s-top s-base栈空时立即返回不匹配。我的实现里 pop 函数本身就带有判空逻辑遇到空栈返回 0主流程拿到 0 就直接判定表达式括号不匹配。这是用栈解决问题的通用习惯pop 前先问自己栈里还有没有元素没有的话当前算法流程是否仍然成立。5.4 strlen 写在 for 循环条件里编译器报警告现象编译时出现关于运算符的警告提示小于号没有定义或没有匹配程序能跑但警告看着心烦。原因代码写成for (i 0; i strlen(str); i)strlen 的返回类型是 size_t属于无符号整数类型。无符号整数和有符号整数做比较时编译器会发出关于类型转换的警告。而且 strlen 在每次循环迭代都会重新计算一遍字符串长度时间复杂度从 O(n) 变成 O(n²)。解决定义一个局部变量int j strlen(str)先用一次 strlen 算出长度循环条件写成i j。这样既消除了类型转换警告又避免了重复调用 strlen。用局部变量存储循环边界是写 C 代码的基本习惯避免在循环条件里调用函数。5.5 相同关键字排序不稳定比较函数用了而不是现象测试归并排序时两组关键字值相同的物品排序后顺序发生了交换输出顺序不稳定和输入顺序不一致。原因合并两个有序序列时判断条件写成if (data[ai] data[bj])当两个值相等时条件不成立右边的元素被先放入临时数组。虽然两个相等的元素无所谓谁先谁后但这样会破坏归并排序的稳定性——如果结构体里还有其他字段排序后相同关键字的记录会丢失原有顺序。解决判断条件改成即cmp(arr[L i], arr[M j]) 0相等时优先从左边取。归并排序是少数天然的稳定排序算法代价很小但如果比较条件写错就会丢掉这个特性。测试时特意构造两条关键字相同、其他字段不同的数据排序后检查它们的相对位置是否保持原样是验证稳定性的标准方法。6. 拿到这份报告之后先做三个验证再动手改这份资源里的代码思路是对的但直接复制粘贴运行之前建议先按下面三个步骤过一遍。第一个步骤是验证链表逻辑用 n5、密码分别为 3、1、5、2、4 的小数据手动在纸上模拟一遍约瑟夫环的出列顺序——从第一个人开始报数报到 3 出列然后换密码继续。跑完手算的结果再用程序输出对比能发现绝大多数指针逻辑的问题。第二个步骤是测试边界输入约瑟夫环用 n1、m1、密码很大的数据括号匹配用([)]和()这类不匹配用例找零钱用 3、4、7 面值找 6 元这种让贪心失效的数据。这些边界用例比随机数据更能检验程序的正确性。第三个步骤是逐行读代码——先走一遍外层循环再跟踪内层循环每一步指针指向哪个节点把q-next p-next这类语句对应的链表变化画在纸上。我在整理这份代码时学到的最重要一课是删除链表的节点时永远先问「谁还指向这个节点」。原报告第二次调试时遇到程序崩溃就是因为 free 之后没有重新连接指针这个教训我在自己的代码里也遇到过不止一次。从那以后我每次写链表或栈相关的代码都强制自己先画数据流向图再动手画完图再写代码调试一次通过的概率明显提高。代码写完用边界数据测试测试通过再用随机数据这个流程慢慢成了习惯。这份报告虽然来自 2017 年的实验课但这些习惯到今天依然受用希望帮到你。本文还有配套的精品资源点击获取