数据结构笔记【全-408统考】【附思维导图】_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。在兄弟结点之间加一条线
      • 2。对每个结点,只保留它与第一个孩子的连线,而与其它孩子的连线全部抹掉
      • 3。以树根为轴心,顺时针旋转45度
    • 森林转化为二叉树

      • 先将每棵树转换为二叉树,然后把其他树视为右兄弟。与上面相同
    • 森林转为二叉树的画法

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

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

    • 树的两种方式

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

      • 先根遍历

        • 对应二叉树的先序序列
      • 后根遍历

        • 对应二叉树的中序序列
    • 森林的两种遍历方式

      • 先序遍历森林

        • 对应二叉树的先序遍历
      • 中序遍历森林

        • 对应二叉树的中序遍历
  • 补充总结:

    • 考试可能会考,树到二叉树之后的右指针变化,右孩子结点个数,原来两个结点之间的关系。需要我熟练掌握转换。没事多画画,带入特殊构造点。哈哈

树和二叉树的应用

  • 二叉排序树BST

    • 中序遍历可得到递增序列

    • 二叉排序树的非递归查找算法

      • 查找失败:左或右为空
    • 插入

      • 二叉排序树的插入算法
      • 构造:从空开始
    • 删除

      • 被删除的三种情况

        • 1。叶子结点,直接删除
        • 2。若只有一颗左子树或右子树,直接用子树进行代替
        • 3。如果左右子树都有,则用其直接后继(或直接前驱)代替。然后从二叉树中删除这个元素,从而转换为前两种情况(中序遍历的后继元素,)(不要忘记对替代的元素删除后进行调整)
    • 查找

      • 查找效率取决于树的高度

      • 二分查找和二叉排序树的区别和联系

        • 时间性能差不多
        • 二叉排序树的查找不唯一,相同关键字的插入顺序不同,生成的二叉排序树可能不同
        • 维护有序时,二叉排序树不需要移动,执行时间为log2n.二分查找为哦(n).所以当有序表时静态时采用顺序表作为存储结构,二分查找实现,为动态查找表时,采用二叉排序树作为逻辑结构。
  • 平衡二叉树AVL

    • 概念

      • 平衡因子

        • 左右子树的差值,只能是-1,0,1
    • 插入

      • 先检查是否会因插入导致失衡

      • 如果导致了失衡,需要进行调整。先找到距离最近的平衡因子绝对值大于1的结点A,再对以A为根的子树,进行调整到平衡。

      • 平衡二叉树的四种调整

        • LL平衡旋转(右单旋转)

          • 由于A的左孩子的左子树插入结点引起。左侧结点高,旋转到右侧
          • 最后两层看为一个整体,最上层为根结点进行右旋转一次。根结点的右结点变为新右结点的左结点。新右结点为根结点的父结点
        • RR平衡旋转(左单旋转)

          • 由于A的右孩子的右子树上插入结点引起。右侧结点高
          • 与LL相反
        • LR平衡旋转(先左后右双旋转)

          • A的左孩子的右子树上插入了一个结点
          • 先左旋C替换B,然后再右旋替换A
        • RL平衡旋转(先右后左双旋转)

          • 由于A的右孩子的左子树上插入新结点
          • 先右旋C替换B,然后左旋替换A
      • 注意️平衡二叉树根据关键字插入。

    • 平衡二叉树的查找

      • 比较次数

        • 最多比较次数相当于树的最大高度
      • 深度为h的平衡二叉树的最少结点

        • 递推公式

          • 这种情况下其非叶子结点平衡因子也都是1
      • n个结点平衡二叉树的最大深度

        • Log2n向上取整
  • 哈夫曼树和哈夫曼编码

    • 带权路径长度(WPL)最小的二叉树称为哈夫曼树

      • 哈夫曼树的wpl计算,只计算叶子结点,别看错啦
    • 哈夫曼树的构造过程

    • 哈夫曼树的特点

      • 1。每个初始结点最终都成为叶结点,权值越小的结点到根结点的路径长度越大
      • 2。构造过程共新建了n-1个结点,总共2n-1个结点
      • 3。哈夫曼树不存在度为1度结点
      • 其他补充:哈夫曼树可能构造的不唯一(可为左或者右,影响哈夫曼编码),但wpl一定是相同且最优的
    • 哈夫曼编码

      • 编码

        • 固定长度编码

          • 每个字符用相同长度的二进制表示
        • 可变长度编码

          • 不同长度的

            • 优点是对频率高的字符赋予短编码,从而使得字符的平均编码长度减短,起到压缩数据的效果
        • 前缀编码

          • 没有一个编码是另外一个编码的前缀,称这种为
      • 哈夫曼树构造哈夫曼编码

        • 权值为字符出现的次数或频度
        • 字符仅出现在叶结点上
        • 0转向左孩子,右转向右孩子
      • 哈夫曼编码长度计算

        • 遵循前缀编码
      • 补充

        • 哈夫曼编码是对于确定的字符串来讲的(根据字符串的次数建立)
    • 哈夫曼树的推广

      • 需要添加权为0的假结点,并且离根最远

