数据结构实验源码跑通指南：gcc编译、Makefile与逐实验边界验证

简介：面向南京邮电大学数据结构课程及同类学习者，这份7z压缩包汇集四次课程实验的完整源码，可用于线性表、栈与队列、树形结构、图算法等知识点的上机实践与对照学习。包内共64个文件，以13个h头文件和10个cpp源文件为主体，配有pdb、obj、dsw、dsp等工程构建与调试文件，整体约1.58MB，便于在本地还原编译环境并查看模块组织。已有2642人学习，内容涉及多项式运算、线性表操作、二叉树与哈夫曼树、图的基本操作及飞机换乘次数等实验场景，读者可据此理解顺序存储与链式存储的取舍、栈队列的典型应用、树与图算法的编码实现，也能参考工程配置和调试排错思路。源码适合作为学习辅助与思路比对材料，使用时应遵循学术诚信，在理解基础上改进而非直接复制。

1. 先别急着交：这套数据结构实验源码得先在你机器上跑通

某高校课程设计周最真实的画面是这样的：实验报告模板下好了，数据结构实验源码压缩包也解压了，gcc一敲，满屏 error 直接把人按在椅子上——光一个ElemType未定义就能卡掉半个下午。这套源码解决的正是这个问题：它按实验把线性表、栈和队列、串、树、图、查找、排序的实现分开摆好，每个实验都有能独立编译的测试入口，不依赖任何 IDE 私有工程文件。它适合两类人：一类是报告写完了但结果对不上、想找一份能跑通的参照实现来对答案；另一类是打算把这些代码吃透、改成自己版本再交的。源码是死的，编译参数和输入数据是活的，先跑通再谈理解，这个顺序反了，后面全是白费功夫。

2. 源码包拆解：七个实验的文件映射与三层结构

拿到一个课程实验源码包，最忌讳的是直接双击main.c开干。先花二十分钟把目录结构摸清楚，比后面调三小时段错误划算得多。这一章的重点不是罗列文件，而是讲清楚它为什么这样分层，以及每一层对应实验报告的哪个部分。

2.1 三层结构：ADT 声明、算法实现、测试入口

合格的数据结构实验源码，基本都遵循「头文件放抽象数据类型、.c放算法实现、main放测试」的三层组织。头文件里干三件事：typedef定义元素类型、struct定义存储结构、函数原型声明。这一层直接对应实验报告里要求手写的 ADT 定义，改元素类型（比如把int换成char）只需要动一处typedef，其余代码不用碰。

实现文件只写函数体，不写main。这样做的好处很实在：某个实验的链表删除写错了，编译错误只会在它自己的编译单元里报，不会牵连到排序实验。测试入口main单独一个文件，里面通常是硬编码一组数据加几个printf，方便你肉眼比对输出。

提示：如果解压后发现整套源码只有一个巨型main.c，里面塞了十几个实验的函数，那基本可以判断这是拼凑版本，改一处全崩。遇到这种结构，我的做法是按实验手工拆成独立文件再编译，拆的过程本身就是复习。

另一个常见的结构差异是「带头结点」还是「不带头结点」的链表。这套源码用的是带头结点版本，头结点不存数据，插入删除时不用特判第一个位置，代码短一截万无一失。代价是遍历要从head->next开始，初学者经常在这里多输出一个随机值。看清main里初始化那行有没有malloc头结点，就知道属于哪种。

2.2 文件与实验的映射关系

不同版本的源码目录命名不完全一致，但实验内容跑不出那几类。下面这张表是按典型课程实验顺序整理的映射，拿到包之后对照着找文件即可，找不到就按「核心结构」那一列grep关键字。

表里「重点观察什么」这一列是血泪经验堆出来的。判定一个实验有没有真正跑对，不是看它输出了一行结果，而是看边界用例：空表插入、只有一个结点的树、只有一个顶点的图、全相同的待排序数组。这些用例在源码自带的main里往往没有，得自己补。

2.3 输入输出约定：数据从哪进、结果往哪出

