简介：面向数据结构课程学习与实验复现需求，这套南邮数据结构实验源码覆盖线性表、栈与队列、二叉树与哈夫曼树、图及其基本操作等核心内容，并含多项式运算、飞机换乘次数等典型实验场景，适合高校学生对照课程进度完成上机练习，也便于自学者梳理 C/C++ 实现思路。压缩包共 64 个文件，约 1.58MB，以 10 个 cpp 源文件和 13 个 h 头文件为主体，另有 dsw、dsp 等工程配置文件、exe/pdb 等编译产物及 doc 实验报告，便于直接查看工程结构、模块组织与运行结果。目前已有 2640 人学习，读者可从中获得各实验的代码框架、数据结构定义、核心算法实现和报告参考，用于调试排错、对比不同存储方式与算法策略，并积累调试经验。使用时建议结合课程要求独立理解与改写，将其作为辅助材料而非直接提交的答案。

1. 一套数据结构实验源码，值不值得花一晚上跑通

实验课上照着敲完、交完就忘的代码，和能在自己机器上一次编译通过、还能随手改两行看结果的代码，中间隔的不是智商，是一整套工程细节。这套某高校计算机专业数据结构课程的完整实验源码，按实验分目录，从顺序表、单链表、栈与队列，一路到二叉树、哈夫曼、图、哈希表和各类排序，每个目录都带main.c和固定测试数据，能独立编译、独立运行。它解决的不是“我没听过快速排序”这种问题，而是“我知道原理但写不出能跑的实现”和“跑出来了但不知道对不对”这两件事。适合三类人：正在赶实验报告的学生、想刷一遍基础结构的转行从业者、以及需要一份能改造成教学或面试题库素材的工程师。下面的内容按“先跑通、再看懂、最后能改”的顺序拆，每一步都落到具体命令和参数上。

2. 源码包先跑通再谈看懂：目录、编译链与测试数据

拿到一包源码，最忌讳的动作是从第一个.c文件开始读。人的短期记忆装不下十几个文件里的结构体定义，读三页就断线。正确顺序是：先让每个目录都能编译出可执行文件，再用固定输入跑出固定输出，最后才回头看核心函数。这一章就是把“能编译、能跑、能比对”这三步固化下来。

2.1 目录与文件职责：先画一张调用地图

这类成套源码的目录组织通常高度一致，先认目录再认文件，比逐个打开快得多。下面是我拆这类包时习惯先画的一张表，实际目录名可能略有差异，但职责划分基本对得上：

读的顺序建议从main.c的输入解析开始，看它怎么读数据、怎么调用核心函数、怎么打印结果，再顺着调用跳到.c里的实现。头文件里只放结构体定义和函数声明，一个.h里出现大段函数体，说明这份源码是“贴代码式”写法，改的时候要格外小心重复定义。

2.2 编译链：gcc 单文件、多文件与 Makefile

单个实验目录往往只有一个.c加一个main.c，直接一条gcc就能出可执行文件。多文件实验要分开编译再链接，好处是改一个文件只重编那一个，调试时也方便单独替换某个模块：

# 单文件实验：开满警告，保留调试符号，关掉优化方便单步 gcc -std=c99 -Wall -Wextra -g -O0 01_seqlist/seqlist.c 01_seqlist/main.c -o build/seqlist # 多文件实验：-c 只编译不链接，产出 .o 目标文件 gcc -std=c99 -Wall -Wextra -g -O0 -c 04_tree/btree.c -o build/btree.o gcc -std=c99 -Wall -Wextra -g -O0 -c 04_tree/main.c -o build/tree_main.o gcc build/btree.o build/tree_main.o -o build/btree # 跑一下，看退出码 ./build/btree; echo "exit=$?"

参数逐条解释：-std=c99是因为源码里普遍用了for (int i = 0; ...)这种循环内声明和//注释，用默认的 gnu 方言可能在某些编译环境下报错；-Wall -Wextra把“变量未初始化”“有返回值函数缺 return”这类隐式问题全部暴露出来，这类警告在数据结构代码里十有八九是真 bug；-g保留符号表，段错误时gdb能打出函数名和行号；-O0关优化，避免变量被优化掉导致单步跳行。

嫌每次手敲太长，就在包根目录放一个 Makefile，让make一把编完：

