408 数据结构核心代码与逻辑速记
适用：计算机考研 408《数据结构》复习
默认语言：C 语言
重点：定义 → 核心操作 → 代码模板 → 逻辑 → 时间复杂度 → 高频易错点
0. 总体框架
408 里这几种线性结构可以先用一句话记住：
| 结构 | 核心特征 | 最常考的操作 |
|---|---|---|
| 顺序表 | 连续存储、下标随机访问 | 按位插入、按位删除、查找 |
| 单链表 | 结点离散、靠指针连接 | 插入、删除、逆置 |
| 栈 | LIFO 后进先出 | 入栈、出栈、括号/表达式 |
| 队列 | FIFO 先进先出 | 入队、出队、循环队列 |
| 二叉树 | 递归定义明显 | 四种遍历、深度、结点计数 |
一、顺序表（Sequential List）
1.1 基本结构
c#define MaxSize 50typedef int ElemType;typedef struct { ElemType data[MaxSize]; int length; // 当前有效元素个数} SqList;
核心逻辑
data是连续内存。- 第
i个逻辑元素通常存放在data[i-1]（教材若按 1 开始编号）。 - 随机访问：
L.data[i]，时间复杂度O(1)。 - 在中间插入/删除，需要移动大量元素，所以通常是
O(n)。
1.2 按位插入
设第 i 个位置插入 e（1 ≤ i ≤ length+1）。
cbool ListInsert(SqList *L, int i, ElemType e){ if (i < 1 || i > L->length + 1) return false; if (L->length >= MaxSize) return false; // 从后往前移动，给 data[i-1] 腾位置 for (int j = L->length; j >= i; j--) L->data[j] = L->data[j - 1]; L->data[i - 1] = e; L->length++; return true;}
为什么“从后往前”？
假设：
text[a b c d] ↑ 在第2个位置插入 X错误：从前往后搬a → b → c → d会覆盖原数据正确：从后往前搬d → 空位c → db → cX → b原来的位置
口诀：插入后移，从后往前。
1.3 按位删除
删除第 i 个元素，并用 *e 带回被删除的元素。
cbool ListDelete(SqList *L, int i, ElemType *e){ if (i < 1 || i > L->length) return false; *e = L->data[i - 1]; // 从前往后覆盖被删除位置 for (int j = i; j < L->length; j++) L->data[j - 1] = L->data[j]; L->length--; return true;}
口诀：删除前移，从前往后。
1.4 按值查找
cint LocateElem(SqList L, ElemType e){ for (int i = 0; i < L.length; i++) if (L.data[i] == e) return i + 1; // 返回位序 return 0; // 查找失败}
- 最好情况：
O(1) - 最坏情况：
O(n) - 平均情况：
O(n)
1.5 顺序表复杂度表
| 操作 | 复杂度 |
|---|---|
| 按下标访问 | O(1) |
| 按值查找 | O(n) |
| 指定位置插入 | O(n) |
| 指定位置删除 | O(n) |
高频坑
- 位序和数组下标差 1。
- 插入必须判断
i <= length + 1。 - 删除必须判断
i <= length。 - 插入移动元素一定要从后往前。
- 删除移动元素一定是从前往后。
二、单链表（Singly Linked List）
2.1 结点结构
ctypedef int ElemType;typedef struct LNode { ElemType data; struct LNode *next;} LNode, *LinkList;
若采用带头结点的单链表：
cLinkList L;L = (LNode *)malloc(sizeof(LNode));L->next = NULL;
为什么常用头结点？
头结点不存有效数据，它让第一个数据结点的插入、删除与普通位置操作更加统一。
2.2 按位查找
查找第 i 个数据结点：
cLNode *GetElem(LinkList L, int i){ if (i < 1) return NULL; LNode *p = L->next; int j = 1; while (p != NULL && j < i) { p = p->next; j++; } return p;}
逻辑
链表不能直接跳到第 i 个结点，必须从头开始顺着 next 走。
所以：
单链表按位查找 =
O(n)
2.3 在第 i 个位置插入
cbool ListInsert(LinkList L, int i, ElemType e){ if (i < 1) return false; // 找到第 i-1 个结点 LNode *p = L; int j = 0; while (p != NULL && j < i - 1) { p = p->next; j++; } if (p == NULL) return false; LNode *s = (LNode *)malloc(sizeof(LNode)); if (s == NULL) return false; s->data = e; s->next = p->next; p->next = s; return true;}
插入的关键顺序
textp -> q先：s->next = p->next再：p->next = s结果：p -> s -> q
先接后断，避免丢链。
2.4 删除第 i 个结点
cbool ListDelete(LinkList L, int i, ElemType *e){ if (i < 1) return false; LNode *p = L; int j = 0; while (p->next != NULL && j < i - 1) { p = p->next; j++; } if (p->next == NULL) return false; LNode *q = p->next; *e = q->data; p->next = q->next; free(q); return true;}
删除逻辑
textp -> q -> r修改：p -> r最后 free(q)
2.5 头插法建立链表
cLinkList List_HeadInsert(void){ LinkList L = (LNode *)malloc(sizeof(LNode)); L->next = NULL; ElemType x; while (scanf("%d", &x) == 1 && x != -1) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; } return L;}
特点
输入：
text1 2 3 4
链表结果：
text4 -> 3 -> 2 -> 1
因此：
头插法 = 输入顺序的逆序。
2.6 尾插法建立链表
cLinkList List_TailInsert(void){ LinkList L = (LNode *)malloc(sizeof(LNode)); L->next = NULL; LNode *tail = L; ElemType x; while (scanf("%d", &x) == 1 && x != -1) { LNode *s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = NULL; tail->next = s; tail = s; } return L;}
尾插法保持输入顺序。
2.7 单链表逆置：408 高频
cvoid Reverse(LinkList L){ LNode *p = L->next; LNode *r = NULL; L->next = NULL; while (p != NULL) { r = p->next; // ① 暂存后继 p->next = L->next; // ② 当前结点指向已逆置部分 L->next = p; // ③ 插到头结点后 p = r; // ④ 处理下一个 }}
可以把它理解成：
text原：1 -> 2 -> 3 -> NULL不断取出 p 的结点，插到头结点后面：2 -> 13 -> 2 -> 1
逆置核心四步：存后继 → 改指针 → 接头 → 后移。
2.8 单链表复杂度
| 操作 | 复杂度 |
|---|---|
| 按位查找 | O(n) |
| 按值查找 | O(n) |
| 已知前驱后插入 | O(1) |
| 已知前驱后删除 | O(1) |
| 从头遍历 | O(n) |
| 逆置 | O(n) |
三、栈（Stack）
3.1 基本原则
LIFO = Last In, First Out = 后进先出
最常见场景：
- 函数调用栈
- 括号匹配
- 表达式求值
- 递归
- DFS 的非递归实现
3.2 顺序栈结构
c#define MaxSize 50typedef struct { int data[MaxSize]; int top;} SqStack;
推荐约定：
texttop = -1 表示空栈
3.3 初始化
cvoid InitStack(SqStack *S){ S->top = -1;}
3.4 入栈
cbool Push(SqStack *S, int x){ if (S->top == MaxSize - 1) return false; // 栈满 S->data[++S->top] = x; return true;}
关键
c++S->top
先让 top 指向新位置，再放元素。
3.5 出栈
cbool Pop(SqStack *S, int *x){ if (S->top == -1) return false; // 栈空 *x = S->data[S->top--]; return true;}
3.6 读栈顶
cbool GetTop(SqStack S, int *x){ if (S.top == -1) return false; *x = S.data[S.top]; return true;}
3.7 链栈
通常把链表头部作为栈顶，这样入栈、出栈都是 O(1)。
ctypedef struct StackNode { int data; struct StackNode *next;} StackNode;
入栈：
cs->next = top;top = s;
出栈：
cp = top;top = top->next;free(p);
3.8 栈的核心逻辑
考试看到“后进先出”，优先联想到：
textpush：压入栈顶pop ：弹出栈顶
千万不要把栈和队列混淆：
text栈： LIFO队列： FIFO
四、队列（Queue）
4.1 基本原则
FIFO = First In, First Out = 先进先出
典型应用：
- 层序遍历
- BFS
- 打印任务
- 缓冲区
- 操作系统中的等待队列
4.2 顺序队列为什么容易“假溢出”？
若简单地让：
cfront++;rear++;
队尾走到数组末尾，即使前面已经有空位，也无法继续入队。
这就是假溢出。
解决方法：循环队列。
五、循环队列
5.1 推荐结构：增加 size
c#define MaxSize 50typedef struct { int data[MaxSize]; int front; int rear; int size;} SqQueue;
初始化：
cvoid InitQueue(SqQueue *Q){ Q->front = 0; Q->rear = 0; Q->size = 0;}
其中：
front：队头元素所在位置rear：下一次入队的位置size：当前元素个数
因此：
text队空：size == 0队满：size == MaxSize
5.2 入队
cbool EnQueue(SqQueue *Q, int x){ if (Q->size == MaxSize) return false; Q->data[Q->rear] = x; Q->rear = (Q->rear + 1) % MaxSize; Q->size++; return true;}
5.3 出队
cbool DeQueue(SqQueue *Q, int *x){ if (Q->size == 0) return false; *x = Q->data[Q->front]; Q->front = (Q->front + 1) % MaxSize; Q->size--; return true;}
5.4 核心公式
循环队列最重要的就是：
cindex = (index + 1) % MaxSize;
它的作用是：
text0 → 1 → 2 → ... → MaxSize-1 → 0 → 1 → ...
看到“循环”就想 % MaxSize。
5.5 不使用 size 的另一种经典方案
牺牲一个数组单元：
text队空：front == rear队满：(rear + 1) % MaxSize == front
这套判定一定要和你的初始化、入队、出队代码配套。
408 做题最怕“判空判满条件写错”。
5.6 链式队列
ctypedef struct QNode { int data; struct QNode *next;} QNode;typedef struct { QNode *front; QNode *rear;} LinkQueue;
若维护头、尾指针：
- 入队：在尾部插入，
O(1) - 出队：头部删除，
O(1)
六、二叉树
6.1 结点结构
ctypedef struct BiTNode { char data; struct BiTNode *lchild; struct BiTNode *rchild;} BiTNode, *BiTree;
二叉树最大的特点：
递归定义与递归代码天然匹配。
七、四种遍历
7.1 先序遍历
根 → 左 → 右
cvoid PreOrder(BiTree T){ if (T == NULL) return; printf("%c ", T->data); PreOrder(T->lchild); PreOrder(T->rchild);}
口诀：
先看根，再左，再右。
7.2 中序遍历
左 → 根 → 右
cvoid InOrder(BiTree T){ if (T == NULL) return; InOrder(T->lchild); printf("%c ", T->data); InOrder(T->rchild);}
重要性质：
二叉搜索树（BST）的中序遍历得到有序序列。
7.3 后序遍历
左 → 右 → 根
cvoid PostOrder(BiTree T){ if (T == NULL) return; PostOrder(T->lchild); PostOrder(T->rchild); printf("%c ", T->data);}
口诀：
左右处理完，最后处理根。
7.4 层序遍历
利用队列：
cvoid LevelOrder(BiTree T){ if (T == NULL) return; BiTree Q[100]; int front = 0, rear = 0; Q[rear++] = T; while (front < rear) { BiTree p = Q[front++]; printf("%c ", p->data); if (p->lchild != NULL) Q[rear++] = p->lchild; if (p->rchild != NULL) Q[rear++] = p->rchild; }}
逻辑一定要会：
text根入队↓出一个结点↓访问它↓左孩子入队↓右孩子入队↓继续出队
所以：
层序遍历 = 二叉树 + 队列。
八、二叉树高频递归代码
8.1 求树高
cint TreeDepth(BiTree T){ if (T == NULL) return 0; int left = TreeDepth(T->lchild); int right = TreeDepth(T->rchild); return (left > right ? left : right) + 1;}
核心递推：
text空树：0非空：max(左子树高度, 右子树高度) + 1
8.2 求结点总数
cint CountNode(BiTree T){ if (T == NULL) return 0; return CountNode(T->lchild) + CountNode(T->rchild) + 1;}
8.3 求叶结点数量
cint CountLeaf(BiTree T){ if (T == NULL) return 0; if (T->lchild == NULL && T->rchild == NULL) return 1; return CountLeaf(T->lchild) + CountLeaf(T->rchild);}
判断叶结点的关键词：
cT->lchild == NULL && T->rchild == NULL
8.4 求双分支结点数量
cint CountDoubleChild(BiTree T){ if (T == NULL) return 0; int cnt = 0; if (T->lchild != NULL && T->rchild != NULL) cnt = 1; return cnt + CountDoubleChild(T->lchild) + CountDoubleChild(T->rchild);}
九、二叉树遍历的“递归三板斧”
考试遇到递归遍历，可以先写：
cvoid XXX(BiTree T){ if (T == NULL) return; // ① 根位置 XXX(T->lchild); // ② 左右子树 XXX(T->rchild); // ③ 根位置}
把 printf 放在哪一行，就决定遍历类型：
textprintf 在递归左子树前 → 先序printf 在左右子树之间 → 中序printf 在递归右子树后 → 后序
这是非常高频的识别点。
十、二叉树与栈 / 队列的联系
| 操作 | 常用辅助结构 |
|---|---|
| 先序非递归遍历 | 栈 |
| 中序非递归遍历 | 栈 |
| 后序非递归遍历 | 栈 |
| 层序遍历 | 队列 |
| DFS | 栈 / 递归 |
| BFS | 队列 |
一句话：
深度优先想栈，广度优先想队列。
十一、408 高频易错点总表
顺序表
text插入：从后往前删除：从前往后
单链表
text插入：先保存后继，再修改链接删除：先改前驱链接，再 free 被删结点
栈
textLIFO栈顶操作
队列
textFIFO循环队列注意 % MaxSize
二叉树
text先序：根左右中序：左根右后序：左右根层序：用队列
十二、复杂度一页速记
| 数据结构 | 随机访问 | 查找 | 插入 | 删除 |
|---|---|---|---|---|
| 顺序表 | O(1) | O(n) | O(n) | O(n) |
| 单链表 | O(n) | O(n) | 已知前驱 O(1) | 已知前驱 O(1) |
| 顺序栈 | O(1)（栈顶） | — | O(1) | O(1) |
| 循环队列 | — | — | O(1) | O(1) |
二叉树遍历：
text时间复杂度：O(n)辅助空间：递归遍历通常为 O(h)层序遍历最坏可达 O(n)
其中 h 为树高。
十三、考场速记版
text【顺序表】连续存储 → 下标访问 O(1)插入：后移，从后往前删除：前移，从前往后【单链表】离散存储 → 按位找必须从头走插入：s->next = p->next; p->next = s;删除：q = p->next; p->next = q->next; free(q);逆置：存后继 → 改指针 → 接头 → 后移【栈】LIFOPush 入栈顶Pop 出栈顶【队列】FIFO循环队列：index = (index + 1) % MaxSizesize 方案：空：size == 0满：size == MaxSize【二叉树】先序：根 左 右中序：左 根 右后序：左 右 根层序：队列【二叉树递归】空树是递归终止条件“根处理的位置”决定先/中/后序
十四、建议的复习顺序
第一轮： 先把所有结构的“定义 + 指针关系 + 操作顺序”背熟。
第二轮： 不看答案默写 插入 / 删除 / Push / Pop / EnQueue / DeQueue / 四种遍历。
第三轮： 开始做 408 真题，把代码和选择题、算法题结合起来。
最值得做到“肌肉记忆”的代码：
ListInsert、ListDelete、Reverse、Push、Pop、EnQueue、DeQueue、PreOrder、InOrder、PostOrder、LevelOrder。
