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