数据结构C语言版补考速成：核心考点与代码模板

数据结构（C语言版）这门课，几乎是计算机专业的第一道分水岭。期末前很多人手里只剩一本教材和一堆没整理完的笔记，补考前想临时抱佛脚，结果连单链表反转都要对着代码发半天呆。这篇文章不讨论“数据结构重不重要”，直接给你一套照着练就能上手的补考救急方案：先搭知识框架，再逐个过线性表、栈、队列、串、树、图、查找、排序这些核心章节，每个章节配可直接运行的 C 语言代码，最后给 7 天速成路线、答题模板和常见报错排查清单。

内容同时覆盖几种典型场景：期末不挂科、补考救急、考研复试前专业课框架梳理、软考数据结构备考。如果你零基础，建议先把第 4 节的知识地图看完，再往后看代码时不要死记，而是把每个结构理解成“数据怎么存、怎么增删改查”。打开 VSCode，一边看文章一边把代码跑起来会更有用——数据结构这门课，光看不写等于没看。

1. 数据结构（C语言版）核心能力速览

这里额外说一句：表里的“运行环境”是通用判断，不同学校的实验环境可能不一样。有的学校用 Dev-C++，有的用 VS，有的直接在 Linux 终端里用 gcc 编译。建议考前先确认学校实验课用的编辑器，提前适配，避免考试时操作不顺手。

2. 适用场景与学习边界

2.1 谁能用这套内容

• 期末考前一周到两周，需要快速过一遍核心考点的同学。
• 补考前想把知识框架重新建起来，而不是从头啃教材的同学。
• 考研复试前需要把数据结构专业课框架、算法模板快速捡起来的同学。
• 备考软考、准备面试算法题，需要一套精简 C 语言数据结构笔记的同学。

2.2 能解决什么问题

这门课挂科和失分的点通常很集中：不知道每个结构适用于什么场景、手写代码没有模板、复杂度分析不会表达。本文给出的每个章节都按“结构定义 -> 核心操作 -> 常见考点 -> 复杂度”的套路整理，目的就是让你拿到题目后能快速定位到对应的数据结构模板。

2.3 不适合什么场景

如果抱着“背两天就裸考”“完全不写代码只想看概念”的心态，这套内容帮不了太多。数据结构的代码题、算法设计题必须动手练，只看不写会在考场上卡住。补考和正常考试一样，要遵守学校纪律，不能有任何作弊行为，学习资源的目的是帮你真正掌握，而不是走捷径。

另一点要注意：课程实验报告、老师课件、题库如果来自校内渠道或他人整理，转发和使用前要确认授权。不要把他人的作业直接提交，也不要为了“速成”把别人的代码原封不动交上去，一旦涉及抄袭，后果比挂科严重得多。

3. 开发环境准备：VSCode 与 GCC 配置速查

3.1 环境搭建

用 VSCode 写 C 语言是比较通用的方案，免费、跨平台、补全和调试都方便。基础流程是先装 VSCode，再装 C/C++ 插件，最后确认编译器可用。Windows 下比较常见的是安装 MinGW-w64，Linux 下直接装 gcc。

以 Ubuntu/Debian 为例，安装命令如下：

sudo apt update sudo apt install gcc gcc --version

Windows 下如果装好 MinGW-w64，需要把安装目录下的 bin 文件夹加入系统 PATH，然后在终端里验证：

gcc --version

确认编译器可用后，用 VSCode 打开一个文件夹，写好代码后打开终端编译运行。

3.2 编译命令模板

单文件 C 程序的编译运行，先切到代码所在目录，然后执行：

gcc test.c -o test ./test

如果代码里有多个文件，可以把所有.c文件一次编译：

gcc main.c list.c queue.c -o program ./program

编写代码时把结构体定义、函数声明、主函数拆好，考试的手写代码题也按这个习惯写：先结构体，再辅助函数，最后主逻辑。平时在 VSCode 里跑通，考场上写伪代码、写核心函数会顺很多。

4. 知识框架梳理：先建地图再学细节

4.1 数据结构整体分类

数据结构解决的核心问题是“数据怎么组织、怎么存储、怎么操作”。从逻辑上看，分为线性结构和非线性结构：

