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

本文涉及的产品
视觉智能开放平台,视频资源包5000点
视觉智能开放平台,分割抠图1万点
视觉智能开放平台,图像资源包5000点
简介: IKU达人数据结构与算法系列学习之队列的基本概念、如何判断队列已满/已空、队列的链式存储结构[头的出入队]、双端队列、中缀、后缀、前缀表达式、特殊矩阵和一二维数组的压缩储存等具体操作详解步骤;举例说明、注意点及常见报错问题所对应的解决方法你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!

欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

image.gif

专栏跑道二

➡️ 24 Network Security -LJS

image.gif

image.gif

image.gif

专栏跑道三


➡️ MYSQL REDIS Advance operation

image.gif

专栏跑道四

➡️HCIP;H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

image.gif

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

image.png

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

image.gif

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

image.gif

image.gif

上节回顾



队列的基本概念

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队列的定义和初始化:

image.gif 编辑

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;
}
image.gif

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
image.gif

1.4.2入队操作:

image.gif 编辑

  • 通过取余操作,只要队列不满,就可以一直利用之前已经出队了的空间,逻辑上实现了循环队列的操作
  • 于是,队列已满的条件:队尾指针的再下一个位置是队头,即(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;
}
image.gif

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;
}
image.gif

image.gif 编辑

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

bool GetHead(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //队空报错
        return false;  
    x = Q.data[Q.front];
    return true;
}
image.gif

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

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;
}
  • image.gif
  • 不牺牲一个存储空间,在结构体中多建立一个变量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;
  • image.gif

  • 不牺牲一个存储空间,在结构体中多建立一个变量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初始化(带头结点):

  • image.gif 编辑


3.2初始化(不带头结点):

  • image.gif


3.3入队(带头结点):

  • image.gif

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;         //表尾指针指向新的表尾
}
  • image.gif

3.5入队(不带头结点):

  • image.gif 编辑

3.6出队(带头结点):

  • image.gif

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;
}
  • image.gif

3.8出队(不带头结点):

  • image.gif 编辑

队列满的条件:

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

4.双端队列

4.1定义:

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

4.2考点:

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

image.gif 编辑

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

4.3代码实现:

image.gif

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

算数表达式:

由三个部分组成:操作数、运算符、界限符

我们平时写的算术表达式都是中缀表达式

如何可以不用界限符也能无歧义地表达运算顺序

Reverse Polish notation(逆波兰表达式=后缀表达式)

Polish notation(波兰表达式=前缀表达式)

中缀、后缀、前缀表达式:

image.gif

中缀转后缀的方法(手算):

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

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

image.gif 编辑

中缀表达式转后缀表达式(机算,用栈实现):

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

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

后缀表达式的计算(手算):

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

后缀表达式的计算(机算,用栈实现):

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

中缀表达式转前缀表达式(手算):

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

中缀表达式的计算(机算,用栈实现):

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

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

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

6.栈在递归中的应用

函数调用的特点:

最后被调用的函数最先执行结束(LIFO)

函数调用时,需要用一个栈(函数调用栈)存储,里面包含以下信息:

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

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

栈在递归中的应用:

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

栈在递归中过程:

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

缺点:

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

可能包含很多重复计算

7.队列的应用

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

操作系统中的应用

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

8.特殊矩阵的压缩储存

一维数组的存储结构:

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

二维数组的存储结构:

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

普通矩阵的存储:

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

对称矩阵的压缩存储:

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

image.gif 编辑

三角矩阵的压缩存储:

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

三对角矩阵的压缩存储:

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

image.gif 编辑

稀疏矩阵的压缩存储:

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

image.gif 编辑


相关文章
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习(11)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊-除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明

热门文章

最新文章