栈

概念

栈的数学性质

出栈排列数目（$n$ 个不同元素以某种顺序依次进栈，并可在任意时刻出栈）满足函数 $Catalan()$：$N=\frac{1}{n+1}C^n_{2n}$。

栈的基本操作

初始化、判空、进栈 push、出栈 pop、读栈顶、销毁。

顺序存储结构

顺序栈

判空、判满条件以及进栈、出栈的操作顺序（先改指针还是先存取元素），会因实际给的条件不同而变化（主要取决于初始栈顶指针的位置），因此需要具体问题具体分析。

共享栈

利用栈底位置相对不变的特性，让两个顺序栈共享一个一维数组空间：

采用共享栈的好处：更有效地利用存储空间；降低发生上溢的可能。

链式存储结构

链栈

通常采用单链表实现，并规定所有操作都是在单链表的表头进行。

不存在栈满上溢的情况。

应用

栈的常见/常考应用

括号匹配、表达式求值、调用函数（递归调用、子程序调用）、进制转换、迷宫求解。

递归

递归定义

若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。

递归模型

递归模型不能是循环定义的，其必须满足下面的两个条件：

  • 边界条件（递归出口）
  • 递归表达式（递归体）

递归精髓

将原始问题转换为属性相同但规模较小的问题。

递归优缺点

优点：代码简单，容易理解。

缺点：效率不高。原因是递归调用过程中包含很多重复的计算。

栈在函数调用中的作用

在函数调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了工作栈来进行数据存储。

函数调用（或者可以专指递归调用）次数过多容易造成栈溢出等。

⚠注意

尾递归和单向递归可以用循环/迭代消除，不一定非要使用栈（关于尾调用、尾递归）。

表达式求值

表达式表示方法

前缀（波兰式）、中缀、后缀（逆波兰式）。

例：中缀式 (a+b+c×d)/e，转化为前缀式为 /++ab×cde，转化为后缀式为 ab+cd×+e/。

与前缀式和后缀式不同的是，中缀式中的括号是必需的。

一个中缀式可能有多种前/后缀式，因为前/后缀式是由中缀式按某一种运算次序而生成的。

表达式树

表达式树的前序遍历为前缀表达式，中序遍历为中缀表达式（不带括号），后序遍历为后缀表达式。

中缀化后缀

手算：

1）按照运算符的运算顺序对所有运算单位加括号。

2）将运算符移至对应括号后面，即相当于按 “左操作数 右操作数 运算符” 重新组合。

3）去除所有括号。

机算：

1）遇数字直接输出，遇运算符入栈。

2）运算符入栈时先将前面优先级 ≥ 自己的一一出栈。

3）右括号与最近的左括号匹配，将它们之间的符号出栈（右括号不入栈）。

中缀化前缀

手算：中缀化前缀第二步改成运算符移至对应括号前面即可。

机算：TODO

后缀式运算

从左到右入栈，数字直接入，遇到运算符时将栈内 2 个操作数出栈（运算符几目就出栈几个），进行运算后将值入栈，重复操作。

前缀式运算

从左到右，将连续出现的两个操作数和在它们之前紧靠的运算符构成一个最小表达式。

中缀式运算

准备俩栈，操作数直接入栈 1，运算符入栈 2。

运算符入栈之前若发现栈顶的运算符优先级 ≥ 自己，则先将其出栈自己再入栈，并从栈 1 弹出相应数目的操作数与之运算，得到的值入栈 1。

入完栈后就开始出栈运算，再将运算结果入栈，直到栈 2 为空。

队列

概念

略

顺序存储结构

顺序队列

了解即可，容易出现 “假溢出”。

循环队列

逻辑环状的顺序队列。

🌱循环队列非空时首尾指针指向的不同情况对出入队操作、初始状态以及判空/满的影响。

设定第一个进入队列的元素存储在 0 下标处：

  1. front 指向队首元素

    出队先取元素，再移 front。

    初始 front 为 0。

  2. front 指向刚出队元素（队首元素前一个位置）

    出队先移 front，再取元素。

    初始 front 指向 MaxSize - 1。

  3. rear 指向队尾元素

    进队先移 rear，后存元素。

    初始 rear 为 MaxSize-1。

  4. rear 指向队尾元素后一个位置

    进队先存元素，后移 rear。

    初始 rear 为 0。

