数据结构复习（期末考试）

教材：严蔚敏《数据结构（C 语言版）》
基于老师划定的考试范围整理

一、绪论（基础概念）

1.1 数据结构三要素

要素	说明	例子
逻辑结构	数据元素之间的逻辑关系	线性（栈/队列）、树形（一对多）、图状（多对多）、集合
存储结构	数据在计算机中的存放方式	顺序存储、链式存储、索引存储、散列存储
数据运算	对数据进行的操作	增、删、改、查、排序

1.2 算法五大特性

口诀：有确定可行出入

特性	含义
有穷性	算法在有限步后终止
确定性	每条指令有确切含义，无二义性
可行性	每条操作都是基本可执行的
输入	有 0 个或多个输入
输出	有 1 个或多个输出

1.3 时间复杂度计算

常见的数量级（由小到大）：

[
O(1) < O(\log_2 n) < O(n) < O(n\log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
]

代码形式	复杂度
单循环 `for(i=0;i<n;i++)`	(O(n))
双层嵌套 `for(i=0;i<n;i++) for(j=0;j<n;j++)`	(O(n^2))
循环每次乘 2 `while(x<n) x*=2`	(O(\log_2 n))
递归：每个问题分为两半 `T(n)=2T(n/2)+O(1)`	(O(n))
冒泡/选择/插入排序	(O(n^2))

简单计算法： 找最内层语句的执行次数，只保留最高阶，系数全扔掉。

例题：

① for(i=1; i<=n; i*=2) sum++;          → O(log₂n)

② for(i=0; i<n; i++)                    → O(n²)
     for(j=0; j<n; j++) sum++;

③ for(i=0; i<n; i++) sum++;            → O(n)（并列循环，取最大）
   for(j=0; j<n; j*=2) sum++;

二、栈与队列

2.1 栈（Stack）—— LIFO 后进先出

定义： 限定仅在栈顶进行插入和删除操作的线性表。

形象理解： 像一摞盘子——后来的放上面，先被拿走。

入栈（Push）→    │  │  ← 出栈（Pop）
                  │e3│ ← 栈顶（top），后进
                  │e2│
                  │e1│ ← 栈底（bottom），先进
                  └──┘

核心操作：

操作	含义	判空/判满
Push	元素入栈，top++	判满：`top == MaxSize-1`
Pop	栈顶元素出栈，top–	判空：`top == -1`
GetTop	读取栈顶但不删除	—

应用场景： 括号匹配、表达式求值、函数递归调用、进制转换、迷宫求解。

进制转换举例： 十进制转二进制，不断除 2 取余，余数依次入栈，最后依次出栈即为结果。

2.2 队列（Queue）—— FIFO 先进先出

定义： 只允许在一端插入（队尾）、另一端删除（队头）的线性表。

形象理解： 像排队——先来的先服务。

1 2	出队 ← │e1│e2│e3│e4│ ← 入队 ↑队头 ↑队尾

循环队列（严书顺序存储实现）：

严书中用 front 指向队头元素，rear 指向队尾元素的下一个位置。

操作	严书公式
入队（EnQueue）	`Q.rear = (Q.rear + 1) % MAXQSIZE`
出队（DeQueue）	`Q.front = (Q.front + 1) % MAXQSIZE`
判空	`Q.front == Q.rear`
判满	`(Q.rear + 1) % MAXQSIZE == Q.front`
求长度	`(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE`

⚠️ 严书循环队列牺牲一个存储单元来区分空满。因此：最大存储元素数 = MAXQSIZE − 1。

应用场景： 打印队列、BFS（广度优先搜索）、CPU 任务调度、消息缓冲。

2.3 栈与队列的简答题答法

“请解释栈与队列”的标准答案结构：

对比维度	栈（Stack）	队列（Queue）
逻辑结构	线性表，一端操作	线性表，两端操作
存取原则	LIFO（后进先出）	FIFO（先进先出）
操作端	仅栈顶	队头删除，队尾插入
类比	一摞盘子	排队等候
存储实现	顺序栈 / 链栈	顺序队列 / 链队列（循环队列最常用）
应用	括号匹配、递归、进制转换	BFS、打印队列、CPU 调度

2.4 栈应用实例

例 1：括号匹配检验

问题： 判断表达式 {[()]} 中的括号是否配对正确。

思路： 遇左括号入栈，遇右括号时与栈顶匹配则出栈，否则非法。

🍉 图解 { [ ( ) ] } 的检验过程：

读入 { → 入栈    读入 [ → 入栈    读入 ( → 入栈    读入 ) → 遇右括号
      │ │              │(│             │{│            栈顶是 ( = 配对
      │[│              │[│             │[│            弹出 ( ✓
      │{│              │{│             │{│
      └─┘              └─┘             └─┘             └─┘

读入 ] → 遇右括号    读入 } → 遇右括号    读完、栈空 ✅
栈顶是 [ = 配对      栈顶是 { = 配对      全部匹配！
弹出 [ ✓              弹出 { ✓

代码：

int BracketMatch(char *str) {
    char stack[100], top = -1;
    for (int i = 0; str[i] != '\0'; i++) {
        char ch = str[i];
        if (ch == '(' || ch == '[' || ch == '{')
            stack[++top] = ch;     // 左括号入栈
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (top == -1) return 0;  // 栈空，多右括号
            char left = stack[top--]; // 出栈
            if ((ch == ')' && left != '(') ||
                (ch == ']' && left != '[') ||
                (ch == '}' && left != '{'))
                return 0;             // 不匹配
        }
    }
    return top == -1;  // 栈空 → 全部匹配
}

例 2：进制转换（十进制 → 二进制）

问题： 将十进制数 13 转为二进制。

思路： 不断除 2 取余数，余数依次入栈，最后依次出栈即为结果——利用栈的 LIFO 特性反转输出顺序。

🍉 图解 13 转二进制：

计算阶段：                出栈阶段：
13 ÷ 2 = 6 ··· 余 1 → 入栈     │1│    栈顶 1 → 弹出来写第一位
 6 ÷ 2 = 3 ··· 余 0 → 入栈     │0│    栈顶 0 → 弹出来写第二位
 3 ÷ 2 = 1 ··· 余 1 → 入栈     │1│    栈顶 1 → 弹出来写第三位
 1 ÷ 2 = 0 ··· 余 1 → 入栈     │1│    栈顶 1 → 弹出来写第四位
                              └─┘

结果：1101（即 13₁₀ = 1101₂）

代码：

void DecToBin(int n) {
    int stack[32], top = -1;
    while (n > 0) {
        stack[++top] = n % 2;   // 余数入栈
        n = n / 2;
    }
    while (top >= 0)
        printf("%d", stack[top--]);  // 依次出栈输出
}
// 输入 13 → 输出 1101

2.5 队列应用实例

例 3：杨辉三角

问题： 打印杨辉三角的前 n 行。

第 i 行第 j 个数 = 上一行第 j-1 个数 + 上一行第 j 个数。

思路： 用队列逐行生成。队头出两个数，相加后入队，形成下一行。

🍉 图解 n=5 的生成过程：

初始队列: [1, 1, 0]           ← 0 是行分隔标记

第1行: 出队→1，打印"1"，队列变 [1, 0]，1+1=2入队 → [1, 0, 2]
       出队→1，打印"1"，队列变 [0, 2]，1+0=1入队 → [0, 2, 1]
       出队→0，打印"\n"，队列变 [2, 1]，2+1=3入队，0再入队 → [2, 1, 3, 0]

第2行: 出队→2，打印"2"，队列变 [1, 3, 0]，2+1=3入队 → [1, 3, 0, 3]
       出队→1，打印"1"，队列变 [3, 0, 3]，1+3=4入队 → [3, 0, 3, 4]
       出队→3，打印"3"，队列变 [0, 3, 4]，3+0=3入队 → [0, 3, 4, 3]
       出队→0，打印"\n"，...

... 依此类推

输出：
1
2 1 3
3 1 3 4 3
4 1 4 6 4 5
...

📌 思路掌握即可，考场上通常不会要求完整代码。重点是理解出两个、加一个、入一个的节奏。

例 4：报数出列（约瑟夫问题简化版）

问题： n 个人围坐一圈，从第 1 个人开始报数 1,2,3，报到 3 的人出列，下一个人重新从 1 报起。输出出列顺序。

思路（队列法）： 所有人入队 → 出队一个，报数；报到 3 → 出列（不再入队），否则重新入队末尾。

🍉 图解 n=6 的过程：

初始队列: [1, 2, 3, 4, 5, 6]

第1轮: 1→计数1，回队尾    队列: [2, 3, 4, 5, 6, 1]
       2→计数2，回队尾    队列: [3, 4, 5, 6, 1, 2]
       3→计数3，出列 ✖    队列: [4, 5, 6, 1, 2]    → 出列: 3

第2轮: 4→计数1，回队尾    队列: [5, 6, 1, 2, 4]
       5→计数2，回队尾    队列: [6, 1, 2, 4, 5]
       6→计数3，出列 ✖    队列: [1, 2, 4, 5]        → 出列: 6

... 依此类推

最终出列顺序: 3, 6, 2, 5, 1, 4

代码：

void CountOff(int n, int m) {
    int Q[100], front = 0, rear = 0;
    for (int i = 1; i <= n; i++)
        Q[rear++] = i;             // 所有人入队
    int count = 0;
    while (front < rear) {
        int x = Q[front++];        // 队头出队
        count++;
        if (count == m) {
            printf("%d ", x);      // 报到 m → 出列
            count = 0;
        } else {
            Q[rear++] = x;         // 没到 m → 回到队尾
        }
    }
}
// CountOff(6, 3) → 输出: 3 6 2 5 1 4

栈与队列应用速记

结构	应用	核心技巧
栈	括号匹配	左入栈，右弹出比对
栈	进制转换	除 N 取余入栈，逆序出栈
队列	杨辉三角	出队两个相加，和入队
队列	报数出列	报中→出，没报中→回队尾

例题 1： 入栈序列 1,2,3,4，哪些出栈序列合法？

✅ 合法：3,2,4,1（入1,2,3→出3→出2→入4→出4→出1）
✅ 合法：1,2,3,4（每次入一个即出）
❌ 非法：3,1,2,4（3 出时 1,2 已在栈里，1 在 2 下面，不可能比 2 先出）

🎯 判断法则： 出栈序列中，若元素 i 在 j 之前出栈且 i < j，则 i 出栈时 j 必在栈中，此时 j 下面可能还有其他元素。大数先出时，小数必须按入栈顺序反过来出。

例题 2： 入队序列 1,2,3，出队序列？

→ 必定是 1,2,3（队列 FIFO，不改变顺序）

三、数组与顺序查找

3.1 顺序查找（Sequential Search）

定义： 从数组的一端开始，逐个比较，找到目标元素即返回位置，遍历完仍未找到则返回 -1。

代码：

int SeqSearch(int a[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (a[i] == key) return i;   // 找到，返回下标
    }
    return -1;                        // 未找到
}

带”哨兵”的优化版本：

int SeqSearch(int a[], int n, int key) {
    a[0] = key;    // 哨兵放在 a[0]（此时从后往前找）
    int i = n;
    while (a[i] != key) i--;
    return i;      // i=0 表示未找到
}

哨兵法省去了每次循环判断 i<n 的比较操作。

时间复杂度：

情况	比较次数	复杂度
最好（第 1 个命中）	1	(O(1))
最坏（最后一个 / 不在）	n	(O(n))
平均（等概率）	((n+1)/2)	(O(n))

适用场景： 数组无序或数据量较小时。如果有序，用二分查找更好。

3.1.2 数组遍历输出

最基础的算法——从头到尾访问每个元素。

🍉 例子： 输出数组 [13, 21, 37, 56, 64] 的所有元素。

1	a[0] = 13 → a[1] = 21 → a[2] = 37 → a[3] = 56 → a[4] = 64

代码：

void Traverse(int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}
// 输出: 13 21 37 56 64

时间复杂度： (O(n))——每个元素访问恰好一次。

变形： 条件遍历（只输出偶数、只输出正数等）——在循环内加 if 判断即可。

3.1.3 数组逆置

将数组前后对调，首尾交换。

核心思路：

交换前: [13, 21, 37, 56, 64]
              ↕ 对调  ↕
              ↓          ↓
交换后: [64, 56, 37, 21, 13]

a[0] ↔ a[n-1]
a[1] ↔ a[n-2]
a[2] ↔ a[n-3]
…走到数组中间停止

🍉 图解过程：

初始: [13, 21, 37, 56, 64]
       i=0              j=4
       ↕ swap ↕

第1步: [64, 21, 37, 56, 13]
           i=1      j=3
           ↕ swap ↕

第2步: [64, 56, 37, 21, 13]
               i=j=2
               停止（中间元素 37 不需要动）

代码：

void Reverse(int a[], int n) {
    int i = 0, j = n - 1, temp;
    while (i < j) {
        temp = a[i];      // 交换 a[i] 和 a[j]
        a[i] = a[j];
        a[j] = temp;
        i++;
        j--;
    }
}

时间复杂度： (O(n))——交换 (n/2) 次，去掉系数 = (O(n))。

空间复杂度： (O(1))——只用一个临时变量 temp。

3.1.4 求最大/最小值

int FindMax(int a[], int n) {
    int max = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] > max) max = a[i];
    return max;
}
// a = [13, 21, 37, 56, 64] → max = 64

时间复杂度 (O(n))，一次遍历。

3.1.5 数组求和

int Sum(int a[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) sum += a[i];
    return sum;
}
// a = [13, 21, 37, 56, 64] → sum = 191

时间复杂度 (O(n))。

数组基础算法对比

算法	循环次数	时间	关键技巧
遍历输出	n	(O(n))	依次访问
求最大/最小	n	(O(n))	保持当前最优
求和	n	(O(n))	累加
逆置	n/2	(O(n))	双指针向中间夹
顺序查找	≤n	(O(n))	依次对比
二分查找	≤log₂n	(O(\log_2 n))	必须有序，折半跳

3.1.1 二分查找（折半查找）—— 有序表的查找

二分查找虽然不在本次考试编程题范围内，但在严蔚敏教材中是查找章节的核心算法，可能在小题中考查。

前提条件： 查找表必须是有序的顺序表（数组）。

核心思想： 每次取中间位置 mid 与 key 比较——相等→找到；key 更小→去左半继续找；key 更大→去右半继续找。

🍉 例子：在有序数组 [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92] 中查找 key = 21

初始: low=1, high=11, mid = (1+11)/2 = 6
      元素: [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]
                             ↑ mid=56
      56 > 21 → key 在左半 → high = mid-1 = 5

第1轮: low=1, high=5, mid = (1+5)/2 = 3
      元素: [5, 13, 19, 21, 37, ...]
                  ↑ mid=19
      19 < 21 → key 在右半 → low = mid+1 = 4

第2轮: low=4, high=5, mid = (4+5)/2 = 4
      元素: [..., 21, 37, ...]
                  ↑ mid=21
      21 == 21 → ✅ 找到！返回位置 4

查找 key = 66（不存在）的过程：

初始: low=1, high=11, mid=6 → 56 < 66 → low=7

第1轮: low=7, high=11, mid=9 → 80 > 66 → high=8

第2轮: low=7, high=8, mid=7 → 64 < 66 → low=8

第3轮: low=8, high=8, mid=8 → 75 > 66 → high=7

第4轮: low=8 > high=7 → ❌ 查找失败，low 指向插入位置

严书代码：

int Search_Bin(SSTable ST, KeyType key) {
    int low = 1, high = ST.length;    // 严书从 1 开始
    while (low <= high) {
        int mid = (low + high) / 2;
        if (key == ST.elem[mid].key) return mid;      // 找到
        else if (key < ST.elem[mid].key) high = mid - 1;
        else low = mid + 1;
    }
    return 0;  // 未找到
}

二分查找判定树： 上述 11 个元素的查找过程可用判定树表示（mid 即根，左子=left..mid-1，右子=mid+1..right）。

时间复杂度： (O(\log_2 n))（每次比较后搜索范围减半）

3.2 串的简单操作

严蔚敏教材中，串为仅由字符组成的线性表，C 语言中常用 char[] 实现。

操作	严书函数	含义	例子
求串长	`StrLength(S)`	返回字符串长度	`"hello"` → 5
串连接	`Concat(T, S1, S2)`	S1+S2→T	`Concat(T,"ab","cd")` → T=`"abcd"`
求子串	`SubString(Sub, S, pos, len)`	从 S 第 pos 位起取 len 长→Sub	`SubString(Sub,"abcde",2,3)` → Sub=`"bcd"`
串比较	`StrCompare(S, T)`	逐字符比 ASCII，返回正/负/0	`StrCompare("abc","abd")` < 0
模式匹配	`Index(S, T, pos)`	T 在 S 中第 pos 位后首次出现的位置	`Index("ababc","ab",1)` → 1
判空	`StrEmpty(S)`	S 是否为空串	`""` → TRUE

数据对象： (D = {a_i \mid a_i \in \text{字符集} })
数据关系： (R = { \langle a_{i-1}, a_i \rangle })（线性关系）

空串 vs 空格串： 空串 ""（长度为 0），空格串 " "（长度 ≥ 1，元素为空格字符）。

📌 串的复习重点：基本操作名称与参数顺序（严书风格）、空串与空格串区分、KMP 中 next 数组。

3.3 广义表的表头与表尾

严蔚敏教材第 5 章”数组和广义表”核心考点。广义表 (LS = (a_1, a_2, \dots, a_n))，其中 (a_i) 可以是原子或子表。

定义

概念	严书定义	记忆
表头 Head	广义表 LS 的第一个元素 (a_1)	“第一个，可以是原子或子表”
表尾 Tail	去掉第一个元素后，其余元素组成的表	“剩下的，一定是个表（带括号）”

取表头表尾口诀

🔑 Head 去外层括号取第一个，Tail 去外层括号再去第一个，剩下的括回来。

核心规则

Head(LS) = (a_1)（第一个元素本身，原子不带括号，子表保留原有括号）
Tail(LS) = ((a_2, \dots, a_n))（一定是广义表，带括号）
空表 () 没有表头和表尾

操作示例

广义表 LS	Head(LS)	Tail(LS)	说明
`(a, (b, c))`	`a`	`((b, c))`	表头是原子 a；表尾是 (b,c) 再带括号
`((a, b), c, d)`	`(a, b)`	`(c, d)`	表头是子表 (a,b)；表尾 (c,d) 带括号
`(a)`	`a`	`()`	只有一个元素，表尾为空表
`()`	无	无	空表既无表头也无表尾

复合操作的求法

例题： 已知 (LS = ((a, b), (c, d)))，求 Head(Tail(LS))。

LS = ((a, b), (c, d))

① Tail(LS)      = Tail(((a, b), (c, d)))
                 = ((c, d))           // 去掉第一个 (a,b)，剩下的括起来

② Head(Tail(LS)) = Head(((c, d)))
                 = (c, d)             // 取第一个元素

严书广义表结构

严蔚敏教材中广义表的存储通常采用头尾链表存储结构（tag=0→原子，tag=1→子表，hp 指向表头，tp 指向表尾）。

四、树与二叉树

4.1 树的定义

树（Tree） 是 n（n ≥ 0）个结点的有限集合。

n = 0 时为空树
非空时：有且仅有一个根结点，其余结点可分为 m 个互不相交的有限集合，每个集合本身又是一棵树（称为根的子树）

核心特点： 一对多关系、层次结构、无环、除根外每个结点有唯一前驱。

4.2 二叉树的核心性质

编号	性质	公式
①	第 i 层最多结点数	(2^{i-1})
②	深度为 k 的二叉树最多结点数	(2^k - 1)
③	叶子与度为 2 的结点	(n_0 = n_2 + 1)
④	n 个结点的完全二叉树深度	(\lfloor \log_2 n \rfloor + 1)
⑤	完全二叉树结点 i 的左孩子	(2i)
⑥	完全二叉树结点 i 的右孩子	(2i + 1)
⑦	完全二叉树结点 i 的双亲	(\lfloor i/2 \rfloor)

🔥 必考性质：(n_0 = n_2 + 1) —— 叶子数 = 度为 2 的结点数 + 1。

4.3 二叉树的遍历

遍历	顺序	口诀
先序（Preorder）	根 → 左 → 右	DLR
中序（Inorder）	左 → 根 → 右	LDR
后序（Postorder）	左 → 右 → 根	LRD
层序	从上到下、从左到右	队列

🔥 必考题型：给出两种遍历序列，画出二叉树。

例：先序 ABCDEF，中序 CBAEDF，画出二叉树

步骤：

先序第一个是根 → 根 = A
在中序中找到 A → 左边 {C,B} 是左子树，右边 {E,D,F} 是右子树
左子树先序为 BC，中序为 CB → 根=B，C 在 B 左边 → C 是 B 的左孩子
右子树先序为 DEF，中序为 EDF → 根=D，E 在 D 左边、F 在 D 右边 → E 是 D 左孩子，F 是 D 右孩子

结果：
        A
       / \
      B   D
     /   / \
    C   E   F

🎯 唯一确定规则： 先序+中序 → ✅ 唯一；后序+中序 → ✅ 唯一；先序+后序 → ❌ 不唯一（无法区分左右）

4.4 求二叉树的结点数和叶子数

结点数（递归）：

1	总结点数 = 1（根结点） + 左子树结点数 + 右子树结点数

叶子结点数（递归）：

1
2
3

若为空树 → 0
若为叶子（左右为空） → 1
否则 → 左子树的叶子数 + 右子树的叶子数

🍉 简单例子：

    A
   / \
  B   C      叶子：D, E, C → 3 个
 / \
D   E        结点：5 个（A,B,C,D,E）

公式法： 若题目只给结点数 n，可利用 (n = n_0 + n_1 + n_2) 和 (n_0 = n_2 + 1) 联立求解。

4.5 二叉树的存储结构（严书）

存储方式	结构	适用
顺序存储	用数组，根在 1 号，左孩 2i，右孩 2i+1	完全二叉树
二叉链表（最常用）	`lchild	data

4.6 二叉树简答题标准结构

“请解释树的概念” → ①树的递归定义 ②基本术语（根、孩子、双亲、兄弟、叶子、深度、度）③树的存储方式（双亲表示法、孩子链表表示法、孩子兄弟表示法）④树与二叉树的转换（左孩右兄）⑤常见应用（文件系统、组织架构）

五、图

5.1 图的基本概念

术语	定义
图（Graph）	由顶点集 V 和边集 E 组成：(G=(V,E))
有向图	边有方向，`<v,w>` 表示从 v 到 w 的弧
无向图	边无方向，`(v,w)` 与 `(w,v)` 相同
完全图	无向完全图有 (n(n-1)/2) 条边；有向完全图有 (n(n-1)) 条边
度（Degree）	与该顶点关联的边数；有向图分入度和出度
连通图	任意两点间均有路径（无向图）；有向图称强连通图
连通分量	极大连通子图
生成树	包含全部 n 个顶点的极小连通子图（n-1 条边）
网	边/弧带有权值的图

简答题标准结构：

1. 定义：G = (V, E)，V 是顶点集合，E 是边集合
2. 分类：有向图 vs 无向图；带权图（网）vs 无权图
3. 基本术语：度、路径、连通、生成树
4. 存储方式：邻接矩阵（O(n²)）、邻接表（O(n+e)）
5. 遍历算法：DFS（深度优先，用栈）、BFS（广度优先，用队列）
6. 应用场景：最短路径、拓扑排序、最小生成树、社交网络

5.2 图的存储

存储方式	邻接矩阵	邻接表
空间	(O(n^2))	(O(n+e))
适用	稠密图	稀疏图
判边	(O(1))	(O(e/n))
找邻接点	需遍历整行	直接取链表

5.3 图的遍历

	DFS（深度优先）	BFS（广度优先）
辅助结构	栈（递归隐式使用）	队列
策略	一条路走到黑再回溯	一层层展开
类比	走迷宫	涟漪扩散

六、编程题专项

6.1 应用题：栈与队列综合

常见题型： 利用栈实现队列 / 利用队列实现栈 / 判断出栈序列合法性。

【模板】判断出栈序列是否合法：

// 给定入栈序列 1..n，判断序列 seq[] 是否为合法出栈序列
int isLegal(int seq[], int n) {
    int stack[n], top = -1;
    int pushNum = 1;       // 下一个要入栈的数
    for (int i = 0; i < n; i++) {
        // 若栈顶不是目标，持续入栈
        while (top == -1 || stack[top] != seq[i]) {
            if (pushNum > n) return 0;  // 全部入完仍不匹配
            stack[++top] = pushNum++;
        }
        top--;  // 匹配成功，出栈
    }
    return 1;
}

【模板】两个栈模拟队列：

核心思路： 栈 A 管入队（Push），栈 B 管出队（Pop）。栈 B 空时，把 A 全部倒入 B，顺序自然反转。

🍉 图解操作过程：

操作序列：EnQueue(1), EnQueue(2), DeQueue(), EnQueue(3), DeQueue(), DeQueue()

① EnQueue(1)       ② EnQueue(2)       ③ DeQueue()
   栈A:│1│            栈A:│2│            B空→A全部倒入B
       └─┘                │1│                └─┘
                          └─┘           栈A:│ │
                                        栈B:│2│
                                            │1│    弹出B栈顶→输出1
                                            └─┘

④ EnQueue(3)       ⑤ DeQueue()        ⑥ DeQueue()
   栈A:│3│            B非空→直接弹B          B空→A全部倒入B
       └─┘           栈A:│3│               栈A:│ │
                         └─┘               栈B:│3│    弹出→输出3 ※
   栈B:│2│           栈B:│2│    弹出→输出2       └─┘
       └─┘               └─┘

※ 这里说明：3 在 2 后面才入队，但弹出顺序 1→2→3，完美遵守 FIFO！

完整代码：

#include <stdio.h>
#define MAX 100

typedef struct {
    int data[MAX];
    int top;
} Stack;

typedef struct {
    Stack A;   // 入队栈
    Stack B;   // 出队栈
} Queue;

// 栈操作
void InitStack(Stack *s) { s->top = -1; }
int StackEmpty(Stack s) { return s.top == -1; }
void Push(Stack *s, int x) { s->data[++(s->top)] = x; }
int Pop(Stack *s) { return s->data[(s->top)--]; }

// 队列操作
void InitQueue(Queue *q) {
    InitStack(&q->A);
    InitStack(&q->B);
}

void EnQueue(Queue *q, int x) {
    Push(&q->A, x);           // 入队 → 直接压入栈 A
}

int DeQueue(Queue *q) {
    if (StackEmpty(q->B)) {   // 栈 B 为空 → 把 A 全部倒入 B
        while (!StackEmpty(q->A)) {
            int x = Pop(&q->A);
            Push(&q->B, x);
        }
    }
    if (StackEmpty(q->B)) {   // B 仍空 → 队列为空
        printf("队列为空\n");
        return -1;
    }
    return Pop(&q->B);        // 从 B 出栈 = 出队
}

int QueueEmpty(Queue q) {
    return StackEmpty(q.A) && StackEmpty(q.B);
}

// 测试
int main() {
    Queue q;
    InitQueue(&q);
    EnQueue(&q, 1);
    EnQueue(&q, 2);
    printf("%d ", DeQueue(&q));  // 输出: 1
    EnQueue(&q, 3);
    printf("%d ", DeQueue(&q));  // 输出: 2
    printf("%d ", DeQueue(&q));  // 输出: 3
    return 0;
}

时间复杂度分析：

操作	平均	最坏
EnQueue	(O(1))	(O(1))
DeQueue	(O(1))（均摊）	(O(n))（栈 B 空时需倒入）

🎯 每个元素恰好入 A 一次、出 A 一次、入 B 一次、出 B 一次，总操作 4n 次。分摊到 n 次出队，每次均摊 O(1)。

记忆口诀： “A 管进，B 管出，B 空就倒 A 的货。”

6.2 算法题：数组顺序查找

基础实现：

int SeqSearch(int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key) return i;
    return -1;
}

哨兵优化：

int SeqSearch(int a[], int n, int key) {
    a[0] = key;        // a[0] 作为哨兵
    int i = n;         // 从尾部开始
    while (a[i] != key) i--;
    return i;          // 返回 0 表示未找到
}

🎯 哨兵法的优点：每轮循环少一次边界判断（i >= 0），提高效率。

七、考点速查表

题型	考点	复习建议
编程题 1	栈与队列应用	掌握出栈序列合法性判断、双栈模拟队列
编程题 2	数组顺序查找	背哨兵版代码，理解时间复杂度 O(n)
简答题 1	树的遍历（给遍历画树）	先序+中序 / 后序+中序 → 唯一确定二叉树
简答题 2	解释图的概念	用”定义→分类→术语→存储→遍历→应用”六段式
简答题 3	解释栈和队列	用”定义→原则→操作→存储→应用”五段式 + 对照表
简答题 4	解释树	递归定义 + 术语 + 二叉树性质 + 遍历方式
简答题 5	绪论概念	数据结构三要素 + 算法五大特性 + 逻辑/存储结构分类
小题	时间复杂度	表格速记、会分析循环嵌套
小题	二叉树结点/叶子	(n_0 = n_2 + 1)、递归求和
小题	串操作	求串长、子串、比较、连接
小题	表头/表尾	Head 取第一个（去外括号），Tail 取剩余（保留外括号）
小题	图概念	无向完全图边数 (n(n-1)/2)、连通分量、生成树
小题	输入/输出序列	栈（LIFO 约束）、队列（FIFO 不改变顺序）

📌 建议：简答题用”结构化作答”，编程题背模板代码，小题刷概念和计算。