导图社区 ③栈、队列和数组
24自用408数据结构,栈(Stack)是一种操作受限的线性表,只允许在一端进行插入或删除操作的线性表。
编辑于2023-07-03 15:45:29 广东第三章
栈(Stack)
基本概念
一种操作受限的线性表,只允许在一端进行插入或删除操作的线性表
注意
后进先出LIFO
n个不同元素,出栈元素不同排列组合个数为
基本操作
InitStack(&s)
StackEmpty(s)
Push(&s,x
Pop(&s,&x
GetTop(S,&x)
DestroyStack(&S)
栈的顺序存储结构
顺序栈实现
栈顶指针:初始为S.top=-1(有可能为0,意为指向栈顶元素的下一个存储单元,出栈入栈等操作都会发生变化注意)
S.top=-1
进栈操作:栈不满时,栈顶指针先加1,再送值至栈顶元素
S.data[++S.top]=x
出栈操作:栈非空时,先取栈顶元素,再将栈顶指针减1
x=S.data[S.top--]
读栈和出栈注意区别
读栈顶元素,栈顶元素不改变
栈空条件:S.top==-1;栈满条件:S.top==MaxSize-1:栈长:栈顶指针加1
S.top==-1
栈的空间不足时,会发生上溢
共享栈
两个顺序栈共享一个一维数组空间
判空:top左=-1时,左栈空;top右=MaxSize,右栈空
判满:两个指针相邻,top右-top左=1
进栈:左号栈top左先加1,再赋值;右栈top右先减1,再赋值
出栈与进栈相反
栈的链式存储结构
便于多个栈共享存储空间和提高效率
不会发生上溢
采用单链表实现,并规定所有操作都是在单链表的表头进行的
队列(Queue)
基本概念
一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除
注意
先进先出FIFO
不可以随意读取栈或队列中间的某个数据
基本操作
队列的顺序存储结构
队列的顺序存储
队头指针,队尾指针:队头指针front指向队头元素,队尾指针rear指向队尾元素的下一个位置(这个指针指向不是固定,得认真审题,看指针指向含义)
Q.front==Q.rear==0
进队操作:队不满时,先送值到队尾元素,再将队尾指针加1
出队操作:队不空时,先取队头元素值,再将队头指针加1
队空条件:Q.front==Q.rear==0
如果用Q.rear==MaxSize作为队满条件,会出现“假上溢”
循环队列
将顺序队列臆造为一个环状的空间,即把存储队列元素的表从逻辑上视为一个环
基本操作
队首指针进1:Q.front=(Q.front+1)%Maxsize
队尾指针进1:Q.rear=(Q.rear+1)%MaxSize
队列中元素个数:(Q.rear-Q.front+MaxSize)%MaxSize
判满
1| 牺牲一个单元来区分队空和队满,且在以“队头指针在队尾指针的下一位置作为队满的标志
队满条件:(Q.rear+1)%MaxSize=Q.front
队空条件:Q.front==Q.rear
队列中元素个数:(Q.rear-Q.front+MaxSize)%MaxSize
2| 类型中增设表示元素个数的数据成员
队空:Q.size==0
队满:Q.size==MaxSize
这两种情况都有Q.front==Q.rear
3| 类型中增设tag数据成员
队空:tag=0时,因删除导致Q.front=Q.rear
队满:tag=1时,因插入导致Q.front==Q.rear
队列的链式存储结构
实际上是一个同时带有队头指针和队尾指针的单链表
不带头结点的链式队列在操作上往往比较麻烦,通常使用带头结点的单链
优点
单链表表示的链式队列特别适合于数据元素变动比较大的情形,而且不存在队列满且产生溢出的问题
若程序中需要使用多个队列时,与多个栈的情形一样,最好使用链式队列,这样就不会出现分配不合理和“溢出”问题”
双端队列
允许两端都可以进行入队和出队操作的队列
为升级版栈,只要栈能实现的,双端队列都能实现
类型
输出受限的双端队列:允许在一端进行插入和删除,但在另一端只允许插入的双端队列
输入受限的双端队列:允许在一端进行插入和删除,但在另一端只允许删除的双端队列
栈和队列应用
栈的应用
括号匹配
表达式求值
中缀表达式转后缀表达式
手算
1| 按照左优先原则,找到优先级最高的运算符
2| 按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数
3| 重复②直到所有运算符都被处理
4| 左优先原则:只要左边的运算符能着计算,就优先算左边的
机算
1| 遇到操作数
直接加入后缀表达式
2| 遇到界限符
①遇到左括号直接入栈; ②遇到右括号,依次弹出栈内运算符并加入后缀表达式,直到,弹出左括号为止。注意,界限符不加入后缀表达式。
3| 遇到运算符
依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式。 若遇到左括号或栈空,则停止。最后再把当前运算符入栈
中缀表达式转前缀表达式
手算
1| 按照右优先原则,找到优先级最高的运算符
2| 按照[运算符 左操作数 右操作数] 的方式组合成一个新的操作数
3| 重复②直到所有运算符都被处理
4| 右优先原则:只要右边的运算符能着计算,就优先算左边的
后缀表达式的计算
手算
从左往右扫描,每遇到一个运算符,就让运算符前面最近的两个操作数执行对应运算,合体为一个操作数
机算
1| 从左往右扫描下一个元素,直到处理完所有元素
2| 若扫描到操作数则压入栈,并返回①;否则执行③
3| 若扫描到运算符,则弹出两个栈顶元素,执行相应运算,运算结果压回栈顶,回到①
中缀表达式的计算
机算
1| 初始化两个栈,操作数栈和运算符栈
2| 若扫描到操作数,压入操作数
3| 遇到界限符或运算符,则按照中缀转后缀相同的逻辑压入运算符栈(期间也会弹出运算符,每当弹出一个运算符时,就需要再弹出两个操作数栈的栈顶元素并执行相应运算,运算结果再压回操作数栈
递归
两个条件
太多层递归可能会导致栈溢出
队列的应用
队列在层次遍历中的应用
层序遍历树
队列在计算机系统中的应用
解决主机与外部设备之间速度不匹配的问题
解决多用户引起的资源竞争问题
图的广度优先遍历
数组
数组的定义
相同类型元素构成的有限序列,线性表的推广
数组的存储结构
数组元素ai的地址:LOC(ai)=LOC(a0)+i×L(0≤i≤n)
多维数组(二维数组为例)
按行优先
数据元素aij的地址:LOC(aij)=LOC(a0)+[i×(列数)+j]×L]
按列优先
数据元素aij的地址:LOC(aij)=LOC(a0)+[j×(行数)+i]×L]
特殊矩阵
对称矩阵
关于主对角线对称的矩阵
计算方法
按行优先
1| 先找出每一行的元素个数(第1行到第i行l
2| 将每一行个数累加求和即可得到表达式
3| 上下三角区的元素将表达式中i和j互换即可
按列优先
步骤与按行相同,将行改成列即可
三角矩阵
下三角矩阵
上三角区的所有元素均为同一常量
存储完下三角区和主对角线元素之后,紧接着存储对角线上方的常量一次即可
存储常量的下标k为n(n+1)/2(数组以0开头)
上三角矩阵
下三角区的所有元素均为同一常量
存储完上三角区和主对角线元素之后,紧接着存储对角线下方的常量一次即可
三对角矩阵
又称带状矩阵,以对角线为中心的三条对角线的区域,其他区域的元素都为0
在一维数组存放的下标为k=2i+j-3
已知k,i=(k+1)/3+1 向下取整即可 j=k-2i+3
计算元素下标之间的对应关系的方法一致 在审题时,一定要注意数组的下标是从0开始还是从1开始 还有矩阵的下标是从1开始还是从0开始
稀疏矩阵
矩阵中非零元素的个数t,相对矩阵元素的个数来说非常少,即s>>t的矩阵称为稀疏矩阵
存储方式
三元组
将非零元素及其相应的行和列构成一个三元组(行标,列标,值)
注意:稀疏矩阵压缩存储后便失去了随机存取的特性
稀疏矩阵的三元组既可以采用数组存储,也可以采用十字链表法存储