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

本文涉及的产品
视觉智能开放平台,视频资源包5000点
视觉智能开放平台,图像资源包5000点
视觉智能开放平台,分割抠图1万点
简介: 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 编辑


相关文章
|
3天前
|
弹性计算 双11 开发者
阿里云ECS“99套餐”再升级!双11一站式满足全年算力需求
11月1日,阿里云弹性计算ECS双11活动全面开启,在延续火爆的云服务器“99套餐”外,CPU、GPU及容器等算力产品均迎来了全年最低价。同时,阿里云全新推出简捷版控制台ECS Lite及专属宝塔面板,大幅降低企业和开发者使用ECS云服务器门槛。
|
20天前
|
存储 弹性计算 人工智能
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
阿里云弹性计算产品线、存储产品线产品负责人Alex Chen(陈起鲲)及团队内多位专家,和中国电子技术标准化研究院云计算标准负责人陈行、北京望石智慧科技有限公司首席架构师王晓满两位嘉宾,一同带来了题为《通用计算新品发布与行业实践》的专场Session。本次专场内容包括阿里云弹性计算全新发布的产品家族、阿里云第 9 代 ECS 企业级实例、CIPU 2.0技术解读、E-HPC+超算融合、倚天云原生算力解析等内容,并发布了国内首个云超算国家标准。
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
|
2天前
|
人工智能 弹性计算 文字识别
基于阿里云文档智能和RAG快速构建企业"第二大脑"
在数字化转型的背景下,企业面临海量文档管理的挑战。传统的文档管理方式效率低下,难以满足业务需求。阿里云推出的文档智能(Document Mind)与检索增强生成(RAG)技术,通过自动化解析和智能检索,极大地提升了文档管理的效率和信息利用的价值。本文介绍了如何利用阿里云的解决方案,快速构建企业专属的“第二大脑”,助力企业在竞争中占据优势。
|
5天前
|
存储 安全 Oracle
【灵码助力安全3】——利用通义灵码辅助智能合约漏洞检测的尝试
本文探讨了智能合约的安全性问题,特别是重入攻击、预言机操纵、整数溢出和时间戳依赖性等常见漏洞。文章通过实例详细分析了重入攻击的原理和防范措施,展示了如何利用通义灵码辅助检测和修复这些漏洞。此外,文章还介绍了最新的研究成果,如GPTScan工具,该工具通过结合大模型和静态分析技术,提高了智能合约漏洞检测的准确性和效率。最后,文章总结了灵码在智能合约安全领域的应用前景,指出尽管存在一些局限性,但其在检测和预防逻辑漏洞方面仍展现出巨大潜力。
|
7天前
|
负载均衡 算法 网络安全
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
阿里云平台WoSign品牌SSL证书是由阿里云合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品,用户在阿里云平台https://www.aliyun.com/product/cas 可直接下单购买WoSign SSL证书,快捷部署到阿里云产品中。
1849 6
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
|
10天前
|
Web App开发 算法 安全
什么是阿里云WoSign SSL证书?_沃通SSL技术文档
WoSign品牌SSL证书由阿里云平台SSL证书合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品。
1789 2
|
19天前
|
编解码 Java 程序员
写代码还有专业的编程显示器?
写代码已经十个年头了, 一直都是习惯直接用一台Mac电脑写代码 偶尔接一个显示器, 但是可能因为公司配的显示器不怎么样, 还要接转接头 搞得桌面杂乱无章,分辨率也低,感觉屏幕还是Mac自带的看着舒服
|
26天前
|
存储 人工智能 缓存
AI助理直击要害,从繁复中提炼精华——使用CDN加速访问OSS存储的图片
本案例介绍如何利用AI助理快速实现OSS存储的图片接入CDN,以加速图片访问。通过AI助理提炼关键操作步骤,避免在复杂文档中寻找解决方案。主要步骤包括开通CDN、添加加速域名、配置CNAME等。实测显示,接入CDN后图片加载时间显著缩短,验证了加速效果。此方法大幅提高了操作效率,降低了学习成本。
5386 15
|
13天前
|
人工智能 关系型数据库 Serverless
1024,致开发者们——希望和你一起用技术人独有的方式,庆祝你的主场
阿里云开发者社区推出“1024·云上见”程序员节专题活动,包括云上实操、开发者测评和征文三个分会场,提供14个实操活动、3个解决方案、3 个产品方案的测评及征文比赛,旨在帮助开发者提升技能、分享经验,共筑技术梦想。
1130 152
|
21天前
|
存储 缓存 关系型数据库
MySQL事务日志-Redo Log工作原理分析
事务的隔离性和原子性分别通过锁和事务日志实现,而持久性则依赖于事务日志中的`Redo Log`。在MySQL中,`Redo Log`确保已提交事务的数据能持久保存,即使系统崩溃也能通过重做日志恢复数据。其工作原理是记录数据在内存中的更改,待事务提交时写入磁盘。此外,`Redo Log`采用简单的物理日志格式和高效的顺序IO,确保快速提交。通过不同的落盘策略,可在性能和安全性之间做出权衡。
1585 14

热门文章

最新文章

  • 1
    2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    11
  • 2
    2024重生之回溯数据结构与算法系列学习(11)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    6
  • 3
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    8
  • 4
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    10
  • 5
    2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    8
  • 6
    2024重生之回溯数据结构与算法系列学习(7)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    7
  • 7
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    6
  • 8
    23
    6
  • 9
    2024重生之回溯数据结构与算法系列学习之单双链表精题(4)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    8
  • 10
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    6