跑之前必须先确认输入方式，否则你会对着一个等待scanf的黑屏发呆。实验源码通常三种风格：交互式scanf逐个读、main里硬编码数组、从文件或标准输入重定向读。三种的处理方式完全不同。

用两条命令就能把整个包的输入方式盘出来：

# 找出哪些实验依赖键盘输入，哪些是硬编码数据 grep -rn "scanf\|fopen\|argv" --include="*.c" . # 按代码行数排序，快速判断哪几个实验是重头戏 find . -name "*.c" -exec wc -l {} + | sort -n | tail -8

第一条命令里的-rn表示递归搜索并显示行号，--include="*.c"把范围限定在 C 源文件，避免把编译日志里的同名文字也算进去。输出的每一行会告诉你文件、行号和上下文，凡是出现scanf的，运行后必须手工喂数据；出现argv的，说明要从命令行传参。

第二条命令用的是find -exec ... +，而不是管道接xargs。这两种写法效果接近，但-exec {} +会把找到的文件批量传给wc一次性执行，文件路径里带空格也不会被拆断，在中文目录名或者带空格的解压路径下更稳。sort -n按数值排序，tail -8只留最长的八个文件。行数明显偏多的那个，通常就是当年被要求写得最细的图或者排序实验。

注意：如果源码从文件读数据，路径多半写成相对路径（如./input.txt）。在源码目录里编译出来的可执行文件，必须回到同一目录运行，否则fopen返回空指针，程序直接段错误，报错信息还看不出是路径问题。

3. 编译环境落地：gcc 参数、Makefile 与一键批量构建

实验源码跑不起来，八成不是代码逻辑的问题，而是编译环境。这一章把工具链选型、单文件编译、批量构建三件事讲透，照着敲就能把整个包编出来。

3.1 为什么优先用 gcc 命令行，而不是现成的 IDE 工程

很多人第一反应是找个 IDE 新建工程、把.c文件拖进去。这在实验周里是给自己挖坑。IDE 工程文件里存的是绝对路径和私有编译选项，换一台机器、换一个用户名就找不到头文件；有些工程还会默认开 C++ 编译器去编.c，malloc返回值强转的写法在 C++ 下直接报错。更麻烦的是，你没法把「怎么编译的」写进实验报告附录。

命令行编译的优势是全过程可见、可复现、可写进报告。一行gcc命令就是一份完整的构建说明，助教照着敲也能得到同样的结果。而且开了告警之后，很多潜在问题在编译阶段就暴露出来，不用等到运行时段错误。

3.2 单文件与多文件编译的具体参数

先看单文件实验，比如链表：

# 单文件实验：开全告警、关优化、带调试符号 gcc -std=c99 -Wall -Wextra -O0 -g linklist.c -o linklist ./linklist

参数逐个说清楚：-std=c99统一语言标准，避免源码里for (int i = 0; ...)这种 C99 写法在默认标准下报错；-Wall -Wextra打开常用和额外的告警，未使用变量、隐式类型转换、有符号无符号比较都会提示；-O0关闭优化，保证调试时断点位置和源码行号对得上；-g生成调试符号，后面用gdb才有源码级信息；-o指定输出文件名。真正要提交或者测性能时，再把-O0换成-O2。

多文件实验的编译方式不同，数据类型和实现分开时要把所有.c一起交给编译器：

# 多文件实验：main + 实现文件一起编译链接 gcc -std=c99 -Wall -Wextra -O0 -g main.c list.c -o list_demo # 如果头文件不在当前目录，用 -I 指定搜索路径 gcc -std=c99 -Wall -Wextra -O0 -g -I./include main.c src/list.c -o list_demo

这里的关键点是：编译器只认.c文件，头文件通过#include在预处理阶段展开，不需要出现在命令行里；但头文件所在的目录必须让编译器找得到，否则报No such file or directory，这时候才需要-I。一个常见翻车是只编译了main.c，链接阶段报一堆undefined reference to ListInsert，原因就是实现文件没参与链接。

3.3 写一个能批量编译的 Makefile

实验包里有七八个可执行目标，每次都手敲gcc不现实。写一个十几行的 Makefile，make一下全部编完，make clean一下全部清掉：

