企业官网建设流程全解析

简介：文档为数据结构各章节算法的 C 语言版本，配套严蔚敏《数据结构(C语言版)》使用，覆盖顺序表、栈和队列、查找排序、字符串匹配、树与图等核心内容，适合期末复习、ACM 训练、考研机试与复试刷题、校招笔试面试准备。文档不是零散函数，而是将字符统计、多项式相加、后缀表达式求值、二分查找、哈希表、KMP 匹配、八种经典排序、哈夫曼树、图的广度优先搜索和最小生成树等经典算法组织为可独立运行的完整代码，每个示例都可单独编译执行，便于在理解原理的同时动手验证。资源为单个 Word 文档（docx），包体约 162KB，目录按章节标注清晰，排版良好，可直接在文档中补注释或扩展新题目；已有 1391 人学习。配合教材和机试题单使用，能显著提升手写代码与调试能力，是准备机试、复试和面试前查漏补缺的实用备查资料。课后自学或考前冲刺时，也可作为代码模板快速定位，提高复习效率。

1. 为什么这份文档值得一页一页过，而不是当作答案合集

数据结构各章节算法实现（C语言版）这份文档，每到期末、考研冲刺和面试前一周就会被翻出来。它把线性表、栈、队列、串、树、图、查找、排序八类经典算法收在了一起，看起来像一份“标准答案”，于是一批人复制粘贴跑通就觉得完事了。真正的分水岭不在跑通，而在你能不能把这份 C 语言实现默写出来，能不能说清每一行的作用，能不能在边界条件上不被面试官问倒。

这篇笔记就顺着文档的章节顺序过一遍：每个算法给你最小可运行版本，把参数和边界讲透，再标出那些容易翻车的细节。适合三类人：准备考研数据结构 408 的，面试要手写链表反转和二叉树遍历的，以及课程设计要交实验报告、不想只靠抄代码的同学。先从线性表开始。

2. 线性表、栈与队列：顺序存储还是链式存储，先做对选型

这一章是所有后续内容的地基：树的兄弟表示法、图的邻接表、BFS 用的队列，全是这章数据结构的复合应用。我一般建议先把线性表和栈队列的代码调到能盲写，再去碰树和图。

2.1 顺序表与单链表：结构体定义和插入删除的差异

顺序表和链表的核心差异只有一句：内存连续还是指针串联。顺序表随机访问是 O(1)，插入删除要挪动后续元素；链表插入删除只需要改指针，但前提是你已经找到前驱结点，而查找本身要 O(n)。选择题经常在这里挖坑，比如“频繁按位置访问元素用哪个”，答案永远是顺序表。

顺序表最简定义：

#define MAXN 100 typedef struct { int data[MAXN]; int len; } SeqList;

这里的len表示当前元素个数，不是最大容量。插入前检查len >= MAXN是表满，删除前检查len == 0是表空，这两个条件写反或者漏写，后续所有操作都会带病运行。很多教材里顺序表的下标从 0 开始，第 i 个元素存在data[i-1]，手撕时先明确这一点再写循环。

单链表结点的结构体几乎人人都能写出来，但反转链表这道题能挂掉一半人，核心问题在于“先存后继再改指针”：