• 线性结构：线性表、栈、队列、串、数组。
• 非线性结构：树、二叉树、图、集合。

从存储方式看，分为顺序存储、链式存储、索引存储、散列存储。C 语言里顺序存储通常用数组实现，链式存储用结构体 + 指针实现。

4.2 知识点与考试题型对应

建议打印这张表放旁边。做题时先判断题目属于哪个模块，再回忆对应模板，比一上来就翻书快得多。

5. 线性表：顺序表与链表

5.1 顺序表的 C 语言实现

顺序表的特点是逻辑相邻、物理也相邻，用数组实现，支持随机访问。插入和删除要移动大量元素，所以时间复杂度是 O(n)。

#include <stdio.h> #define MaxSize 100 typedef struct { int data[MaxSize]; int length; } SeqList; void InitList(SeqList *L) { L->length = 0; } int InsertList(SeqList *L, int pos, int val) { 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] = val; L->length++; return 1; } int DeleteList(SeqList *L, int pos, int *val) { if (pos < 1 || pos > L->length) return 0; *val = L->data[pos - 1]; for (int i = pos; i < L->length; i++) { L->data[i - 1] = L->data[i]; } L->length--; return 1; } int main() { SeqList L; InitList(&L); InsertList(&L, 1, 10); InsertList(&L, 2, 20); InsertList(&L, 2, 15); int x; DeleteList(&L, 2, &x); printf("deleted=%d length=%d\n", x, L.length); return 0; }

考试时顺序表最容易丢分的点有两个：一是插入位置参数是 1 开始还是 0 开始，二是移动元素的方向写反。插入时要先移动后面的元素，从后往前循环；删除时要覆盖前面的元素，从前往后循环。把这两个方向的循环写对，顺序表推导题基本就没问题。

5.2 单链表的 C 语言实现

单链表用结构体 + 指针把不连续的节点串起来，插入删除不需要移动元素，但查找需要从头遍历。头结点可以简化边界判断，面试和考试题里很常见。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } LNode, *LinkList; LinkList CreateListTail(int arr[], int n) { LinkList head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; LNode *tail = head; for (int i = 0; i < n; i++) { LNode *p = (LNode *)malloc(sizeof(LNode)); p->data = arr[i]; p->next = NULL; tail->next = p; tail = p; } return head; } void PrintList(LinkList head) { LNode *p = head->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); } LinkList ReverseList(LinkList head) { LNode *cur = head->next; LNode *pre = NULL; while (cur != NULL) { LNode *temp = cur->next; cur->next = pre; pre = cur; cur = temp; } head->next = pre; return head; } int main() { int arr[] = {1, 2, 3, 4, 5}; LinkList L = CreateListTail(arr, 5); PrintList(L); L = ReverseList(L); PrintList(L); return 0; }

链表相关的题目非常多：反转、合并两个有序链表、删除倒数第 N 个节点、判断是否有环。这些题的核心都是“指针操作顺序”，写代码前先在草稿纸上画两个节点的连线，把 next 指针要不要提前保存想清楚。单链表最经典的坑是 cur->next 被修改后，原链表断了，所以要先用 temp 保存原后继。

6. 栈、队列与串

6.1 顺序栈的 C 语言实现

栈是先进后出的线性表，只在一端插入和删除。顺序栈用数组加 top 指针实现，入栈出栈都是 O(1)。

#include <stdio.h> #define MaxSize 100 typedef struct { int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *s) { s->top = -1; } int Push(SqStack *s, int x) { if (s->top == MaxSize - 1) return 0; s->data[++s->top] = x; return 1; } int Pop(SqStack *s, int *x) { if (s->top == -1) return 0; *x = s->data[s->top--]; return 1; } int IsEmpty(SqStack s) { return s.top == -1; } int main() { SqStack s; InitStack(&s); Push(&s, 1); Push(&s, 2); Push(&s, 3); int x; while (!IsEmpty(s)) { Pop(&s, &x); printf("%d ", x); } printf("\n"); return 0; }