CC := gcc CFLAGS := -std=c99 -Wall -Wextra -O0 -g TARGETS := sqlist linklist stack queue btree graph sort search # 默认目标：把所有实验编成同名可执行文件 all: $(TARGETS) # 模式规则：目标名与源文件名同名（去掉 .c 后缀） %: %.c $(CC) $(CFLAGS) $< -o $@ # 清理所有编译产物 clean: rm -f $(TARGETS)

逻辑说明：TARGETS变量列出所有实验的可执行文件名，all依赖它们，make不带参数时编第一个目标，也就是all。模式规则%: %.c表示「任意目标都可以由同名.c文件生成」，$<展开成第一个依赖（源文件），$@展开成目标名（可执行文件名）。这样加一个新实验只要往TARGETS里补一个名字，不用复制粘贴编译命令。

提示：Makefile 的命令行必须以 Tab 开头，用空格会报missing separator。这是新手最高频的翻车点，报错信息完全看不出是缩进问题。在编辑器里打开「显示制表符」能省很多时间。

要临时改优化级别或者加 sanitizer，不用改文件，命令行覆盖变量即可：

# 临时开 O2 测性能 make CFLAGS="-std=c99 -O2 -Wall" # 临时加内存越界检查 make CFLAGS="-std=c99 -g -O0 -fsanitize=address,undefined -fno-omit-frame-pointer"

变量覆盖的优先级高于 Makefile 里的:=赋值，这是 GNU make 的规则，用起来非常顺手。-fno-omit-frame-pointer是为了让地址检查器拿到完整调用栈，配合 sanitizer 一起用时建议加上。

3.4 先做一轮自动化体检，再手工跑

编译通过不等于逻辑正确。在逐个手工验证之前，用 sanitizer 把整个包扫一遍，能提前抓出越界写、释放后使用、未初始化读这些光看输出发现不了的问题：

# 用地址检查器单独编一个实验，跑一遍看有没有越界或泄漏 gcc -std=c99 -g -O0 -fsanitize=address,undefined \ -fno-omit-frame-pointer graph.c -o graph_asan ./graph_asan

地址检查器在程序退出时会把泄漏和越界一次性打印出来，带完整的调用栈和内存地址，比gdb单步找快得多。检查器本身会带来几倍性能开销，只在调试阶段开，测性能数据时必须关掉。较新的 gcc 和 clang 都内置支持，不需要额外安装。

4. 逐实验跑通：从线性表到图算法的验证命令与边界用例

代码能编过只是入场券，真正花时间的是验证每个实验的输出对不对。这一章按实验类型走一遍，每个给一段核心代码和验证要点，重点是边界值。

4.1 线性表：位序与下标差一，插入删除先测边界

顺序表最容易错的地方不是循环写法，而是位序和数组下标错一位。教材上位序从 1 开始，C 数组从 0 开始，插入位置合法范围是1..length+1，这个+1就是允许插到表尾。

/* 顺序表插入：i 为位序，合法范围 1 到 length+1 */ int ListInsert(SqList *L, int i, ElemType e) { if (i < 1 || i > L->length + 1) return 0; /* 位置越界，直接拒绝 */ if (L->length >= MAXSIZE) return 0; /* 表满，拒绝 */ for (int j = L->length; j >= i; j--) /* 从尾到头整体后移一位 */ L->data[j] = L->data[j - 1]; L->data[i - 1] = e; /* 位序 i 对应下标 i-1 */ L->length++; return 1; }

逻辑上就三步：判越界、后移、写入。参数i是位序，写进数组前必须减一；循环上界写j >= i而不是j > i，才能把第 i 个位置腾出来。验证时至少跑四个用例：i=1（头插）、i=length+1（尾插）、i=0（越界）、i=length+2（越界），后两个必须返回 0 且表内容不变。链表则要额外测删除唯一的结点后头结点是否还在、释放后有没有再访问。

4.2 栈与队列：括号匹配看栈空，循环队列看队满

栈的典型实验是括号匹配，判断依据不是「有没有左右括号成对出现」，而是「扫描结束后栈是否为空」。中途右括号多于左括号，或者左右类型不匹配，都要立刻判失败。

