数据结构笔记【全-408统考】【附思维导图】_408数据结构思维导图

数据结构

思维导图

绪论

基本概念

• 数据

  • 信息的载体

• 数据元素

  • 数据的基本单位

• 数据项

  • 是构成数据元素的不可分割最小单位。学生记录是一个数据元素，由学号姓名这些数据项共同组成

• 数据对象

  具有相同性质的数据元素的集合，是数据的子集

• 数据类型

  • 数据类型是一个值的集合和定义在集合上的一组操作的总称。

  • 原子类型

    • 值不可分的数据类型

  • 结构类型

    • 可分的

  • 抽象结构类型

    • 抽象数据组织及与之相关的操作

数据结构三要素

• 算法的设计取决于所选的逻辑结构，而算法的实现依赖于所选的存储结构

• 逻辑结构

  • 数据元素之间的关系，分为线性结构和非线性结构

  • 线性结构

    • 线性表，栈，队列等

  • 非线性结构

    • 树、图、集合等

  • 集合（无关系）、线性结构（一对一）、树形结构（一对多）、图状结构或网状结构（多对多）

• 存储结构

  • 顺序存储

    • 可以随机存取，只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。

  • 链式存储、

    • 只能顺序存储。不会出现碎片现象，能充分利用所有存储单元，指针要占用额外空间

  • 索引存储

    • 检索速度快，附加的索引表额外占用存储空间。增加和删除数据时也要修改索引表，会消耗不少时间

  • 散列存储

    • 也叫哈希存儲。根据元素的关键字直接计算出该元素的存储地址，
    • 其优点是检索、增加和删除结点的操作都很快：
    • 缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

• 数据的运算

  运算的定义针对逻辑结构，运算的实现针对逻辑结构

复杂度分析

算法概念与特性

• 有穷性、确定性、可行性 、输入、输出

好的算法满足

• 正确性、可读性、健壮性、效率与低存储量需求

总结：

• 逻辑结构：栈，线性表，队列
• 顺序表，单链表，邻接表，单双链表，循环链表。
  还有一些名词：顺序存储，链式存储，索引存储，散列存储（哈希存储）。

线性表

顺序存储

• 顺序表

链式存储

• 单链表、双链表、循环链表、静态链表

总结几个判空

• 没有头结点的链表判空 head==null
• 有头结点的链表判空 head->next == null
• 循环单链表的判空： L->next =L
• 循环双链表的判空: L-next == L && L->prior==L

栈和队列

操作受限

• 栈

  • 基本概念

    • 栈的数学性质

      • 出栈元素的不同排列个数为
        (n个数的排列为A!,计算完排列之后别忘了取出不合适的)

    • 基本操作

  • 顺序栈

    • 操作

      • S.top。S.top=-1

        • 进栈

          • 栈未满的情况下：S.data[++S.top]=x;

        • 出栈

          • 栈不空的情况下：x=S.data[S.top–];

        • 判空

          • S.top==-1

        • 栈满

          • S.top==MaxSize-1

        • 栈长

          • S.top+1

      • S.top=0时，即top指向栈顶元素的下一位置。则入栈操作变成S.data[S.top++]=x,出栈为x=S.data[–S.top]

    • 区分top指向的是当前栈顶元素还是下一元素

  • 链栈

  • 共享栈

    • 初始指针

      • top0=-1，top1=Maxsize

    • 栈满

      • top1-top0=1

    • 进栈操作

      • 0号栈先加一再赋值，一号栈先赋值再加一

    • 出栈

      • 相反

    • 特点

      • 更好的利用存储空间，避免上溢

• 队列

  • 基本概念

    • 队首出（删除），队尾入队（增加）

    • 判空

      • Q.frontQ.rear0
      • 子主题 2

    • 判满

      • 无法判断，继而引出循环队列

  • 循环队列

    • 三种区分队空与队满方法

      • 牺牲一个元素

        • 队满

          • (Q.rear+1)%MaxSize ==Q.front

        • 队空

          • Q.front==Q.rear

        • 元素个数

          • （Q. rear-Q. front+MaxSize）% Maxsize

      • 增设表示元素个数

      • 增设tag数据成员

      • P79页循环队列出入队示意图

  • 链式队列

  • 双端队列

    • 输出受限的双端队列
    • 输入受限的双端队列

推广

• 数组

  • 一维数组

  • 多维数组

    • 压缩矩阵

      • 对称矩阵

      • 上下三角矩阵

        • 存储元素个数比对称矩阵多一

      • 三对角矩阵

        • 特点

          • ｜i-j｜>1

      • 按行优先和按列优先

    • 稀疏矩阵

      • 可采用三元组存储

栈和队列的应用

• 栈

  • 栈的括号匹配

    • 从左到右扫描，最后栈为空才算成功匹配

  • 前中后缀表达式

    • 后缀表达式：考虑算法的优先级，没有括号 ，遇到运算符，依次弹出栈中优先级高于或等于的运算符。
    • 中缀转前缀：从右往左扫描下一元素。（先出栈的是左操作数）
    • 后缀表达式转为中缀表达式
    • 表达式之间的互相转换
    • 后缀表达式的求值
    • 习题解析王道P98页

  • 栈的递归

    • 在于能发将原始问题转换为属性相同但规模交较小的问题。

    • 递归调用过程：

      • 在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出等。而其效率不高的原因是递归调用过程中包含很多重复的计算。

• 队列

  • 队列的层次遍历

    • 层次遍历二叉树过程
    • 图的广度优先搜索（使用队列）

  • 队列在计算机系统中的应用

树与二叉树

树

• 递归的数据结构，也是一种逻辑结构

• 定义

  • 两个特点：前驱后继结点个数