图的基本概念

  • 图的定义

    • 图G是由顶点集V和边集E组成,记做G=(V,E)
    • V(G)代表顶点个数,不能为空
    • E(G)代表边关系的集合
    • |V|代表图G的顶点个数,也称为图G的阶
    • 补充:线性表可以是空表,树可以是空树,但是图不能是空图,也就是说,图不能一个顶点也没有,可以没有边,不能没有顶点
  • 有向图

    • 注意是用<v,e>表示边
  • 无向图

    • 注意是用(v,w)表示
  • 简单图

    • 一个图G若满足:①不存在重复边:②不存在顶点到自身的边,则称图G为简单图
    • 补充:数据结构中仅讨论简单图。
  • 多重图

    • 若图G中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则G为多重图。多重图的定义和简单图是相对的
  • 完全图

    • 对于无向图,E的取值范围是0到n(n-1)2,有n(n-1)/2条边的无向图称为完全图,在完全图中任意两个顶点之间都存在边。对于有向图,E的取值范围是0到n(n-1),有n(n-1)条弧的有向图称为有向完全图,在有向完全图中任意两个顶点之间都存在方向相反的两条弧。
  • 子图

    • 顶点和边的集合都是他的子集,可以说是图的子图
    • 注意:并非卩和E的任何子集都能构成G的子图,因为这样的子集可能不是图,即E的子集中的某些边关联的顶点可能不在这个V的子集中
  • 连通、连通图、连通分量

    • 在无向图中,若从顶点ν到顶点ν有路径存在,则称ν和w是连通的。
    • 若图G中任意两个顶点都是连通的,则称图G为连通图,否则称为非连通图。
    • 无向图中的极大连通子图称为连通分量
    • 若一个图有n个顶点,并且边数小于n-1,则此图必是非连通图。
    • 注意:弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图,极大连通子图是无向图的连通分量,极大即要求该连通子图包含其所有的边;极小连通子图是既要保持图连通又要使得边数最少的子图
  • 强连通、强连通分量

    • 在有向图中,若从顶点v到顶点w和从顶点w到顶点ν之间都有路径,则称这两个顶点是强连通的

    • 若图中任何一对顶点都是强连通的,则称此图为强连通图。

      • 强连通图和完全有向图区别
    • 有向图中的极大强连通子图称为有向图的强连通分量,

    • 注意:强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性,在有向图中考虑强连通性

  • 生成树、生成森林

    • 连通图的生成树是包含图中全部顶点的一个极小连通子图。
    • 若图中顶点数为n,则它的生成树含有n-1条边。
    • 对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。
    • 在非连通图中,连通分量的生成树构成了非连通图的生成森林。
  • 顶点的度,入度和出度

    • 对于有向图,顶点v的度分为入度和出度,有向图的入度与出度和相等,并且等于边数。
    • 无向图全部顶点度的和等于边数的二倍
    • 顶点的度等于其入度和出度之和
  • 边的权和网

    • 边上标的数值称为边的权
    • 有权值的图就就叫做网
    • 带权路径长度:一条路径上所有边的权值之和
  • 稠密图和稀疏图

    • 边的多少,没有具体划分,一般是E<VlogV
  • 路径、路径长度和回路

    • 两个顶点直接的路径是经过顶点的集合
    • 路径上边的数目称为路径长度
    • 第一个顶点和最后一个顶点相同的路径称回路
  • 简单路径、简单回路

    • 在路径序列中,顶点不重复出现的路径称为简单路径。
    • 除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。
  • 距离

    • 如果两个顶点直接存在路径,则最短的路径称V到E为距离
  • 有向树

    • 个顶点的入度为0、其余顶点的入度均为1的有向图,称为有向树。
  • 常见考点

    • 对于n个顶点的无向图G,

    • 对于n个顶点的有向图G

