简介面向数据结构课程学习与实验复现需求这套南邮数据结构实验源码覆盖线性表、栈与队列、二叉树与哈夫曼树、图及其基本操作等核心内容并含多项式运算、飞机换乘次数等典型实验场景适合高校学生对照课程进度完成上机练习也便于自学者梳理 C/C 实现思路。压缩包共 64 个文件约 1.58MB以 10 个 cpp 源文件和 13 个 h 头文件为主体另有 dsw、dsp 等工程配置文件、exe/pdb 等编译产物及 doc 实验报告便于直接查看工程结构、模块组织与运行结果。目前已有 2640 人学习读者可从中获得各实验的代码框架、数据结构定义、核心算法实现和报告参考用于调试排错、对比不同存储方式与算法策略并积累调试经验。使用时建议结合课程要求独立理解与改写将其作为辅助材料而非直接提交的答案。1. 一套数据结构实验源码值不值得花一晚上跑通实验课上照着敲完、交完就忘的代码和能在自己机器上一次编译通过、还能随手改两行看结果的代码中间隔的不是智商是一整套工程细节。这套某高校计算机专业数据结构课程的完整实验源码按实验分目录从顺序表、单链表、栈与队列一路到二叉树、哈夫曼、图、哈希表和各类排序每个目录都带main.c和固定测试数据能独立编译、独立运行。它解决的不是“我没听过快速排序”这种问题而是“我知道原理但写不出能跑的实现”和“跑出来了但不知道对不对”这两件事。适合三类人正在赶实验报告的学生、想刷一遍基础结构的转行从业者、以及需要一份能改造成教学或面试题库素材的工程师。下面的内容按“先跑通、再看懂、最后能改”的顺序拆每一步都落到具体命令和参数上。2. 源码包先跑通再谈看懂目录、编译链与测试数据拿到一包源码最忌讳的动作是从第一个.c文件开始读。人的短期记忆装不下十几个文件里的结构体定义读三页就断线。正确顺序是先让每个目录都能编译出可执行文件再用固定输入跑出固定输出最后才回头看核心函数。这一章就是把“能编译、能跑、能比对”这三步固化下来。2.1 目录与文件职责先画一张调用地图这类成套源码的目录组织通常高度一致先认目录再认文件比逐个打开快得多。下面是我拆这类包时习惯先画的一张表实际目录名可能略有差异但职责划分基本对得上目录实验内容关键文件依赖01_seqlist顺序表seqlist.c / seqlist.h / main.c无02_linkedlist单链表、双链表linkedlist.c / main.c无03_stack_queue顺序栈、链栈、循环队列stack.c / queue.c / main.c无04_tree二叉树建树与遍历btree.c / btree.h / main.c无05_huffman哈夫曼树与编码huffman.c / main.c04 的结构体定义06_graph邻接矩阵、邻接表、DFS/BFS、最短路graph.c / graph.h / main.c无07_search二叉排序树、哈希表bst.c / hash.c / main.c无08_sort插入、冒泡、快排、归并、堆排sort.c / main.c无common公共宏、计时、随机数据生成util.h / util.c无读的顺序建议从main.c的输入解析开始看它怎么读数据、怎么调用核心函数、怎么打印结果再顺着调用跳到.c里的实现。头文件里只放结构体定义和函数声明一个.h里出现大段函数体说明这份源码是“贴代码式”写法改的时候要格外小心重复定义。2.2 编译链gcc 单文件、多文件与 Makefile单个实验目录往往只有一个.c加一个main.c直接一条gcc就能出可执行文件。多文件实验要分开编译再链接好处是改一个文件只重编那一个调试时也方便单独替换某个模块# 单文件实验开满警告保留调试符号关掉优化方便单步 gcc -stdc99 -Wall -Wextra -g -O0 01_seqlist/seqlist.c 01_seqlist/main.c -o build/seqlist # 多文件实验-c 只编译不链接产出 .o 目标文件 gcc -stdc99 -Wall -Wextra -g -O0 -c 04_tree/btree.c -o build/btree.o gcc -stdc99 -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$?参数逐条解释-stdc99是因为源码里普遍用了for (int i 0; ...)这种循环内声明和//注释用默认的 gnu 方言可能在某些编译环境下报错-Wall -Wextra把“变量未初始化”“有返回值函数缺 return”这类隐式问题全部暴露出来这类警告在数据结构代码里十有八九是真 bug-g保留符号表段错误时gdb能打出函数名和行号-O0关优化避免变量被优化掉导致单步跳行。嫌每次手敲太长就在包根目录放一个 Makefile让make一把编完CC : gcc CFLAGS : -stdc99 -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 FAILdiff的退出码是 0 表示一致非 0 表示有差异-u会按行给出上下文方便直接看出是第几行、差在哪个数字上。这一步的价值在于把“编译通过”和“逻辑正确”彻底分开编译通过只说明语法和链接没问题diff通过才说明你的指针操作没把数据搞丢。遇到输出格式不匹配多了空格、少了换行的情况别急着改算法先看printf的分隔符。这类源码大量使用%d 这种带尾随空格的格式diff会把它当成真实差异报出来。通常的处理是先统一成行尾不留空格再重新比对。3. 线性表、栈与队列下标、指针、循环数组的三套边界线性结构是整包源码里最容易“看起来会、写起来错”的部分。原因不复杂顺序表考的是下标推导链表考的是指针顺序循环队列考的是取模判满三套边界规则各不相同混着记必然出问题。这一章把三处最容易错的边界单独拎出来。3.1 顺序表插入删除的下标推导与长度陷阱顺序表的核心只有两行挪数据和改长度。但这两行的顺序和方向一旦写反程序不会报错只会默默丢数据。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; /* 静态分配实验场景够用 */ int length; /* 当前元素个数不是下标上限 */ } SeqList; /* pos 为 1 基位序合法范围 1 ~ length1返回 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不是 length1 */ *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这个条件上会撞车。常见三种处理方式源码里通常只用一种但你要知道另外两种存在方案判空判满实际容量特点牺牲一个单元front rear(rear1)%M frontM-1实现最简单容量少一个增加 size 计数size 0size MM容量不浪费多维护一个变量增加 tag 标记front rear tag 0front rear tag 1M省空间逻辑稍绕#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指向下一个空位”所以判满用(rear1)%M front如果改成“rear指向队尾元素本身”公式就变成(rear2)%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 中找两个 parent0 且 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存储结构的选择直接决定代码形态先看一张对比表维度邻接矩阵邻接表空间O(n²)稠密图合适O(ne)稀疏图合适判断两点是否有边O(1)O(度数)遍历某点所有邻边O(n)O(度数)实现难度低二维数组直接写中需要指针或数组模拟链表适合的算法Floyd、稠密图 PrimDijkstra、稀疏图 BFS单源最短路用 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 hrefhttps://download.csdn.net/download/programchangesworld/8590767 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p 
长河君 · 2026/10/31 11:29:49 · 阅读 1.2k C语言数据结构实验源码：从编译跑通到改代码的工程细节
简介面向数据结构课程学习与实验复现需求这套南邮数据结构实验源码覆盖线性表、栈与队列、二叉树与哈夫曼树、图及其基本操作等核心内容并含多项式运算、飞机换乘次数等典型实验场景适合高校学生对照课程进度完成上机练习也便于自学者梳理 C/C 实现思路。压缩包共 64 个文件约 1.58MB以 10 个 cpp 源文件和 13 个 h 头文件为主体另有 dsw、dsp 等工程配置文件、exe/pdb 等编译产物及 doc 实验报告便于直接查看工程结构、模块组织与运行结果。目前已有 2640 人学习读者可从中获得各实验的代码框架、数据结构定义、核心算法实现和报告参考用于调试排错、对比不同存储方式与算法策略并积累调试经验。使用时建议结合课程要求独立理解与改写将其作为辅助材料而非直接提交的答案。1. 一套数据结构实验源码值不值得花一晚上跑通实验课上照着敲完、交完就忘的代码和能在自己机器上一次编译通过、还能随手改两行看结果的代码中间隔的不是智商是一整套工程细节。这套某高校计算机专业数据结构课程的完整实验源码按实验分目录从顺序表、单链表、栈与队列一路到二叉树、哈夫曼、图、哈希表和各类排序每个目录都带main.c和固定测试数据能独立编译、独立运行。它解决的不是“我没听过快速排序”这种问题而是“我知道原理但写不出能跑的实现”和“跑出来了但不知道对不对”这两件事。适合三类人正在赶实验报告的学生、想刷一遍基础结构的转行从业者、以及需要一份能改造成教学或面试题库素材的工程师。下面的内容按“先跑通、再看懂、最后能改”的顺序拆每一步都落到具体命令和参数上。2. 源码包先跑通再谈看懂目录、编译链与测试数据拿到一包源码最忌讳的动作是从第一个.c文件开始读。人的短期记忆装不下十几个文件里的结构体定义读三页就断线。正确顺序是先让每个目录都能编译出可执行文件再用固定输入跑出固定输出最后才回头看核心函数。这一章就是把“能编译、能跑、能比对”这三步固化下来。2.1 目录与文件职责先画一张调用地图这类成套源码的目录组织通常高度一致先认目录再认文件比逐个打开快得多。下面是我拆这类包时习惯先画的一张表实际目录名可能略有差异但职责划分基本对得上目录实验内容关键文件依赖01_seqlist顺序表seqlist.c / seqlist.h / main.c无02_linkedlist单链表、双链表linkedlist.c / main.c无03_stack_queue顺序栈、链栈、循环队列stack.c / queue.c / main.c无04_tree二叉树建树与遍历btree.c / btree.h / main.c无05_huffman哈夫曼树与编码huffman.c / main.c04 的结构体定义06_graph邻接矩阵、邻接表、DFS/BFS、最短路graph.c / graph.h / main.c无07_search二叉排序树、哈希表bst.c / hash.c / main.c无08_sort插入、冒泡、快排、归并、堆排sort.c / main.c无common公共宏、计时、随机数据生成util.h / util.c无读的顺序建议从main.c的输入解析开始看它怎么读数据、怎么调用核心函数、怎么打印结果再顺着调用跳到.c里的实现。头文件里只放结构体定义和函数声明一个.h里出现大段函数体说明这份源码是“贴代码式”写法改的时候要格外小心重复定义。2.2 编译链gcc 单文件、多文件与 Makefile单个实验目录往往只有一个.c加一个main.c直接一条gcc就能出可执行文件。多文件实验要分开编译再链接好处是改一个文件只重编那一个调试时也方便单独替换某个模块# 单文件实验开满警告保留调试符号关掉优化方便单步 gcc -stdc99 -Wall -Wextra -g -O0 01_seqlist/seqlist.c 01_seqlist/main.c -o build/seqlist # 多文件实验-c 只编译不链接产出 .o 目标文件 gcc -stdc99 -Wall -Wextra -g -O0 -c 04_tree/btree.c -o build/btree.o gcc -stdc99 -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$?参数逐条解释-stdc99是因为源码里普遍用了for (int i 0; ...)这种循环内声明和//注释用默认的 gnu 方言可能在某些编译环境下报错-Wall -Wextra把“变量未初始化”“有返回值函数缺 return”这类隐式问题全部暴露出来这类警告在数据结构代码里十有八九是真 bug-g保留符号表段错误时gdb能打出函数名和行号-O0关优化避免变量被优化掉导致单步跳行。嫌每次手敲太长就在包根目录放一个 Makefile让make一把编完CC : gcc CFLAGS : -stdc99 -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 FAILdiff的退出码是 0 表示一致非 0 表示有差异-u会按行给出上下文方便直接看出是第几行、差在哪个数字上。这一步的价值在于把“编译通过”和“逻辑正确”彻底分开编译通过只说明语法和链接没问题diff通过才说明你的指针操作没把数据搞丢。遇到输出格式不匹配多了空格、少了换行的情况别急着改算法先看printf的分隔符。这类源码大量使用%d 这种带尾随空格的格式diff会把它当成真实差异报出来。通常的处理是先统一成行尾不留空格再重新比对。3. 线性表、栈与队列下标、指针、循环数组的三套边界线性结构是整包源码里最容易“看起来会、写起来错”的部分。原因不复杂顺序表考的是下标推导链表考的是指针顺序循环队列考的是取模判满三套边界规则各不相同混着记必然出问题。这一章把三处最容易错的边界单独拎出来。3.1 顺序表插入删除的下标推导与长度陷阱顺序表的核心只有两行挪数据和改长度。但这两行的顺序和方向一旦写反程序不会报错只会默默丢数据。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; /* 静态分配实验场景够用 */ int length; /* 当前元素个数不是下标上限 */ } SeqList; /* pos 为 1 基位序合法范围 1 ~ length1返回 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不是 length1 */ *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这个条件上会撞车。常见三种处理方式源码里通常只用一种但你要知道另外两种存在方案判空判满实际容量特点牺牲一个单元front rear(rear1)%M frontM-1实现最简单容量少一个增加 size 计数size 0size MM容量不浪费多维护一个变量增加 tag 标记front rear tag 0front rear tag 1M省空间逻辑稍绕#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指向下一个空位”所以判满用(rear1)%M front如果改成“rear指向队尾元素本身”公式就变成(rear2)%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 中找两个 parent0 且 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存储结构的选择直接决定代码形态先看一张对比表维度邻接矩阵邻接表空间O(n²)稠密图合适O(ne)稀疏图合适判断两点是否有边O(1)O(度数)遍历某点所有邻边O(n)O(度数)实现难度低二维数组直接写中需要指针或数组模拟链表适合的算法Floyd、稠密图 PrimDijkstra、稀疏图 BFS单源最短路用 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 hrefhttps://download.csdn.net/download/programchangesworld/8590767 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p