Loading... ## 栈 ### 基础知识 #### 定义 栈 (Stack) 是**只允许在一端**进行插入或删除操作的**线性表**。 重要术语：栈顶，栈底，空栈。 **特点**：后进先出 (Last In First Out, LIFO) #### 基本操作 - 初始化 InitStack； - 销毁 DestroyStack； - 进栈 Push； - 出栈 Pop； - 读取栈顶元素 GetTop； - 判空 StackEmpty； #### 常考题型 - 进栈顺序为 `a -> b -> c -> d ->e` 时有哪些合法的出栈顺序？ n 个不同元素进栈，出栈元素不同的排列个数为 $\frac{1}{n + 1} C_{2n}^n$ 。 上述公式称为卡特兰 (Catalan) 数，可采用数学归纳法证明。 ### 顺序栈 #### 代码定义 ```c++ typedef struct { ElemType data[MAX_SIZE]; int top; // 栈顶指针 } SqStack; ``` #### 基本操作 - 初始化。`top` 设为 -1，因为 0 也是有效的位置。(top 为 0 是另一种写法) - 进栈。顺序栈有大小上限，记得判断是否溢出。 - 出栈。 - 获取栈顶元素。 - 判空。 #### 共享栈 两个栈共享同一片空间，即两个栈存在于空间头和尾，且向中间延伸。 ```c++ typdef struct { ElemType data[MAX_SIZE]; int top0; // 0 号栈的栈顶指针 int top1; // 1 号栈的栈顶指针 } ``` ### 链栈 用链式存储方式实现的栈。 带头节点和不带头节点的两种实现方式。 ### 应用 #### 中缀表达式转后缀表达式 只要左边的运算符能先计算，就优先计算左边的。因为后缀表达式可以有很多种，不利于算法实现，而优先计算左边的运算符可以统一转出的结果，方便代码实现。 ``` A + B * (C - D) - E / F // 一般转成 A B C D - * + E F / - // 而不是 A B C D - * E F / - + ``` 计算只需要从左往右扫描，遇到数则入栈，遇到运算符则将两个栈顶元素弹出，计算，并压回栈中。 > 注意先弹出的元素是中缀表达式中运算符右边的数。 **算法过程** - 遇到数字直接加入后缀表达式。 - 遇到 `(` 则直接入栈，遇到 `)` 则依次弹出栈内运算符并加入后缀表达式，直到弹出 `(` 为止。 - 遇到运算符则依次弹出栈中优先级**大于等于**当前运算符的所有运算符，并加入后缀表达式，遇到 `(` 或栈空则停止。之后再将当前运算符入栈。 - 处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。 #### 中缀表达式转前缀表达式 和后缀表达式相似，只要右边的运算符可以先计算，就先计算右边的。 ``` A + B * (C - D) - E / F // 一般转成 - + A * B - C D / E F // 而不是 + A - * B - C D / E F ``` 前缀表达式的计算和后缀表达式相反，从右往左扫描即可。 ## 队列 ### 基础知识 **队列 (Queue)** 是只允许在一端进行插入，在另一端删除的**线性表**。 - 特点：先进先出 (First In First Out, FIFO) - 队头，队尾 - 空队列 #### 基本操作 - 初始化 - 销毁 - 入队 - 出队 - 读取队头元素 - 判空 ### 顺序实现 ```c++ typedef struct { ElemType data[MAX_SIZE]; int front, rear; // 队头指针和队尾指针 } SqQueue; ``` #### 循环队列 ```c++ bool EnQueue(SqQueue &Q, ElemType x) { // return false if this queue is full. if (queue is full) return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MAX_SIZE; return true; } ``` #### 考点 - 如何初始化，入队，出队 - 判空和判满。 - 计算队列的长度。 **分析思路** - 确定 `front, rear` 指针是指向哪个位置。如 `rear` 是指向最后一个元素还是最后一个元素之后的一个位置。 - 确定判空和判满的方法。可以牺牲一个存储单元，或者利用 `size` 变量记录队列长度，或者增加 `bool tag` 来记录最近一次操作是入队还是出队。 ### 链式实现 ```c++ typedef struct LinkNode { ElemType data; struct LinkNode *next; } LinkNode; typedef struct { LinkNode *front, *rear; } LinkQueue; ``` ### 双端队列 只允许从两端插入，两端删除的线性表。 #### 考点 - 判断输出的序列是否合法。 ### 应用 - 树的层次遍历 - 图的广度优先搜索 - 操作系统的先来先服务 (First Come First Service) 策略 ## 数组 各数组元素大小相同，且物理上连续存储。 二维数组的存储有**行优先**和**列优先**两种形式，目的是把二维数组映射成一维。 ### 矩阵 描述矩阵元素时，行列通常从 1 开始，而描述数组的时候下标一般从 0 开始，需要注意。 #### 对称矩阵 对称矩阵可以只存储主对角线和下三角区，按照**行优先**原则将各元素存入一维数组中。 可以通过一个映射函数来将矩阵下标映射为一维数组的下标。比如上述压缩存储方式下，$a_{i, j}$ 对应的数组下标是 $\frac{i(i - 1)}{2} + j - 1 \ \ (i > j)$ 。 **注意点：** - 存储的是上三角还是下三角 - 行优先存储还是列优先存储 - 矩阵元素下标是从 0 开始还是从 1 开始 - 数组下标是从 0 开始还是从 1 开始 #### 三角矩阵 下三角矩阵：除了主对角线和下三角区域，其余的元素都相同。 上三角矩阵同理。 存储方式和对称矩阵相似，只需要多一个位置记录另一半区的元素。 #### 三对焦矩阵 又称带状矩阵，当 $|i - j| > 1$ 时，有 $a_{i, j} = 0 \ \ (1 \leq i, j \leq n)$ 。 ![image-20240504142222189.png][1] #### 稀疏矩阵 非零元素远远少于矩阵元素的个数的矩阵。 稀疏矩阵就不需要存储所有的元素了，只需要记录非零元素的值以及其所在的位置即可。 **十字链表法**： 其实就是用二维链表来存储。 ![image-20240504142241185.png][2] ### 考点 ![image-20240504142553153.png][3] [1]: https://blog.domineto.top/usr/uploads/2024/05/757480505.png [2]: https://blog.domineto.top/usr/uploads/2024/05/91742051.png [3]: https://blog.domineto.top/usr/uploads/2024/05/3882833749.png 最后修改：2024 年 05 月 04 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