0%

【知识总结】 第三章-栈、队列和数组

定义

  • 只能在栈顶进行插入和删除的线性表
  • 后进先出结构
  • 重要的数学结论:n个不同的元素,进栈顺序已知,则出栈顺序不同的排列有\(\frac{C_{2n}^{n}}{n+1}\)

顺序存储

  • 利用连续存储单元存放元素,同时附设一个栈顶指针top
  • top可以表示栈顶元素的下标(非空情况从0开始),也可以表示栈顶元素的位序(数值上等于栈大小,非空情况从1开始)
  • 前者空栈时,top为-1;后者空栈时top为0
  • 前者进栈为\(S.data[++S.top]\),后者进栈为\(S.data[S.top++]\)
  • 前者出栈为\(S.data[S.top--]\),后者出栈为\(S.data[--S.top]\)
  • 共享栈
    • 将两个栈的栈底设置在一维数组的两端,栈顶向内延申共享空间。
    • 以top表示栈顶元素下标为例
      • \(top1=-1\)时1栈为空
      • \(top2=Maxsize\)时2栈为空
      • \(top1=top2-1\)时栈满

链式存储

  • 采用链式存储的栈,优点是便于多个栈共享存储空间,提高效率,不存在栈满上溢的情况。
  • 通常用单链表实现,所有操作在表头进行
  • 对于带头结点和不带头结点的链栈,具体的实现会有不同

队列

定义

  • 只能在队头删除,在队尾插入的受限线性表
  • 先进先出

顺序存储

  • 使用连续的存储单元存放队列中的元素,附设指针front和rear。(不同教材指针定义不唯一,本笔记规定front表示队头位置,rear表示队尾元素的下一个位置)
  • 使用顺序队列存在假溢出问题,即下标到了Maxsize,但是数组中还有空位置
  • 可以改进为循环队列
    • 初始:\(front=rear=0\)
    • 入队:\(rear=(rear+1) mod Maxsize\)
    • 出队:\(front=(front+1) mod Maxsize\)
    • 队长:\((rear+Maxsize-front) mod Maxsize\)
    • 这里可以发现,最大容量实际上到不了\(Maxsize\),原因队空和队满的判断都是\(rear=front\),处理方法有三种
      • 牺牲一个单元,默认情况,即队满判断是\((rear+1) mod Maxsize=front\)
      • 增加一个size记录元素个数,以此区分队满和队空
      • 增设tag标记,删除元素后tag为0,插入元素后tag为1。初始tag为0。以此记录最近一次操作是插入还是删除来判断队满和队空

链式存储

  • 队列的链式称为链队列
  • 本质上是同时带有队头指针和队尾指针的单链表
  • 不带头结点情况
    • 当front和rear都是NULL时,队列为空
    • 出队先判断是否空,空则无法出队;不空则front指向其后继。若没有后继,则front和rear都置NULL
    • 入队先判断是否空,不空则将新结点插入到rear的后面并更新rear;空则设置front和rear都指向新结点
  • 带头结点情况(统一了操作,更方便,front此时就是头结点)
    • 当front=rear时,队列为空
    • 入队插入到rear后并更新rear
    • 出队判断是否空,空则无法出队;不空则删除front的后继。若front后继为rear,则rear=front
  • 双端队列
    • 普通情况:在两端都可以入队或出队
    • 输出受限:只能在一端出队,可在两端入队
    • 输入受限:只能在一端入队,可在两端出队

栈和队列的应用

括号匹配

  • 问题:假设输入表达式包含圆括号方括号,任意嵌套,要求判断表达式合法性
  • 算法:利用栈,遇到左括号压栈,遇到右括号则和栈中左括号进行匹配消解,不匹配则不合法。

表达式求值

  • 后缀表达式的值计算:遇到操作数压栈,遇到操作符则弹出操作数进行计算,结果压栈
  • 中缀表达式转后缀表达式:
    • 人脑方法:利用二叉树的中序遍历和后序遍历得到结果
    • 计算机算法
      • 遇到数字直接输出到后缀表达式
      • 遇到'('入栈
      • 遇到')'依次弹出栈,加到后缀表达式,直到弹出了'(',不用加到后缀表达式
      • 遇到其他运算符根据优先级规定,可能入栈,可能连续弹出,因为不好记,所以直接对照人脑方法得出的答案即可(仅限笔试)。

递归

  • 任何递归算法都可以用栈改成非递归算法
  • 当然除了用栈,也可以根据状态转移方程用dp来做

广度优先遍历

又叫做层次遍历,队列的应用

计算机系统

队列在操作系统的资源管理中也有应用:

  • 打印机数据缓冲区就是一个数据队列
  • cpu资源竞争也是进程的队列。

数组和特殊矩阵

定义

  • 数组是由\(n\)个(\(n\geq 1\))同类型数据元素构成的有限序列,每个数据元素称为一个数组元素
  • 数组下标取值范围叫做维界
  • 数组是线性表的推广
    • 一维数组可以看作是线性表
    • 二维数组可以看作是数据元素是定长线性表的线性表
    • 数组一旦被定义,维数和维界都不变
    • 除了初始化和销毁,数组只能存取元素、修改元素(不能叫插入和删除,这个应该是和线性表的区别)

存储结构

  • 数组本身是逻辑结构,但是大部分计算机语言都提供数组数据类型
  • 逻辑意义上的数组可以用计算机语言中的数组数据类型进行存储
  • \(LOC(a_i)=LOC(a_0)+i\times L(0\leq i<n)\)\(L\)是每个元素所占的存储单元个数
  • 多维数组映射方法(假设m行n列)
    • 行优先:\(LOC(a_{i,j})=LOC(a_{0,0})+[n\times(i)+j]\times L\)
    • 列优先:\(LOC(a_{i,j})=LOC(a_{0,0})+[m\times(j)+i]\times L\)

矩阵的压缩存储

  • 压缩存储:相同值元素只分配一个存储空间,零元素不分配空间,能节约存储
  • 特殊矩阵
    • 矩阵有很多相同的元素,或很多零元素,并且这些元素分布有一定规律。
    • 常见的特殊矩阵:对称矩阵、上三角矩阵、下三角矩阵、对角矩阵、三对角矩阵

对称矩阵

  • 只存放下三角部分,包括对角元素,把\(A[n][n]\)\(B[\frac{n^2+n}{2}]\)压缩表示
  • 对于\(A[i][j]\)\(i\geq j\),其前面有元素个数\(x=1+2+\cdots+i-1+j\)(二维矩阵按行优先展开为一维数组,后同),故其对应于\(B[x]\)。数组下标都是从0开始的。

三角矩阵

  • 下三角矩阵上三角区域元素为常数
  • 上三角矩阵下三角区域元素为常数
  • 注意在数学里,这个常数大都是0,但这里认为是某常数C
  • 存储和对称矩阵类似,但要多一个位置存储该常数即可

三对角矩阵

  • 又叫做带状矩阵,所有非零元素都集中在以主对角线为中心的3条对角线区域
  • 同样可以按行优先方式展开到一维数组中

稀疏矩阵

  • 对于非零元素个数远少于矩阵元素个数的情况,矩阵为稀疏矩阵
  • 采用三元组(行标,列标,值)的方式进行压缩
  • 稀疏矩阵压缩后无法随机存取
  • 稀疏矩阵的三元组可以用数组存储也可以用十字链表存储

十字链表

  • 每一行都有行头结点
  • 每一列都有列头结点
  • 数据结点除了三元组,还包括列后继指针,行后继指针