企业官网建设流程全解析

简介：这份南京邮电大学数据结构课程实验源码合集，面向正在学习数据结构、需要完成课程实验或准备期末复习的本科生与自学者，围绕线性表、栈与队列、树形结构、图及其典型算法提供可运行的实践样例。压缩包共64个文件，以13个h头文件和10个cpp源文件为核心，辅以dsp、dsw工程配置，pdb、obj、ilk等编译调试中间文件，exe可执行文件及doc实验报告，7z包约1.58MB，结构紧凑。已有2640人学习，说明其在课程实验场景中具有一定参考价值。读者可据此对照多项式运算、线性表操作、二叉树与哈夫曼树、图的基本操作及换乘次数等问题，理解数组与链式存储差异、LIFO与FIFO特性、查找效率、最短路径和最小生成树等知识点，并借鉴工程组织与调试过程；源码宜作为学习辅助，结合独立思考使用。

1. 期末周前一周，我翻出了一套数据结构实验源码

每年临近期末，实验室里总有人对着一段跑不出结果的二叉树代码发呆。指针明明赋了值，打印出来却是乱码；栈写完了，括号匹配的用例能过，表达式求值又崩了。这时候能有一份能编译、能对照、注释还写清楚的数据结构实验源码，比翻三本教材都管用。这套资源就是按实验课进度整理的全套源码：线性表、栈与队列、串、树与二叉树、图、查找、排序基本都在里面，每个实验一个独立目录、一个可单独编译的 main。适合两类人：一类是实验课要交作业、想先跑通再理解的在校生；另一类是离开学校几年、想回头补一遍基础结构的开发者，拿它当可执行的复习提纲。

2. 资源盘点：这套数据结构实验源码里到底装了什么

拿到一个源码包，最忌讳的是上来就逐个文件点开看。我的习惯是先看目录结构和文件命名，五分钟就能判断作者的代码组织水平，也能预判后面调试会踩什么坑。这套资源的结构相对朴素，没有引入任何第三方库，也没有 CMake 之类的构建体系，属于典型的课程作业组织方式，但胜在每个实验自洽，单独抽出来也能用。

2.1 实验清单与目录组织

按常见的数据结构实验课大纲，这套源码大致覆盖七个模块，目录名多半是exp01到exp07这类编号，也有按拼音首字母命名的变体。

这个划分方式的好处是边界清楚：想验证快排，就只编译exp07/sort.c，不会牵扯到图的代码。坏处也明显，各实验之间几乎没有共享的类型定义，typedef struct在多个文件里重复出现，后面想整合成一个库，得先做一轮去重。如果时间紧，直接按实验目录逐个跑通就行，不必先动结构。

目录里通常还会带data/存放测试输入，比如data/sort_input.txt是一万条随机整数，data/graph_input.txt是顶点数和边表。这类数据文件的格式往往只在源文件的scanf里体现，没有单独的说明文档，所以我一般先搜一遍fopen和scanf的参数，反推出输入约定，比猜要快得多。

2.2 编译环境与代码风格约定

源码基本是纯 C，标准库用到stdio.h、stdlib.h、string.h、math.h，个别排序实验用time.h做计时。这意味着 gcc 或 clang 直接就能编，Windows 上 MinGW、MSVC 也能过，只是 MSVC 对变长数组和//注释之外的 C99 特性支持要加编译选项。我的建议是统一用-std=c11，避免某些写法在旧标准下报错。

代码风格上有几个共性值得提前知道，因为它们直接影响你读代码的速度：

• 结构体多用typedef起别名，比如typedef struct LNode { ... } LNode, *LinkList;，看到LinkList就知道是指针类型，别当成值类型用。
• 函数返回int的状态码约定俗成：1 表示成功（OK），0 表示失败（ERROR），部分实验用宏定义了#define OK 1、#define ERROR 0、#define OVERFLOW -1。
• 内存分配几乎不做失败检查，malloc完直接解引用。这是课程代码的常态，但你在自己机器上跑大规模数据时，要留意这一点。
• 打印输出格式不统一，有的用%d加空格，有的用%5d对齐。做结果对比时，最好自己写个简单的过滤脚本，别肉眼比对。

