数据结构栈队列数组表
2020-06-01 17:07:35 1 举报AI智能生成
自己考研期间画的数据结构框架图，参考了大话数据结构和王道的数据结构的书，希望可以帮到大家，大家多多点赞
作者其他创作
大纲/内容
线性表
栈
（操作受限）
（操作受限）
基本概念
限制在表一端进行插入和删除操作的线性表
基本概念
限制在表一端进行插入和删除操作的线性表
特点
后进先出 LIFO
术语
溢出
上溢
栈顶指针超出了最大范围
下溢
栈顶指针超出了最小范围
分类
顺序栈
定义
用一组连续的存储单元存放，从栈底到栈顶
存储类型描述
操作
初始化
判断空
压栈
出栈
读栈顶元素
栈长度
s.top+1
评价
操作复杂度o(1)
链栈
定义
采用链式存储
存储类型描述
操作
与单链表相同
共享栈
概念
为了增加内存空间的利用率和减少溢出的可能性，
由两个栈共享一片连续的内存空间【0….m】时，
应将两栈的栈底分别设于内存空间的两端，
这样，当两个栈的栈顶在栈空间的某一位置相遇或两栈顶指针相邻（即值之差的绝对值为1）时，
才会上溢。当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。
由两个栈共享一片连续的内存空间【0….m】时，
应将两栈的栈底分别设于内存空间的两端，
这样，当两个栈的栈顶在栈空间的某一位置相遇或两栈顶指针相邻（即值之差的绝对值为1）时，
才会上溢。当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。
操作
判断空
空
top0=-1时，0号栈空
top1 = MaxSize时，1号栈空
top1 = MaxSize时，1号栈空
栈满
两栈相邻：top1-top0==1（top1>top0）
两栈顶指针值相减的绝对值为1
两栈顶指针值相减的绝对值为1
压栈
当0号栈压栈时，top0先+1，再赋值，1号栈压栈则top-1，再赋值
出栈
当0号栈出栈时，先赋值，top0-1，1号栈出栈先赋值，再top1+1
评价
操作复杂度o(1)
优点
多个栈共享一个顺序存储空间，充分利用了存储空间，
只有在整个存储空间都用完时才能产生溢出，
只有在整个存储空间都用完时才能产生溢出，
缺点
其缺点是当一个栈满时要向左、右栈查询有无空闲单元。
如果有，则要移动元素和修改相关的栈底和栈顶指针。
当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。
如果有，则要移动元素和修改相关的栈底和栈顶指针。
当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。
应用
数制转换
括号匹配
栈与递归的实现
表达式求值
前缀表达式
运算符在式子前
中缀表达式
运算符在式子中
后缀表达式
运算符在式子后
队列
（操作受限）
（操作受限）
基本概念
也是受限的线性表，只允许在一端进行插入，另外一端进行删除
特点
先进先出
分类
（实现）
（实现）
顺序存储的队列
概念
用一维数组实现
存储类型描述
操作
实现
先动指针，再赋值
先赋值，再动指针
初始化
front=rear=0
入队
将元素插入rear指针所指的位置，然后rear+1
出队
删除front所指的元素，然后front+1并返回被删除的元素
判断非空
队列为空：front==rear==0
队列为满
rear==maxSize-1
长度
rear-front
评价
容易出现假溢出
循环队列
概念
为了克服假溢出，把顺序存储的队列想象为一个首尾相连的队列
特点
首尾相连，但实质还是一维数组
操作
初始化
出队
font=(front+1)%maxSize
入队
rear=(rear+1)%maxSize
长度
(rear+maxSize-front)%maxSize
非空判断
牺牲一个单元用来区分队列空或满，
约定队头指针在队尾指针的下一个位置作为队满的标志
约定队头指针在队尾指针的下一个位置作为队满的标志
队列满：(rear+1)%maxSize==front
队列空
front==rear
长度
(rear+maxSize-front)%maxSize
在类型中添加一个标识元素个数成员
队列空
size==0
队列满
size==maxSize
类型中添加标识判断队列是否为空
空
tag=0
满
tag=1
初始化
front==rear==0
链式存储的队列
概念
实质是拥有队头指针和队尾指针的单链表
存储类型描述
操作
初始化
判断空
入队
出队
双端队列
概念
允许在队列的两端进行入队和出队的操作的队列，元素结构仍然是线性结构
分类
输出受限的两端队列
只允许在一端进行删除，但两端都可以进行插入
输入受限的两端队列
只允许在一端进行插入，但两端都可以进行删除
应用
层次遍历
计算机系统
主机与打印机
CPU资源竞争
数组
（推广）
（推广）
定义
n个相同类型的元素构成的有限序列
一维数组可看成线性表，二维数组可以看成线性表中的线性表
存储结构
按行优先
一维(以A[1...n-1]为例)：loc(ai) = loc(a[0])+i*L
二维(行列下标范围分别为[a1...b1]和[a2...b2])：
loc(a[i,j])=loc(a[a1,b1])+[(i-a1)*(b2-a2+1)+(j-a2)]*L
loc(a[i,j])=loc(a[a1,b1])+[(i-a1)*(b2-a2+1)+(j-a2)]*L
按列优先
矩阵的压缩存储
对称矩阵
需要空间：n(n+1)/2
元素下标
之间的关系
之间的关系
对称矩阵A[1...n][1...n]，
存放在一维数组B[n(n+1)/2]中
存放在一维数组B[n(n+1)/2]中
k=i(i-1)/2+j-1 (i>=j，下三角区和主对角线元素)
k=j(j-1)/2+i-1(i<j，上三角区a[i,j]=a[j,i])
三角矩阵
下三角
需要空间：n(n+1)/2+1
元素下标
之间的关系
之间的关系
下三角矩阵A[1...n][1...n]，
存放在一维数组B[n(n+1)/2+1]中
存放在一维数组B[n(n+1)/2+1]中
k=i(i-1)/2+j-1(i>=j,下三角区和主对角线元素)
k=n(n+1)/2(i<j,上三角区元素)
上三角
需要空间：n(n+1)/2+1
元素下标
之间的关系
之间的关系
上三角矩阵A[1...n][1...n]，
存放在一维数组B[n(n+1)/2+1]中
存放在一维数组B[n(n+1)/2+1]中
k=(i-1)(2n-i+2)/2+(j-i)(下三角区和主对角线元素)
k=n(n+1)/2(i<j,下三角区元素)
三对角矩阵
需要空间：2*2+(n-2)*3+1
元素下标
之间的关系
之间的关系
下三角矩阵A[1...n][1...n]，
存放在一维数组B[(n-2)*3+5]中
存放在一维数组B[(n-2)*3+5]中
k=2i+j-3
稀疏矩阵
压缩存储方式
三元组顺序表
(行标，列标，值)
(行标，列标，值)
十字链表
广义表
（推广）
（推广）
概念
n个元素组成的有穷序列，LS=（a1,a2,a3.....）
其中ai是原子项，或者是一个广义表
LS是广义表的名字，n为它的长度
其中ai是原子项，或者是一个广义表
LS是广义表的名字，n为它的长度
若广义表非空时，a1(表中的第一个元素为表头)，
其余的元素组成的子表为表尾
其余的元素组成的子表为表尾
表中括号的最大的层数为表的度（表深）
任何一个非空广义表其表头可能是原子，也可能是列表，
而其表尾必定是列表。
而其表尾必定是列表。
操作
getHead
获得表头，可能是原子，可能是列表
getTail
获得表尾，一定是列表（带括号的）
0 条评论
下一页
为你推荐
查看更多
