3.1 栈
3.1.1 栈的基本概念
-
栈（Stack）是特殊的线性表，其只允许在一端进行插入或删除操作
-
空栈：没有数据元素的栈
-
栈顶：允许插入和删除的一端
-
栈底：不允许插入和删除的一端
-
栈的特点：后进先出
-
出栈顺序排列情况个数（常考题型）：n 个不同元素进栈，出栈元素不同排列情况有 \(\frac{1}{n+1}C_{2n}^n\) 种，该公式称为卡特兰（Catalan）数
-
特殊结论：
① 若最后一个入栈的元素第一个出栈，则出栈顺序必为入栈顺序的逆序
② 若一段连续的进栈后（
Push:a4,a5,a6,a7）发生了一次出栈Pop:a7，那么该段时间内先进栈的不可能先出栈
-
-
栈的深度： 指栈中的元素个数
（在题目中通常给出入栈和出栈序列，求最大深度；有时入栈序列和出栈序列是间接给出的，如以中缀表达式和后缀表达式的形式给出入栈和出栈序列）
3.1.2 顺序栈
- 栈是一种操作受限的线性表，类似线性表，也对应两种存储方式
- 顺序栈：用顺序存储的方式实现栈
- 顺序栈存在大小不可变的缺点
- 顺序栈的销毁只需使栈顶“指针”回到初始化的状态，函数结束后系统会自动回收静态分配的资源
(1) 定义和初始化
- 注意： 不同的初始化策略将影响后续操作对栈顶“指针”位置的判断
#define MaxSize 10
typedef struct{ElemType data[MaxSize]; //顺序栈用静态数组存放元素int top; //栈顶“指针”
}SqStack;void InitStack(SqStack &S){S.top = -1; //栈顶“指针”初始为-1
}//判断栈空
bool StackEmpty(SqStack S){if(S.top==-1)return true;elsereturn false;
}void testStack(){SqStack S; //声明一个顺序栈InitStack(S);//后续操作
}
(2) 进栈
#define MaxSize 10
typedef struct{ElemType data[MaxSize];int top;
}SqStack;//入栈操作
bool Push(SqStack &S, ElemType x){if(S.top==MaxSize-1) //检查是否栈满return false;S.top = S.top + 1; //“指针”+1，定位至入栈位置S.data[S.top] = x; //入栈/*上述两步可用：S.data[++S.top] = x;*/return true;
}
(3) 出栈
#define MaxSize 10
typedef struct{ElemType data[MaxSize];int top;
}SqStack;//出栈操作
bool Pop(SqStack &S, ElemType &x){ //注意使用的是&xif(S.top==-1) //检查是否栈空return false;x = S.data[S.top]; //获取出栈元素S.top = S.top - 1; //“指针-1”，相当于出栈/*上述两步可用：x = S.data[S.top--];*/
}
(4) 读取栈顶元素
#define MaxSize 10
typedef struct{ElemType data[MaxSize];int top;
}SqStack;bool GetTop(SqStack S, ElemType &x){ //注意使用的是&xif(S.top==-1) //检查是否栈空return false;x = S.data[S.top];return true;
}
ps：共享栈
-
共享栈：两个栈共享同一片空间
- 实现目的是为了更有效的利用存储空间
-
利用栈底位置相对不变的特性，可让两个顺序栈共享同一个一维数组空间，两个栈底分别设置在数组两端
-
共享栈栈满条件：
top0 + 1 == top1
#define MaxSize 10
typedef struct{ElemType data[MaxSize];int top0; //0号栈栈顶“指针”int top1; //1号栈栈顶“指针”
}ShStack;//初始化共享栈
void InitStack(ShStack &S){//共享栈的两个“指针”分别在栈空间的两端（外侧）S.top0 = -1;S.top1 = MaxSize; //指向data[MaxSize-1]右侧
}
3.1.3 链栈
-
链栈：用链式存储方式实现的栈
- 优点：便于多个栈共享存储空间和提高效率，且通常不存在栈满上溢的情况
-
通常采用单链表实现链栈，处理方式和单链表基本相同，只是要求入栈和出栈在链表的同一端进行（通常是表头）
-
由于链栈的插入和删除都在头部进行，所以不需要头结点（不排除题目要求带头结点）
(1) 定义
typedef struct Linknode{ElemType data;struct Linknode *next;
}Linknode,*LiStack;
3.2 队列
3.2.1 队列的基本概念
-
队列（Queue）是种特殊的线性表，其只允许在一端插入（入队），在另一端删除（出队）
-
队头：出队的一端
-
队尾：入队的一端
-
队列的特点：先进先出（First In First Out）
3.2.2 顺序队列
-
队列是一种操作受限的线性表，类似线性表，也对应两种存储方式
-
顺序队列：用顺序存储的方式实现队列
-
顺序队列实现入队、出队的特点使其又称为循环队列
-
如下所示代码采用的队满、队空判断策略是允许牺牲一个单元的方案
(1) 定义和初始化
#define MaxSize 10
typedef struct{ElemType data[MaxSiz]; //顺序队列用静态数组int front,rear; //队头和队尾“指针”
}SqQueue;//初始化队列
void InitQueue(SqQueue &Q){//初始时队头和队尾“指针”指向0Q.rear = Q.front = 0;
}//判断队列是否为空
bool QueueEmpty(SqQueue Q){if(Q.rear==Q.front)return true;elsereturn false
}
(2) 入队
#define MaxSize 10
typedef struct{ElemType data[MaxSiz]; //顺序队列同静态数组int front,rear; //队头和队尾“指针”
}SqQueue;bool EnQueue(SqQueue &Q, ElemType x){if((Q.rear+1)%MaxSize == Q.front) //检查是否满队，满队条件：队尾指针的下一位置为对头return false;Q.data[Q.rear] = x; //x入队Q.rear = (Q.rear+1)%MaxSize; //队尾“指针”后移，+1后取余return true;
}
(3) 出队
bool DeQueue(SqQueue &Q, ElemType &x){ //注意使用的&xif(Q.rear==Q.front) //检查是否队空return false;x = Q.data[Q.front];Q.front = (Q.front+1)%MaxSize; //队头“指针”后移return true;
}
- 队列元素个数计算：
(rear + MaxSize -front)%MaxSize
(4) 队满、队空判断
-
不同的初始化策略影响队满、队空的判断方式
-
假溢出：可以理解为不合理的队满判断策略导致队列仍有空间，但被判定为溢出
-
判断队满、队空策略
-
允许牺牲一个单元的方案：队尾指针的下一个位置为队首指针，则队满；队首、队尾指针相等，则队空
-
不允许牺牲存储单元的方案
(1) 结构体增设
size数据成员- 队空时
Q.size==0；队满时Q.size==Maxsize - 两种情况下均有
Q.front==Q.rear
(2) 结构体增设
tag数据成员- 若当前的一次操作是出队，且出队成功，则置
tag=0；若当前的一次操作是入队，且入队成功，则置tag=1 - 队空时
Q.front==Q.rear且tag=0，表明使得两个指针相等的上一次操作是出队操作，导致队空 - 队满时
Q.front==Q.rear且tag=1，表明使得两个指针相等的上一次操作是入队操作，导致队满
- 队空时
-
3.2.3 链式队列
(1) 定义
//链式队列结点
typedef struct LinkNode{ElemType data;struct LinkNode *next;
}LinkNode;//链式队列首尾指针
typedef struct{LinkNode *front,*rear; //队列的对头和队尾指针
}LinkQueue;
(2) 初始化
带头结点：
//带头结点队列初始化
void InitQueue(LinkQueue &Q){//初始时front和rear都指向头结点Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));Q.front->next = NULL;
}//判断带头结点队列是否为空
bool IsEmpty(LinkQueue Q){if(Q.front==Q.rear)return true;elsereturn false;
}
不带头结点：
//不带头结点队列初始化
void InitQueue(LinkQueue &Q){//初始时front和rear都指向NULLQ.front = NULL;Q.rear = NULL;
}//判断不带头结点队列是否为空
bool IsEmpty(LinkQueue Q){if(Q.front==NULL)return true;elsereturn false;
}
(3) 入队
带头结点：
void EnQueue(LinkQueue &Q, ElemType x){LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = NULL; //新结点总是在队尾，指针域直接置NULLQ.rear->next = s; //新结点队尾入队，即插入到rear之后Q.rear = s; //更新队尾指针
}
不带头结点：由于不带头结点的队列初始化时头指针和尾指针都指向NULL，所以当第一个元素入队时要特殊处理
void EnQueue(LinkQueue &Q, ElemType x){LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = x;s->next = NULL;if(Q.front==NULL){ //入队的是第一个元素Q.front = s;Q.rear = s;}else{Q.rear->next = s;Q.rear = s;}}
(4) 出队
带头结点：
- 队头指针始终指向头结点
bool DeQueue(LinkQueue &Q, ElemType &x){ //注意使用的&xif(Q.front==Q.rear) //检查是否是空队return false;LinkNode *p = Q.front->next;//用指针p指向出队结点x = p->data; //获取出队的元素Q.front->next = p->next; //头结点指针指向待出队结点的下一个结点if(Q.rear==p) //判断出队的结点是否为最后一个Q.rear = Q.front; //修改rear指针free(p); //释放return true;
}
3.2.4 双端队列
双端队列：允许从队列两端进行插入、删除的线性表
输入受限的双端队列：只允许从一端插入、但可从两端删除的线性表
输出受限的双端队列：只允许从一端删除、但可从两端插入的线性表
- 对于双端队列的输出序列，无论从那一段输出，先出的排在前面
- 双端队列的考题通常围绕判断序列是否满足题设条件，带入验证即可
- 在栈中合法的输出序列，在双端队列必合法
3.3 栈的应用
3.3.1 括号匹配
用顺序栈实现的括号匹配：
#define MaxSize 10 // 顺序栈容量
typedef struct{char data[MaxSize];int top;
}SqStack;//初始化栈
void InitStack(SqStack &S);//判断是否栈空
bool StackEmpty(SqStack S);//新元素入栈
bool Push(SqStack &S, char x);//栈顶元素出栈
bool Pop(SqStack &S, char &x);bool bracketCheck(char str[], int length){/*str[]为待处理的字符数组，length为字符的个数*/SqStack S;InitStack(S);for(int i=0; i<length; i++){if(str[i]=="(" || str[i]=="[" || srt[i]=="{"){Push(S, str[i]); //扫描左括号并入栈} else{if(str[i]==')'||str[i]==']'||str[i]=='}'){if(StackEmpty(S)) //扫描到右括号，且此时栈空return false; //匹配失败char topElem;Pop(S, topElem); //栈顶元素出栈if(str[i]==")" && topElem!="(") return false;if(str[i]=="]" && topElem!="[") return false;if(str[i]=="}" && topElem!="{") return false;}}}return StackEmpty(S); //检索结束后，若栈空，则匹配成功
}
- 若字符数量未知的话，为了避免栈溢出，可以采用链栈
- 对栈的基本操作可以直接使用相关函数，但建议进行函数声明，简要说明函数接口
- 用栈实现括号匹配算法思路：
- 依次扫描所有字符，遇到左括号则入栈，遇到右括号则弹出栈顶元素进行匹配
- 匹配失败的三种情况：① 左括号单身、② 右括号单身、③ 左右括号不匹配
3.3.2 表达式求值
注意：“左、右操作数”和“左、右优先原则” 等说法为便于理解所设
1. 三种算数表达式
-
算数表达式（如“ \(5 \times (7-(1+1))-2 \div 4\) ”）由三个部分组成：操作数、运算符、界限符，界限符即表达式中的括号，反映了计算的先后顺序
-
波兰数学家提出了可以不用界限符也能无歧义地表达运算顺序：后缀表达式（逆波兰表达式）、前缀表达式（波兰表达式），原来的表达式则另称为中缀表达式
-
中缀表达式： 运算符在两个操作数中间
-
后缀表达式： 运算符在两个操作数后面
-
前缀表达式： 运算符在两个操作数前面
-
| 中缀表达式 | 后缀表达式 | 前缀表达式 |
|---|---|---|
| \(a+b\) | \(ab+\) | \(+ab\) |
| \(a+b-c\) | \(ab+c-\) 或$ abc-+$ | \(-+abc\) |
| \(a+b-c\times d\) | \(ab+cd\times-\) | \(-+ab*cd\) |
2. 中缀表达式转后缀表达式
- 手算转换方法：
① 确定中缀表达式各个运算符的运算顺序；
② 根据运算顺序，按 ”左操作数、右操作数、运算符“ 的方式组合成一个新的操作数（即运算结果）；
③ 若还有运算符未处理，重复②
-
注意： 由于运算的顺序不唯一，因此同一中缀表达式对应的后缀表达式不唯一
-
注意： 根据算法结果的唯一性原则，计算机处理得到的表达式应是唯一确定的，其转换应遵循 “左优先” 原则（即优先处理表达式左侧可计算的操作符）
-
中缀转后缀机算算法：
初始化一个栈，用于保存暂时不能确定运算顺序的运算符；
从左往右处理各个元素，直到末尾，可能遇到三种情况：
① 遇到操作数：直接加入后缀表达式
② 遇到界限符：若遇到 “(” （左界限符）直接入栈；若遇到 “)” 则依次弹出栈顶运算符并加入后缀表达式，直到弹出 “(” 为止，注意界限符不加入表达式
③ 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到栈顶为 “(” 时则停止（不弹出）。之后再把当前运算符入栈
处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式总结： 执行步骤③时，当栈中有运算符说明式中存在未计算的两个操作数，若优先级低于当前运算符，说明式中的操作数无法计算，若优先级相同根据左优先原则需要弹出
-
后缀表达式计算手算方法：从左往右扫描，每遇到一个运算符，就让该运算符前面最近的两个操作数执行对应运算，并组成一个新操作数，计算过程中应注意两个操作数的左右顺序
- 根据后缀表达式的计算特点，最后出现的操作数先被计算，即后进先出，可以用栈进行代码实现
-
后缀表达式计算机算算法：
① 对后缀表达式从左往右扫描下一个元素，直到处理完所以元素；
② 若扫描到操作数则压入栈，并回到①，否则执行③；
③ 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①。注意： ② 操作最先出栈的是“右操作数”
-
后缀表达式适用于基于栈的编程语言，如Forth、PostScript
3. 中缀表达式转前缀表达式
-
手算转换方法：
① 确定中缀表达式各个运算符的运算顺序；
② 根据运算顺序，按 ”运算符、左操作数、右操作数“ 的方式组合成一个新的操作数（即运算结果）；
③ 若还有运算符未处理，重复② -
“右优先” 原则：优先处理表达式右侧可计算的运算符
-
前缀表达式计算的机算算法：
① 对前缀表达式从右往左扫描下一个元素，直到处理完所以元素；
② 若扫描到操作数则压入栈，并回到①，否则执行③；
③ 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①。注意： ② 操作最先出栈的是“左操作数”
4. 中缀表达式的计算
-
用栈实现中缀表达式的计算可结合中缀转后缀算法和后缀表达式求值算法
-
中缀计算算法：
初始化两个栈，运算符栈和操作数栈（分别服务两个算法）
对中缀表达式从左往右扫描下一个元素，直到处理完所以元素：
① 若扫描到操作数，压入操作数栈
② 若扫描到运算符或界限符，则按 “中缀转后缀” 算法逻辑压入运算符栈
③ 过程中若弹出运算符，每当弹出一个运算符，就弹出两个操作数栈顶元素进行相应运算，结果再压回操作数栈
3.3.3 栈在递归中的应用
-
适合用“递归”算法解决的问题：可以将原始问题转换为属性相同，但规模较小的问题
- 实现一个递归算法需要有递归表达式（递归体）和边界条件（递归出口）
-
递归调用时，函数调用栈可称为“递归工作栈”
- 每进入一层递归，就将函数调用所需信息压入栈顶
- 每退出一层递归，就从栈顶弹出相应信息
- 缺点：效率低，太多层递归可能导致栈溢出；可能包含大量重复计算
- 可自定义栈将递归算法改造成非递归算法
-
函数调用的特点：最后被调用的函数最先执行结束
-
函数调用时，需要一个“函数调用栈”存储：
① 调用返回地址；② 实参；③ 局部变量
3.4 队列的应用
- 树的层次遍历（作辅助队列，详见树章节）
- 图的广度优先遍历（作辅助队列，详见图章节）
- 在操作系统中的应用：
- 在计算机系统中的应用
- 解决多用户引起的资源竞争问题（如多进程 “先来先服务”等策略）
- 解决主机与外部设备之间速度矛盾（如主机和打印机间设置打印数据缓冲区）
3.5 数组和特殊矩阵
-
数组：
-
数组中各元素大小相同，且物理上连续存放
-
数组下标默认从 0 开始，下标取值范围称为数组的维界
-
数组的存储结构：行优先存储、列优先存储
-
-
普通矩阵可用二维数组存储（注意矩阵元素行、列号通常从 1 开始，而数组下标通常从 0 开始）
-
特殊矩阵：对称矩阵、三角矩阵、三对角矩阵、稀疏矩阵等
- 其中对称矩阵、三角矩阵、三对角矩阵都是方阵
- 某些特殊矩阵可以压缩（节省）存储空间
-
对称矩阵的压缩存储：
-
策略：只存储主对角线+上三角区（或下三角区）
-
按行优先原则将各元素存入一维数组中：
-
数组大小：\(\dfrac{n(n+1)}{2}\)
-
矩阵元素的便捷使用：通过实现一个“映射”函数计算矩阵下标对应的一维数组下标
（下三角策略）按行优先原则，\(a_{i,j}\) 是第 \(\dfrac{(i-1)i}{2}+j\) 个元素，对应的数组下标 \(k=\dfrac{(i-1)i}{2}+j-1\) （数组从0开始）
-
-
-
三角矩阵的压缩存储：
- 下三角矩阵：除主对角线和下三角区，其余元素都相同
- 上三角矩阵：除主对角线和上三角区，其余元素都相同
- 策略：下三角矩阵为例，按行优先原则将主对角线和下三角区存入一维数组，并在最后一个位置存储常量 c（上三角区的相同元素）
- 数组大小：\(\dfrac{n(n+1)}{2}+1\)
-
三对角矩阵的压缩存储：
-
三对角矩阵又称带状矩阵，当 \(|i-j|>1\) 时，有 \(a_{i,j}=0\)
-
策略：行优先原则，只存储带状部分
-
数组大小：3n-2（矩阵除了第一行和最后一行有2个，其他行每行3个）
-
前 \(i-1\) 行共 \(3(i-1)-1\) 个元素
-
\(a_{i,j}\) 是 \(i\) 行第 \(j-i+2\) 个元素（只看带状部分）
-
\(a_{i,j}\) 是第 \((3(i-1)-1)+(j-i+2)=2i+j-2\) 个元素
-
已知数组下标 \(k\) 求 \(i,j\)：
下标 \(k\) 对应第 \(k+1\) 个元素，矩阵前 \(i-1\) 行共 \(3(i-1)-1\) 个元素，前 \(i\) 行共 \(3i-1\) 个元素，显然 \(3(i-1)-1<k+1\leq 3i-1\)，于是有 \(i\geq(k+2)/3\)，\(i\) 向上取整使满足 \(i=(k+2)/3\)，再进一步求 \(j\)
-
-
-
稀疏矩阵的压缩存储：
-
稀疏矩阵：非零元素远远少于矩阵元素的个数
-
稀疏矩阵要保存的信息： 每个非零元素对应一个三元组（行标 i，列标 j，\(a_{ij}\)）、稀疏矩阵的行数、列数、非零元素个数
（由于稀疏矩阵的非零元素的分布没有规律，所以仅存储非零元素的值是不行的，还要存储其所在的行和列信息）
-
适合稀疏矩阵压缩存储的存储结构：
- 数组存储
- 十字链表存储
-
稀疏矩阵采用压缩存储后，主要缺点是丧失了随机存取的特性，需要进行映射计算
-