数据结构C语言版期末复习指南：高频考点与代码模板

1. 数据结构到底在学什么

很多同学第一次接触《数据结构（C语言版）》时，最大的感受是“上课能听懂，作业不会写，考试更懵”。这其实不是智商问题，而是这门课和C语言、高数都不一样，它需要你切换一种思维方式：从“怎么写代码”变成“怎么设计数据和组织数据”。

数据结构这门课研究的是数据的逻辑结构、物理存储结构，以及基于这些结构的操作算法。

• 逻辑结构解决的是“数据之间是什么关系”，比如一对一、一对多、多对多；
• 存储结构解决的是“这些关系在计算机里怎么存”，比如顺序存储、链式存储；
• 算法解决的是“在某种结构上怎么做增删改查、遍历、排序、查找”。

如果你正在准备期末考试、补考救急或者考研复试，这篇文章会按照严蔚敏《数据结构（C语言版）》的章节顺序，把高频考点、必背代码、易错点和复习优先级全部梳理一遍。

本文适合三类读者：

1. 零基础速成的同学：上课没听，想短期建立知识框架。
2. 考前抱佛脚的同学：马上考试，需要高频考点和典型代码。
3. 考研复试/软考备考的同学：需要把数据结构的核心内容系统化。

学完之后，你应该能回答这几个问题：

• 线性表、栈、队列、树、图分别适合什么场景？
• 每种结构的查找、插入、删除时间复杂度是多少？
• 排序算法里，哪些是稳定的？哪些不稳定？
• 考试最常见的算法题：链表反转、二叉树遍历、快速排序怎么写？

2. 先建立一个总的知识框架

数据结构的内容看起来很多，但本质上就三大块：线性结构、树形结构、图形结构，外加查找与排序两大算法应用。

下面先用一个表格帮你建立整体认知：

复习建议：线性和树是重点，图是难点，查找和排序是拿分点。

从考试分值来看，线性表、二叉树、排序通常占大头。图的部分虽然难，但考题相对固定，掌握好模板就能拿分。

3. 线性表：顺序表和链表必须吃透

线性表是最基本、最常用的一种数据结构，它的特点是：数据元素之间是一对一的线性关系。

在线性表中，按存储方式又分为顺序表和链表两种。这两种结构几乎是所有学校期末考试必考的。

3.1 顺序表的插入和删除

顺序表就是用一段地址连续的存储单元依次存储数据元素，本质上就是数组。它的特点是随机访问快，但插入和删除需要移动大量元素。

顺序表插入操作的代码框架：

// 文件路径：seqlist_insert.c #include <stdio.h> #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; // 在顺序表 L 的第 i 个位置插入元素 e // 注意：i 从 1 开始计数 int ListInsert(SeqList *L, int i, int e) { int k; // 1. 判断插入位置是否合法 if (L->length >= MAXSIZE) { printf("顺序表已满，无法插入\n"); return 0; } if (i < 1 || i > L->length + 1) { printf("插入位置不合法\n"); return 0; } // 2. 从最后一个元素开始，依次向后移动 for (k = L->length - 1; k >= i - 1; k--) { L->data[k + 1] = L->data[k]; } // 3. 插入新元素 L->data[i - 1] = e; // 4. 表长加 1 L->length++; return 1; }

这里有两个高频考点：

插入位置合法区间：1 <= i <= L.length + 1，注意可以在表尾插入。移动次数：在长度为 n 的顺序表中插入一个元素，平均需要移动 n/2 个元素。

同理，删除第 i 个元素时，需要将第 i+1 到第 n 个元素全部向前移动一位。时间复杂度同样是O(n)。

3.2 链表的创建、反转与删除

链表的优点是插入和删除不需要移动元素，只需要修改指针。但它的缺点是查找某个位置的结点需要从头遍历。

链表结点定义：

// 文件路径：linklist.c #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } LNode, *LinkList;

这里特别提醒：LNode是结构体类型名，LinkList是指向结构体的指针类型别名，两者经常混用，考试也喜欢在这里出辨析题。

头插法创建链表：

