admin管理员组

文章数量:1794759

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队列的定义和初始化代码实现：
代码语言：javascript代码运行次数：0运行复制
//队列的顺序存储类型
# 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定义：

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

基本操作：

代码语言：javascript代码运行次数：0运行复制
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入队操作实现代码：
代码语言：javascript代码运行次数：0运行复制
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出队操作：
出队操作实现代码：
代码语言：javascript代码运行次数：0运行复制
//出队，删除一个队头元素，用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;
}
循环队列——获得队头代码实现:
代码语言：javascript代码运行次数：0运行复制
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代码实现：

代码语言：javascript代码运行次数：0运行复制
# 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代码实现：

代码语言：javascript代码运行次数：0运行复制
# 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入队（带头结点）代码实现：
代码语言：javascript代码运行次数：0运行复制
//新元素入队 (表尾进行)
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出队（带头结点）代码实现：
代码语言：javascript代码运行次数：0运行复制
//队头元素出队
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：链式存储，十字链表法
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-10-18，如有侵权请联系 cloudcommunity@tencent 删除存储队列数据结构与算法数组指针

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

版权声明：本文标题：2024重生之回溯数据结构与算法系列学习（7）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754674760a1705054.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。