2024重生之回溯数据结构与算法系列学习（7）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】

上章节回顾

队列的基本概念

1.队列的定义：

• 栈（Stack）是只允许在一端进行插入或删除操作的操作受限的线性表
• 队列（Queue）是只允许在一端进行插入，在另一端删除的线性表
• 队头：允许删除的一端，对应的元素被称为队头元素
• 队尾：允许插入的一端，对应的元素被称为队尾元素
• 队列的特点：先进先出First In First Out（FIFO）

1.2队列的基本操作：

• InitQueue(&Q)：初始化队列，构造一个空队列Q。
• DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。
• EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
• DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。
• GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。
• QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。

1.3队列的顺序存储结构

1.3.1队列的定义和初始化：

1.3.3队列的定义和初始化代码实现：

//队列的顺序存储类型
# define MaxSize 10;     //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];   //用静态数组存放队列元素
                              //连续的存储空间，大小为——MaxSize*sizeof(ElemType)
    int front, rear;          //队头指针和队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    //初始化时，队头、队尾指针指向0
    Q.rear = Q.front = 0;
}

void test{
    SqQueue Q;                //声明一个队列
    InitQueue(Q);
    //...
}

// 判空
bool QueueEmpty(SqQueue 0){
    if(Q.rear == Q.front)    //判空条件后
        return true;
    else 
        return false;
}

1.4循环队列

1.4.1定义：

将循环队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

基本操作：

a%b == a除以b的余数

初始：Q.front = Q.rear = 0;

队首指针进1：Q.front = (Q.front + 1) % MaxSize

队尾指针进1：Q.rear = (Q.rear + 1) % MaxSize —— 队尾指针后移，当移到最后一个后，下次移动会到第一个位置

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

​

1.4.2入队操作：

• 通过取余操作，只要队列不满，就可以一直利用之前已经出队了的空间，逻辑上实现了循环队列的操作
• 于是，队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front
• 代价：牺牲了一个存储单元，因为如果rear和front相同，与判空的条件相同了

1.4.3入队操作实现代码：

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;
}

1.4.4出队操作：

出队操作实现代码：

//出队，删除一个队头元素，用x返回
bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //队空报错
        return false;  

    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize; //队头指针后移动

    return true;
}

循环队列——获得队头代码实现:

bool GetHead(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //队空报错
        return false;  

    x = Q.data[Q.front];
    return true;
}

实际上获取队头元素的值就是出队操作去掉队头指针后移的代码

​

2.判断队列已满/已空：

方案1——耗费一个Elemtype类型的大小空间：

• 使用前面讲的牺牲一个存储空间的方式来解决
• 初始化时rear=front=0
• 队列元素个数：(rear+MaxSize-front)%MaxSize
• 队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front
• 队空条件：Q.rear==Q.front

方案2——Size代码实现：

# define MaxSize 10;     
typedef struct{
    ElemType data[MaxSize];   
    int front, rear;        
    int size;               //队列当前长度
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;
    size = 0;
}

不牺牲一个存储空间，在结构体中多建立一个变量size

初始化时rear=front=0；size = 0;

队列元素个数= size

插入成功size++；删除成功size--;

此时队满条件：size==MaxSize

队空条件：size == 0;

方案3——tag代码实现：

# define MaxSize 10;     
typedef struct{
    ElemType data[MaxSize];   
    int front, rear;        
    int tag;               //最近进行的是删除or插入
}SqQueue;

不牺牲一个存储空间，在结构体中多建立一个变量tag

初始化时rear=front=0；tag = 0;

因为只有删除操作，才可能导致队空，只有插入操作，才可能导致队满因此

每次删除操作成功时，都令tag=0；

每次插入操作成功时，都令tag=1；

队满条件：front==rear && tag == 1

队空条件：front==rear && tag == 0

队列元素个数：(rear+MaxSize-front)%MaxSize

​

3.队列的链式存储结构

3.1初始化（带头结点）：

​

3.2初始化（不带头结点）：

3.3入队（带头结点）：

3.4入队（带头结点）代码实现：

//新元素入队 (表尾进行)
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点
    s->data = x;
    s->next = NULL;     //s作为最后一个结点，指针域指向NULL
    Q.rear->next = s;   //新结点插入到当前的rear之后
    Q.rear = s;         //表尾指针指向新的表尾
}

3.5入队（不带头结点）：

​

3.6出队（带头结点）：

3.7出队（带头结点）代码实现：

//队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front == Q.rear)
        return false;                    //空队
    
    LinkNode *p = Q.front->next;         //p指针指向即将删除的结点 (头结点所指向的结点)
    x = p->data;
    Q.front->next = p->next;             //修改头结点的next指针
    if(Q.rear == p)                      //此次是最后一个结点出队
        Q.rear = Q.front;                //修改rear指针
    free(p);                             //释放结点空间

    return true;
}

3.8出队（不带头结点）：

队列满的条件：

• 顺序存储：预分配的空间耗尽时队满
• 链式存储：一般不会队满，除非内存不足

4.双端队列

4.1定义：

• 双端队列：只允许从两端插入、两端删除的线性表
• 输入受限的双端队列：只允许从一端插入、两端删除的线性表
• 输出受限的双端队列：只允许从两端插入、一端删除的线性表
• 不管是怎么样的双端队列实际都是栈和队列的变种

4.2考点：

• 判断输出序列合法性
• 在栈中合法的输出序列，在双端队列中必定合法
• 栈在括号匹配中的应用
• 括号匹配问题：

• 若有括号无法被匹配则出现编译错误
• 遇到左括号就入栈
• 遇到右括号，就“消耗”一个左括号【即出栈】

4.3代码实现：

​

5.栈在表达式求值中的应用