栈的应用题常考括号匹配、表达式求值、递归转非递归。括号匹配的思路是：遇到左括号入栈，遇到右括号检查栈顶是否匹配，不匹配或栈空就是错误。考试时如果给一个出栈序列让你判断是否合法，直接把元素按序入栈，再模拟出栈过程即可。

6.2 循环队列的 C 语言实现

队列是先进先出的线性表。为了利用数组空间，一般用循环队列，通过取模运算让队尾回到数组开头。判断队列满的方式是(rear + 1) % MaxSize == front，会牺牲一个存储单元，这和顺序栈的判满方式不一样，是常考选择题。

#include <stdio.h> #define MaxSize 100 typedef struct { int data[MaxSize]; int front, rear; } SqQueue; void InitQueue(SqQueue *q) { q->front = q->rear = 0; } int EnQueue(SqQueue *q, int x) { if ((q->rear + 1) % MaxSize == q->front) return 0; q->data[q->rear] = x; q->rear = (q->rear + 1) % MaxSize; return 1; } int DeQueue(SqQueue *q, int *x) { if (q->front == q->rear) return 0; *x = q->data[q->front]; q->front = (q->front + 1) % MaxSize; return 1; } int main() { SqQueue q; InitQueue(&q); EnQueue(&q, 10); EnQueue(&q, 20); EnQueue(&q, 30); int x; while (DeQueue(&q, &x)) { printf("%d ", x); } printf("\n"); return 0; }

循环队列选择题的高频考点是：已知队头 front、队尾 rear、容量 MaxSize，求队列元素个数。公式是(rear - front + MaxSize) % MaxSize。如果题目用front == rear判空、用(rear + 1) % MaxSize == front判满，套这个公式基本不会错。

6.3 串的模式匹配

串是字符组成的线性结构。朴素模式匹配是两个循环逐字符比较，最坏时间复杂度 O(mn)。KMP 算法通过 next 数组跳过已匹配的位置，最坏 O(n+m)。期末和考研复试主要考两点：能说出朴素匹配和 KMP 的思路区别，会手算 next 数组。

next 数组手算技巧：next[1] 固定为 0，next[2] 固定为 1，从第三个位置开始看前面子串的“最长相等前后缀长度再加 1”，这是考试计算题最容易拿分的部分，建议考前专门练 5 道 next 数组题。

7. 树与二叉树

7.1 二叉树结构定义与递归遍历

树是非线性结构，二叉树每个节点最多两个子树。用 C 语言定义二叉树节点时，每个节点包含数据域和左右子树指针。前序、中序、后序遍历的递归写法非常固定，属于必须默写的内容。

#include <stdio.h> #include <stdlib.h> typedef struct BiTNode { char data; struct BiTNode *left, *right; } BiTNode, *BiTree; BiTree CreateNode(char val) { BiTree node = (BiTree)malloc(sizeof(BiTNode)); node->data = val; node->left = NULL; node->right = NULL; return node; } void PreOrder(BiTree root) { if (root == NULL) return; printf("%c ", root->data); PreOrder(root->left); PreOrder(root->right); } void InOrder(BiTree root) { if (root == NULL) return; InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } void PostOrder(BiTree root) { if (root == NULL) return; PostOrder(root->left); PostOrder(root->right); printf("%c ", root->data); } int main() { BiTree root = CreateNode('A'); root->left = CreateNode('B'); root->right = CreateNode('C'); root->left->left = CreateNode('D'); root->left->right = CreateNode('E'); printf("Pre: "); PreOrder(root); printf("\n"); printf("In: "); InOrder(root); printf("\n"); printf("Post: "); PostOrder(root); printf("\n"); return 0; }

这三种遍历的核心区别就是printf的位置。前序在递归左子树之前打印，中序在左子树和右子树之间打印，后序在两边都递归完之后打印。考试给出二叉树画遍历序列，或者给出前序和中序推后序，都靠这个理解。

7.2 层序遍历与队列

层序遍历按从上到下、从左到右的顺序访问节点，需要借助队列。这个思路经常用在求树高、判断完全二叉树、二叉树剪枝等题目中。