CC := gcc CFLAGS := -std=c99 -Wall -Wextra -g -O0 BUILD := build TARGETS := $(BUILD)/seqlist $(BUILD)/linkedlist $(BUILD)/btree $(BUILD)/graph all: $(TARGETS) $(BUILD)/seqlist: 01_seqlist/seqlist.c 01_seqlist/main.c | $(BUILD) $(CC) $(CFLAGS) $^ -o $@ $(BUILD)/linkedlist: 02_linkedlist/linkedlist.c 02_linkedlist/main.c | $(BUILD) $(CC) $(CFLAGS) $^ -o $@ $(BUILD)/btree: 04_tree/btree.c 04_tree/main.c | $(BUILD) $(CC) $(CFLAGS) $^ -o $@ $(BUILD)/graph: 06_graph/graph.c 06_graph/main.c | $(BUILD) $(CC) $(CFLAGS) $^ -o $@ $(BUILD): mkdir -p $(BUILD) clean: rm -rf $(BUILD) .PHONY: all clean

$^是全部依赖文件，$@是目标名，| $(BUILD)表示目录存在性检查排在编译之前。缩进必须是制表符，用空格替代会直接报missing separator，这是新手第一个翻车点。make clean后再make能复现从零构建，遇到“明明改了代码却没生效”时，先make clean再编，比怀疑人生快。

2.3 输入输出约定：用固定测试数据反推接口

每个实验目录通常配一组test.in/test.out，格式大同小异：第一行是元素个数 n，第二行是 n 个整数，后面的若干行是操作指令或查询。先把这套约定摸清楚，就不用去猜函数签名了：

# 用重定向把测试数据喂进去，输出重定向到临时文件 ./build/seqlist < 01_seqlist/test.in > /tmp/out.txt # 和随包的期望输出做比对，完全一致才算逻辑通过 diff -u 01_seqlist/test.out /tmp/out.txt && echo "PASS" || echo "FAIL"

diff的退出码是 0 表示一致，非 0 表示有差异，-u会按行给出上下文，方便直接看出是第几行、差在哪个数字上。这一步的价值在于把“编译通过”和“逻辑正确”彻底分开：编译通过只说明语法和链接没问题，diff通过才说明你的指针操作没把数据搞丢。

遇到输出格式不匹配（多了空格、少了换行）的情况，别急着改算法，先看printf的分隔符。这类源码大量使用"%d "这种带尾随空格的格式，diff会把它当成真实差异报出来。通常的处理是先统一成行尾不留空格，再重新比对。

3. 线性表、栈与队列：下标、指针、循环数组的三套边界

线性结构是整包源码里最容易“看起来会、写起来错”的部分。原因不复杂：顺序表考的是下标推导，链表考的是指针顺序，循环队列考的是取模判满，三套边界规则各不相同，混着记必然出问题。这一章把三处最容易错的边界单独拎出来。

3.1 顺序表：插入删除的下标推导与长度陷阱

顺序表的核心只有两行：挪数据和改长度。但这两行的顺序和方向一旦写反，程序不会报错，只会默默丢数据。

#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; /* 静态分配，实验场景够用 */ int length; /* 当前元素个数，不是下标上限 */ } SeqList; /* pos 为 1 基位序：合法范围 1 ~ length+1；返回 1 成功，0 失败 */ int ListInsert(SeqList *L, int pos, int e) { if (L->length >= MAXSIZE) return 0; /* 表满，先判满再判位序 */ if (pos < 1 || pos > L->length + 1) return 0; /* 位序越界 */ for (int i = L->length; i >= pos; i--) /* 从后往前挪，避免覆盖 */ L->data[i] = L->data[i - 1]; L->data[pos - 1] = e; /* 位序转下标要减 1 */ L->length++; /* 长度最后加 */ return 1; } /* 删除第 pos 个元素，用 e 带回被删的值 */ int ListDelete(SeqList *L, int pos, int *e) { if (pos < 1 || pos > L->length) return 0; /* 删除时上限是 length，不是 length+1 */ *e = L->data[pos - 1]; for (int i = pos; i < L->length; i++) /* 从前往后挪 */ L->data[i - 1] = L->data[i]; L->length--; return 1; }

循环方向是最关键的一点：插入必须从表尾往插入位置倒着挪，正着挪会把data[pos-1]覆盖掉，后面全是重复值；删除必须从插入位置往表尾正着挪，倒着挪会把最后一个元素复制成一串。判断条件也有讲究，插入的合法上限是length + 1（可以插在表尾），删除的上限是length（不能删不存在的元素），这两个差 1 的地方是判题系统最常见的扣分点。