提示：先把所有源文件用gcc -fsyntax-only *.c过一遍，能在动手跑之前暴露大部分头文件缺失和类型不匹配的问题。

3. 核心模块拆解：从线性表到图的一条完整链路

真正值得逐行读的是那些“看起来简单、实际边界最多”的函数。数据结构实验的分数往往不丢在算法思想上，而是丢在空表、表尾、下标越界这些地方。下面按实验顺序挑几个关键实现拆开讲，每段代码后面都会说明它为什么这么写、参数怎么调。

3.1 顺序表与链表：头结点到底要不要

单链表的第一道坎是头结点。有头结点，插入删除的代码能统一处理首元结点；没有头结点，就得对第一个位置单独判空。这套源码用的是带头结点的写法，操作函数里几乎看不到if (i == 1)这种特殊分支。

/* exp01/linklist.c —— 带头结点的单链表基本操作 */ #include <stdio.h> #include <stdlib.h> typedef struct LNode { int data; /* 数据域，实验里存 int，改成 char* 也能用 */ struct LNode *next; /* 指针域，指向下一个结点 */ } LNode, *LinkList; /* 头插法建表：新结点永远插在头结点之后，结果与输入顺序相反 */ LinkList CreateListHead(int a[], int n) { LinkList L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; /* 头结点不存数据，next 置空作为初值 */ for (int i = 0; i < n; i++) { LNode *p = (LNode *)malloc(sizeof(LNode)); p->data = a[i]; p->next = L->next; /* 先接住原来的首元结点 */ L->next = p; /* 再让头结点指过来，顺序不能反 */ } return L; } /* 删除第一个值为 x 的结点，返回 1 成功，0 未找到 */ int DeleteFirst(LinkList L, int x) { LNode *pre = L, *p = L->next; while (p != NULL && p->data != x) { pre = p; p = p->next; } if (p == NULL) return 0; /* 走到表尾还没命中，说明 x 不在表里 */ pre->next = p->next; /* 跳过 p，等价于摘链 */ free(p); /* 摘下来必须还回去，否则内存泄漏 */ return 1; }

CreateListHead里那两行赋值顺序是血泪经验：先p->next = L->next，再L->next = p。写反了的话，L->next已经被覆盖，p->next指向自己，遍历时直接死循环。DeleteFirst里的pre指针是必需的，单链表只能单向走，删除某个结点必须拿到它的前驱。

DeleteFirst的参数L是头指针，传值即可，因为改的是pre->next而不是L本身；但如果是删除整个表或者改变头指针指向，就得用LinkList *L二级指针，这个区别在实验里经常被忽略，导致释放后外部还拿着旧指针。

顺序表那边则是另一套边界：插入位置i的合法范围是1 <= i <= length+1，删除是1 <= i <= length，差一位就会越界。源码里通常写成if (i < 1 || i > L.length + 1) return ERROR;，读的时候重点看这个条件，别只看主体循环。

3.2 栈与队列：数组实现和链式实现的取舍

顺序栈简单，top指向栈顶元素，入栈先++top再赋值；链栈则top直接指向栈顶结点，入栈就是头插。这套源码两个都给了，对比着看能理解“为什么链栈不需要判满”。

循环队列是这部分最容易翻车的地方，核心是判空判满的条件。牺牲一个存储单元的做法最普遍：

