欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
专栏跑道二
➡️ 24 Network Security -LJS
专栏跑道三
➡️ MYSQL REDIS Advance operation
专栏跑道四
➡️HCIP;H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
上节回顾
队列的基本概念
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队列的定义和初始化代码实现:
//队列的顺序存储类型 //定义队列中元素的最大个数 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代码实现:
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(波兰表达式=前缀表达式)
中缀、后缀、前缀表达式:
中缀转后缀的方法(手算):
- 确定中缀表达式中各个运算符的运算顺序
- 选择下一个运算符,按照「左操作数右操作数运算符」的方式组合成一个新的操作数
- 如果还有运算符没被处理,就继续第二步
- 注意:运算顺序不唯一,因此对应的后缀表达式也不唯一
“左优先”原则:只要左边的运算符能先计算,就优先算左边的,保证手算和机算是一致的
编辑
中缀表达式转后缀表达式(机算,用栈实现):
- 初始化一个栈,用于保存暂时还不能确定运算顺序的运算符。
- 从左到右处理各个元素,直到末尾。可能遇到三种情况:
- 遇到操作数。直接加入后缀表达式。
- 遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式,直到弹出“(”为止。注意:“(”不加入后缀表达式。
- 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,若碰到“(”或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后,将栈中剩余运算符依次弹出,并加入后缀表达式。
后缀表达式的计算(手算):
- 从左往右扫描,每遇到一个运算符,就让运算符前面最近的两个操作数执行对应运算,合体为一个操作数
- 注意:两个操作数的左右顺序
- 特点:最后出现的操作数先被运算,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是第几个元素:
编辑
三角矩阵的压缩存储:
- 下三角矩阵:除了主对角线和下三角区,其余的元素都相同
- 上三角矩阵:除了主对角线和上三角区,其余的元素都相同
- 压缩存储策略:按行优先原则将橙色区元素存入一维数组中,并在最后一个位置存储常量c
- 下三角矩阵,按行优先的原则,ai,j是第几个元素:
- 编辑
- 上三角矩阵,按行优先的原则,ai,j是第几个元素:
- 编辑
三对角矩阵的压缩存储:
- 三对角矩阵,又称带状矩阵:当|i - j|>1时,有ai,j = 0 (1≤ i, j ≤n)
- 压缩存储策略:按行优先(或列优先)原则,只存储带状部分
- 按行优先的原则,ai,j是第几个元素:
编辑
稀疏矩阵的压缩存储:
- 稀疏矩阵:非零元素远远少于矩阵元素的个数
- 压缩存储策略1:顺序存储——三元组<i(行),j(列),v(值)>,失去了数组随机存储的特性
- 压缩存储策略2:链式存储,十字链表法
编辑