简介：这份南邮数据结构实验源码包面向正在学习数据结构课程的高校学生和需要复现实验的编程初学者，覆盖线性表、栈与队列、二叉树及哈夫曼树、图的基本操作与最短路径等典型实验主题，可用于对照课程进度理解存储结构与算法实现。压缩包共收录64个文件，以13个头文件和10个C++源文件为核心，辅以pdb、obj、ilk等调试编译中间文件、dsw与dsp工程配置和doc实验报告，整体约1.58MB，便于在本地工程中查阅与运行。目前已有2640人学习。读者可获得四次实验的代码框架、各结构的操作实现与调试配置参考，并借助报告梳理多项式、飞机换乘次数问题的建模思路，也可对照顺序表与链表插入删除、栈实现括号匹配、二叉搜索树查找、图的最短路径与拓扑排序环节阅读，适合作为课程实验的对照材料与排错参照，使用时应理解原理并遵循学术诚信。
1. 课程实验源码合集到底能解决什么问题
上学期期末前一周，A 同学把电脑桌面翻了三遍，才在一堆1.c、test.c、新建文件夹(3)里找到那个能跑通的二叉树实验，剩下几个版本不是编译报错就是输出乱码。这套数据结构实验源码合集解决的正是这个场景：线性表、栈与队列、二叉树、哈夫曼树、图、排序与查找按实验分目录存放，每个目录一份独立可编译的 C 源码，配菜单式交互，改完参数就能直接交实验报告。它适合三类人——正在上数据结构课、需要交实验的；准备手撕链表和树的面试题的；想拿一份能跑的代码当模板、改课程设计的。这不是教材，是一份能直接gcc出可执行文件的工程目录，价值在于省掉你自己搭骨架、调输入输出、猜算法边界的那几个小时。
2. 工程骨架与目录结构：一套实验源码怎么组织才不至于互相覆盖
多数人写实验代码是从一个文件开始的：结构体、函数、main 全塞进main.c，写完一个实验复制一份改下一个。这样做在第三个实验就会出问题——InitList在顺序表和链表里各有一份，函数名一撞，链接器直接报multiple definition。这套源码的做法是把每个实验拆成「头文件 + 实现文件 + 主程序」三件套，结构体定义和函数声明进.h，实现进.c，菜单和测试进独立的main.c。好处很直接：想复习哪一块就单独编哪一块，想对比两种存储结构就把两个.c一起链进去也不会冲突。
2.1 按实验编号切分目录的实际布局
目录按exp01到exp08顺序编号，每个目录自成一个可独立编译的小工程，互不依赖。下面这张表是这套源码的文件清单主干，新加实验照着这个格式往里塞就行：
| 目录 | 对应实验 | 核心文件 | 关键函数 |
|---|---|---|---|
| exp01_seqlist | 顺序表 | seqlist.c / seqlist.h | InitList、ListInsert、ListDelete |
| exp02_linklist | 单链表 | linklist.c / linklist.h | HeadInsert、TailInsert、LocateElem |
| exp03_stack | 顺序栈与链栈 | stack.c / stack.h | Push、Pop、GetTop |
| exp04_queue | 循环队列 | queue.c / queue.h | EnQueue、DeQueue、QueueEmpty |
| exp05_bitree | 二叉树 | bitree.c / bitree.h | CreateBiTree、PreOrder、TreeDepth |
| exp06_huffman | 哈夫曼树 | huffman.c / huffman.h | Select、CreateHuffman、Encode |
| exp07_graph | 图的遍历与最小生成树 | graph.c / graph.h | DFS、BFS、Prim |
| exp08_sort | 排序与查找 | sort.c / sort.h | BubbleSort、QuickSort、BinarySearch |
每个目录里还有一份Makefile或一个build.bat，make一下就能出可执行文件。头文件里只放结构体、宏和函数原型，加上#ifndef头文件保护；实现文件里第一行#include自己的头文件，这样编译器会帮你检查声明和定义是否一致。这种分层不是说实验代码必须写得多正式，而是当你想把顺序表改造成支持字符串元素时，只改.h里的typedef和.c里几处赋值，main.c一行都不用动。
2.2 语言标准与编译参数：为什么建议固定成 C99 加两个警告开关
整套代码用 C 写，不上 C++ 的类和模板，原因很实际：课程实验的评测环境常见的是较老版本的编译器，for (int i = 0; ...)这种写法在 C89 下会直接报错，而 C99 已经被绝大多数教学环境支持。编译命令建议固定成下面这一行，别图省事只敲gcc main.c：
gcc -std=c99 -Wall -Wextra -g -o seqlist main.c seqlist.c-std=c99保证循环内声明变量、//注释这些写法可用；-Wall -Wextra打开常用警告，scanf("%d", x)漏掉取地址符、函数声明了返回值却忘了return、变量定义了没用，这三类错误都能在编译阶段被拦下来，不用等到运行出乱码再回头找；-g保留调试符号，后面用gdb或者valgrind定位越界时全靠它。我把-Wall当成血泪经验来看：实验代码里最容易出的不是算法错，是这些编译器一眼就能看出来的低级错误，关掉警告等于自己把安全网撤了。想再狠一点，调试阶段加-fsanitize=address，数组越界和释放后使用会直接打印出错的代码行号。
如果老师的环境是图形化的老 IDE，把这三个文件一起加进工程即可，不需要改任何源码，只是编译参数换成在 IDE 的编译选项里勾上「显示所有警告」。跨平台这一点在这套代码里处理得比较克制：只用标准库的stdio.h、stdlib.h、string.h、time.h，没有conio.h的getch()，也没有windows.h，所以在 Linux、macOS 和常见的教学环境里都能直接编。
2.3 每个实验共用的菜单骨架与输入校验
八个实验的主程序长得几乎一样：打印菜单、读一个整数、switch分发、循环回到菜单。这段骨架看着啰嗦，但它挡掉了演示时最尴尬的一种翻车——输入一个字母，scanf读失败但不消费缓冲区，while循环空转，屏幕疯狂刷菜单，进程卡死只能强杀。
#include <stdio.h> #include "seqlist.h" static void print_menu(void) { printf("\n===== 顺序表实验 =====\n"); printf("1. 插入元素 2. 删除元素\n"); printf("3. 按值查找 4. 打印全表\n"); printf("0. 退出\n"); printf("请选择: "); } int main(void) { SqList L; InitList(&L); int choice, pos, val; while (1) { print_menu(); if (scanf("%d", &choice) != 1) { /* 读到非数字，返回 0 */ while (getchar() != '\n') { } /* 清空整行残留字符 */ printf("输入无效，请重新输入\n"); continue; } if (choice == 0) break; switch (choice) { case 1: printf("输入位序和值(空格分隔): "); if (scanf("%d %d", &pos, &val) != 2) { while (getchar() != '\n') { } break; } printf(ListInsert(&L, pos, val) ? "插入成功\n" : "插入失败\n"); break; case 2: printf("输入要删除的位序: "); if (scanf("%d", &pos) != 1) { while (getchar() != '\n') { } break; } printf(ListDelete(&L, pos, &val) ? "删除成功\n" : "位序非法\n"); break; case 4: PrintList(&L); break; default: printf("没有这个选项\n"); } } return 0; }这段代码的关键点在三处。scanf的返回值是成功读入的项数，不等于期望值就说明输入流里躺着字母或者符号，此时必须用getchar()把当前行剩余字符吃掉，否则下一次循环读到的还是同一个坏字符。菜单用static函数包起来而不是塞进main，是为了后面把某个实验改造成命令行工具时，直接把main换掉、菜单函数删掉即可，业务函数一行不动。InitList(&L)传地址而不是传值，是因为顺序表结构体里那个length必须被函数改到，传值的话初始化完长度还是随机数，后面所有插入都会算错位置——这个坑在下一章的链表里还会以另一种形式出现。
3. 线性表、栈与队列：顺序存储和链式存储的两套写法
线性结构是整门课的地基，也是实验里最容易「看起来跑通了其实全是错」的部分。顺序表错在边界，链表错在指针，栈和队列错在判空判满的条件写反。这三块代码加起来不到四百行，但每一块都有一个绕不过去的取舍：用连续内存换随机访问，还是用指针跳转换插入删除的 O(1)。看懂这层取舍，后面的树和图的存储结构就是同一套思路往上叠。
3.1 顺序表：结构体三件套与插入删除的下标边界
顺序表的结构体就三样东西：一个定长数组、一个当前长度、一个容量上限。教材上常写成data[MAXSIZE]加length，容量靠宏写死，优点是简单，缺点是想改成动态扩容就得动结构体。这套源码保留教材写法，但在插入函数里把边界判断做全了。
#define MAXSIZE 100 #define OK 1 #define ERR 0 typedef struct { int data[MAXSIZE]; /* 静态数组，下标 0..MAXSIZE-1 */ int length; /* 当前元素个数，合法范围 0..MAXSIZE */ } SqList; /* i 是位序，从 1 开始；e 是要插入的值 */ int ListInsert(SqList *L, int i, int e) { if (i < 1 || i > L->length + 1) return ERR; /* 可插入位置是 1..length+1 */ if (L->length >= MAXSIZE) return ERR; /* 表满 */ for (int j = L->length; j >= i; j--) /* 从尾向前后移 */ L->data[j] = L->data[j - 1]; L->data[i - 1] = e; L->length++; return OK; } int ListDelete(SqList *L, int i, int *e) { if (i < 1 || i > L->length) return ERR; /* 可删除位置是 1..length */ *e = L->data[i - 1]; for (int j = i; j < L->length; j++) /* 从前往后前移 */ L->data[j - 1] = L->data[j]; L->length--; return OK; }位序和数组下标差 1 是这段代码里所有错误的源头，ListInsert的上界是length + 1而ListDelete的上界是length，差的就是「能不能在表尾后一格插入」这一条。移动方向也不能反：插入要从尾部往前挪，否则data[i]先被覆盖，后面的值全变成同一个数；删除反过来，从前往后挪。时间复杂度都是 O(n)，随机访问L.data[i-1]是 O(1)，这就是顺序表拿插入删除的代价换来的东西。
改造成动态数组只需要动两处：结构体里把data换成int *data，加一个int capacity；InitList里malloc出一块初始容量，插入前判断length == capacity就realloc成两倍。这一步不难，但要注意realloc失败会返回NULL并且原指针仍然有效，不能直接L->data = realloc(L->data, ...)，得先用临时指针接住再判断，否则内存泄漏加空指针解引用一起来。
3.2 单链表：带头结点的头插法与尾插法
链表实验的第一个分岔路口是「带不带头结点」。带头结点（也叫哨兵结点）的好处是插入删除不用特判第一个位置，空表和非空表代码一样，教材和考试基本都按这个版本出题。头插法和尾插法的差别只在一行指针赋值，但结果完全相反，很多人跑完发现输出是倒序的，以为自己写错了。
typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; /* 头插法：每次插在头结点之后，结果与输入顺序相反 */ LinkList HeadInsert(void) { LinkList L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; /* 空表：头结点 next 必须置空 */ int x; while (scanf("%d", &x) == 1 && x != 9999) { LNode *s = (LNode)malloc(sizeof(LNode)); s->data = x; s->next = L->next; /* 新结点接管原来的第一个结点 */ L->next = s; /* 头结点指向新结点 */ } return L; } /* 尾插法：维护尾指针，结果与输入顺序一致 */ LinkList TailInsert(void) { LinkList L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; LNode *tail = L; /* 尾指针初始指向头结点 */ int x; while (scanf("%d", &x) == 1 && x != 9999) { LNode *s = (LNode)malloc(sizeof(LNode)); s->data = x; s->next = NULL; /* 新尾结点的 next 必须置空 */ tail->next = s; tail = s; } return L; }HeadInsert里那两行赋值的顺序不能换：先让新结点指向当前第一个结点，再让头结点指向新结点，反过来就把后面的整条链丢了。TailInsert里tail指针是必须的，不维护它每次插入都要从头遍历到尾，插入 n 个元素退化成 O(n²)，在数据量上千的测试里能明显感觉到卡。两个函数都用9999当输入结束标记，这是实验里常见的约定，改成 EOF 结束也行，但交互式演示时 EOF 要按 Ctrl+D 或 Ctrl+Z，不如约定一个哨兵值直观。
删除操作要注意「找前驱」这个动作。删第 i 个结点必须停在 i-1 的位置，p = L; for (int j = 0; j < i-1 && p; j++) p = p->next;然后判断p && p->next再摘链，最后free(q)。漏掉free在实验里不会报错，跑一百次也没事，但这是答辩时老师最爱问的一句「你这个删除有没有释放内存」。
3.3 栈与队列：循环队列判满的三种方案
栈分顺序栈和链栈，顺序栈用一个top下标指向栈顶元素，top == -1为空，top == MAXSIZE-1为满，进栈先++top再赋值。链栈本质就是只在头部插入删除的单链表，头插法天然就是栈，代码可以直接复用上一节的HeadInsert逻辑。真正容易写错的是循环队列，因为它有一个「队空和队满条件撞车」的经典问题。
#define MAXQSIZE 10 typedef struct { int data[MAXQSIZE]; int front; /* 队头指针，指向队头元素 */ int rear; /* 队尾指针，指向队尾元素的下一个位置 */ } SqQueue; void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; } /* 方案一：牺牲一个存储单元，队满时 (rear+1)%MAXQSIZE == front */ int EnQueue(SqQueue *Q, int x) { if ((Q->rear + 1) % MAXQSIZE == Q->front) return 0; /* 队满 */ Q->data[Q->rear] = x; Q->rear = (Q->rear + 1) % MAXQSIZE; return 1; } int DeQueue(SqQueue *Q, int *x) { if (Q->front == Q->rear) return 0; /* 队空 */ *x = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXQSIZE; return 1; }这套写法叫「牺牲一个单元」，容量MAXQSIZE实际只能存 9 个元素，考试里经常拿这个点出选择题。另外两种方案是加一个size计数器（入队size++、出队size--，size == 0空、size == MAXQSIZE满），或者加一个tag标志位记录最后一次操作是入队还是出队。加size的方案最好理解，也最容易改成动态扩容：满了就realloc成两倍并把元素重新摆成从下标 0 开始的连续段。缺点是结构体多一个成员，如果老师给的函数原型是固定的，加字段可能对不上，所以这套源码主线还是用牺牲单元的方案，把另外两种写在注释里当备选。
所有取模的地方都要保证MAXQSIZE是正的，并且rear和front永远落在0..MAXQSIZE-1。一旦某处忘了取模，rear会一路涨到 10、11，访问data[10]就是越界，而 C 不会拦你，程序可能正常跑一百次然后在演示当天崩掉。
3.4 排序与查找：用同一份随机数据对拍六个算法
排序实验最容易糊弄的地方是「我输了 5 个数，输出是排好的，所以对了」。5 个数测不出快排的基准选取问题，也测不出归并的边界。这套源码里给排序单独写了一个测试入口：生成一份随机数组，复制若干份，一份交给标准库的qsort当基准，其余交给各个自写排序，最后用memcmp比对，同时用clock()记录耗时。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> static void quick_sort(int a[], int left, int right) { if (left >= right) return; int i = left, j = right, pivot = a[left]; /* 取最左元素为基准 */ while (i < j) { while (i < j && a[j] >= pivot) j--; a[i] = a[j]; while (i < j && a[i] <= pivot) i++; a[j] = a[i]; } a[i] = pivot; quick_sort(a, left, i - 1); quick_sort(a, i + 1, right); } static int cmp_int(const void *a, const void *b) { return (*(const int *)a) - (*(const int *)b); } int main(void) { const int n = 5000; int *base = (int *)malloc(n * sizeof(int)); int *mine = (int *)malloc(n * sizeof(int)); srand((unsigned)time(NULL)); for (int i = 0; i < n; i++) base[i] = rand() % 10000; memcpy(mine, base, n * sizeof(int)); clock_t t0 = clock(); quick_sort(mine, 0, n - 1); clock_t t1 = clock(); qsort(base, n, sizeof(int), cmp_int); /* 标准库结果作基准 */ if (memcmp(base, mine, n * sizeof(int)) == 0) printf("对拍通过, 自写快排耗时 %.3f ms\n", 1000.0 * (t1 - t0) / CLOCKS_PER_SEC); else printf("对拍失败: 排序结果与基准不一致\n"); free(base); free(mine); return 0; }memcmp按字节比较两块内存，比逐个元素循环快，也比较直观。clock()返回的是 CPU 时间刻度，除以CLOCKS_PER_SEC得到秒，乘 1000 换成毫秒，这个值在不同机器上差别很大，只能用来横向对比同一台机器上的几个算法，不能拿去和别人的结果比。测试数据量取 5000 是个折中：冒泡、插入、选择这类 O(n²) 的算法在这个规模下要跑几十到上百毫秒，肉眼能看出差距，又不会让整个测试等到失去耐心；想测快排和归并的差异，得把规模提到十万级，并且换成有序、逆序、大量重复三种数据分别跑一遍——快排在完全有序的数据上取最左元素做基准会退化成 O(n²)，这是教科书上写了但很多人没亲手复现过的一条。
查找部分一般是顺序查找加折半查找两个函数。折半查找的前提是表有序，实验里通常先调一次排序再查，函数签名写成int BinarySearch(const int a[], int n, int key)，返回下标或 -1。循环条件写成while (low <= right)还是<，mid = (low + high) / 2还是low + (high - low) / 2，这两处是查找实验最常被扣分的地方：前者决定最后一个元素能不能查到，后者在low + high溢出时才会出问题，虽然教学数据量不会溢出，但写成后一种形式是习惯问题。
4. 树与图：递归最深、调试最难的两块
从线性结构跳到树，最大的变化是「一个结点有多个后继」，指针从一条链变成分叉，代码里开始大量出现递归。递归写起来短，但调试体验很差——断点一进去就是十几层调用栈，变量窗口里全是同名局部变量。图更麻烦，它把树的分叉变成任意连接，还要处理「访问过没有」这个状态。这两块代码真正需要想清楚的不是语法，而是「每个函数进来时，我手上拿着的是什么、出去时要交回什么」。
4.1 二叉树：先序建树、三种遍历与求深度
二叉树实验一般从「按先序序列建树」开始，输入串里用#表示空结点，比如ABD##E##C##。这个建树函数是本篇里最典型的递归：读一个字符，是#就返回NULL，否则申请结点、递归建左子树、递归建右子树。
typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; /* 按先序序列建树，'#' 表示空子树，输入示例：ABD##E##C## */ BiTree CreateBiTree(void) { char ch; if (scanf(" %c", &ch) != 1) return NULL; /* 前导空格跳过换行和空白 */ if (ch == '#') return NULL; BiTree T = (BiTree)malloc(sizeof(BiTNode)); T->data = ch; T->lchild = CreateBiTree(); /* 先建左子树 */ T->rchild = CreateBiTree(); /* 再建右子树 */ return T; } int TreeDepth(BiTree T) { if (T == NULL) return 0; int l = TreeDepth(T->lchild); int r = TreeDepth(T->rchild); return (l > r ? l : r) + 1; /* 左右取大，加上本层 */ }scanf(" %c", &ch)里那个空格是格式串的一部分，作用是跳过所有前导空白字符（空格、制表符、换行）。写成scanf("%c", &ch)的话，上一次输入残留的换行符会被当成一个有效字符读进去，结果就是建树提前结束或者结构完全错乱——这是本节最值得记住的一行。TreeDepth是理解递归返回值的好例子：空树深度为 0，非空树深度等于左右子树深度的较大值加一，递归出口和递推式都很清楚，比画图讲一遍有效。
三种遍历只差printf的位置：先序在递归左右子树之前打印，中序在中间，后序在最后。层次遍历要借助队列，把根入队，出队时打印并把左右孩子入队，直到队空。这里可以直接复用第 3 章的循环队列，只是队列里存的类型从int换成BiTree，把data数组的元素类型改一下，其他逻辑一行不动——这就是把数据结构写成独立模块的好处。
中序线索化、找前驱后继这类实验属于进阶内容，代码量比建树和遍历大不少。写线索二叉树时最常见的错误是把lchild和ltag的赋值顺序搞反，或者在后序线索化时忘了处理「右孩子就是后继」这种特殊情况。这套源码里线索化的部分注释写得比较细，建议对照着画一遍三个结点的树，把每个指针的实际指向标出来再看代码。
4.2 哈夫曼树：数组存储与两次最小值选择
哈夫曼树不用指针，用数组存，因为要频繁地按权值找最小，数组遍历比指针跳转方便。结点定义里存权值、双亲下标、左右孩子下标，parent == 0表示还没被合并过。n 个叶子结点合并 n-1 次，总共 2n-1 个结点，数组开2n个单元，下标 0 不用，1 到 n 是叶子。
typedef struct { int weight; int parent, lchild, rchild; /* 存的是数组下标，0 表示无 */ } HTNode, *HuffmanTree; /* 在 1..n 中挑两个 parent==0 且权值最小的结点，下标存入 *s1、*s2 */ void Select(HuffmanTree HT, int n, int *s1, int *s2) { int min1 = 0x7fffffff, min2 = 0x7fffffff; *s1 = *s2 = 0; for (int i = 1; i <= n; i++) { if (HT[i].parent != 0) continue; /* 已合并的跳过 */ if (HT[i].weight < min1) { /* 比最小还小，两个都挪位 */ min2 = min1; *s2 = *s1; min1 = HT[i].weight; *s1 = i; } else if (HT[i].weight < min2) { /* 介于最小和次小之间 */ min2 = HT[i].weight; *s2 = i; } } } void CreateHuffman(HuffmanTree HT, const int w[], int n) { int m = 2 * n - 1; for (int i = 1; i <= m; i++) /* 初始化所有结点 */ HT[i].weight = (i <= n ? w[i - 1] : 0), HT[i].parent = HT[i].lchild = HT[i].rchild = 0; for (int i = n + 1; i <= m; i++) { /* 从第 n+1 个开始合并 */ int s1, s2; Select(HT, i - 1, &s1, &s2); HT[s1].parent = HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } }Select里的双最小值更新逻辑是这段代码的核心，也是最容易写错的地方：新元素比min1小时，min1要降级成min2、s1降级成s2，再更新min1；新元素落在min1和min2之间时只更新min2。只写一个最小值变量的话，第二次选择会选到同一个结点，结果是一棵错误的树——程序不崩，但编码长度算出来不对，而且很难查。0x7fffffff是int的最大值，用来当初始最小值，别用99999之类的具体数，权值大一点就失效。
编码部分从叶子往根回溯，是左孩子记0、右孩子记1，得到的序列是逆序的，要反转一次再存。教材上常用一个临时数组存路径、从后往前填，最后拷出来，这样不用写反转函数。解码就顺着编码串从根往下走，0 走左、1 走右，到叶子输出字符再回到根。
4.3 图：邻接矩阵、DFS/BFS 与 Prim 最小生成树
图的存储有两种：邻接矩阵和邻接表。前者一个二维数组，edge[i][j]存权值，适合稠密图和需要快速判断两点是否相连的场景；后者是数组加链表，适合稀疏图，遍历邻居更快但要自己管内存。这套源码的图实验默认用邻接矩阵，因为最小生成树和最短路算法基本都按矩阵下标操作，写起来直观。
#define MAXV 100 #define INF 0x3f3f3f3f /* 用足够大的数表示无边，避免加法溢出 */ typedef struct { int vex[MAXV]; /* 顶点信息，实验里直接存编号 */ int edge[MAXV][MAXV]; /* 邻接矩阵，INF 表示无边 */ int numV, numE; } MGraph; static int visited[MAXV]; /* 全局访问标记，DFS/BFS 共用一个 */ void DFS(MGraph *G, int v) { visited[v] = 1; printf("%d ", G->vex[v]); for (int w = 0; w < G->numV; w++) if (G->edge[v][w] != INF && G->edge[v][w] != 0 && !visited[w]) DFS(G, w); } void BFS(MGraph *G, int v) { int queue[MAXV], front = 0, rear = 0; visited[v] = 1; queue[rear++] = v; /* 入队 */ while (front != rear) { /* 队非空 */ int u = queue[front++]; /* 出队 */ printf("%d ", G->vex[u]); for (int w = 0; w < G->numV; w++) if (G->edge[u][w] != INF && G->edge[u][w] != 0 && !visited[w]) { visited[w] = 1; /* 入队时就标记，不能等出队 */ queue[rear++] = w; } } }visited[w] = 1的位置在 BFS 里必须放在入队那一刻，不能等到出队再标记，否则同一个顶点会被多个邻居重复入队，队列爆掉。DFS 的标记放在进入函数时，效果一样，但逻辑上要清楚「标记意味着已经安排上了」。INF用0x3f3f3f3f而不是INT_MAX，因为最短路算法里要做dist[u] + edge[u][v]的加法，INT_MAX加任何正数都会溢出成负数，这是很多最短路径实现跑出负数的原因。邻接矩阵自己到自己一般填 0，所以判断「有边」要同时排除INF和0，或者干脆把对角线和无边都设成INF，读的时候统一。
Prim 算法的思路是维护两个数组：lowcost[i]表示顶点 i 到当前生成树的最小边权，closest[i]记录这条边连的是树里哪个顶点。每轮从lowcost里挑一个没进树且值最小的顶点加进去，然后用它更新其他顶点的lowcost。初始化时把起点对应的lowcost设 0，其他设成起点到它们的边权。Kruskal 换一种思路，把所有边按权值排序，用并查集判断加边会不会成环，代码量稍大但更适合稀疏图。两种算法的结果可能不同（权值相同的边选法不同），但总权值一定相同，实验报告里如果要验证，比较总权值比比较边集更靠谱。
5. 常见问题排查：五个让实验代码跑不通、跑通了也不对的坑
实验代码的故障有个特点：编译通过不代表对，跑出结果不代表对，只有换几组数据、卡住边界才暴露。下面五条是我在这套源码里反复遇到、也帮别人看过很多次的问题，每条都按「什么现象 → 为什么 → 怎么解决」写，遇到类似症状可以直接对号入座。
5.1 建树只建出一个结点就结束了
现象：输入完整串ABD##E##C##，程序打印出来的遍历结果只有一个A，或者干脆什么都没打印就退出。原因几乎都是scanf("%c", &ch)没有加前导空格。上一次输入留下的换行符会被%c当成一个正常字符读走，它既不是#也不是有效字母，于是建树立刻返回NULL或者建出一个内容为换行符的结点。解决办法有两个：格式串写成" %c"，让scanf自动跳过所有前导空白；或者在读字符之前手动while (getchar() != '\n') {}清一次缓冲区。第二种只在明确知道缓冲区里有换行时用，混用多个scanf的场景下第一种更稳。同理，gets在读字符串时也会把上一行的换行吞进去，现在更推荐fgets加手动去掉末尾换行。
5.2 链表遍历进入死循环，程序卡住不动
现象：跑链表实验，插入几个元素后调用打印函数，终端一直输出同一个数字，Ctrl+C 才能停。原因基本是某个结点的next没有初始化，或者尾结点的next没有置NULL。malloc分配出来的内存内容是未定义的，可能恰好是 0（看起来正常），也可能是上次释放留下的垃圾指针（崩溃）或其他地址（死循环）。最稳妥的做法是malloc之后立刻把next置空，包括中间结点和尾结点。另一个高频原因是在插入时写成了s->next = s这种自环，或者删除结点时只改了前驱的next却忘了free，导致后面某次遍历走到已释放内存上。排查方法：在打印循环里加一个计数器，超过长度上限就printf出当前结点地址并break，一眼就能看出它在哪个结点上打转。
5.3 数组越界了，但程序一声不吭
现象：顺序表插入第 101 个元素、循环队列里rear忘了取模、图的顶点编号用到了numV，程序有时正常、有时输出乱码、有时在演示现场直接段错误。原因是 C 不做运行时的数组边界检查，写越界就是往相邻内存里塞数据，可能覆盖了别的变量、可能落在未使用的栈空间里，所以「有时候没事」。解决办法是在调试阶段编译时加-fsanitize=address，一旦越界立刻打印出错的代码行；或者用valgrind ./程序名跑一遍，越界读写和内存泄漏都会列出来。更根本的做法是把边界检查写进函数本身：每次插入前判断length < MAXSIZE，每次取模都写成(x + 1) % MAXSIZE，图的顶点编号在输入处就校验一遍范围。
5.4 递归函数在大数据上栈溢出
现象：快排对一千个随机数毫无问题，换成有序的一万个就段错误；二叉树深度统计在链状树上崩掉。原因是递归深度等于数据规模。快排取最左元素做基准时，如果输入已经有序，每次划分只能排除一个元素，递归深度退化成 n，每个栈帧占几十字节，几万层就撑爆默认栈空间。二叉树的递归在退化成单链时同理。解决办法：快排改用三数取中或者随机选基准，避免最坏划分；树的遍历如果深度可能很大，改成显式栈的迭代写法；实在要用递归，可以在编译时调大栈限制，但那是权宜之计，不该写进作业里。判断方法很简单：同样的代码，数据量减半就不崩，基本可以确定是深度问题。
5.5 用了未初始化的变量，结果每次运行都不一样
现象：求最短路径时输出的距离是负数或者一个巨大的数；统计二叉树叶子数时多一个少一个。原因通常是数组或变量只声明没初始化，int dist[MAXV]里躺着栈上的随机值，参与比较后把正确结果挤掉；或者计数变量count忘了置 0，累加在垃圾值上。这类问题最气人的地方是可复现性差，重新编译一次结果就变了，很容易被误判成「玄学」。解决办法是把初始化当成硬性习惯：局部数组用memset(dist, 0x3f, sizeof(dist))统一置成INF风格的大值，计数变量声明时就赋 0，结构体用= {0}初始化。编译时加-Wuninitialized（包含在-Wall里）也能提示一部分，但数组元素级别的未初始化它看不出来，只能靠习惯。
6. 二次开发：把菜单式实验代码改成能批量验证的小工具
这套源码交作业够用，但想拿它做课程设计或者放进自己的代码库，有几个地方值得动手改。第一件是把菜单交互拆掉，改成命令行参数加文件输入输出。菜单适合演示，不适合自动化验证——你没法让脚本去「输入 1、输入 3、输入 5」。改法很轻：保留seqlist.c、bitree.c这些业务文件不动，把main.c换成读argv[1]指定的数据文件，结果写到argv[2]，菜单函数直接删掉。这样同一份业务代码既能交互演示，也能被脚本批量跑。
第二件是给每个实验补一个Makefile，别每次手敲一长串gcc。一个目录一份，模板基本一样，改个名字就行：
CC = gcc CFLAGS = -std=c99 -Wall -Wextra -g TARGET = seqlist OBJS = main.o seqlist.o $(TARGET): $(OBJS) $(CC) $(CFLAGS) -o $@ $^ %.o: %.c $(CC) $(CFLAGS) -c $< -o $@ run: $(TARGET) ./$(TARGET) clean: rm -f $(OBJS) $(TARGET) .PHONY: run clean$@是目标名，$^是所有依赖，$<是第一个依赖，这套写法在八个实验目录里通用，只要改TARGET和OBJS两行。make clean一定要有，否则改了头文件里的结构体定义，旧的.o不会自动重编，跑出来的程序行为和源码对不上，查半天查不出原因。想更省事可以加-MMD -MP自动生成头文件依赖，但对八个实验的小工程来说没必要。
第三件是把定长数组换成动态分配，并顺手把容量作为参数暴露出去。顺序表的MAXSIZE、图的MAXV、队列的MAXQSIZE都是宏，改一次要重新编译。改成运行时传入容量，初始化时malloc，销毁时free，这套代码就从「实验作业」变成了能塞进其他项目的小型数据结构库。改造时注意realloc的返回值要先接临时指针，free之后把指针置NULL，这两条是最容易在改造过程中引入新 bug 的地方。
检验改造有没有改坏，最省事的办法是保留原来的对拍思路：改造前用几组固定输入跑一遍，把输出存成expected.txt；改造后用同样的输入跑，diff一下。排序和查找可以直接用随机数据对拍，树和图这种输出结构比较固定的，用固定输入加输出比对就够。
从那以后我每次接手别人写的实验代码，第一件事都不是读算法，而是先用-Wall -Wextra原样编一遍，看它能吐出多少警告，再把每个实验单独跑一遍空输入和边界输入——大部分问题在这一步就现形了，比读代码快得多。希望帮到你。
本文还有配套的精品资源，点击获取