/* 括号匹配：返回 1 匹配，0 不匹配 */ int BracketMatch(const char *s) { char stack[256]; int top = -1; for (int i = 0; s[i] != '\0'; i++) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') { stack[++top] = s[i]; /* 左括号压栈 */ } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') { if (top < 0) return 0; /* 右括号多余 */ char c = stack[top--]; if ((c == '(' && s[i] != ')') || (c == '[' && s[i] != ']') || (c == '{' && s[i] != '}')) return 0; /* 类型不匹配 */ } } return top == -1; /* 栈空才算全部匹配 */ }

最后一行top == -1是整个函数的结论句，少了它，"(()"这种左括号富余的串会被误判成匹配。测试用例建议覆盖空串、单个右括号、左括号富余、右括号富余、交叉嵌套"([)]"五种，最后一种很多实现会漏。

循环队列的重点在队满判据。牺牲一个存储单元的做法是：队空front == rear，队满(rear + 1) % MAXSIZE == front。入队前先判满，出队前先判空，顺序反了就会在满队时覆盖数据。

4.3 串：BF 与 KMP 的 next 数组起点必须统一

串匹配实验一般要求 BF 和 KMP 两种实现对比。BF 简单，双层循环回溯；KMP 的坑全在next数组下标从 0 还是从 1 开始。源码里两种写法都出现过，改之前先看主串和模式串的下标基准，别把从 1 起的next直接套到从 0 起的实现里。

验证方法很直接：对同一组主串和模式串，BF 和 KMP 返回的首次匹配位置必须完全一致。用随机串批量跑一轮，能快速把next的边界问题逼出来。BF 的时间复杂度是 O(n×m)，手写计数器统计比较次数，能直观看到 KMP 在长串上的优势，这个数据写进实验报告比空谈复杂度有说服力。

4.4 树：三种遍历只差一句 printf，哈夫曼看带权路径长度

二叉树递归遍历是基础中的基础，先序、中序、后序的代码结构完全一样，区别只在printf放在递归调用的哪个位置。

/* 中序遍历：左 - 根 - 右 */ void InOrder(BiTree T) { if (T == NULL) return; /* 空树直接返回，递归出口 */ InOrder(T->lchild); printf("%c ", T->data); InOrder(T->rchild); }

把printf挪到两个递归调用之前就是先序，挪到之后就是后序。递归出口T == NULL必须写在最前面，少了它单结点树能过，空树直接崩。层序遍历要配队列，出队一个结点就把它非空的左右孩子入队，这个实验刚好把树和队列串起来。

哈夫曼树的验证不看遍历结果，看带权路径长度（WPL）和编码长度。手工算一遍权值，和程序输出的 WPL 对上，再用每个字符的编码长度乘以频率求和，两个数一致才算对。贪心合并的时候用最小堆比每次排序高效，源码里如果用的是排序版本，改成堆是很好的加分项。

4.5 图：邻接矩阵与邻接表的转换、遍历和最短路径

图实验是三块内容叠在一起：存储结构、遍历、经典算法。邻接矩阵适合稠密图和需要快速判边的场景，邻接表适合稀疏图，两者之间的转换要能互推。DFS 的递归实现有两处必须注意：visited数组在调用前清零，顶点编号从 0 还是从 1 开始要和数组下标对齐。

/* 邻接矩阵的 DFS：visited 由调用方初始化为全 0 */ void DFS(MGraph G, int v, int visited[]) { visited[v] = 1; printf("%d ", v); for (int w = 0; w < G.vexnum; w++) if (G.arcs[v][w] != 0 && !visited[w]) /* 有边且未访问才递归 */ DFS(G, w, visited); }

递归深度等于最长连通路径的顶点数，顶点上千时可能爆栈，改显式栈更稳。BFS 用队列，访问标记要在入队时就置位，而不是出队时才置位，否则同一个顶点会被重复入队。