typedef struct LNode { int data; struct LNode *next; } LNode; LNode *reverse(LNode *head) { LNode *pre = NULL, *cur = head; while (cur) { LNode *next = cur->next; // 先存后继，否则 cur->next 被覆盖后链表就断了 cur->next = pre; pre = cur; cur = next; } return pre; // 原链表尾结点变成新头 }

这段代码的注释就是血泪经验：如果不先用next保存后继，执行cur->next = pre之后，原来的下一个结点地址就丢了，而且丢了没有后悔药，只能重新遍历。参数上要注意head本身可能是空指针，反转前判空一次；返回的是新的头指针，调用处要记得接收返回值，否则原来的head指向的是反转后的尾结点。

2.2 顺序栈：压栈、弹栈与括号匹配

栈在文档里通常只讲一个数组加一个栈顶指针，但top的语义有两种写法：指向栈顶元素，或者指向下一个空位。这两种写法影响所有相关代码，我的习惯是统一用“top指向当前栈顶元素”，初始化top = -1，压栈先++top再赋值。考试手撕时保持这个口径，能少一个麻烦。

括号匹配是栈的经典验证题，很多同学卡在“弹栈前忘了判空”：

int match(char *s) { char stack[MAXN]; int top = -1; for (int i = 0; s[i]; i++) { if (s[i] == '(' || s[i] == '[') stack[++top] = s[i]; else if (s[i] == ')') { if (top < 0 || stack[top] != '(') return 0; top--; } else if (s[i] == ']') { if (top < 0 || stack[top] != '[') return 0; top--; } } return top == -1; }

注意if (top < 0 || ...)的顺序不能反过来：一旦栈空，stack[top]就越界访问了，C 语言里这是未定义行为，可能当场段错误，也可能玄学地跑很久。这里先判断栈空再取值，属于最基础的防御性写法。括号类型多了之后，建议把左右括号映射成整型再比较，代码会清爽很多。

2.3 环形队列：判空判满的两种实现

线性队列最大的问题是“假溢出”：rear到数组末尾后，即使前面空着也没法入队。环形队列把数组首尾接起来，但判满的条件必须取模。牺牲一个存储单元是最常见做法，也最好理解：

#define MAXN 5 typedef struct { int data[MAXN]; int front, rear; } Queue; void initQueue(Queue *q) { q->front = q->rear = 0; } int isFull(Queue *q) { return (q->rear + 1) % MAXN == q->front; // 牺牲一个格子区分空和满 } int isEmpty(Queue *q) { return q->front == q->rear; } int enQueue(Queue *q, int x) { if (isFull(q)) return 0; q->data[q->rear] = x; q->rear = (q->rear + 1) % MAXN; return 1; } int deQueue(Queue *q, int *x) { if (isEmpty(q)) return 0; *x = q->data[q->front]; q->front = (q->front + 1) % MAXN; return 1; }

这里最大的坑是把isFull写成q->rear + 1 == q->front，少了取模。当rear走到数组末尾再回绕时，这个判断就会失效，队列永远判不满，入队时直接越界写坏内存。另一个容易错的地方是队列实际容量：牺牲一个存储单元后，容量是MAXN - 1，不是MAXN。元素个数用(rear - front + MAXN) % MAXN计算，公式里加MAXN是为了处理负数。后面树的层序遍历和图的 BFS 都要用这版队列，现在把它调通相当于给后面买保险。

3. 串与二叉树：KMP 的 next 数组，递归与非递归一体两面

串这一章，教材一般只要求一个 KMP；树这一章，核心是遍历。把这两章放在一起复习，是因为它们都跟“状态回退”有关：KMP 里模式串指针要回退到 next 数组指定的位置，二叉树非递归遍历要把已经访问过的结点状态压进栈里。搞懂一个，另一个也顺了。

3.1 KMP：next 数组计算与匹配主循环

朴素串匹配就是暴力枚举，主串和模式串每个位置都试一遍，复杂度 O(n*m)，当模式串是“aaaaab”这种重复串时极其难受。KMP 的思路是主串指针不回退，模式串回退到该回退的位置，这个位置由next数组预先算好。

#include <stdio.h> #include <string.h> #define MAXN 100 void getNext(const char *p, int *next) { int m = strlen(p); next[0] = -1; int i = 0, j = -1; while (i < m) { if (j == -1 || p[i] == p[j]) next[++i] = ++j; else j = next[j]; } } int kmp(const char *s, const char *p) { int n = strlen(s), m = strlen(p); int next[MAXN]; getNext(p, next); int i = 0, j = 0; while (i < n && j < m) { if (j == -1 || s[i] == p[j]) { i++; j++; } else { j = next[j]; // 主串不回退，只回退模式串 } } return j == m ? i - j : -1; }

两个细节容易翻车。第一，next[0]初始化为-1，和初始化为0的版本相比，匹配主循环里必须处理j == -1，否则下一轮s[i] == p[j]会访问p[-1]，直接越界。第二，getNext里next[++i] = ++j计算的是失配后跳转的位置，不是最长公共前后缀的长度，很多人手算能算出前缀表，却不知道代码里要整体右移一位并减一。写匹配主循环时，先if (j == -1 || s[i] == p[j])，把j == -1放在前面，顺序错了照样越界。KMP 的复杂度是 O(n+m)，主串指针不回退是它和暴力枚举最直观的区别。如果题目考的是nextval，那是在next基础上再做一次优化，考试前把两种版本的分工记清楚。

3.2 二叉树遍历：递归三行与非递归用栈

二叉树的递归遍历简单到令人怀疑：先序三行，一个空指针判断加两个递归调用，完事。

typedef struct BTNode { int data; struct BTNode *left, *right; } BTNode; void preOrder(BTNode *root) { if (!root) return; printf("%d ", root->data); preOrder(root->left); preOrder(root->right); }

面试不会只考递归，一定会追一句“不用递归怎么写”。递归本质是系统在维护一个调用栈，函数一层层压栈，返回时再弹栈。非递归就是把这个黑匣子打开，自己用数组模拟栈。其中中序非递归最容易写错，因为它要先一路压左孩子，直到空，然后出栈访问，再转向右子树：

void inorderNonRec(BTNode *root) { BTNode *stack[MAXN]; int top = -1; BTNode *cur = root; while (cur || top != -1) { while (cur) { stack[++top] = cur; cur = cur->left; // 先把所有左孩子压栈 } cur = stack[top--]; printf("%d ", cur->data); cur = cur->right; // 转向右子树，下一轮继续左压 } }

循环条件cur || top != -1不能省略前半句：第一次进入时栈为空但cur是根结点，省略了循环直接结束。压栈时cur可能为 NULL，出栈后cur = cur->right也可能为 NULL，但外层循环靠top != -1兜住，不会越界。先序非递归稍微简单，遍历到一个结点先访问再压栈；后序非递归最麻烦，要标记右子树是否已经访问过，考试时如果时间紧，后序建议直接写递归。

3.3 层序遍历与 BST 插入：队列和二叉树的交叉点

层序遍历是二叉树的“广度优先”，必须用队列。把 2.3 的环形队列改一下类型，或者直接用数组模拟，逻辑完全一样：

void levelOrder(BTNode *root) { Queue q; initQueue(&q); if (root) enQueue(&q, root); while (!isEmpty(&q)) { BTNode *cur; deQueue(&q, &cur); printf("%d ", cur->data); if (cur->left) enQueue(&q, cur->left); if (cur->right) enQueue(&q, cur->right); } }

入队时判断孩子是否为空，为空就不入队。这样出队时拿到的每个结点都一定非空，层序代码里不需要再判空。二叉搜索树的插入是另一个高频代码，核心是“小的往左走，大的往右走，遇空就挂上”：

BTNode *bstInsert(BTNode *root, int val) { if (!root) { BTNode *p = (BTNode *)malloc(sizeof(BTNode)); p->data = val; p->left = p->right = NULL; return p; } if (val < root->data) root->left = bstInsert(root->left, val); else if (val > root->data) root->right = bstInsert(root->right, val); return root; }

这段代码看起来简单，坑在内存分配后必须把left和right置空，否则后续遍历会遍历到野指针。如果插入的是重复值，很多实现直接返回，也有实现在左子树或右子树里放重复值，先和队友确认口径再写。

4. 图的 C 语言落地：邻接表建图、DFS/BFS 与并查集

图论代码是考研数据结构里“图和数组”这一考点的重头戏，面试里也总爱让你手写“图的深度优先遍历”。这一章我建议把存储结构和遍历算法绑定记忆：你选邻接矩阵还是邻接表，直接影响建图代码和遍历复杂度。

4.1 邻接矩阵 vs 邻接表：先选存储结构再写代码

邻接矩阵适合稠密图，判断两个顶点是否相邻只要 O(1)，但初始化就要 O(n^2)；邻接表适合稀疏图，空间是 O(V+E)，遍历一个顶点的所有邻接点时间等于它的度。408 选择题喜欢给一个图，让你算两种存储的空间复杂度，记住一句：边数接近 n^2 用矩阵，边数远小于 n^2 用邻接表。

邻接表建图是最常见的代码，用“头插法”把每条边挂到链头：

#define MAXV 100 typedef struct EdgeNode { int adjvex; // 边的另一端顶点编号 struct EdgeNode *next; } EdgeNode; typedef struct { int data; // 顶点信息 EdgeNode *firstedge; // 边链表头 } VertexNode; VertexNode adjlist[MAXV]; void addEdge(int u, int v) { EdgeNode *p = (EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex = v; p->next = adjlist[u].firstedge; adjlist[u].firstedge = p; // 头插法 }

如果是无向图，一条边要插两次：addEdge(u, v); addEdge(v, u);。漏掉第二次边数就会减半，遍历时只能从其中一个方向走到另一个方向，这就是常见“图遍历少顶点”的根源。MAXV是固定数组的上限，实际顶点数n应小于等于它，建图前把adjlist[0..n-1].firstedge全部置 NULL。

4.2 DFS 与 BFS：visited 数组是灵魂

深度优先遍历的递归版和二叉树先序几乎一模一样，但图有环，所以必须加一个visited数组标记已访问：

int visited[MAXV]; void dfs(int u) { visited[u] = 1; printf("%d ", u); for (EdgeNode *p = adjlist[u].firstedge; p; p = p->next) { int v = p->adjvex; if (!visited[v]) dfs(v); } }

递归 DFS 在深度很大的图上可能爆系统栈，所以面试也考非递归版：手动用一个栈，入栈时标记，出栈后把未访问的邻接点全部压栈。这个写法有个细节，标记时机选“入栈时”还是“出栈时”会导致同一个点被多次入栈，建议统一入栈即标记，配合if (!visited[v])判断才能避免重复。

BFS 用队列配合 visited 数组，代码比 DFS 还短：

void bfs(int s) { int q[MAXV], head = 0, tail = 0; visited[s] = 1; q[tail++] = s; while (head < tail) { int u = q[head++]; printf("%d ", u); for (EdgeNode *p = adjlist[u].firstedge; p; p = p->next) { int v = p->adjvex; if (!visited[v]) { visited[v] = 1; // 入队前标记，防止重复入队 q[tail++] = v; } } } }

BFS 这个“入队前标记”和 DFS 的“递归前判断”是同一个原则：访问一个顶点之前先确认它没被访问过。很多同学把visited[v] = 1丢到出队时再写，同一个顶点就会在队列里出现多份，结果还能跑通，但输出顺序和去重逻辑都变味了。剪枝算法里的“剪枝”思想就是 DFS 的延伸：在递归入口加限制条件，提前终止明显不可能的分支，比如迷宫问题里越界就 return。

4.3 并查集与最小生成树：判断加边会不会成环

并查集是图论里出现频率极高的小算法，Kruskal 求最小生成树之前要先按边权排序，然后从小到大选边，每选一条就判断“这条边两端是否已经连通”。如果连通，加进去就成环，必须跳过。这个判断用并查集 O(1) 就能完成：

int parent[MAXV], rnk[MAXV]; int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩 return parent[x]; } void unite(int a, int b) { a = find(a); b = find(b); if (a == b) return; if (rnk[a] < rnk[b]) { int t = a; a = b; b = t; } parent[b] = a; if (rnk[a] == rnk[b]) rnk[a]++; }

find里“路径压缩”把查找路径上的所有结点直接挂到根上，让后续查找接近 O(1)。unite里的按秩合并，目的是把矮树挂到高树上，防止并查集退化成一条链。初始化时parent[i] = i，rnk[i] = 0别漏。Kruskal 整体流程是：所有边按权值升序排序，遍历每条边，只要两端不连通就选入生成树，选够 n-1 条就停。Prim 适合稠密图，Kruskal 适合稀疏图，408 简答题喜欢给一个小图让你手推最小生成树，代码题更倾向考并查集本身。

5. 查找、排序与 KMP 的常见问题排查：五个反复出现的坑

前面几章的代码，照着文档抄完一般能跑。但查找和排序这几节不一样，代码能编译不代表结果对，很多隐藏问题只在特定输入下暴露。这里列几个我见过的典型翻车现场，按“现象 → 原因 → 解决”写，遇到同样问题直接对照处理。

5.1 二分查找：死循环和漏判

现象 1：在有序数组里找一个确定存在的数，程序却返回 -1。原因：循环条件写成while (low < high)，同时high的更新方式是high = mid。当区间只剩一个元素时循环退出，正好漏掉最后一个元素。解决：保留“闭区间”写法，循环用low <= high，找到就返回，否则low = mid + 1、high = mid - 1。这是最不容易出错的模板：

int binarySearch(int a[], int n, int key) { int low = 0, high = n - 1; while (low <= high) { int mid = low + (high - low) / 2; if (a[mid] == key) return mid; else if (a[mid] < key) low = mid + 1; else high = mid - 1; } return -1; }

现象 2：mid = (low + high) / 2在数组很大时计算出负数或异常值。原因：low + high溢出 int，这是经典问题，和算法本身无关。解决：统一写成low + (high - low) / 2，这也是面试官常考的一句话。注意如果你用“左闭右开区间”[low, high)，循环条件要换成low < high，high = mid，low = mid + 1，两种模板混着用最容易出问题。

5.2 快速排序与堆排序：算法实现的两个高发翻车点

现象 1：快排对有序数组反而慢到离谱，甚至递归太深导致栈溢出。原因：基准值固定取a[low]或a[high]，当数组已经有序时，每次划分极度不平衡，复杂度退化到 O(n^2)。这也解释了为什么有些文档里的快排能过随机数据，遇到考试专用的“升序数组”就挂。解决：三数取中，取a[low]、a[mid]、a[high]的中位数作为基准，或者干脆用随机下标。三数取中的代码也不复杂，关键是让基准值尽可能接近中位数。

现象 2：堆排序输出不是升序，或者出现数组越界。原因：堆排序的下标处理错位。0 基数组中，最后一个非叶子结点的下标是n/2 - 1，不是n/2；siftDown的循环条件写成2 * i + 1 <= n，括号里漏了-1，访问了a[n]。解决：先把数组画成完全二叉树，下标从 0 开始数一遍，再写循环就不会错。

void siftDown(int a[], int n, int i) { while (2 * i + 1 < n) { // 有左孩子才继续 int j = 2 * i + 1; if (j + 1 < n && a[j + 1] > a[j]) // 选出左右孩子中的较大者 j++; if (a[i] >= a[j]) break; int t = a[i]; a[i] = a[j]; a[j] = t; i = j; // 交换后继续向下调整 } } void heapSort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i); for (int i = n - 1; i > 0; i--) { int t = a[0]; a[0] = a[i]; a[i] = t; siftDown(a, i, 0); // 堆规模减一，从根再调整 } }

堆排序算法是各类文档排序章节的必收代码，也是最容易“背下来了但写不对”的。siftDown里交换后必须执行i = j继续下沉，漏掉这一步，小元素就沉不下去。

5.3 KMP 的 next 数组：匹配位置错乱

现象：KMP 匹配结果比实际位置靠前或靠后，有时直接段错误。原因：next数组是“前缀表右移一位并减一”的产物，把它当成朴素前缀表直接用，匹配就会错位。还有一种情况是混用了两种版本：next[0] = -1和next[0] = 0的代码交叉粘贴。解决：确定一个版本并保持全篇统一。我在 3.1 里给的是next[0] = -1版本，对应的匹配主循环里必须有j == -1这个分支。getNext计算时，next[++i] = ++j里的j从-1开始，第一次循环算出next[1] = 0，第二次才能正常推进。如果你手算出来的next数组第一位是 0，那匹配循环里就不该出现j == -1，把这个统一就能避开一大半问题。KMP 的主串指针不回退是它和暴力枚举的复杂度差异来源，也是面试时最能体现你理解深度的细节。

6. 把文档代码变成自己的武器：验证与改造

文档里的代码再多也是别人的，照着敲一遍只能练手。我会再做一步：把每章代码改造成自己的“算法笔记本”，每条代码都经过一道在线评测题的验证。比如单链表反转就去找一条链表反转题跑一遍，二叉树层序遍历就去找层序遍历题跑一遍，堆排序就去找排序题，KMP 就去找“找出模式串在主串中首次出现的下标”。让代码在真实输入输出上跑通，比在纸上默写十遍都管用。我一般习惯给每个算法配一道题，代码留一个统一风格的文件头，包含结构体定义、辅助函数和测试用例，命名用list.h、tree.h、graph.h分门别类。

验证之外，还要做两件小事：加断言和加释放函数。在环形队列的deQueue里加一句assert(!isEmpty(q))，调试时就能定位是调用方的问题还是队列本身的问题；树结点、图边结点都是 malloc 出来的，写一个freeTree、freeGraph把内存还回去。C 语言的内存管理不主动做，长时间运行的内存泄漏会积累到措手不及。遇到段错误别靠猜，用 gdb 断在出错行看调用栈，十次里有九次能直接看出指针问题。

我当年调环形队列，判满写成了rear + 1 == front，少了取模，队列永远判不满，数据一路往数组外写，最后角落里堆了一堆垃圾数据还浑然不知。后来把整个队列画在草稿纸上，转了几圈才猛然发现是取模的问题。算法实现这东西，跑通只是开始，边界值、空间释放、异常输入都处理干净才叫真正掌握。希望帮到你。

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