企业官网建设流程全解析

简介：面向计算机专业数据结构课程学习者的华中科技大学实验配套代码包，以C语言实现四个经典实验：顺序表、单链表、二叉树与邻接表（无向图），适合正在做课程实验、需要对照参考实现或在考前复盘基础操作的学生。压缩包共4个文件，均为.c源码，整体约17KB，一实验一文件，便于按知识点单独查阅。其中顺序表部分覆盖建表、插入、删除与查找，并体现数组连续存储下的效率取舍；单链表侧重头插、删除与遍历等指针操作；二叉树涉及节点创建与先序、中序、后序递归遍历；邻接表则给出无向图的构建及深度、广度优先遍历思路。目前已有575人学习，可作为理解顺序与链式存储差异、梳理递归调用与图遍历逻辑的实操参照，也便于对照自己的实验代码排查边界处理上的疏漏。

1. 知识地图：数据结构实验到底在练什么

很多人第一次做数据结构实验，以为任务是“把课本上的算法用 C 语言敲一遍”。真正做下来才发现，这个方向考的是三件事叠在一起：存储结构选得对不对、边界条件写没写全、复杂度的账算不算得清。C 语言、数据结构这两门课的内容在实验里是拧在一起的：指针和结构体负责把抽象类型落地，算法负责把操作代价压下来。多数高校计算机学院在这门课上的推进顺序也基本一致，线性结构打底，树和图铺开，最后落到查找排序的实测。这份笔记按这条主线重排了一遍，适合正在系统学 C 语言版数据结构、或者临近验收想快速过一遍重点的人。

2. 地基先行：C 语言里撑起数据结构的四样硬功夫

数据结构实验里真正拉开差距的，往往不是算法本身，而是下面这层地基。同样是写一个链表，有人半天跑不通，有人半小时收工，差别基本都在指针语义、内存管理、模块组织这几件事上。梳理下来会发现，这四样东西在整门课里会被反复调用，前期省下来的时间，后期要加倍还。

2.1 指针与动态内存：链表的地基

数据结构在内存里有两种落地方式：一种是静态数组，长度写死在编译期；另一种是动态节点，用一次申请一次。链表、树、图的邻接表全都属于后者，所以malloc和free的配对使用是绕不过去的第一关。

malloc只分配不初始化，calloc分配并清零，realloc调整已分配块的大小。写节点时用malloc(sizeof(Node))而不是写死字节数，因为结构体一旦加字段，写死的长度就成了隐藏 bug。分配失败返回NULL，这个判断不能省，虽然多数时候内存够用，但它在边界测试里会突然冒出来。

typedef struct Node { int data; struct Node *next; } Node; /* 申请一个节点并初始化，失败返回 NULL */ Node *create_node(int value) { Node *p = (Node *)malloc(sizeof(Node)); if (p == NULL) { return NULL; /* 分配失败必须显式处理 */ } p->data = value; p->next = NULL; return p; } /* 释放整条链表，注意先保存 next 再 free */ void destroy_list(Node *head) { Node *cur = head; while (cur != NULL) { Node *next = cur->next; /* 顺序反了就是释放后使用 */ free(cur); cur = next; } }

create_node的返回值必须由调用方检查，因为链表的插入失败会往上传染。destroy_list里那行保存next的代码是血泪经验：如果先free(cur)再读cur->next，拿到的就是已经归还给堆管理器的内存，程序在小数据量下可能碰巧能跑，数据一多就崩。释放之后把指针置空是另一个习惯，能挡掉一部分重复释放。

最容易忽略的是二级指针的场合。往空链表里插入第一个节点、或者删除头节点时，头指针本身的值要变，函数参数就得是Node **head，否则改的只是形参副本。很多人在这一步翻车，代码看着没问题，链表就是“少了一个节点”。链表节点的物理地址不连续，是它随机访问慢的根源，也是插入删除快的根源，后面比代价表时会反复回到这一点。

2.2 结构体与 ADT：把定义和实现拆开

抽象数据类型讲的是“数据对象 + 操作集合”，落到 C 语言里就是头文件放类型和函数声明、源文件放实现。这种拆法看起来只是工程习惯，实际上它直接对应实验报告里的“存储结构定义”那一节：结构体字段写清楚了，后面的算法描述才有依据。

/* list.h：只暴露接口，不暴露内部字段 */ #ifndef LIST_H #define LIST_H typedef struct List List; /* 不透明类型，调用方看不到字段 */ List *list_create(void); int list_insert(List *l, int pos, int value); int list_delete(List *l, int pos, int *out); int list_get(const List *l, int pos, int *out); void list_destroy(List *l); #endif