参数约定同样要统一。这套源码里位序统一是 1 基，数组下标是 0 基，转换点只允许出现在“取元素”和“写元素”这两行。如果一半函数按 1 基处理、一半按 0 基，表现是插入第一个位置时数据正确、插入最后一个位置时越界，这种 bug 靠读代码很难发现，靠diff一跑就现形。

时间复杂度上，插入和删除平均移动 n/2 个元素，是 O(n)；按下标取值是 O(1)。实验报告里写这一句就够，不用展开。

3.2 单链表：头结点、尾插法与销毁顺序

链表题的共同特征是“指针赋值顺序决定成败”。这套源码用带虚拟头结点的写法，好处是插入和删除不用对第一个结点做特判，代码路径只有一条。

typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; /* 尾插法建表：数组 a 有 n 个元素，返回带头结点的链表 */ LinkList ListTailInsert(const int *a, int n) { LNode *head = (LNode *)malloc(sizeof(LNode)); if (!head) return NULL; head->next = NULL; /* 头结点不存数据，next 先置空 */ LNode *tail = head; /* tail 永远指向最后一个结点 */ for (int i = 0; i < n; i++) { LNode *p = (LNode *)malloc(sizeof(LNode)); if (!p) return head; /* 半途失败：返回已建好的部分，由调用方释放 */ p->data = a[i]; p->next = NULL; tail->next = p; /* 先接上，再移动尾指针，顺序不能反 */ tail = p; } return head; } /* 销毁：先存后继再 free，否则 free 完就取不到 next 了 */ void DestroyList(LinkList head) { while (head) { LNode *next = head->next; free(head); head = next; } }

尾插法的两个赋值必须按tail->next = p; tail = p;的顺序写。反过来先移动tail，新结点就永远挂不到链上，输出结果长度少 1，且不会报错。头插法则是每次插在头结点之后，天然逆序，很多“链表逆置”的题目就是头插法的直接应用，看源码时可以对照着理解。

销毁函数的顺序是另一处高频错误。free(head)之后再访问head->next属于访问已释放内存，在部分平台上碰巧能跑，换个编译器就段错误。先把next存到局部变量，再释放当前结点，这个习惯要固定下来。

带虚拟头结点还有一个隐性好处：删除第一个数据结点和删除中间结点的代码完全一致，都是prev->next = p->next; free(p);。如果不带头结点，删除首结点要单独改头指针，多一条路径就多一处出错可能。代价是多占一个结点的内存，实验场景完全可以接受。

3.3 栈与循环队列：判空判满的三种写法

顺序栈的争议点在top的语义：指向栈顶元素，还是指向栈顶的下一个空位。两种约定都合法，但混用必错。这套源码统一用“top指向栈顶元素，初始为 -1”，入栈是data[++top] = e，出栈是e = data[top--]，栈空判断是top == -1。

循环队列的坑更多，因为“队空”和“队满”在front == rear这个条件上会撞车。常见三种处理方式，源码里通常只用一种，但你要知道另外两种存在：

#define MAXQ 50 typedef struct { int data[MAXQ]; int front; /* 指向队头元素 */ int rear; /* 指向队尾元素的下一个位置 */ } SqQueue; int QueueEmpty(SqQueue *q) { return q->front == q->rear; } int QueueFull(SqQueue *q) { return (q->rear + 1) % MAXQ == q->front; } /* 牺牲一个单元 */ int EnQueue(SqQueue *q, int e) { if (QueueFull(q)) return 0; /* 满队直接拒绝，不覆盖旧数据 */ q->data[q->rear] = e; q->rear = (q->rear + 1) % MAXQ; /* 取模实现循环 */ return 1; } int DeQueue(SqQueue *q, int *e) { if (QueueEmpty(q)) return 0; *e = q->data[q->front]; q->front = (q->front + 1) % MAXQ; return 1; }

用这个方案时，队列最多存MAXQ - 1个元素。测试数据里如果连续入队 50 个，第 50 个会失败，这不是逻辑错误而是容量约定。看到“入队返回失败但队列看起来没满”，先数一下元素个数是不是刚好等于MAXQ - 1。

另外rear的语义也要和判满公式对齐。上面这套是“rear指向下一个空位”，所以判满用(rear+1)%M == front；如果改成“rear指向队尾元素本身”，公式就变成(rear+2)%M == front。改源码时动了rear的含义却没改判满公式，表现是队列提前报满或者写穿数组，这类问题只能靠单步调试看front/rear的实际值。

4. 树、图与查找结构：递归、邻接表与哈希冲突