队空队满条件（设定第一个进入队列的元素存储在 0 下标处，且所有存储单元都用来存储）：

  1. front、rear 指向队首、队尾元素

    队空：(rear+1) % MaxSize == front

    队满：(rear+1) % MaxSize == front

    初始指针：front = 0，rear = MaxSize - 1

    队列长度：(rear - front + 1 + MaxSize) % MaxSize

  2. front 指向队首元素、rear 指向队尾元素后一个位置

    队空：rear == front

    队满：rear == front

    初始指针：front = rear = 0

    进出队操作：先存取元素，再移动指针

    队列长度：(rear - front + MaxSize) % MaxSize

  3. front 指向刚出队元素、rear 指向队尾元素

    队空：rear == front

    队满：rear == front

    初始指针：front = rear = MaxSize - 1

    进出队操作：先移动指针，再存取元素

    队列长度：(rear - front + MaxSize) % MaxSize

  4. front 指向刚出队元素、rear 指向队尾元素后一个位置

    队空：(front+1) % MaxSize == rear

    队满：(front+1) % MaxSize == front

    初始指针：front = MaxSize - 1，rear = 0

    队列长度：(rear - front - 1 + MaxSize) % MaxSize

可见，上述四种组合中队空队满的判断都是一致的，要想区分有以下三种常见手法：

  1. 牺牲一个存储单元

    以第 2 种组合为例，可以约定以 “队头指针在队尾指针的下一位置” 作为队满的标志，即队满条件变为 (rear + 1) % MaxSize = front。

  2. 增设成员变量 size，表示当前队列元素个数

  3. 增设成员变量 tag

    出队成功置 tag = 0，入队成功置 tag = 1。若因出队使得判断条件达成，则表示队空；若因入队使得判断条件达成，则表示队满。

链式存储结构

链队

队列的链式表示称为链队。

实际上是一个同时有队头指针和队尾指针的单链表，表头为队首，表尾为队尾，尾入首出。

链队 vs 链栈

链栈的头指针（链表名）即为栈顶指针，只有这一个指针。

而链队，从定义上看，由两部分组成：含两个指针的结构体 + 链表，也可以看成含头尾指针的链表，且其头尾指针存在一个结构体中。

这种差异在初始化中尤为明显。

双端队列

双端队列：指允许两端都可以进行插入和删除操作的线性表。

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列。

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列。

双端队列可能的输出序列

  1. 输出受限（一端仅能输入）

    入完再出：输出序列 —从内到外→ 输入序列

    随意出：从第一位慢慢分析。若输出序列第一位是输入序列最后一个，就等于入完再出。

  2. 输入受限（一端仅能输出）

    入完再出：输入序列 —从外到内→ 输出序列

    随意出：从第一位慢慢分析。若输出序列第一位是输入序列最后一个，就等于入完再出。

例如，输入序列 1 2 3 4，不能得到的输出序列（随时出）：

1）输入受限：4 2 1 3、4 2 3 1

2）输出受限：4 1 3 2、4 2 3 1

应用

核心就是利用队列的 FIFO 特性，简单地来说就是用来排队。

在算法中的应用

如层次遍历（广度优先搜索）等。

在计算机系统中的应用

  1. 解决主机与外部设备之间速度不匹配的问题（常使用缓冲区）。

    以主机和打印机之间速度不匹配为例，解决方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入缓冲区，写满就暂停输出，转去做其他事情。打印机就从缓冲区中按照先进先出的原则依次从缓冲区中取出数据进行打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入数据。

    显然，打印数据缓冲区中所存储的数据就是一个队列。这样既保证了打印数据的正确，又使主机提高了效率。

  2. 解决由多用户引起的资源竞争问题。

    如进程调度中的先来先服务调度算法、虚拟内存中的先进先出页面置换算法等。

数组

数组定义

由 $n$ ($n ≥ 1$) 个相同类型的数据元素构成的有限序列。

数组与线性表的关系

数组是线性表的推广。

一维数组可视为一个线性表，二维数组可视为其元素也是定长线性表的线性表，依次类推。

之前讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。
数组可以看成是线性表在下述含义的扩展：表中的数据元素本身也是一个数据结构。

计算机语言中的数组

几乎所有的高级程序设计语言都把数组类型设为固有的数据类型。

由于高级程序设计语言中的数组类型也有随机存取的特性，因此通常都用数组来描述数据结构中的顺序存储结构。

作为逻辑结构的数组可采用计算机语言中的数组数据类型进行存储。

捋一下，数组有三种身份：一种逻辑结构（线性表的推广）、程序设计语言中的数据类型、顺序存储结构。做题时注意区分😏。​

多维数组的映射方法

有按行优先和按列优先两种：