/* exp02/seqqueue.c —— 循环队列，牺牲一个单元区分队空队满 */ #define MAXQSIZE 100 typedef struct { int data[MAXQSIZE]; int front; /* 指向队头元素 */ int rear; /* 指向队尾元素的下一个位置 */ } SqQueue; void InitQueue(SqQueue *q) { q->front = q->rear = 0; /* 初始时两者相等，表示队空 */ } int EnQueue(SqQueue *q, int e) { if ((q->rear + 1) % MAXQSIZE == q->front) return 0; /* 队满 */ q->data[q->rear] = e; q->rear = (q->rear + 1) % MAXQSIZE; return 1; } int DeQueue(SqQueue *q, int *e) { if (q->front == q->rear) return 0; /* 队空 */ *e = q->data[q->front]; q->front = (q->front + 1) % MAXQSIZE; return 1; }

(q->rear + 1) % MAXQSIZE == q->front这个条件的意思是“再进一个就会追上队头”，所以队列实际最多存MAXQSIZE - 1个元素。如果你把它改成q->rear == q->front判满，那队空和队满的条件就完全一样了，程序会在队列满的时候误判为空，这是实验报告里被问得最多的一个问题。

DeQueue用int *e把出队元素带出来，而不是直接 return，是因为返回值要留给状态码。这种“返回值表状态、指针参数带结果”的写法在整份源码里反复出现，读其他模块时可以直接套。

3.3 二叉树：递归建树与非递归遍历

树这一章的代码量最大，但真正需要吃透的是“由先序和中序序列还原二叉树”。这个函数把递归的分治思想体现得很干净。

/* exp04/bitree.c —— 由先序和中序序列构造二叉树 */ typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; BiTree Build(char pre[], int pl, int pr, char in[], int il, int ir) { if (pl > pr) return NULL; /* 空区间代表空子树，递归出口 */ BiTree root = (BiTree)malloc(sizeof(BiTNode)); root->data = pre[pl]; /* 先序第一个必是根 */ int k = il; while (in[k] != pre[pl]) k++; /* 在中序里定位根 */ int leftLen = k - il; /* 左子树结点个数 */ root->lchild = Build(pre, pl + 1, pl + leftLen, in, il, k - 1); root->rchild = Build(pre, pl + leftLen + 1, pr, in, k + 1, ir); return root; }

参数看着多，其实就两组区间：pre[pl..pr]和in[il..ir]，分别表示当前子树在先序和中序数组里的范围。leftLen是关键量，先序里根之后连续leftLen个元素属于左子树，剩下的属于右子树，中序里根左边是左子树、右边是右子树。四个递归调用的下标只要错一个，建出来的树结构就全歪了，但依然能遍历出结果，属于典型的“错得不容易发现”，建议建完树后打印一次层序遍历验证。

非递归遍历用显式栈实现，中序的写法是“一路向左压栈，弹出访问，转向右子树”。这部分源码通常和栈实验复用同一个SqStack，如果你把栈的MAXSIZE改小了，深度大的树就会栈溢出，这是模块之间隐式耦合的一个例子。

哈夫曼树那部分代码会多一个优先队列或者反复找最小值的循环。课程实现多用手写选择最小值的方式，复杂度 O(n²)，结点数上千时明显变慢。想提速就把选择部分换成小根堆，接口不用改，这也是后面二次开发里最容易做的一个优化点。

3.4 图：邻接矩阵还是邻接表

图实验一般给两套存储结构。邻接矩阵适合稠密图和需要快速判断两点是否相邻的场景，邻接表适合稀疏图。最短路用 Dijkstra，邻接矩阵版本的代码最短：

/* exp05/graph_matrix.c —— 邻接矩阵上的 Dijkstra */ #define INF 0x3f3f3f3f #define MAXV 100 int dist[MAXV], visited[MAXV]; void Dijkstra(int g[][MAXV], int n, int src) { for (int i = 0; i < n; i++) { dist[i] = g[src][i]; /* 初始距离直接取源点的出边 */ visited[i] = 0; } dist[src] = 0; visited[src] = 1; for (int i = 1; i < n; i++) { int u = -1, min = INF; for (int j = 0; j < n; j++) /* 找未访问点里 dist 最小的 */ if (!visited[j] && dist[j] < min) { min = dist[j]; u = j; } if (u == -1) break; /* 剩余点不可达，提前收工 */ visited[u] = 1; for (int v = 0; v < n; v++) /* 用 u 松弛邻居 */ if (!visited[v] && g[u][v] < INF && dist[u] + g[u][v] < dist[v]) dist[v] = dist[u] + g[u][v]; } }