算数表达式： 由三个部分组成：操作数、运算符、界限符 我们平时写的算术表达式都是中缀表达式 如何可以不用界限符也能无歧义地表达运算顺序 Reverse Polish notation（逆波兰表达式=后缀表达式） Polish notation（波兰表达式=前缀表达式） 中缀、后缀、前缀表达式：

中缀转后缀的方法（手算）：

1. 确定中缀表达式中各个运算符的运算顺序
2. 选择下一个运算符，按照「左操作数右操作数运算符」的方式组合成一个新的操作数
3. 如果还有运算符没被处理，就继续第二步
4. 注意：运算顺序不唯一，因此对应的后缀表达式也不唯一

“左优先”原则：只要左边的运算符能先计算，就优先算左边的，保证手算和机算是一致的

中缀表达式转后缀表达式（机算，用栈实现）：

1. 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
2. 从左到右处理各个元素，直到末尾。可能遇到三种情况：
3. 遇到操作数。直接加入后缀表达式。
4. 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。
5. 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。

按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的计算（手算）：

• 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
• 注意：两个操作数的左右顺序
• 特点：最后出现的操作数先被运算，LIFO（后进先出），可以使用栈来完成这个步骤
• “左优先”原则：只要左边的运算符能先计算，就优先算左边的

后缀表达式的计算（机算，用栈实现）：

• 从左往右扫描下一个元素，直到处理完所有元素
• 若扫描到操作数则压入栈，并回到第一步；否则执行第三步
• 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步
• 注意：先出栈的是“右操作数”
• 若表达式合法，则最后栈中只会留下一个元素，就是最终结果
• 后缀表达式适用于基于栈的编程语言（stack-orientedprogramming language），如：Forth、PostScript

中缀表达式转前缀表达式（手算）：

• 确定中缀表达式中各个运算符的运算顺序
• 选择下一个运算符，按照「运算符左操作数右操作数」的方式组合成一个新的操作数
• 如果还有运算符没被处理，就继续第二步
• “右优先”原则：只要右边的运算符能先计算，就优先算右边的

中缀表达式的计算（机算，用栈实现）：

中缀表达式的计算=中缀转后缀+后缀表达式求值，两个算法的结合

用栈实现中缀表达式的计算：

• 初始化两个栈，操作数栈和运算符栈
• 若扫描到操作数，压入操作数栈
• 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

6.栈在递归中的应用

函数调用的特点： 最后被调用的函数最先执行结束（LIFO） 函数调用时，需要用一个栈（函数调用栈）存储，里面包含以下信息：

• 调用返回地址
• 实参
• 局部变量

适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题

栈在递归中的应用：

• 计算正整数的阶乘n!
• 求斐波那契数列

栈在递归中过程：

• 递归调用时，函数调用栈可称为“递归工作栈”
• 每进入一层递归，就将递归调用所需信息压入栈顶
• 每退出一层递归，就从栈顶弹出相应信息

缺点：

太多层递归可能会导致栈溢出

可能包含很多重复计算

7.队列的应用

• 树的层次遍历
• 图的广度优先遍历

操作系统中的应用

• 多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用策略。可以用队列实现
• CPU资源的分配
• 打印数据缓冲区

8.特殊矩阵的压缩储存

一维数组的存储结构：

• 起始地址：LOC
• 各数组元素大小相同，且物理上连续存放。
• 数组元素ai的存放地址= LOC + i * sizeof(ElemType)

二维数组的存储结构：

• 分为行优先和列优先，本质就是把二维的逻辑视角转换为内存中的一维储存
• M行N列的二维数组bM中，若按行优先存储，则bi的存储地址= LOC + (i*N + j) * sizeof(ElemType)
• M行N列的二维数组bM中，若按列优先存储，则bi的存储地址= LOC + ( j*M+ i ) * sizeof(ElemType)
• 二维数组也有随机存储的特性

普通矩阵的存储：

• 可用二维数组存储
• 注意：描述**矩阵元素时，行、列号通常从1开始**；而描述**数组时通常下标从0开始**
• 某些特殊矩阵可以压缩存储空间（比如对称矩阵）

对称矩阵的压缩存储：

• 若n阶方阵中任意一个元素ai,j都有ai,j = aj,i则该矩阵为对称矩阵
• 普通存储：n*n二维数组
• 压缩存储策略：只存储主对角线+下三角区（或主对角线+上三角区），按行优先原则将各元素存入一维数组中
• 数组大小应为多少：(1+n)*n/2
• 站在程序员的角度，对称矩阵压缩存储后怎样才能方便使用：可以实现一个“映射”函数矩阵下标->一维数组下标
• 按行优先的原则，ai,j是第几个元素：

三角矩阵的压缩存储：

• 下三角矩阵：除了主对角线和下三角区，其余的元素都相同
• 上三角矩阵：除了主对角线和上三角区，其余的元素都相同
• 压缩存储策略：按行优先原则将橙色区元素存入一维数组中，并在最后一个位置存储常量c
• 下三角矩阵，按行优先的原则，ai,j是第几个元素：

• 上三角矩阵，按行优先的原则，ai,j是第几个元素：

三对角矩阵的压缩存储：

• 三对角矩阵，又称带状矩阵：当|i - j|>1时，有ai,j = 0 （1≤ i, j ≤n）
• 压缩存储策略：按行优先（或列优先）原则，只存储带状部分
• 按行优先的原则，ai,j是第几个元素：

稀疏矩阵的压缩存储：

• 稀疏矩阵：非零元素远远少于矩阵元素的个数
• 压缩存储策略1：顺序存储——三元组<i（行），j（列），v（值）>，失去了数组随机存储的特性
• 压缩存储策略2：链式存储，十字链表法