• 术语

  • 祖先，双亲，子孙，孩子，兄弟结点

  • 结点的度，树的度

    • 树的度：树中结点的最大度数

  • 分支结点，叶子结点

    • 分支结点又称为非终端结点，其度大于0

  • 结点的层次，结点的深度，结点的高度，树的高度。

    • 结点的层次：从树根开始
    • 结点的深度：从根结点开始自顶向下逐层累加
    • 结点的高度：从叶结点开始自底向上逐层累加
    • 树的高度：树中结点最大层数

  • 有序树，无序树

    • 有序树，结点位置不能互换

  • 路径，路径长度

    • 路径是，两个结点之间所经过的结点序列。而路径长度是路径上经过的边的个数

• 树的性质

  • 树中的结点数等于所有结点数+1
  • 度为m的数中第i层至多有
  • 总结计算：由n=分支数+1，即n=1+n1+2n2+3n3+4*n4=n0+n1+n2+n3+n4

二叉树

• 概念

  二叉树是有序树

  • 二叉树和度为2度有序树区别

    度为2度有序树，结点至少三个，而二叉树可以为空
    二叉树的次序是绝对的，不能颠倒

  • 特殊二叉树

    • 满二叉树

      • 满

    • 完全二叉树

      • 左孩子

    • 二叉排序树

      • 相比根结点左小右大

    • 平衡二叉树

      • 左右子树的深度相差均不超过1

  • 二叉树的性质

    • 非空二叉树n0=n2+1

  • 二叉树的存储

    • 顺序存储
      • 适合满二叉树和完全二叉树
      • 存储时建议数组下标从1开始
    • 链式存储
      • 左右指针和数据域
      • 在n哥结点的二叉链表中，含有n+1个指针域

  • 总结：

    • 计算完全二叉树的结点个数，根据叶子结点进行计算。需要注意，最多最少的情况下，可能是倒数第二层最右边的代表叶子结点，也可能是最后一层代表。
    • 完全二叉树，根据结点个数和叶子结点个数求最多，需要考虑最后一层为奇数还是偶数，偶数的一半为消耗上层叶子结点个数，奇数要+1
    • 考虑极端情况下，结点个数
    • 根据树的那几个性质进行推算，注意奇偶数目

• 操作

  • 三种遍历

    • 先序遍历

      • 前缀表达式

    • 后序遍历

      • 中缀表达式（需要加界限符）

    • 中序遍历

      • 后缀表达式

    • 时间复杂度，空间复杂度都为O(n)

  • 线索二叉树

    • 引入线索二叉树的目的
    • 规定
    • 构造过程

  • 二叉树的计算题

    • 空指针的个数

    • 中序+后序推导

    • 中序+前序推导

    • 层序+中序推导

      • 王道第五章 08

• 应用

  • 排序二叉树

    • 平衡二叉树

  • 哈夫曼树

树，森林

• 树的存储结构

  • 双亲表示法

    • 利用结点唯一双亲的性质

    • 可以很快得到每个结点的双亲，但是求孩子结点，需要遍历整个结构

    • 区别二叉树的顺序存储和树的顺序存储

      • 二叉树的顺序存储即代表了结点的编号，也指示了各结点之间的关系。

  • 孩子表示法

    • 将每个结点的孩子结点都用单链表链接起来形成一个线性结构，n个结点n个孩子链表
    • 寻找子女非常方便，但是寻找双亲需要遍历

  • 孩子兄弟表示法

    • 二叉链表表示：每个结点分为三部分，结点值，指向结点第一个孩子结点的指针，指向结点下一个兄弟结点的指针。

    • 通过第二个指针可以方便找到结点的所有兄弟结点。

    • 最大优点，方便实现树转换为二叉树的操作，易于查找孩子结点。

      • 子主题 1

    • 缺点是从当前结点查找父结点比较麻烦

• 树，森林与二叉树的转换

  给定一颗树找到可以唯一的一颗二叉树与之对应，物理结构上看，他们的二叉链表上一样的，只是解释不同

    - 二叉树转换为树或者森林也是唯一的
  1

  • 树转二叉树的规则

    • 左孩子右兄弟
    • 补充：树转成二叉树时，若有几个叶子结点具有共同的双亲，则转换成二叉树后之后一个叶子结点，

  • 树转二叉树的画法

    • 1。在兄弟结点之间加一条线
    • 2。对每个结点，只保留它与第一个孩子的连线，而与其它孩子的连线全部抹掉
    • 3。以树根为轴心，顺时针旋转45度

  • 森林转化为二叉树

    • 先将每棵树转换为二叉树，然后把其他树视为右兄弟。与上面相同

  • 森林转为二叉树的画法

    • 1。将森林的每棵树转换为响应的二叉树，
    • 2。每棵树的根也可视为兄弟关系在每棵树的根之间加一根连线
    • 3。以第一棵树的根为轴心顺时针旋转45度

  • 二叉树转换为森林的规则

    • 如果二叉树非空，则将二叉树的根和左子树视为第一棵树，将其右链断开
    • 二叉树的右子树又可以视为由森林转换的二叉树，直到只剩下一颗右子树为止
    • 将每棵二叉树分别转换

• 树和森林的遍历

  • 树的两种方式

    • 补充：无法使用中根遍历，因为可能会有多个孩子。也可使用层次遍历

    • 先根遍历

      • 对应二叉树的先序序列

    • 后根遍历

      • 对应二叉树的中序序列

  • 森林的两种遍历方式

    • 先序遍历森林

      • 对应二叉树的先序遍历

    • 中序遍历森林

      • 对应二叉树的中序遍历

• 补充总结：

  • 考试可能会考，树到二叉树之后的右指针变化，右孩子结点个数，原来两个结点之间的关系。需要我熟练掌握转换。没事多画画，带入特殊构造点。哈哈
    声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/621926