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