#include <stdio.h> #include <stdlib.h> typedef struct BiTNode { char data; struct BiTNode *left, *right; } BiTNode, *BiTree; #define MaxSize 50 typedef struct { BiTree data[MaxSize]; int front, rear; } Queue; void InitQueue(Queue *q) { q->front = q->rear = 0; } int EnQueue(Queue *q, BiTree node) { if ((q->rear + 1) % MaxSize == q->front) return 0; q->data[q->rear] = node; q->rear = (q->rear + 1) % MaxSize; return 1; } int DeQueue(Queue *q, BiTree *node) { if (q->front == q->rear) return 0; *node = q->data[q->front]; q->front = (q->front + 1) % MaxSize; return 1; } void LevelOrder(BiTree root) { if (root == NULL) return; Queue q; InitQueue(&q); EnQueue(&q, root); BiTree cur; while (DeQueue(&q, &cur)) { if (cur == NULL) continue; printf("%c ", cur->data); if (cur->left) EnQueue(&q, cur->left); if (cur->right) EnQueue(&q, cur->right); } printf("\n"); }

层序遍历的通用模板是“出队一个节点，访问它，再把它的左右孩子入队”。凡是要求“按层”处理的题，基本都能套这个模板。二叉树的另一个常考概念是二叉排序树：左子树所有节点值小于根，右子树所有节点值大于根，中序遍历二叉排序树得到递增序列，这个性质在查找章节还会用到。

8. 图：邻接表、DFS 与 BFS

图分为有向图和无向图，存储方式常考邻接矩阵和邻接表。邻接矩阵适合稠密图，判断两个顶点是否相连是 O(1)；邻接表适合稀疏图，遍历邻接点更高效。DFS 用递归或栈，BFS 用队列，这两个算法必须会写。

邻接表的核心结构体通常包含顶点数组和边链表：

#include <stdio.h> #include <stdlib.h> #define MaxVerNum 100 typedef struct ArcNode { int adjvex; struct ArcNode *next; } ArcNode; typedef struct VNode { char data; ArcNode *first; } VNode, AdjList[MaxVerNum]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; int visited[MaxVerNum]; void DFS(ALGraph *G, int v) { visited[v] = 1; printf("%c ", G->vertices[v].data); ArcNode *p = G->vertices[v].first; while (p != NULL) { if (!visited[p->adjvex]) { DFS(G, p->adjvex); } p = p->next; } }

图论算法题的高频考点是：根据给定图手画 DFS/BFS 序列、用 Prim 或 Kruskal 求最小生成树、用 Dijkstra 求单源最短路径。这些题不要求写出完整可运行的 C 语言代码，但要求你描述算法步骤、写出每轮更新的表。复习时把 Prim 和 Dijkstra 的填表过程各手推 3 遍，比背代码有用。

9. 查找与排序

9.1 折半查找

折半查找要求线性表有序且能随机访问，所以适合顺序表，不适合链表。每次把区间缩小一半，时间复杂度 O(log n)。

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

注意折半查找的循环条件是low <= high，不是low < high。漏掉等号会导致查找最后一个元素时失败。考研和期末题喜欢考“查找失败时的比较次数”和“ASL 平均查找长度”，手画折半查找判定树是解题关键。

9.2 快速排序

快速排序是常考排序算法的主体。它的思想是选一个枢轴元素，把比它小的放左边、比它大的放右边，然后左右递归。下面这段是考研手写代码的高频版本。

void QuickSort(int arr[], int low, int high) { if (low < high) { int pivot = arr[low]; int i = low, j = high; while (i < j) { while (i < j && arr[j] >= pivot) j--; arr[i] = arr[j]; while (i < j && arr[i] <= pivot) i++; arr[j] = arr[i]; } arr[i] = pivot; QuickSort(arr, low, i - 1); QuickSort(arr, i + 1, high); } }

快排必须记住三点：先从右往左找比枢轴小的元素，再从左往右找比枢轴大的元素；挖坑填数的顺序是从右开始；每一趟结束后枢轴元素到了最终位置。考试常问“第一趟快排后序列是什么”，按这个规则手推即可。

9.3 排序算法复杂度速查表