Prim 和 Kruskal 的结果都是最小生成树，但边的输出顺序可能不同，比对时不能直接比数组，要比总权值再检查边集是否一致。Dijkstra 实验重点测不可达的情况：两个顶点之间没有路径时，距离数组应保持无穷大，很多人初始化写成了 0，结果所有不可达点都被算成距离零，输出的最短路径全是假的。

4.6 排序与查找：用对拍代替肉眼比对

排序实验的输出是一整行数字，肉眼根本看不出快排和归并谁对。最省事的验证办法是对拍：用一个绝对正确的标准实现当参照，随机生成输入，比对输出。Python 内置的sorted就是现成的标准答案。

# 对拍：随机生成数据，与 Python 内置排序结果逐一比对 import random, subprocess for _ in range(200): n = random.randint(0, 200) data = [random.randint(-10000, 10000) for _ in range(n)] inp = f"{n}\n" + " ".join(map(str, data)) + "\n" # 约定：先读 n，再读 n 个数 r = subprocess.run(["./sort"], input=inp, capture_output=True, text=True) got = list(map(int, r.stdout.split())) if got != sorted(data): print("MISMATCH", n, data, got) break else: print("all pass")

约定的输入格式是「第一行个数，第二行数据」，所以 C 程序那边必须先scanf("%d", &n)再循环读数组，格式对不上会读出一堆零。循环里特意让n可以为 0，就是为了测空数组这个边界——很多快排实现在n=0时访问a[0]直接段错误。subprocess.run的input参数把字符串喂给子进程的标准输入，capture_output=True抓走标准输出，text=True让结果按字符串而不是字节处理。

查找实验里折半查找的循环条件是low <= high，不是<，少了等号会漏掉最后一个元素。哈希表要测冲突处理，线性探测的删除必须打删除标记而不是直接清空，否则会截断探测链。

4.7 内存与越界：跑通之后再扫一遍

链表、树、图这三个实验大量使用malloc，跑通输出不代表没有内存问题。用地址检查器复跑一遍，泄漏和越界会直接给出文件和行号：

# 链表实验做内存体检：泄漏、越界、释放后使用都能报出来 gcc -std=c99 -g -O0 -fsanitize=address btree.c -o btree_asan ./btree_asan # 没有 sanitizer 的环境可以用 valgrind 代替 valgrind --leak-check=full --show-leak-kinds=all ./btree

地址检查器在程序退出时打印泄漏摘要，valgrind的--leak-check=full会列出每一处未释放的内存和分配时的调用栈。两者选一个即可，前者快、输出简洁，后者对未初始化读的检测更细。树的实验尤其要看这一项，递归建树漏释放一个分支，内存泄漏量会随结点数线性增长。

5. 避坑与排查：五个让实验结果对不上的高频问题

这一章按「现象、原因、解决」三段式整理。每一条都是跑这套源码时真实会撞上的，遇到问题先在表里对号，比盲改代码快。

5.1 编译报 ElemType 未定义或重复定义

现象：unknown type name 'ElemType'，或者反过来redefinition of 'struct LNode'。

原因：前者是头文件包含顺序不对，.c里先用了ElemType才#include定义它的头文件；后者是同一个头文件被两个路径间接包含，而又没写包含守卫。

解决：在每个.h文件开头加#ifndef XXX_H/#define XXX_H/#endif三件套，保证只展开一次。包含顺序统一成「本模块头文件、系统头文件、其他模块头文件」，ElemType的定义放在最基础的那个头文件里。改完重新全量编译，不要增量编译，避免旧的预处理结果干扰判断。

5.2 链表和树上莫名其妙段错误

现象：程序跑到删除结点或者遍历到一半就崩，gdb停在printf或者->next那一行。

原因：三类。删除结点时先free再访问p->next，释放后使用；遍历时没判空就取p->data；头结点被当成数据结点处理，或者反过来。

解决：删除操作的标准顺序是「先保存后继、再改指针、最后释放」，写成q = p->next; p->next = q->next; free(q);，顺序不能颠倒。所有遍历循环的条件写成while (p != NULL)，循环体第一行不要假设p有效。用gdb的bt看调用栈，p的值打印出来，是0x0就是空指针，是0xffff...一类就是野指针。