头文件用#ifndef保护，是为了防止同一个文件被间接 include 多次导致重复定义。typedef struct List List;这种前置声明配合源文件里的完整定义，好处是调用方只能通过接口操作数据，字段改了不影响上层代码。

typedef struct Node Node;和struct Node { ... };是两件事，前者是给类型起别名，后者是定义结构体标签，写混了在相互引用时会报“未知类型”。实验里链表、树节点经常需要自引用，struct Node *next;里那个struct不能省，因为此时 typedef 还没完成。把接口和实现分开还有一个隐性好，测试代码可以直接包含头文件，不用把实现复制一遍。

2.3 编译、调试与内存检查的最小工作流

多文件工程用一条命令直接编译也能跑，但报错时定位不到具体模块。拆成“先编译成目标文件，再链接”的两步走，错误信息会明确告诉你是哪个文件、哪一行。加上-Wall -Wextra把警告打开，很多未初始化、隐式类型转换的问题在编译期就能被拦住，不用等到运行时靠 printf 一层层排。

# 分步编译：各自生成 .o，再统一链接 gcc -std=c11 -Wall -Wextra -g -c list.c -o list.o gcc -std=c11 -Wall -Wextra -g -c main.c -o main.o # 链接时打开地址消毒器，越界和释放后使用会被直接报出来 gcc -g main.o list.o -o demo -fsanitize=address # 运行，有内存错误会打印调用栈 ./demo

-c表示只编译不链接，-g保留调试符号，-fsanitize=address在运行期检查堆越界、重复释放、内存泄漏。调试不是无法解释的东西，gdb里break加print能看到指针的真实地址，链表的next指向自己、指向已释放区域这类问题，看一眼地址就清楚了。测试用例要覆盖空结构、单元素、首尾位置、满容量这几种情况，assert比肉眼核对可靠得多。

3. 线性结构：顺序表、链表、栈与队列的取舍清单

线性结构是整门课里代码量最大、也最容易被低估的一块。知识点本身不难，难在每种结构都有自己的一套约定：下标从 0 还是 1 开始、长度变量表示元素个数还是最大容量、栈顶指针指向栈顶元素还是下一个空位。约定一旦和判空判满的写法对不上，代码就会在边界处出错。

3.1 顺序表与链表：一张代价对比表

顺序表和链表的选择，本质上是“随机访问”和“插入删除”之间的交换。梳理下来会发现，很多选择并不需要死记，把下面这张表填一遍，答案自己就出来了。

表里“已知位置”这四个字是整张表的前提，也是最容易被忽略的地方。链表插入确实是 O(1)，但前提是你已经拿到了那个位置的指针；如果给的是下标 i，还得先花 O(n) 走一遍。实验报告里写复杂度时漏掉这个前提，结论就是错的。

顺序表的插入要先把第 i 个位置及之后的元素整体后移一位，再写入新值，同时把长度加一。移动方向必须从后往前，否则前面的元素会覆盖后面的。扩容时通常按 1.5 倍或 2 倍增长，增长率太小会导致频繁搬移，太大则浪费空间，均摊下来 2 倍是比较常见的选法。链表则在频繁插入删除、元素个数不可预知的场景更稳。

3.2 栈与队列：受限线性表的两类考法

栈和队列都是操作受限的线性表，考点集中在“用数组还是用链表实现”以及“判空判满怎么配套”。

顺序栈有两个常见约定：top指向栈顶元素，或者top指向下一个可写入的空位。前者判空是top == -1，入栈要先加后写；后者判空是top == 0，入栈要先写后加。两种写法都对，混用就错。链栈则用头插实现入栈、删头实现出栈，不存在栈满问题，代价是多一个指针的空间。

队列的坑更集中。普通顺序队列用rear一直往后走，前面出队留下的空位用不上，这就是假溢出。解决办法是循环队列，把下标对容量取模。判空判满有三种写法，最常用的是牺牲一个存储单元：front == rear为队空，(rear + 1) % MAX == front为队满。

#define MAX 100 typedef struct { int data[MAX]; int front; /* 指向队头元素 */ int rear; /* 指向队尾的下一个空位 */ } Queue; /* 队空：front == rear；队满：牺牲一个单元 */ int queue_empty(const Queue *q) { return q->front == q->rear; } int queue_full(const Queue *q) { return (q->rear + 1) % MAX == q->front; } int enqueue(Queue *q, int value) { if (queue_full(q)) return 0; /* 满则拒绝，调用方决定怎么处理 */ q->data[q->rear] = value; q->rear = (q->rear + 1) % MAX; /* 取模实现回绕 */ return 1; } int dequeue(Queue *q, int *out) { if (queue_empty(q)) return 0; *out = q->data[q->front]; q->front = (q->front + 1) % MAX; return 1; }