稳定性是选择题高频考点：只有简单插入、冒泡、归并是稳定的，快排、堆排、选择排序、希尔排序都不稳定。判断方法可以靠记口诀，也可以从代码逻辑上理解：稳定性只关心“相等元素排序后相对顺序是否改变”。

10. 速成复习路线与答题模板

10.1 考前 7 天复习路线

如果只剩一周，不建议按教材章节顺序硬啃。推荐这样分配：

• 第 1 天：把第 4 节知识框架表格过一遍，搞清楚线性、树、图、查找、排序分别考什么。
• 第 2 天：线性表和栈队列，把 5、6 两节的代码全部跑通。
• 第 3 天：二叉树实现、三种递归遍历、层序遍历，手动画 3 棵树的遍历序列。
• 第 4 天：图论，重点练 DFS/BFS，能把邻接矩阵和邻接表互相转换。
• 第 5 天：查找和排序，重点手推折半查找、快速排序、归并排序过程。
• 第 6 天：做一套往年真题，严格按考试时间。
• 第 7 天：只复盘错题，把“会写但写错”的代码手写一遍。

每天保证至少 2 小时上机，手写代码题一定不要只在脑内过，要在编辑器或草稿纸上完整写出来。

10.2 算法设计题回答模板

期末和补考的算法题一般要求写出结构体定义、函数实现、时间复杂度分析。按下面这个套路写，条理会清楚很多：

// 第一步：定义结构体，说明数据类型 typedef struct Node { int data; struct Node *next; } LNode, *LinkList; // 第二步：实现题目要求的功能 // 例如：删除链表中所有值为 target 的节点 void DeleteTarget(LinkList head, int target) { LNode *pre = head; LNode *cur = head->next; while (cur != NULL) { if (cur->data == target) { pre->next = cur->next; free(cur); cur = pre->next; } else { pre = cur; cur = cur->next; } } } // 第三步：说明时间复杂度和空间复杂度 // 时间复杂度 O(n)，空间复杂度 O(1)

阅卷时老师最看重的是函数能不能解决问题、边界条件是否考虑、复杂度是否写对。写的时候先把自己的思路用注释写出来，再逐步补代码，哪怕最后不完美也比空白强。

10.3 代码题审题步骤

拿到算法设计题，先做四件事：

1. 识别数据结构：是数组、链表、栈、队列还是二叉树、图。
2. 明确目标操作：是查找、插入、删除、反转还是遍历。
3. 找边界条件：空表、单节点、尾节点、目标值不存在、重复元素。
4. 确定复杂度：写完后主动标注时间和空间复杂度。

很多同学不是不会写，而是没定位到模板。数据结构题目的题干里通常有非常明显的暗示，比如“先进后出”对应栈，“先进先出”对应队列，“有序表”对应折半查找或归并，“递归”大概率对应树。

11. 常见问题排查与避坑指南

考试中代码写错不可怕，可怕的是不知道错在哪。平时在编译环境里把代码跑通，能显著减少考场上的低级错误。建议把常见的段错误、空指针、越界问题整理成自己的“踩坑清单”，考前一晚看一遍。

12. 最佳实践与学习建议

数据结构的学习效率差距，主要来自“是否动手”。我的建议是：每个核心结构都建立三个文件版本，第一遍抄写并理解，第二遍盖住代码自己默写，第三遍修改参数或换一个需求重新实现。三遍之后，链表反转、二叉树遍历、快排这类高频题基本就是肌肉记忆了。

画图是另一个被低估的方法。学链表时画箭头图，学树时画递归展开图，学图时画邻接矩阵和邻接表转换图。遇到不会的题，先在草稿纸上画图，画完思路通常就出来了。对考研复试来说，能对着图讲清 Prim 算法的选边过程，比死背代码更容易给老师留下好印象。

最后说一句实用的：这份内容适合补救，但真正的目标是建立知识框架。补考通过只是第一步，后面学操作系统、数据库、算法设计都会反复用到这些结构。建议把 5 到 9 节的代码模板保存下来，作为自己的“数据结构最小代码库”，以后写算法题、做课程设计、复习复试时都能直接拿出来用。建议收藏备用，考前照着章节顺序过一遍，比临时找零散笔记稳得多。