非线性结构是这包源码里代码量最大的部分，也是最值得逐行读的部分。二叉树考递归思维，哈夫曼考贪心选择，图考存储结构的选择，哈希考冲突处理策略。四块的共同点是：结构体定义只有几行，算法全在函数里，读的时候一定要拿纸画一遍中间状态。

4.1 二叉树：先序建树与三种遍历（含非递归栈版）

建树用的是扩展先序序列，#表示空子树。比如ABD##E##C##对应一棵左子树较深的树。这种输入方式对递归极其友好，读一个字符就决定当前子树的存在与否：

typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; /* 按先序序列建树，'#' 表示空子树，输入示例：ABD##E##C## */ BiTree CreateBiTree(void) { char ch = getchar(); if (ch == '#' || ch == EOF) return NULL; /* 空子树直接返回 */ BiTree t = (BiTree)malloc(sizeof(BiTNode)); if (!t) return NULL; t->data = ch; t->lchild = CreateBiTree(); /* 先建左子树 */ t->rchild = CreateBiTree(); /* 再建右子树 */ return t; }

这里最容易翻车的是getchar()读到了上一次输入残留的换行符，第一个字符就是\n，整棵树的根结点变成一个不可见字符，输出看起来“少了个结点”。解决办法是在调用前清一次输入缓冲，或者改用scanf(" %c", &ch)带前导空格跳过空白。

递归遍历三行代码，没什么好讲的，真正值得看的是非递归版本，因为它把“递归栈”这个黑匣子摊开了：

/* 非递归中序：显式栈模拟系统调用栈 */ void InOrderNonRecursive(BiTree root) { BiTree stack[64]; /* 实验数据树高远小于 64，静态栈够用 */ int top = -1; BiTree p = root; while (p || top >= 0) { if (p) { stack[++top] = p; /* 一路向左，沿途压栈 */ p = p->lchild; } else { p = stack[top--]; /* 左边走不动了，弹栈访问 */ printf("%c ", p->data); p = p->rchild; /* 转向右子树 */ } } }

栈的深度等于树高，链状树的最大深度是 n，所以静态栈大小要按最坏情况给。很多包的示例里写stack[100]，节点数超过 100 的链状树会直接越界写坏栈内存，表现是遍历到某一步突然输出乱码。改成malloc(n * sizeof(BiTNode *))或按实测树高动态分配更稳。参数上，top初始为 -1 表示空栈，压栈用前置++，弹栈用后置--，和顺序栈的约定保持一致即可，但一套代码里必须统一。

4.2 二叉排序树与哈夫曼编码表

二叉排序树的插入是一路比较、一路下沉，递归写法最直观，但要记得把返回值接回左右孩子指针，否则新建的结点挂不上去：

/* 插入 key，返回新的根；重复 key 直接返回原树，不重复插入 */ BiTree BstInsert(BiTree t, int key) { if (!t) { BiTree p = (BiTree)malloc(sizeof(BiTNode)); p->data = key; p->lchild = p->rchild = NULL; return p; } if (key < t->data) t->lchild = BstInsert(t->lchild, key); else if (key > t->data) t->rchild = BstInsert(t->rchild, key); return t; }

t->lchild = BstInsert(...)这种写法不能省成BstInsert(t->lchild, key);，后者在子树为空时新建的结点没有父指针接回去，插入直接丢失。这是二叉排序树实现里最隐蔽的一个错误，编译无警告，运行无崩溃，只是树里少了个数。

哈夫曼树的结构通常用数组存，每个结点记weight、parent、lchild、rchild，索引充当“指针”：

typedef struct { int weight; int parent, lchild, rchild; /* 0 表示无，结点从 1 开始编号 */ } HTNode, *HuffmanTree; /* 在 1..range 中找两个 parent==0 且 weight 最小的结点，用 s1、s2 带回 */ static void SelectTwo(HuffmanTree ht, int range, int *s1, int *s2) { *s1 = *s2 = 0; for (int i = 1; i <= range; i++) { if (ht[i].parent != 0) continue; if (*s1 == 0 || ht[i].weight < ht[*s1].weight) { *s2 = *s1; *s1 = i; } else if (*s2 == 0 || ht[i].weight < ht[*s2].weight) { *s2 = i; } } }

SelectTwo是线性扫描，整体复杂度 O(n²)，实验规模（几十个字符）完全够用。换成小根堆是 O(n log n)，属于加分项，不是必需项。要注意的是*s1、*s2的初值必须为 0 且判断里带*s1 == 0，否则第一次比较会拿ht[0]当候选，ht[0]通常是未初始化的野值。