图的存储及基本操作

  • 邻接矩阵法

    • 无向图的邻接矩阵是对称的,可只存储上下三角矩阵

    • 对于无向图,每行或列非0元素的个数是改顶点的度

    • 对于有向图,行个数对应出度,列对应入度

    • 特点:容易检验出两个顶点之间是否有边相连,但是要确定多少边,必须要按行或列检测,时间代价大

      • 稠密图适合使用邻接矩阵存储表示
    • 设图G的邻接矩阵为A,An的元素An[i][j]等于由顶点i到顶点j的长度为n的路径的数目

  • 邻接表法

    • 特点

      • 无向图存储空间为O(V+2E),有向图存储空间为O(V+E)
      • 稀疏图,采用邻接表会节省存储空间
      • 可以在O(n)下找到某顶点的所有可到达邻边,但是要确定两个顶点之间是否存在边则需要在边表中进行查询,效率低
      • 无向图的度就等于结点数,只考虑度。
      • 有向图。要考虑入度和出度,出度可直接数结点个数
      • 有向图的邻接表中,一个顶点的出度只需要计算其邻接表中结点的个数,但是其顶点的入度需要遍历全部的邻接表
      • 图的邻接表表示不唯一,但邻接矩阵的表示却是唯一的
  • 十字链表

    • 有向图的一种链式存储结构

    • 特点

      • 空间复杂度
      • 如何找到指定顶点的所有出边?——顺着绿色线路找
        如何找到指定顶点的所有入边?——顺着橙色线路找
    • 图的十字链表表示是不唯一的,但一个十字链表的表示是一个确定的图

  • 邻接多重表

    • 无向图的另一种链式存储结构

    • 区别

      • 同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点
  • 四种存储的对比

  • 图的基本操作

图的遍历

  • 广度优先遍历(BFS)

    • 借助辅助队列

    • 复杂度

      • 邻接表存储时

        • 时间复杂度为O(|V|+|E|)
        • 空间复杂度最坏为O(|v|)
        • 访问
      • 邻接矩阵

        • O(V^2)
      • 分析时只需要分析访问的顶点和邻接点需要的时间

    • 广度优先生成树

      • 根据广度优先遍历得到的
      • 基于邻接表存储的广度优先生成树不唯一,
  • 深度优先遍历(DFS)

    • 借用栈

    • 类似树的先跟遍历

    • 空间复杂度

      • 空间复杂度:最好o(1)
      • 最坏o(|V|)
      • 没有特殊说明,写最坏的复杂度
    • 时间复杂度

      • 邻接矩阵

        • O(V^2)
      • 邻接表存储时

        • 时间复杂度为O(|V|+|E|)
    • 深度优先遍历邻接表的访问过程,并给出访问序列

  • 图的生成树特点

  • 图的遍历如何来确定图的连通性?有向图?无向图?

  • 求解图的连通性问题,拓扑排序,求解关键路径

图的基本应用

  • 最小生成树

    • 求最小生成树的两种方法

      • Kruskal算法

        • 每次选最小的边使两个顶点相连(原本已经连通就不选)
      • Pim算法

        • 每次选取离树最近的点加入该生成树
    • 最小生成树的概念是?

      • 唯一?多个?
  • 最短路径

    • 单源最短路径

      • BFS算法(无权图)

        • 过程?
      • Dijkatra算法(带权图,无权图)

        • 执行过程?

          • 从V1开始遍历寻找能够到达最小的顶点路径,然后加入到集合中
          • 分为n-1次执行过程,不包含开始节点,每次选取最小能到达的
        • 复杂度

        • 不适用于求带负权值的图?

        • 基于贪心

    • 每对顶点间的最短路径

      • Floyd算法(带权图,无权图)

        • 执行过程?

          • 初始:
          • 以V0为顶点进行中转
          • n 轮递推
        • 基于动态规划

  • 有向无环图:DAG图

    • 描述含有公共子式的有效工具,共享,节约空间
    • 什么是有向无环图?
    • 二叉树和有向无环图描述表达式的表示对比
  • 拓扑排序:AOV网

    • 算法步骤?

      • 输出没有前驱节点的顶点(入度为0)
    • 逆拓扑排序

      • 删除没有后继的顶点(出度为0)
    • 可以用DFS实现拓扑排序或逆拓扑排序

    • 拓扑排序不可以唯一确定一个图

    • 如果不能构成一个拓扑排序,则存在回路,即含有顶点数目大于1的强连通分量?why ?

    • 三角矩阵是一个有序的拓扑序列(可能不唯一)

  • 关键路径:AOE网

    • 关键路径

      • 最早开始时间和最晚开始时间相同的点边连成的路径
    • 求关键路径

      • 1。求事件的最早发生事件,并行取最大值
      • 2。求事件的最晚发生事件,逆过程,并行取最小
      • 3。根据1确定活动的最早发生时间。等于弧的起点的最早开始时间
      • 4。根据2确定活动的最晚开始时间,等于,弧的顶点减去弧长
      • 3,4差值为0的边的组合为关键活动,每个关键路径上的事件构成关键路径
      • 注意️,关键路径可能有多个。缩短工期时如果仅缩短一条关键路径是没用的。必须加快这个关键活动在每个关键路径都包含的
  • 可以通过什么判定有向图是否存在回路?

    • 拓扑排序和深度优先遍历,求关键路径P257