LinkList List_HeadInsert(LinkList *L) { LNode *s; int x; *L = (LinkList)malloc(sizeof(LNode)); // 创建头结点 (*L)->next = NULL; printf("请输入结点值，输入 -1 结束：\n"); scanf("%d", &x); while (x != -1) { s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = (*L)->next; (*L)->next = s; scanf("%d", &x); } return *L; }

头插法最后的链表元素顺序和输入顺序是相反的，这一点经常出判断题。

链表反转是笔试和上机考试的高频题：

// 反转单链表 LinkList ReverseList(LinkList L) { LNode *pre, *p, *r; pre = L->next; p = pre->next; pre->next = NULL; while (p != NULL) { r = p->next; p->next = pre; pre = p; p = r; } L->next = pre; return L; }

这个代码的逻辑是：用pre指向当前已反转链表的第一个节点，p指向当前需要反转的节点，r保存下一个节点的地址防止断开丢失。每次把p->next指向前一个节点，然后整体向后移动。

很多同学写反转链表时出错，原因通常是忘记了保存p->next，导致链表断链。

4. 栈和队列：受限的线性表

栈和队列可以理解为“加了操作限制的线性表”。它们本身不难，但考试喜欢结合出栈序列、循环队列判断来考。

4.1 栈：后进先出

栈（Stack）只允许在一端进行插入和删除操作，这一端称为栈顶。特点是后进先出（LIFO）。

栈的基本操作：入栈Push、出栈Pop、读栈顶元素GetTop。

顺序栈的定义：

// 文件路径：seqstack.c #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; // 栈顶指针，指向栈顶元素 } SeqStack;

入栈和出栈核心代码：

// 入栈 int Push(SeqStack *S, int e) { if (S->top == MAXSIZE - 1) { return 0; // 栈满 } S->top++; S->data[S->top] = e; return 1; } // 出栈 int Pop(SeqStack *S, int *e) { if (S->top == -1) { return 0; // 栈空 } *e = S->data[S->top]; S->top--; return 1; }

注意：初始化时让top = -1，表示空栈；入栈时先移动指针再赋值；出栈时先取值再移动指针。很多同学容易把顺序搞反。

考试比较爱考的一个题型是：已知入栈序列为 1,2,3,4,5，问下列哪个出栈序列是合法的。解法就是模拟入栈出栈过程，看是否有元素“穿越”的现象。

4.2 队列：先进先出

队列（Queue）只允许在队尾插入，队头删除，特点是先进先出（FIFO）。

顺序队列有个问题：随着不断的入队和出队，队头指针后移，前面空出来的位置无法利用，造成“假溢出”。所以实际应用和考试中一般使用循环队列。

循环队列的核心是求模运算，这里也是考点最密集的地方。

// 文件路径：circular_queue.c #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; // 队头指针，指向队头元素 int rear; // 队尾指针，指向队尾元素的下一个位置 } SqQueue; // 入队 int EnQueue(SqQueue *Q, int e) { if ((Q->rear + 1) % MAXSIZE == Q->front) { return 0; // 队满 } Q->data[Q->rear] = e; Q->rear = (Q->rear + 1) % MAXSIZE; return 1; } // 出队 int DeQueue(SqQueue *Q, int *e) { if (Q->front == Q->rear) { return 0; // 队空 } *e = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZE; return 1; }

循环队列这里有几个必须背下来的判断：

• 队空条件：Q.front == Q.rear
• 队满条件：(Q.rear + 1) % MAXSIZE == Q.front
• 队列长度：(Q.rear - Q.front + MAXSIZE) % MAXSIZE

注意，循环队列为了区分队空和队满，牺牲了一个存储单元，这是书上最常见的设计方案。

5. 串：KMP 算法是考研重灾区

串（String）是特殊的线性表，元素都是字符。期末考试的串部分通常只考两件事：模式匹配和KMP 算法的 next 数组计算。

朴素的模式匹配算法（BF算法）写法简单，但最坏时间复杂度是 O(m×n)，也就是主串长度乘模式串长度。

KMP 算法通过避免主串指针的回溯，将时间复杂度降低到 O(m+n)。它的核心不是匹配过程本身，而是求 next 数组。

next 数组的手工求法，是很多学校的必考题。这里给一个简单的计算规则：

1. next[1] = 0（约定，部分教材也用 -1）；
2. next[2] = 1；
3. 从第 3 个字符开始，看当前位置之前的字符串中，最长相等前后缀的长度加 1。

以模式串abaabc为例：

求解思路：j=3 时，前面是 "ab"，没有相等前后缀，所以 next=1；j=4 时，前面是 "aba"，前缀 "a" 和后缀 "a" 相等，长度为 1，所以 next=1+1=2；j=5 时，前面是 "abaa"，前缀 "ab" 和后缀 "aa" 不相等，前缀 "a" 和后缀 "a" 相等，长度 1 加 1，所以 next=2。

如果教材使用next[0] = -1的版本，整体规律不变，只是下标差一。考试时先看清教材约定。

需要说明的是：KMP 算法完整代码比较长，复试或期末考试如果考手写，通常只要求写出 next 数组或填空；如果上机考，建议把标准 KMP 代码背熟，即使不理解也能写对。

6. 树与二叉树：遍历是绝对核心

树这一章在数据结构考试里占的分数非常多。不管是期末、补考还是考研408，树都是必考内容。

树结构用来表示一对多的关系，比如文件目录、公司组织架构。而学习中重点研究的是二叉树，因为它结构规整、容易用代码实现。

6.1 二叉树的重要性质

下面几条性质几乎每年都考：

1. 第 i 层最多有2^(i-1)个结点（i >= 1）。
2. 深度为 k 的二叉树最多有2^k - 1个结点。
3. 对任何一棵二叉树，叶子结点数 n0 = 度为 2 的结点数 n2 + 1。
4. 具有 n 个结点的完全二叉树的深度为log2(n) + 1向下取整。
5. 完全二叉树从上到下、从左到右编号为 1 到 n，则编号为 i 的结点：左孩子为 2i，右孩子为 2i+1，父节点为 i/2（整除）。

性质 3 是最经典的考点，很多填空题直接引用它。例如已知一棵二叉树有 n2 个度为 2 的结点，问叶子结点数，答案就是 n2+1。

6.2 二叉树的存储与遍历

二叉树的存储可以使用顺序存储或链式存储。考试和实战中更常用链式存储，也就是二叉链表。

// 文件路径：binary_tree.c #include <stdio.h> #include <stdlib.h> typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 先序创建二叉树：输入 "AB#D##C##" 这样带 # 的序列 BiTree CreateBiTree(BiTree *T) { char ch; scanf(" %c", &ch); if (ch == '#') { *T = NULL; } else { *T = (BiTree)malloc(sizeof(BiTNode)); (*T)->data = ch; CreateBiTree(&((*T)->lchild)); CreateBiTree(&((*T)->rchild)); } return *T; }

遍历是二叉树最重要的操作。遍历方式有四种：先序、中序、后序、层次。

递归遍历的代码非常简洁：

// 先序遍历：根 -> 左 -> 右 void PreOrder(BiTree T) { if (T != NULL) { printf("%c ", T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } // 中序遍历：左 -> 根 -> 右 void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); printf("%c ", T->data); InOrder(T->rchild); } } // 后序遍历：左 -> 右 -> 根 void PostOrder(BiTree T) { if (T != NULL) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c ", T->data); } }

这三种递归遍历的代码非常相似，区别只是printf的位置。考试手写代码时，一定不要记混。

除此之外，还有一个高频考点：给出两个遍历序列还原二叉树。

做题规则：

• 先序序列的第一个结点是根结点。
• 后序序列的最后一个结点是根结点。
• 中序序列中，根结点左边是左子树，右边是右子树。

比如先序为ABDEC，中序为DBEAC，可以从先序确定 A 是根，从中序知道 DBE 是左子树、C 是右子树，再递归分析。

6.3 哈夫曼树与哈夫曼编码

哈夫曼树是一种带权路径长度最短的二叉树，也叫最优二叉树。构造算法其实很简单：

1. 从结点集合中选出权值最小的两个结点。
2. 合并它们，生成一个新结点，权值为两结点权值之和。
3. 将新结点放回集合，重复直到只剩一个结点。

考试常见题：给定一组权值{2, 3, 4, 7}，构造哈夫曼树并求带权路径长度 WPL。

计算方式是：每个叶子结点的权值乘以它到根结点的路径长度，然后求和。注意，哈夫曼树中没有度为 1 的结点，这是一个高频判断题。

哈夫曼编码的应用是数据压缩：出现频率高的字符用短编码，出现频率低的字符用长编码。编码时左分支为 0，右分支为 1。

7. 图：遍历、最短路径与最小生成树

图结构相对抽象，很多同学在这一章容易放弃。但图在考试中的题型比较固定，只要把核心算法理解清楚，拿分并不难。

图的存储方式有两种：邻接矩阵和邻接表。

• 邻接矩阵适合稠密图，判断两个顶点之间是否有边很快，时间复杂度 O(1)，但空间复杂度 O(n²)。
• 邻接表适合稀疏图，空间复杂度 O(n+e)，但判断两个顶点间是否有边需要遍历链表。

7.1 图的遍历：DFS 和 BFS

图的遍历有两个算法，和树的遍历思路类似：

• 深度优先搜索（DFS）：相当于树的先序遍历，用递归或栈实现。
• 广度优先搜索（BFS）：相当于树的层次遍历，用队列实现。

DFS 的伪代码非常好记：

void DFS(Graph G, int v) { visited[v] = 1; // 标记已访问 printf("%d ", v); // 访问结点 // 遍历 v 的所有邻接点 w for (每个邻接点 w) { if (!visited[w]) { DFS(G, w); // 递归访问 } } }

BFS 的伪代码：

void BFS(Graph G, int v) { int queue[MAXSIZE], front = 0, rear = 0; visited[v] = 1; printf("%d ", v); queue[rear++] = v; while (front != rear) { int u = queue[front++]; for (每个 u 的邻接点 w) { if (!visited[w]) { visited[w] = 1; printf("%d ", w); queue[rear++] = w; } } } }

考试经常问“给出从某顶点出发的 DFS/BFS 序列”，解法就是按邻接表或邻接矩阵中顶点的存储顺序依次访问。

7.2 最小生成树：Prim 和 Kruskal

最小生成树用于在带权连通图中找一棵权值之和最小的生成树。

• Prim 算法：从一个顶点出发，每次选择距离当前生成树最近的一个顶点加入。适合稠密图。
• Kruskal 算法：每次选择权值最小的边，只要不形成回路就加入。适合稀疏图。

做题时，Kruskal 算法更容易手算出结果。只要记住一个原则：每次选权值最小的边，如果这条边的两个顶点不在同一个连通分量中，就选择它。

7.3 最短路径：Dijkstra 和 Floyd

Dijkstra 算法解决单源最短路径问题，也就是从一个源点到其他所有顶点的最短路径。它的思路是贪心：每次选择一个距离源点最近且未确定最短路径的顶点，更新它相邻顶点的距离。

Floyd 算法解决所有顶点对之间的最短路径，核心是一个三重循环：

for (k = 0; k < n; k++) for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];

上面这段代码非常经典，考研 408 也喜欢考。它的含义是：允许经过前 k 个顶点作为中转，更新 i 到 j 的最短路径。

8. 查找：二分查找、二叉排序树与哈希表

查找这一章的知识点相对零散，但考试容易出大题。

8.1 二分查找

二分查找的前提是线性表有序，且采用顺序存储。它的时间复杂度是 O(log n)。

二分查找的递归实现：

// 文件路径：binary_search.c int BinarySearch(int arr[], int low, int high, int key) { if (low > high) { return -1; // 查找失败 } int mid = (low + high) / 2; if (arr[mid] == key) { return mid; } else if (arr[mid] > key) { return BinarySearch(arr, low, mid - 1, key); } else { return BinarySearch(arr, mid + 1, high, key); } }

注意，二分查找的判定树是一棵平衡二叉树，查找失败的比较次数不超过树的深度。

8.2 二叉排序树

二叉排序树（BST，Binary Search Tree）的定义是：左子树所有结点的值小于根结点，右子树所有结点的值大于根结点；左右子树也分别是二叉排序树。

二叉排序树的插入操作：

BiTree BST_Insert(BiTree T, int key) { if (T == NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data = key; T->lchild = T->rchild = NULL; } else if (key < T->data) { T->lchild = BST_Insert(T->lchild, key); } else if (key > T->data) { T->rchild = BST_Insert(T->rchild, key); } // key 等于 T->data 时，不插入，保持关键字不重复 return T; }

对二叉排序树进行中序遍历，可以得到一个递增有序序列。这个结论经常考。

8.3 哈希表

哈希表通过散列函数把关键字映射到表中的一个位置，查找时间复杂度在理想情况下是 O(1)。

常见散列函数有除留余数法，冲突处理方法有开放定址法中的线性探测法、平方探测法，以及链地址法。

考试题一般给一组关键字，让你用线性探测法构造哈希表，并计算平均查找长度 ASL。

做题时要注意：装填因子，也就是表中记录数除以表长，会直接影响查找效率。哈希表装得越满，冲突概率越大，平均查找长度越长。

9. 排序：复杂度、稳定性与代码

排序这章是数据结构的最后一个重点，也是期末最容易出大题的地方。考试通常要求记住所有排序算法的复杂度、稳定性和适用场景。

9.1 排序算法对比总表

记忆技巧：

• 稳定排序只有四个：直接插入、冒泡、归并、基数。
• 快速排序最坏情况发生在序列基本有序时，时间复杂度退化为 O(n²)。
• 堆排序和归并排序的时间复杂度任何情况下都是 O(n log n)。
• 归并排序的空间复杂度是 O(n)，因为它需要额外的辅助数组。

9.2 必背代码：快速排序

快速排序是考试中出现频率最高的排序代码。它是一种分治算法：选一个基准值，把比它小的放左边，比它大的放右边，然后对左右两部分递归排序。

// 文件路径：quick_sort.c // 一趟划分：把数组分成左小右大两部分 int Partition(int arr[], int low, int high) { int pivot = arr[low]; // 以第一个元素为基准值 while (low < high) { // 从右向左找比基准小的元素 while (low < high && arr[high] >= pivot) { high--; } arr[low] = arr[high]; // 从左向右找比基准大的元素 while (low < high && arr[low] <= pivot) { low++; } arr[high] = arr[low]; } arr[low] = pivot; // 基准值放到最终位置 return low; // 返回基准值的最终位置 } // 快速排序递归入口 void QuickSort(int arr[], int low, int high) { if (low < high) { int pivotPos = Partition(arr, low, high); QuickSort(arr, low, pivotPos - 1); QuickSort(arr, pivotPos + 1, high); } }

快速排序每一趟结束后，基准值会被放到最终位置，它左边的元素都小于它，右边的元素都大于它。这个性质经常出选择题：给出一趟排序后的序列，让你判断可能使用了哪种排序算法。

9.3 必背代码：堆排序

堆排序也比较常考。堆是一种特殊的完全二叉树：

• 大根堆：每个结点的值都大于或等于左右孩子。
• 小根堆：每个结点的值都小于或等于左右孩子。

堆排序的核心是“建堆 + 调整”。

// 对大根堆进行调整 void HeapAdjust(int arr[], int root, int len) { int temp = arr[root]; for (int i = 2 * root + 1; i < len; i = 2 * i + 1) { // 找出左右孩子中较大的那个 if (i + 1 < len && arr[i] < arr[i + 1]) { i++; } if (arr[i] > temp) { arr[root] = arr[i]; root = i; } else { break; } } arr[root] = temp; }

堆排序的平均时间复杂度是 O(n log n)，且没有引入额外的大数组，空间复杂度为 O(1)，非常优秀。但它是不稳定的。

10. 常见易错点与排查清单

下面是学生在复习过程中最容易犯的错误，很多都是补考同学反馈的真实踩坑点。

11. 复习时间安排与应试技巧

如果你是零基础速成，一周时间完全可以把数据结构拉到及格线。这里给一个亲测有效的“一周救急安排”：

• 第 1 天：重点复习时间复杂度和线性表，包括顺序表、链表增删改查代码。
• 第 2 天：栈和队列 + 串。掌握栈的应用，比如括号匹配；循环队列的判断条件；KMP 只练 next 数组。
• 第 3 天：二叉树。把三种遍历递归代码默写三遍；熟练掌握已知两个序列还原二叉树。
• 第 4 天：图。只掌握邻接矩阵转 DFS/BFS 序列、Prim/Kruskal 手算、Dijkstra 表格法。
• 第 5 天：查找。重点做二分查找和哈希表的题。
• 第 6 天：排序。把所有排序算法的手算过程过一遍，快速排序代码默写三遍。
• 第 7 天：刷期末真题，重点刷计算题和算法填空。

应试技巧上，有几点值得注意：

第一，手写代码时先写函数头和返回值，即使内部逻辑不完整，也能得到步骤分。第二，计算复杂度时不要只写结果，把基本语句的执行次数推导过程写上。第三，遇到设计题，优先考虑哈希表和二叉树，这两种结构的代码模板最好背。

这里也明确说明一下：不要让代码成为复习的全部。数据结构考试中，概念题、计算题和画图题占的分数通常更高。例如让你画出某个序列在排序过程中的每一趟结果，这种题背再多的代码都没用，一定要亲手在草稿纸上推演。

12. 写在最后

数据结构这门课确实有难度，但它并不是靠天赋才能学好的科目。关键是把知识框架搭起来，把算法过程在草稿纸上推演清楚，再把核心代码模板默写熟练，期末不挂科完全没有问题。

如果你正在准备补考或考研，不要贪多求快。把线性表、二叉树、排序这三块吃透，就已经覆盖了考试的大部分分数。图的算法看懂了模板就多练习几遍，不需要追求理解每一种算法的数学证明。

希望这篇知识框架梳理能帮你减少找资料的时间，把精力真正花在理解和代码练习上。如果文章对你有帮助，可以先收藏备用，复习过程中随时回来对照检查。