front和rear的语义必须在注释里写死，后面所有函数都按这个约定来。牺牲一个单元的意思是队列最多存MAX - 1个元素，这个代价换来了判空判满不用额外的标志位。如果不想浪费，也可以加一个count变量记录元素个数，判空判满都看它。

栈的典型应用是括号匹配、中缀表达式转后缀、递归消除和深度优先搜索；队列的典型应用是层序遍历、广度优先搜索和各类缓冲。实验里常把栈和队列组合起来用，比如用栈实现队列、用两个队列实现栈，这类题的关键是先把两种结构的语义写清楚，再动手搬元素。

3.3 单链表操作模板与必须补的边界

单链表的代码量不大，但边界条件多，是最容易在验收时被追问的结构。带头结点和不带头结点是第一个分岔：带头结点的链表，第一个节点不存数据，插入删除的逻辑可以统一；不带头结点则要单独处理“在头部操作”的情况。实验里两种都会出现，看到代码先确认属于哪一种。

/* 带头结点的单链表，在第 pos 个位置（从 1 开始）插入 value */ int list_insert(List *l, int pos, int value) { if (pos < 1) return 0; /* 位置非法 */ Node *pre = l->head; /* 从头结点出发 */ int i = 0; while (pre != NULL && i < pos - 1) { /* 走到第 pos-1 个节点 */ pre = pre->next; i++; } if (pre == NULL) return 0; /* pos 超过表长加一 */ Node *node = create_node(value); if (node == NULL) return 0; node->next = pre->next; /* 先接后 */ pre->next = node; /* 再断前 */ l->size++; return 1; }

这段代码里pre从head出发，走pos - 1步，停下时正好是待插入位置的前驱。循环条件里的pre != NULL不能省，否则pos大于表长时会空指针解引用。插入的两行顺序不能换，先让新节点接上后继，再让前驱指向新节点，反过来会丢掉后半条链。

必须补的边界清单：位置为 1 的头部插入、位置为表长加一的尾部插入、空表插入、位置为 0 或负数、位置超出表长、删除后释放内存并修正长度、删除后链表变空时头结点的next要置空。另外逆置、合并两个有序链表、找中间节点、判断是否有环这几道题，几乎每年都会以某种形式出现，模板要能默写出来，并且能说清每一步的指针变化。

4. 树与图：非线性结构的存储选型与遍历套路

从线性结构走到树和图，最大的变化是“一个节点有多个后继”，指针不再是一条线，而是一张网。这一块的重点不在于把每个算法都背下来，而在于知道每种存储结构适合什么形态的数据，以及遍历框架怎么套用到不同问题上。

4.1 二叉树：遍历、层序与递归转非递归

二叉树的四种遍历里，前序、中序、后序是深度优先，层序是广度优先。递归写法三行就能写完，但实验通常要求至少掌握一种非递归写法，因为递归深度受栈空间限制，退化成一棵单支树时很容易爆栈。

非递归的核心是用一个显式栈模拟函数调用栈。以中序为例，一路向左压栈直到空，然后弹出访问，再转向右子树。

/* 非递归中序遍历：左-根-右 */ void inorder(BiTree root) { BiTree stack[100]; int top = 0; /* 栈顶指针，指向下一个空位 */ BiTree p = root; while (p != NULL || top > 0) { while (p != NULL) { /* 一路向左，沿途压栈 */ stack[top++] = p; p = p->left; } p = stack[--top]; /* 弹出并访问 */ visit(p); p = p->right; /* 转向右子树 */ } }

栈的容量要按树高估计，链式存储的二叉树如果退化成单支，树高等于节点数，固定数组就不够用了，这时要用动态栈或者改回递归并评估深度。前序的非递归只要把访问时机提前，后序则要借助一个记录上次访问节点的指针，或者用“根-右-左”再整体逆序的技巧。

层序遍历用队列，出队一个节点就把它访问一遍，然后把左右孩子依次入队。由遍历序列还原树是实验报告里的常客：前序加中序、后序加中序都能唯一确定一棵树，前序加后序不行，因为分不清只有一个孩子时它在左还是在右。

4.2 树的应用：哈夫曼、二叉排序树与平衡的直觉