5.3 图算法结果对不上，或者只访问了一部分顶点

现象：DFS 只输出前几个顶点就结束，Dijkstra 输出的距离全是零或者全是同一个值。

原因：visited数组没清零，上一轮遍历的标记残留；顶点编号从 1 开始但数组从 0 开始，visited[G.vexnum]越界或者漏标；距离数组初始化成了 0 而不是一个足够大的数。

解决：把所有visited的清零动作放进遍历函数内部的开头，而不是依赖调用方。顶点编号统一：要么全部从 1 开始、数组开n+1，要么全部从 0 开始、数组开n，两者不能混。距离数组初始化用memset(dist, 0x3f, sizeof(dist))或者循环赋一个明确的大值，别用 0。

5.4 排序结果顺序错乱或者少一个元素

现象：快排输出看起来差不多对，但有一两个元素位置不对；归并排序偶尔丢最后一个元素。

原因：快排的分区边界写成了i <= j还是i < j没想清楚；归并的临时数组只拷贝了mid-left个元素，右半段漏了；插入排序的内层循环上界写成j > 0而不是j >= 0。

解决：别靠看，直接用上一章的对拍脚本跑两百轮，n从 0 到 200 全覆盖，错一轮就打印输入。对拍能定位到具体是哪种输入出错，比如「全是重复元素」说明分区把相等元素全分到一边导致退化，「已经有序」说明快排基准选得不好。定位到输入类型之后再回头看边界条件，比盯着代码空想有效得多。

5.5 换台机器就编不过，或者中文输出乱码

现象：在自己的机器上好好的，拿到实验室机器上一编译就报错；或者程序能跑，但printf出来的中文全是问号。

原因：源码里用了 C99 才支持的写法，对方编译器默认标准更老；源文件保存成了带 BOM 的 UTF-8，老版本 gcc 把 BOM 当非法字符；Windows 下换行是\r\n，拿到 Linux 上某些解析逻辑会多出一个字符。

解决：编译时显式加-std=c99或-std=c11，不要依赖默认标准。源文件统一保存为「UTF-8 无 BOM」，编辑器里找这个选项。换行符统一成 LF，git配置里加core.autocrlf相关设置，避免提交时被自动转换。控制台编码问题不在代码层面解决，把输出里的中文提示改成英文，能省掉一整类环境差异。

6. 进阶用法：把源码改造成自己的实验交付物

直接交一份和源码一模一样的代码，风险不用多说。这套源码真正有价值的地方在于它是一份可运行的参照实现，你要做的是在它上面加自己的东西。我的习惯是分三步改。

第一步，把测试数据从main里抽出来，改成从标准输入读。这样同一份可执行文件可以喂不同的用例，配合前面那个对拍脚本，验证覆盖面立刻上一个台阶。改动很小，只是把硬编码数组换成scanf循环，但实验报告里「测试用例设计」那一节就有内容可写了。

第二步，给关键函数加计数器。排序实验统计比较次数和移动次数，查找实验统计查找长度，图算法统计松弛次数。这些数据是用来支撑复杂度分析的，比抄一遍大 O 记号有说服力。加计数器的方式很土但有效：在比较和赋值语句旁边各加一个全局变量自增，跑完打印出来。

第三步，把公共的类型定义和工具函数抽到一个common.h里，比如ElemType、Status、OK/ERROR宏、随机数组生成函数。抽完之后每个实验文件都会短一截，报告里的模块结构图也画得出来了。

注意：改源码之前先复制一份原始版本到独立目录，或者用版本管理工具打一个基线提交。改坏了能退回去，这个后悔药比任何调试技巧都值钱。

验证改造有没有改变语义，就用对拍跑一遍原始版本和改造版本，两边输出必须逐字节一致。我吃过一次亏：为了加计数器把循环里的比较挪了位置，排序结果没错，但比较次数统计少算了一轮，报告里的曲线整个偏了一截，交上去之后才发现。从那以后我每次改完源码，都强制走一遍「原始版本与改造版本对拍 + sanitizer 复跑」，两步都过了才认为改动是安全的。希望帮到你。

本文还有配套的精品资源，点击获取