编码表的生成从每个叶子往上走到根，左孩子记 0、右孩子记 1，得到的是逆序码，需要倒着存进编码数组。这一步顺序搞反，编码能生成、能解码，但和标准答案对不上，diff一跑就露馅。

4.3 图：邻接矩阵与邻接表的 DFS/BFS、Dijkstra

存储结构的选择直接决定代码形态，先看一张对比表：

单源最短路用 Dijkstra，邻接矩阵版本写起来最直接：

#define INF 0x3f3f3f3f /* 用这个值而不是 INT_MAX，加边权不会溢出 */ #define MAXV 100 int dist[MAXV], visited[MAXV], prev[MAXV]; void Dijkstra(int n, int g[MAXV][MAXV], int src) { for (int i = 0; i < n; i++) { dist[i] = INF; visited[i] = 0; prev[i] = -1; } dist[src] = 0; for (int k = 0; k < n; k++) { int u = -1, best = INF; for (int i = 0; i < n; i++) /* 选未访问中 dist 最小的点 */ if (!visited[i] && dist[i] < best) { best = dist[i]; u = i; } if (u == -1) break; /* 剩下的点都不可达 */ visited[u] = 1; for (int v = 0; v < n; v++) { /* 松弛所有邻边 */ if (g[u][v] != INF && dist[u] + g[u][v] < dist[v]) { dist[v] = dist[u] + g[u][v]; prev[v] = u; } } } }

INF取0x3f3f3f3f而不是INT_MAX，是因为松弛时要算dist[u] + g[u][v]，两个INT_MAX相加会溢出成负数，最短路结果直接变成垃圾。0x3f3f3f3f约 10.6 亿，两个相加仍在int范围内，是图论代码里的通用做法。

prev数组用来回溯路径，从终点一路往前找prev直到源点，把路径反转过来输出。很多源码只输出距离不输出路径，改造成“输出路径”是很常见的加分需求，加一个数组就够。

邻接表版本的 BFS 需要手写队列或者复用第 3 章的循环队列。这块的坑是结点编号从 0 还是 1 开始，源码里两种都可能出现，for (int i = 1; i <= n; i++)和for (int i = 0; i < n; i++)差一个下标，输入数据对不上时第一个想到的就该是这里。

4.4 哈希表：除留余数与线性探测的装载因子

哈希表实验的评分点集中在冲突处理。这套源码用除留余数法加线性探测，表长取素数，冲突时往后找第一个空位：

#define HASHSIZE 13 /* 取小于表长的最大素数，冲突分布更均匀 */ typedef struct { int key; int state; /* 0 空，1 占用，2 已删除 */ } HashSlot; HashSlot ht[HASHSIZE]; int Hash(int key) { return key % HASHSIZE; } /* 插入：找到空位或已删除位就写入；key 已存在则忽略 */ int HashInsert(int key) { int start = Hash(key); for (int i = 0; i < HASHSIZE; i++) { int idx = (start + i) % HASHSIZE; /* 线性探测，步长固定为 1 */ if (ht[idx].state != 1) { ht[idx].key = key; ht[idx].state = 1; return 1; } if (ht[idx].key == key) return 1; /* 已存在，不重复插 */ } return 0; /* 表满 */ } /* 查找：从哈希位置往后扫，遇到真空位才算失败 */ int HashFind(int key, int *pos) { int start = Hash(key); for (int i = 0; i < HASHSIZE; i++) { int idx = (start + i) % HASHSIZE; if (ht[idx].state == 0) return 0; /* 真空位：后面不可能再有 */ if (ht[idx].state == 1 && ht[idx].key == key) { *pos = idx; return 1; } } return 0; }

state用三个值而不是用key == -1表示空，是为了区分“从未使用”和“被删除”。用线性探测又支持删除时，如果删除后直接把位置置空，会导致后面本应能查到的 key 提前中断查找，表现是“刚删了一个无关的 key，另一个 key 就查不到了”。这就是必须引入删除标记的原因。

表长取素数是老规矩，HASHSIZE = 13时装载因子在 0.75 以下，线性探测的平均查找长度还在可接受范围；实验数据量再大就要扩表或换成链地址法。链地址法的实现更简单，每个桶挂一条单链表，删除也不用标记，只是多了指针操作。

5. 常见问题与排查：五个连夜改代码的坑