哈夫曼树解决的是带权路径长度最小的问题。做法是每次从森林里取两个权值最小的树合并，新树根权值为两者之和，放回森林，重复到只剩一棵。用小根堆维护这些权值，每次取两个、插入一个，复杂度是 O(n log n)。哈夫曼编码的前缀性质来自“任何字符都在叶子上”，所以没有一个编码是另一个编码的前缀，解码时不会产生歧义。

二叉排序树的中序遍历是有序序列，查找、插入的平均复杂度是 O(log n)，但插入序列有序时会退化成链表，复杂度掉到 O(n)。这个退化是实验里常见的对比素材：同一组数据换个插入顺序，树高差好几倍。平衡二叉树通过旋转把树高控制在 O(log n)，四种失衡情况 LL、RR、LR、RL 分别对应单旋和双旋，重点是判断失衡类型，而不是硬背旋转代码。

堆是另一类常考结构，本质是完全二叉树加数组存储。下标 i 的左右孩子是 2i 和 2i+1（从 1 开始存），建堆用自底向上的下沉操作，复杂度是 O(n) 而不是 O(n log n)，插入和删除堆顶是 O(log n)。堆排序、优先队列、Top-K 问题都建立在这个结构上。

4.3 图的两种存储：邻接矩阵与邻接表的选型

图有两种主流存法，选型取决于图的稠密程度和你要做的操作。

邻接矩阵的优点是判断边快、实现简单，缺点是点数一多空间就爆。邻接表的空间和边数成正比，适合稀疏图，但判断两点是否相邻要遍历链表。实际实验里点数通常在几百以内，两种都能跑，但报告里要写清楚为什么选这一种。

邻接表的节点定义要注意，无向图的一条边要在两个顶点的链表里各存一次，有向图只存一次。边数统计时，无向图遍历完所有链表得到的计数是实际边数的两倍，这个细节在报告里写错会被扣分。

4.4 图的遍历与两类经典算法：最短路与最小生成树

深度优先和广度优先是图算法的基础框架，两者都需要一个visited数组防止重复访问。DFS 用递归或显式栈，BFS 用队列。连通分量的个数等于外层循环调用遍历的次数，这个结论在实验里经常被用来验证结果。

拓扑排序只适用于有向无环图，做法是统计每个顶点的入度，把入度为 0 的顶点入队，出队时把它指向的顶点入度减一，减到 0 就入队。如果最后输出的顶点数少于总数，说明图里有环。

最短路径有两个常考算法。Dijkstra 解决单源最短路，要求边权非负，朴素实现 O(n²)，用优先队列可以优化到 O((n+e) log n)。Floyd 解决任意两点间最短路，三重循环 O(n³)，代码短，允许负权边但不能有负权环。选择依据很直接：只要一个源点用 Dijkstra，要全部点对用 Floyd，点数很小的时候 Floyd 反而更省事。

最小生成树有两个算法。Prim 从一个点出发，每次选一条连接已选集合和未选集合的最小边，复杂度 O(n²)，适合稠密图。Kruskal 把所有边排序，依次取最小边，用并查集判断是否成环，复杂度 O(e log e)，适合稀疏图。两个算法得到的生成树权值相同，但形态可能不同，实验里如果要求和，结果必须一致。

5. 查找排序易错点：复杂度分档、稳定性与实测里的坑

查找和排序是整门课里最“看起来会、写起来错”的部分。算法思想几句话就能说完，但边界、稳定性、实测方法这几处特别容易翻车。这一章把知识点和易错点放在一起，先分档，再逐条说清容易错在哪。

5.1 查找三兄弟：顺序、折半与散列的分档

顺序查找对存储没有要求，平均查找长度是 (n+1)/2，有序表里可以在找到大于目标值的元素时提前终止，但复杂度仍是 O(n)。折半查找要求有序且顺序存储，每次把区间缩小一半，复杂度 O(log n)，比较次数约 log₂n。折半的判定树是一棵平衡二叉树，查找成功的平均长度可以直接按层数算出来。

散列查找的平均复杂度接近 O(1)，代价是要设计哈希函数并处理冲突。冲突处理分两类：开放定址法（线性探测、二次探测、再散列）和链地址法。装填因子 α 等于元素个数除以表长，α 越大冲突越多，查找长度越长。实验报告里常要求计算查找成功和查找失败的平均查找长度，失败长度的算法是把每个地址到第一个空位的探测次数求平均，这一步最容易算错，因为要按哈希函数的值域逐个算，不能只算已占用的位置。

