数据结构C语言版这门课几乎是计算机专业的第一道分水岭。期末前很多人手里只剩一本教材和一堆没整理完的笔记补考前想临时抱佛脚结果连单链表反转都要对着代码发半天呆。这篇文章不讨论“数据结构重不重要”直接给你一套照着练就能上手的补考救急方案先搭知识框架再逐个过线性表、栈、队列、串、树、图、查找、排序这些核心章节每个章节配可直接运行的 C 语言代码最后给 7 天速成路线、答题模板和常见报错排查清单。内容同时覆盖几种典型场景期末不挂科、补考救急、考研复试前专业课框架梳理、软考数据结构备考。如果你零基础建议先把第 4 节的知识地图看完再往后看代码时不要死记而是把每个结构理解成“数据怎么存、怎么增删改查”。打开 VSCode一边看文章一边把代码跑起来会更有用——数据结构这门课光看不写等于没看。1. 数据结构C语言版核心能力速览能力项说明课程范围线性表、栈、队列、串、树、图、查找、排序教材参考严蔚敏《数据结构C语言版》兼容期末、考研常见考点适合场景课前预习、期中复习、期末速成、补考救急、考研复试梳理、软考备考学习形式知识框架 C 语言代码示例 复习路线 答题模板运行环境Windows / Linux / macOS需安装 GCC 或 MSVC 等 C 语言编译环境前置要求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-w64Linux 下直接装 gcc。以 Ubuntu/Debian 为例安装命令如下sudo apt update sudo apt install gcc gcc --versionWindows 下如果装好 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 知识点与考试题型对应知识模块常见概念题常见代码题常考复杂度线性表顺序表与链表的优缺点插入、删除、反转、合并O(n)栈和队列先进后出、先进先出进出栈序列、循环队列判空判满O(1)串模式匹配思想KMP 的 next 数组O(mn) / O(nm)树与二叉树节点数、深度、遍历序列递归遍历、层序、求高度O(n)图连通性、生成树DFS、BFS、最短路径O(n²) / O(ne)查找平均查找长度折半查找、二叉排序树O(log n)排序稳定性、趟数快排、冒泡、简单选择见排序表建议打印这张表放旁边。做题时先判断题目属于哪个模块再回忆对应模板比一上来就翻书快得多。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(nm)。期末和考研复试主要考两点能说出朴素匹配和 KMP 的思路区别会手算 next 数组。next 数组手算技巧next[1] 固定为 0next[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 排序算法复杂度速查表算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入排序O(n²)O(n²)O(1)稳定希尔排序约 O(n^1.3)O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定简单选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定稳定性是选择题高频考点只有简单插入、冒泡、归并是稳定的快排、堆排、选择排序、希尔排序都不稳定。判断方法可以靠记口诀也可以从代码逻辑上理解稳定性只关心“相等元素排序后相对顺序是否改变”。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 代码题审题步骤拿到算法设计题先做四件事识别数据结构是数组、链表、栈、队列还是二叉树、图。明确目标操作是查找、插入、删除、反转还是遍历。找边界条件空表、单节点、尾节点、目标值不存在、重复元素。确定复杂度写完后主动标注时间和空间复杂度。很多同学不是不会写而是没定位到模板。数据结构题目的题干里通常有非常明显的暗示比如“先进后出”对应栈“先进先出”对应队列“有序表”对应折半查找或归并“递归”大概率对应树。11. 常见问题排查与避坑指南问题现象可能原因排查方式解决方案编译报 undefined reference函数只声明没定义或文件没一起编译检查编译命令里是否包含所有 .c 文件把实现补齐多文件一起编译编译报 segment fault空指针访问、数组越界、非法内存访问用 printf 打点定位崩溃位置检查 malloc 返回值、数组下标、指针释放程序运行结果不对插入删除时移动元素方向写反用一组小数据手动推演对照 5.1 节的顺序表代码链表操作后丢失节点修改 next 前没保存原后继画链表指针变化示意图先把 temp cur-next 记住递归栈溢出递归层数太深或缺少递归出口检查递归结束条件补充 root NULL 等终止条件快速排序死循环左右扫描条件没有取等号或枢轴选错用小数组模拟第一趟严格按照 ij、arr[j]pivot 的写法感觉自己会但写不出来平时只看不练缺少模板对着本文代码手写默写每个核心结构独立写一遍复杂度写错没有数最内层循环执行次数用变量代入 n4、n8 手算按“最深层循环体执行次数”估算考试中代码写错不可怕可怕的是不知道错在哪。平时在编译环境里把代码跑通能显著减少考场上的低级错误。建议把常见的段错误、空指针、越界问题整理成自己的“踩坑清单”考前一晚看一遍。12. 最佳实践与学习建议数据结构的学习效率差距主要来自“是否动手”。我的建议是每个核心结构都建立三个文件版本第一遍抄写并理解第二遍盖住代码自己默写第三遍修改参数或换一个需求重新实现。三遍之后链表反转、二叉树遍历、快排这类高频题基本就是肌肉记忆了。画图是另一个被低估的方法。学链表时画箭头图学树时画递归展开图学图时画邻接矩阵和邻接表转换图。遇到不会的题先在草稿纸上画图画完思路通常就出来了。对考研复试来说能对着图讲清 Prim 算法的选边过程比死背代码更容易给老师留下好印象。最后说一句实用的这份内容适合补救但真正的目标是建立知识框架。补考通过只是第一步后面学操作系统、数据库、算法设计都会反复用到这些结构。建议把 5 到 9 节的代码模板保存下来作为自己的“数据结构最小代码库”以后写算法题、做课程设计、复习复试时都能直接拿出来用。建议收藏备用考前照着章节顺序过一遍比临时找零散笔记稳得多。