查找

基本概念

  • 平均查找长度ASL(会计算成功和失败)

    • 一次的查找的长度是需要比较的关键字次数
    • 平均查找长度是所有查找过程中进行关键字的比较次数的平均值
    • 区分,平均比较次数
    • 模拟查找过程,有序表是右叶子不存在
  • 静态查找

    • 顺序、折半、散列查找
  • 动态查找

    • 需要动态的插入或删除操作
    • 查找、散列查找

线性结构

  • 顺序查找

    • 逐个遍历
  • 折半查找(仅适用于有序的顺序存储结构)

    • 掌握代码,算法过程。
  • 分块查找

    • 又称索引顺序查找,详细见操作系统中文件系统

    • 如果索引查找和块内查找均采用顺序查找

      • ASL=LS+LI
      • ASL=(b+1)/2+(s+1)/2
      • b为将数据分为b块,每块有s个记录
    • 如果索引查找采用折半查找而块内查找均采用顺序查找

      • ASL=LS+LI
      • ASL={log2^(b+1)}向上取整+(s+1)/2

树形结构

  • 二叉排序树

  • 二叉平衡树

  • B树

    • B树的基本特点

      • 1。每个节点最多,m个子树,m-1个节点
      • 2。如果根节点不是只有自己,他就至少俩子树
      • 3。除了根节点的非叶节点都有「m/2】个子树,即最少可以是-1个关键字
    • 高度范围

    • 插入

      • 分裂:

        • 【m/2】分为两部分,左部分不动,右部分新节点,【m/2】的结点插入父节点
    • 删除

      • 如果k不在终端,需要用k的前驱代替k

      • k在终端结点(最低层非叶子结点)时

        • 直接删除:兄弟结点≥【m/2】

        • 兄弟够借

        • 兄弟不够借

          • 双亲和左或右兄弟合并
    • B树的插入、删除、查找过程

  • B+树

    • B+树了解基本概念和性质

      • 与b树的区别差异

散列表

  • 性能分析

    • 构造方法

      • 直接定址法

        • 适合关键字分布基本连续
      • 除留取余法

      • 数字分析法

      • 平方取中法

  • 冲突处理

    • 开放定址法

      • 线性探测

        • di=i
      • 平方探测

        • di=±i^2
      • 再散列

      • 伪随机序列法

    • 拉链法

      • 存在一个链表里,类似十字链表法
    • 影响冲突的三个因素

  • 查找成功、失败的ASL

  • 注意

    • 在除留取余法,除数的确定一般取小于散列表长的最大质数

    • 装填因子

      • a=表中记录数n/散列表长度m
    • 散列表

      • Asl依赖于装填因子,不依赖于n和m

      • 散列表的删除不能简单进行删除?

        搜索路径会被中断,可以标记删除

排序

内部排序

  • 插入排序

    • 直接插入排序

      • 依次将2—n个元素插入到前面已排好序的子序列中,比较是从右到左比较
    • 折半插入排序

    • 希尔排序

      • 对于i+nd上的元素进行直接插入排序,然后缩小到d=1
      • 大规模数据很高效
  • 交换排序

    • 冒泡排序

      • 最好比较n-1次
      • 每次都可以将一个元素放到最终位置上
    • 快速排序

      • 分置思想:每次排序形成一个左边小右边大的序列
  • 选择排序

    • 简单选择排序

      • 从后面未排序的序列中找到最小的放到前面,区分插入排序
    • 堆排序(重点)

      • 过程:先按照层次遍历建立好二叉树,然后进行调整,调整是自下而上(自右向左)进行。之后再自上而下。大根堆是和最大的优先交换,小根堆是刚好相反。
      • 如果输出堆顶需要先将最下面的替代顶,然后从上到下调整,调整是和最大的进行互换。
      • 排序算法适合关键字较多的情况下。如1亿个选出100个最大的
      • 堆排序的复杂度?
      • 插入元素和删除元素的复杂度?
  • 归并排序

    • 最好最坏相同

      • 10tb大文件排序
  • 基数排序

    • 从低位开始串联(默认是最低位优先)