INF取0x3f3f3f3f而不是INT_MAX，是为了做加法时不会溢出成负数，这个技巧在竞赛代码里很常见，课程代码里也照搬了。g是二维数组参数，第二维必须写MAXV，否则编译不过，这是 C 语言传二维数组的硬性要求。n是实际顶点数，可以小于MAXV，循环只跑到n。

邻接表版本的 Dijkstra 需要手写一个“找最小 dist”的循环或者用堆，代码会长一倍。如果你的实验只要求邻接矩阵，建议先把这份跑通，再自己加一个邻接表版本做对比，实验报告的深度立刻不一样。

3.5 排序与查找：同一组数据压一遍

排序实验的价值不在单个算法，而在于横向对比。源码里通常把冒泡、快排、直接插入、堆排、归并放在一个文件里，每个函数签名一致，方便替换调用。

快排的基准选择是个可以动手改的点：把pivot = a[low]改成三数取中，或者在递归深度超过阈值时切到插入排序，都是标准优化。改完用同一组一万条随机数计时，效果能直接体现在实验报告的表格里。

查找部分的重心是折半查找的循环条件和二叉排序树的删除。折半查找写while (low <= high)还是while (low < high)，取决于区间是闭还是半开，两种写法都能对，但混着用必错。BST 删除则要分三种情况：叶子、只有一个孩子、有两个孩子，最后一种要用中序前驱或后继替换，源码里一般选前驱，替换完再递归删前驱结点。

4. 跑起来：从解压到全部用例通过的完整步骤

这份资源的门槛在于“每个实验的输入方式不一样”，有的从标准输入读，有的从data/下的文件读，有的干脆在main里硬编码数组。所以别指望一条命令跑完全部，得分层处理。

4.1 环境准备与一键编译

Windows 上装 MinGW-w64 或者直接用 WSL，Linux 和 macOS 自带 gcc/clang。先确认版本，-std=c11需要 gcc 4.7 以上，基本不用担心。

# 检查编译器 gcc --version # 进入源码根目录，先只做语法检查，不生成可执行文件 gcc -std=c11 -fsyntax-only exp01/*.c

语法检查能过，再写一个 Makefile 批量编译。不要用gcc *.c -o main把全部文件编到一起，多个实验都有main函数，链接时会报multiple definition of main。

CC = gcc CFLAGS = -Wall -Wextra -g -std=c11 # 每个子目录下的 .c 单独编成一个同名可执行文件 TARGETS = $(patsubst %.c,%,$(wildcard exp*/*.c)) all: $(TARGETS) %: %.c $(CC) $(CFLAGS) $< -o $@ -lm clean: rm -f $(TARGETS)