5.2 排序算法的分档与稳定性

八个经典排序可以按平均复杂度分成三档，选型时先看数据规模，再看是否要求稳定、是否允许额外空间。

稳定性指的是相等元素的相对次序是否保持不变，只有插入、冒泡、归并、基数这四种是稳定的。快速排序不稳定，因为划分时的交换会打乱相等元素的顺序；堆排序不稳定，因为堆顶和末尾交换会跨越很多元素。

快速排序的最坏情况出现在每次划分都极不均衡时，比如数据已经有序而基准取第一个元素，这时退化成 O(n²)，递归深度也变成 O(n)。三数取中或者随机选基准能把这种情况的概率压到很低，但严格说最坏仍然是 O(n²)。

5.3 五条最容易翻车的易错点

折半查找的边界条件。易漏点在于while的条件写成low < high还是low <= high，以及mid更新时是high = mid还是mid - 1。为什么会漏？因为大部分人只记了一个模板，没推导过区间收缩的过程，换一道“查找第一个大于等于 x 的位置”的题就套不上了。怎么补：拿三个元素的数组手工走一遍，把每次的low、high、mid写在纸上，确认区间每轮都在缩小、不会死循环，再把这个推导过程写进实验报告的算法描述里。

快速排序的基准选择。易漏点在于基准取首元素，测试数据又是已经有序的，复杂度直接掉到 O(n²)，但程序仍然能跑出正确结果，所以不测时间就发现不了。为什么漏？因为注意力都在“结果对不对”上，没意识到“跑得快不快”也是实验指标。怎么补：准备三组数据，随机、升序、降序，同一份代码分别跑一遍并记录耗时，把三数取中的版本也跑一遍做对比，差异会非常直观。

稳定性、比较次数、交换次数三个概念混着用。易漏点是在报告里写“该算法稳定”却没有给出理由，或者把比较次数当成时间复杂度。为什么漏？因为这三个词在课本里挨着出现，复习时容易打包记忆。怎么补：造一组带相同关键字的小数据，把每一趟的中间状态打印出来，亲眼看相等元素有没有换位置；比较次数和交换次数用小规模数据手工数一遍，再和程序计数器的结果对上。

计时代码本身不可靠。易漏点是用低精度计时函数测几十个元素的小数组，结果全是 0 或者全是噪声；或者编译器把没有输出的循环整个优化掉，测出来快得不正常。为什么漏？因为这类问题不会报错，只会让实测数据毫无意义。怎么补：规模至少上万，同一组数据重复多次取平均，计时前后都要保证排序结果被实际使用（比如打印校验和），并把“数据规模、重复次数、编译选项”写进报告，让结果可复现。

只用一组数据验证。易漏点是测试用例永远是那五六个随机数，空数组、单元素、全部相同、已经逆序这几种情况一个都没覆盖。为什么漏？因为随机数据“看起来”已经很有代表性了。怎么补：写一个数据生成器，按类型批量产出用例，再用一个暴力参照实现做对照，两边结果必须完全一致；边界用例单独列一张表，跑完打勾。这套做法在树和图的实验里同样适用，能省下大量手工核对的时间。

6. 复习清单：按场景选结构，按复杂度排优先级

复习到后期，最有效的动作不是再刷一遍代码，而是把“什么场景用什么结构”这张对照表默写出来，再用它去反查自己哪一块是空的。

拿着这张表逐行问自己：这一行的结构，我能不能在十分钟内写出插入、删除、查找三个操作的完整代码，并且说清每个操作的复杂度和边界条件。说不清的那一行，就是当天要补的洞。

第二件事是把复杂度账单独过一遍。线性结构看插入删除的搬移代价，树看高度和退化，图看点数与边数的关系，查找排序看平均和最坏两栏。凡是能在报告里写出推导过程的，才算真会；只会背结论的，换一道题就露馅。

第三件事是把易错点清单化。折半的区间、快排的基准、循环队列的判满、链表的头结点、图的visited、Dijkstra 的负权限制，这六条是我自己踩过坑之后固定下来的检查项，每次写完代码逐条对一遍，比事后调试省时间。

我自己的习惯是：每次实验提交前，强制走一遍“空、单元素、首尾、满、重复值”这五类用例，再跑一次带地址消毒器的编译。这个流程第一次用会觉得麻烦，用几次之后就变成肌肉记忆了。有次图实验的邻接表在删除边时漏了释放节点，就是靠这一步在提交前抓出来的，否则验收现场被问一句“内存泄漏在哪”会很难看。希望帮到你。

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