外部排序

  • 外部排序

    • 多路归并排序

各种排序算法的比较p346页,很重要。

基于比较的排序,最少的比较次数

选择排序和归并排序的比较次数和初始状态无关

字符串模式匹配

考纲要求:统考大纲只要求掌握字符串模式匹配,需重点掌握KMP匹配算法的原理及next数组的推理过程,手工求next数组可以先计算出部分匹配值表然后再变形,或根据公式来求解。了解 nextval数组的求解方法。

模式匹配

  • 子串的定位操作称为串的模式匹配,是求子串在主串的位置

匹配方式

  • 暴力匹配

    • 复杂度为O(m*n)
  • KMP

    • 优点

      • 主串不回溯
    • 前缀和后缀匹配

      • 串的前缀:包含第一个字符,且不包含最后一个字符的子串
      • 串的后缀:包含最后一个字符,且不包含第一个字符的子串
      • 通过前缀和后缀可以求出PM表
    • 求解NEXT数组

      • NEXT数组的第一个和第二个分别为0和1
      • Next数组等于PM表右移,(然后整体+1,要看首位是-1还是0)
      • 或者按王道课上面的直接找前面相同的最大前缀和后缀 ,最后要+1 。abax 对x前面的aba进行分析为 ab ab最长,next就是 2+1;如果是 ababac x 那么next就是1
  • 改进KMP

    • 求nextval数组
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/WeDon_t/article/details/111043790

智能推荐

服务器设置虚拟内存有什么好处,高频率内存有哪些优势?虚拟内存是什么-程序员宅基地

文章浏览阅读601次。为增进大家对内存的认识,本文将为大家介绍高频率内存的优势。此外,小编还将对虚拟内存加以探讨。我们每天都在同内存打交道,但大家对内存真的了解吗?上篇文章中,我们对服务器内存以及服务器内存技术有所介绍,为增进大家对内存的认识,本文将为大家介绍高频率内存的优势。此外,小编还将对虚拟内存加以探讨。如果你对内存及其相关知识具有兴趣,不妨继续往下阅读哦。一、高频率内存优势由于决定内存性能的核心因素有内存容量、..._服务器内存频率高有什么好处

微信小程序使用echarts真机调试报错:HTMLCanvasView is not defined_html canvas is not defined-程序员宅基地

文章浏览阅读3.6k次,点赞4次,收藏8次。报错内容:解决办法:给组件传入force-use-old-canvas="true"就可以在真机调试里展示了。重点:发布线上时,一定要将这句去掉,现在只是不支持真机调试,线上是可以使用的。重点:发布线上时,一定要将这句去掉,现在只是不支持真机调试,线上是可以使用的。重点:发布线上时,一定要将这句去掉,现在只是不支持真机调试,线上是可以使用的。<view style="width:..._html canvas is not defined

计算机基础知识 常见简答,第一章 计算机基础知识(多选和简答)及答案-程序员宅基地

文章浏览阅读457次。计算机第一章计算机基础知识多项选择题(有两个或两个以上正确答案)1、下列说法中,正确的是________。A、一个汉字用1个字节表示 B、在微机中,使用最普遍的字符编码是ASCII码C、高级语言程序可以编译为目标程序 D、ASCII码的最高位用作奇偶校验位2、文件型(外壳型)计算机病毒主要感染扩展名为________。A、COM B、BAT C、EXE D、DOC3、..._达成某一任务的指令的会合称为语言

[SceneKit专题]25-如何制作一个像Can-Knockdown的游戏-程序员宅基地

文章浏览阅读232次。说明SceneKit系列文章目录更多iOS相关知识查看github上WeekWeekUpProject本教程将包含以下内容:在SceneKit编辑器中建立基本的3D场景.编程加载并呈现3D场景.建立仿真物理,如何应用力.通过触摸与3D场景中的物体交互.设计并实现基本的碰撞检测.开始开始前,先下载初始项目starter project打开项目,简单查看一下里面都有些..._can knockdown1下载