$(wildcard exp*/*.c)展开成所有实验源文件，patsubst把.c后缀去掉得到目标名，模式规则%: %.c负责编译。-Wall -Wextra打开全部警告，课程代码里未使用的变量、隐式类型转换会被报出来，正好当代码审查用。-lm是链接数学库，math.h里的sqrt、pow需要它。

注意：如果把可执行文件和源文件放在同一目录，clean里的rm -f $(TARGETS)只会删掉无后缀的可执行文件，不会误删.c，前提是目标名不带后缀。改 Makefile 时别把TARGETS写成带.c的形式。

4.2 单实验调试：输入约定与断点位置

编译出可执行文件后，先看main里的输入方式。常见的三种：

第一种，scanf从标准输入读，那就手动敲或者用重定向：./exp01/linklist < data/link_input.txt。第二种，fopen读固定路径，这种要保证工作目录对，建议在源码根目录执行，别cd进子目录。第三种，数组硬编码，直接跑就行，改数据要重新编译。

输入格式没有文档时，看scanf的格式串反推是最快的。比如scanf("%d", &n)后面跟一个for循环读n个数，那输入第一行就是元素个数。图实验常见的是先读顶点数和边数，再读边数行u v w三元组，按这个顺序准备数据不会错。

调试时断点优先打在三处：malloc之后看返回值是否为 NULL、循环边界看下标是否越界、free之前看指针是否已经被释放过。用 gdb 的话，gcc -g编译后gdb ./exp01/linklist，break DeleteFirst直接停在函数入口，print *L能看到头结点内容，比加printf干净。

4.3 用对拍验证排序和查找

排序结果对不对，肉眼比对不靠谱。写个简单的对拍脚本，用系统sort或者 Python 的sorted生成标准答案，再和程序输出 diff。

# 生成 10000 个随机整数 python3 -c "import random; print('\n'.join(str(random.randint(-100000,100000)) for _ in range(10000)))" > /tmp/in.txt # 标准答案 sort -n /tmp/in.txt > /tmp/expected.txt # 跑自己的排序程序（假设它从标准输入读、按行输出） ./exp07/sort < /tmp/in.txt > /tmp/actual.txt diff /tmp/expected.txt /tmp/actual.txt && echo "PASS"

sort -n是按数值排序，不加-n会按字典序，负数和多位数都会排错，这个坑我踩过不止一次。对拍的价值在于能把“小数据对、大数据错”的隐藏越界问题暴露出来，一万条数据足够触发大部分下标错误。

查找实验的对拍稍微麻烦一点，因为要验证“找到了”和“没找到”两种结果。我的做法是让程序输出下标，找不到输出 -1，然后用 Python 逐个校验a[idx] == target，比直接比下标更可靠，因为重复元素的存在会让下标不唯一。

5. 避坑与排查：五个真实翻车现场

5.1 编译通过但一运行就段错误

现象：gcc没有任何警告，执行时立刻Segmentation fault，加printf也打不出来。

原因：绝大多数是malloc之后没检查就解引用，或者结构体指针没初始化。课程代码里LNode *p;声明完直接p->data = x;的写法并不少见，p是个野指针，指向哪里全看栈上残留值，玄学得很。

解决：编译时加-g -fsanitize=address，AddressSanitizer 会直接打印出错的文件和行号，比 gdb 单步快得多。养成习惯，所有指针声明处直接初始化为NULL。

5.2 链表遍历打印停不下来

现象：程序卡在打印循环里，输出刷屏或者长时间无响应。

原因：链表成环。常见于头插法里两行赋值写反，p->next = L->next和L->next = p顺序颠倒，新结点的next指向了自己。另一种是删除结点时忘了改前驱的next，只是free了结点，链表还连着已释放的内存。

解决：遍历时加计数器，超过预期长度就 break 并报错，能快速定位是哪次插入出的问题。释放前先把pre->next = p->next写对，再free(p)，顺序不能反。

5.3 文件读入少一条或者最后一条重复

现象：data/里的输入文件明明有 100 行，程序只处理了 99 条，或者最后一条被处理了两次。

原因：while (!feof(fp))配合fscanf的经典错误。feof只有在读操作失败之后才返回真，所以循环会多跑一次，把上一次的结果重复处理。如果文件末尾有换行符，还可能出现最后一条读到一半的情况。

解决：直接用fscanf的返回值做循环条件，while (fscanf(fp, "%d", &x) == 1)，读成功才进循环。这个写法在整份源码里不一定统一，遇到读文件的地方先检查这一句。

5.4 排序小数据正确、大数据出错

现象：10 个元素的用例全过，换成一万个就出现乱序或者崩溃。

原因：数组开小了。int a[100];然后读一万条数据，越界写坏了栈上其他变量，表现可能是排序结果错、可能是循环变量被改、也可能是返回地址被覆盖直接崩。另一种是快排递归深度过大导致栈溢出，有序数组配首元素基准最容易触发。

解决：数组大小用宏或者动态分配，别写死。快排加三数取中，或者递归深度超过2*log2(n)时改用堆排。测试数据规模至少覆盖到实验要求上限的两倍。

5.5 多个源文件一起编译报重定义

现象：multiple definition of 'InitList'，或者undefined reference to 'Push'。

原因：把所有实验的.c一起编译了，不同实验里有同名函数；或者头文件里直接定义了变量（不是extern声明），被多个.c包含后重复定义。

解决：按实验目录分别编译，这是最省事的。如果确实要整合成一个项目，把公共类型和函数声明放.h，定义放.c，头文件里只写extern声明，函数定义前加static限制作用域。

6. 二次开发：把实验代码改成能讲清楚的项目

实验代码最大的问题是“每个函数都能跑，但凑一起不像一个项目”。想让它在简历或者课程设计里站得住，做两件事就够了：统一接口，加一层验证。

第一步，把七个实验里重复的typedef抽到一个ds.h里，所有结构体、状态码宏、MAXSIZE常量集中管理。然后给每个模块写一对Create/Destroy函数，把malloc和free收口。这样别人拿到你的代码，不用逐个文件找哪里分配了内存。接口风格参考下面这样：

/* ds.h —— 公共定义，所有实验共用 */ #ifndef DS_H #define DS_H #define OK 1 #define ERROR 0 #define MAXSIZE 1024 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; LinkList List_Create(void); /* 创建空表，返回头结点 */ int List_Insert(LinkList L, int i, ElemType e); int List_Delete(LinkList L, int i, ElemType *e); void List_Destroy(LinkList L); /* 释放全部结点，含头结点 */ #endif

统一前缀之后，List_、Stack_、Queue_、Tree_、Graph_一眼能看出归属，和系统库函数也不容易撞名。

第二步，加一个test/目录，用最朴素的断言把每个模块的关键路径压一遍。不用引入测试框架，一个assert加一个计数就够了：

/* test/test_list.c */ #include <assert.h> #include <stdio.h> #include "ds.h" int main(void) { LinkList L = List_Create(); for (int i = 1; i <= 5; i++) assert(List_Insert(L, i, i * 10) == OK); ElemType e; assert(List_Delete(L, 3, &e) == OK && e == 30); /* 删中间 */ assert(List_Delete(L, 1, &e) == OK && e == 10); /* 删首元 */ assert(List_Delete(L, 4, &e) == OK && e == 50); /* 删表尾 */ assert(List_Delete(L, 4, &e) == ERROR); /* 越界必须失败 */ List_Destroy(L); printf("list ok\n"); return 0; }

首元、中间、表尾、越界这四种情况覆盖到，链表的坑基本就填完了。栈和队列照着写，树重点测空树和单结点树，图测不连通的情况。这套测试跑一遍不到一秒，但能挡住后面九成的回归问题。

第三步，如果你想让项目更有说服力，挑一个模块做性能对比。把排序实验里的五个算法统一到Sort_接口下，用同一份随机数据跑计时，输出一张 Markdown 表格。数据规模从一千到十万，每个规模跑三次取平均。这个过程会逼你处理计时精度、缓存影响、编译器优化等级这些细节，比单纯交实验报告有价值得多。

我自己的习惯是，每次改完公共头文件，先把test/全跑一遍再动其他代码。有次图省事跳过了，结果MAXSIZE从 1024 改成 100 之后，循环队列的判满条件全部失效，测试用例挂了三个才反应过来。从那以后我每次调整常量或者结构体布局，都强制走一遍make test，后悔药这东西，能提前吃就别省。希望帮到你。

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