这一节记录的五个问题，基本覆盖了这套源码在新机器上跑不通的绝大多数情况。每条按“现象 → 原因 → 解决”写，遇到对不上的现象，先按顺序核一遍。

5.1 现象：程序在free之后段错误

现象很典型：链表或二叉树销毁函数跑到一半突然Segmentation fault，用gdb看栈帧停在一个free调用附近，但看不出哪里越界。

原因是释放顺序错了。free(p)之后再取p->next属于访问已释放内存，有的平台这块内存还没被复用，读出来是旧值，程序碰巧能跑完；换个编译器或加个-O2，内存被立即回收，直接崩。树的后序销毁也常犯这个错：先释放根，再去递归释放孩子。

解决方式只有一个：任何销毁逻辑里，先把后继指针存到局部变量，再做释放。树的后序销毁则严格按“左、右、根”的顺序递归，根最后释放。养成习惯后，这类段错误基本绝迹。

5.2 现象：遍历输出总比预期少一个结点

现象是链表打印出来少一个元素，或者二叉树中序遍历少最后一个字符，但插入函数的返回值都显示成功。

原因通常是循环条件写成了while (p->next)。带头结点的链表，从head->next开始遍历时条件应该是while (p)，用p->next会在最后一个结点前停下；反过来如果不带头结点，从head开始用while (p)又会漏掉判空，空表直接崩。

解决方式是先确认链表带不带头结点，再决定循环条件。一个稳妥的判断方法：打印函数的第一行先输出head->next == NULL的真假，空表时应该打印出“空表”而不是崩溃。这个自检花两行代码，能省掉大量排查时间。

5.3 现象：循环队列入队失败，但看起来没满

现象是连续入队到第MAXQ - 1个之后，EnQueue返回 0，可程序里打印的元素个数明显小于数组长度。

原因就是“牺牲一个单元”的约定：判满条件是(rear + 1) % MAXQ == front，队列实际容量只有MAXQ - 1。这个设计换来实现简单，代价是浪费一个槽位，很多人在读源码时忽略了这一点。

解决办法有两条路：要么把测试数据规模控制在MAXQ - 1以内，要么改成size计数方案，判满改成size == MAXQ，容量用满。改的时候记得入队size++、出队size--，两个分支都要改，漏一个就会出现“明明空队列却报满”的怪现象。

5.4 现象：先序建树输入第一字符就异常

现象是输入ABD##E##C##之后，建出来的树根结点是一个空白或乱码字符，遍历输出完全对不上。

原因是getchar()读到了上一轮scanf遗留的换行符。scanf("%d", &n)只取走数字，回车还留在缓冲区里，紧接着的CreateBiTree()第一个getchar()就把\n当成了结点数据。

解决办法是在建树前清一次缓冲区，或者把读取方式统一成scanf(" %c", &ch)，格式串里那个空格会跳过所有空白字符。更彻底的做法是整个程序只用一种输入方式，混用scanf和getchar是这类问题的根源。

5.5 现象：Dijkstra 输出的距离是负数或一个奇怪的巨大值

现象是打印出来的最短距离出现负数，或者是一个接近2147483647的数字。

原因有两个。一是邻接矩阵里“无边”的初值用了INT_MAX，松弛时dist[u] + g[u][v]两个大数相加溢出成负数，负数又比任何正常距离都小，于是被当成更短的路径写进dist。二是矩阵初始化时对角线没置 0，源点到自身的距离不是 0，后续所有松弛都基于错误起点。

解决办法是把INF换成0x3f3f3f3f，并在建图前把整个矩阵先刷成INF，再把g[i][i]置 0。刷矩阵这一步用memset(g, 0x3f, sizeof(g))一行搞定，前提是INF的每个字节都相同，0x3f3f3f3f正好满足。

6. 排序实验的量化验证：把 O(n²) 和 O(nlogn) 打成计数器

排序这一组实验的正确性最容易验证，随手一组数据跑完对个序列就知道对不对，真正难的是“怎么证明它确实是 O(nlogn)”。我的做法是在比较和移动的地方各挂一个计数器，用数据说话，而不是靠背诵结论。下面以快速排序为例，在分区函数里加计数：

static long g_cmp; /* 关键字比较次数 */ static int Partition(int *a, int low, int high) { int pivot = a[low]; /* 取首元素为枢轴，实验数据随机时够用 */ while (low < high) { while (low < high && (++g_cmp, a[high] >= pivot)) high--; <p> <a href="https://download.csdn.net/download/programchangesworld/8590767" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>