Unity Shader的结构_unity的扩展sprites的shader-程序员宅基地

文章浏览阅读1.3k次。材质和Unity Shader在unity中,需要配合使用材质Material和Unity Shader才能达到需要的效果流程创建一个材质→创建一个Unity Shader,并把它赋给上一步中创建的材质→把材质赋给要渲染的对象→在材质面板中调整Unity Shader的属性,以得到满意的效果Unity中的材质Unity中的材质需要配合一个GameObject的Mesh或者Particle Systen组件来工作,它决定了我们的游戏对象看起来是什么样子的Unity中的Shader为了和前面通用的_unity的扩展sprites的shader

spring cloud 的断路器(Hystrix) 依赖添加注意点_hystrix最新依赖-程序员宅基地

文章浏览阅读3.6k次。最新的Hystrix 依赖都是隶属于netfix下,这样@HystrixCommand 和@EnableHystrixDashboard 才能使用&lt;dependency&gt; &lt;groupId&gt;org.springframework.cloud&lt;/groupId&gt; &lt;artifactId&gt;spring-cloud-starter-netf..._hystrix最新依赖

随便推点

Qt之文本编码转换_qt 将txt文件转换成字符串-程序员宅基地

文章浏览阅读844次。一、QTextCodecQTextCodec类提供了文本编码转换功能。指定字符集对文本进行转换。1.Qt程序中所有要显示到界面上的字符串最好都是用tr()函数;代码如下(示例):QTextCodec::setCoderForTr(QTextCodec::codecForName("UTF-8"));QLabel label;label.setText(QObject::tr("你好,世界!"));2.对于不是要显示到界面上的字符串中如果包含了中文,可以使用QString()进行编码转换。代_qt 将txt文件转换成字符串

在idea上使用git建立连接gitee上的仓库_the breanch to pull from should be selected-程序员宅基地

文章浏览阅读2k次。error: failed to push some refs to 'https://gitee.com/liyue25/test.git'To https://gitee.com/liyue25/test.githint: Updates were rejected because the remote contains work that you dohint: not have locally. This is usually caused by another repository push_the breanch to pull from should be selected

day11-函数作业_写一个自己的rjust函数,创建一个字符串的长度是指定长度,原字符串在新字符串中右-程序员宅基地

文章浏览阅读94次。写一个自己的rjust函数,创建一个字符串的长度是指定长度,原字符串在新字符串中右对齐,剩下的部分用指定的字符填充。写一个自己的index函数,统计指定列表中指定元素的所有下标,如果列表中没有指定元素返回-1。写一个自己的replace函数,将指定字符串中指定的旧字符串转换成指定的新字符串。编写一个函数,提取指定字符串中所有的字母,然后拼接在一起产生一个新的字符串。写一个自己的endswith函数,判断一个字符串是否已指定的字符串结束。写一个自己的upper函数,将一个字符串中所有的小写字母变成大写字母。._写一个自己的rjust函数,创建一个字符串的长度是指定长度,原字符串在新字符串中右

spring自定义全局异常_18jzz大全-程序员宅基地

文章浏览阅读1.3k次。spring自定义全局异常背景学习目标案列背景在springmvc的controller中程序员经常要封装错误对象返回错误,前端显示错误文案。通过spring的异常处理器,来进行自定义异常处理学习目标学习全局异常拦截器处理controller所有的异常的返回封装定义枚举异常码,设计自定义异常案列创建枚举异常码,定义系统异常情况/** * @author tianjz */..._18jzz大全

[py]你真的了解多核处理器吗? 了解多线程-程序员宅基地

文章浏览阅读95次。越来越多的人搞爬虫,设计到多线程爬取, 还有一些机器学习的一些模块也需要这玩意, 感觉自己不会逼格不高. 抽时间赶紧玩一玩这东西, 希望提高对软件的认知和归属感,不要太傻.cpu内部架构参考你知道CPU是如何工作的?-视频CPU核心越多越好?你的CPU可能正在养老!你真的了解多核处理器吗?1.双核≠双性能多核不一定会使你的手机或电脑速度更快,但它将提高你的PC的整体性能,这是一个...

XBee模块实现QGC与PX4飞控的组网通信连接_xbee实现多机控制-程序员宅基地

文章浏览阅读2k次,点赞5次,收藏18次。本篇博客介绍如何利用XBee模块实现QGC地面站与飞控的通信_xbee实现多机控制

推荐文章

热门文章

相关标签