矩阵也是这两种映射方法。

矩阵

特殊矩阵

具有许多相同元素或零元素且它们的分布存在一定规律的矩阵。

常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。

压缩存储

为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。

其目的是节省存储空间。

特殊矩阵的压缩存储

方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

⚠注意：矩阵行列下标从 1 开始，数组要看题目。

对称矩阵

$n$ 阶方阵存放在一维数组 B[n(n+1)/2] 中，一般存下三角（含主对角）。

数组下标 $k$ 与行号 $i$、列号 $j$ 的对应关系（数组下标从 0 开始、行优先、存下三角）：

$k= \begin{cases}\frac{i(i-1)}{2}+j-1, & i \geqslant j\left(\text {下三角区和主对角线元素}\right) \ \frac{j(j-1)}{2}+i-1, & i<j\left(\text {上三角区元素} a_{i, j}=a_{j, i}\right)\end{cases}$

三角矩阵

存储思想与对称矩阵类似，不同之处在于最后多存储常量项 $c$ 一次。

存放在一维数组 B[n(n+1)/2+1] 中。

数组下标 $k$ 与行号 $i$、列号 $j$ 的对应关系（数组下标从 0 开始、行优先、存下三角）：

$k= \begin{cases}\frac{i(i-1)}{2}+j-1, & i \geqslant j \text { (下三角区和主对角线元素) } \ \frac{n(n+1)}{2}, & i<j \text { (上三角区元素 })\end{cases}$

数组下标 $k$ 与行号 $i$、列号 $j$ 的对应关系（数组下标从 0 开始、行优先、存上三角）：

$k= \begin{cases}\frac{(i-1)(2 n-i+2)}{2}+(j-i), & i \leqslant j\text { (上三角区和主对角线元素) } \ \frac{n(n+1)}{2}, & i>j \text { (下三角区元素) }\end{cases}$

对角矩阵/带状矩阵

一维数组。

稀疏矩阵

矩阵中非零元素的个数 t，相对于矩阵元素的个数 s 来说非常少，即 $s \gg t$ 的矩阵称为稀疏矩阵。

表示方法

  • 三元组表示法

    一个三元组（行标，列标，值）唯一确定一个非零元。

  • 伪地址表示法

    每行只有两个存储单元：值、伪地址。

    伪地址即元素在矩阵中按照行优先或列优先存储的相对位置（相对第一个元素）。

    对于稀疏矩阵 $A_{m×n}$，其元素 $A_{ij}$ 的伪地址为 $n(i−1)+j$，可反推真实地址。

压缩存储方法

三元组表/三元组顺序表、十字链表、伪地址顺序表等。

三元组表一般第 0 行用来存储稀疏矩阵的行数、列数和非零元个数。

稀疏矩阵压缩存储后便失去了随机存取特性。

刷题总结

  • 王道 P84 选择 01

    栈和队列的逻辑结构相同，都是线性结构（行行行，都是线性表）。

    栈和队列的本质区别：插入、删除操作的限定不一样（没毛病）。

  • 某时刻同处于栈中的元素，不管如何进出栈，它们出栈的相对顺序仍保持先进后出。

  • 链队默认带头结点？

    王道 P85：选择 12 默认带头结点；选择 17 “只设头指针” 说是意味着没有头结点。

  • 链队用循环链表不是不行，只是自找麻烦（出入队后还要维持循环）。

  • 由于在队首做出队操作，为了便于删除队头元素，故总是选择链头作为队首。

    具有首尾指针的单链表，链首能快速增删元素，而链尾只有插入元素方便。

  • 循环队列出队，队首指针也是 +1。

  • 链队出队时队尾指针也可能会修改（队空了）。

  • 计算递归调用次数或者求第 $i$ 个被执行的递归函数时，画递归调用树比较方便，例如：

  • 矩阵/多维数组存到一维数组后的下标

    三要点：矩阵类型、行优先 or 列优先、该元素在矩阵中的位置（注意对称矩阵）。

    一细节：数组起始序号。

    二维数组 A[n][n] 和 A[0…n-1][0…n-1] 写法是等价的。

    数组起始序号为 1，则元素在矩阵中是第几个（取决于位置、矩阵类型、行/列优先），它在数组中的下标就是第几个；数组起始序号为 0，在前面基础上 -1。

  • 对称矩阵容易忽视的点：

    1）$a_{i,j}$ 和 $a_{j,i}$ 压缩存储到同一存储位置。

    2）三角矩阵比对称矩阵多存储一个常量。