蝴蝶效应
0%

《大话数据结构》要点整理

发表于 更新于 分类于

前言

根据《大话数据结构》提取的一些书籍中的要点，根据自己习惯整理，可能对于他人不适用。整理了大部分要点，后续比较复杂的图结构和算法没有再深入整理。

绪论

  • 数据

    • 数据元素
      • 数据项

  • 逻辑结构

    数据对象之间的相互关系

    • 集合结构

    • 线性结构

    • 树形结构

    • 图形结构

  • 物理结构

    数据的逻辑结构在计算机中的存储形式

    • 顺序存储结构

    • 链式存储结构

  • 抽象数据类型

    • 数据类型

      • 原子类型

      • 结构类型

算法

  • 常见时间复杂度

    • 常数阶

    • 线性阶

    • 平方阶

    • 对数阶

    • nLogn阶

    • 立方阶

    • 指数阶

线性表

  • 顺序存储结构

  • 链式存储结构

    • 单链表

    • 静态链表

    • 循环链表

    • 双向链表

栈

  • 顺序栈

    • 两栈共享空间

  • 链栈

队列

  • 顺序队列

    • 循环队列

  • 链队列

串

由零个或多个字符组成的有限序列，又名叫字符串

  • 顺序存储

  • 链式存储

  • 匹配算法

    • 朴素模式

    • KMP

树

n(n>=0)个结点的有限集

  • 空树
    n=0

  • 度

    • 结点的度
      结点拥有的子树个数

    • 树的度
      树内个结点的度的最大值

    • 深度
      树中结点的最大层次（根为第一层）

  • 结点关系

    • 孩子

    • 双亲

    • 兄弟

    • 祖先

    • 子孙

  • 子树是否固定次序

    • 有序树

    • 无序树

  • 森林
    m(m>=0)棵互不相交的树的集合

  • 存储结构

    • 双亲表示法

      • 将每个结点顺序存储，每个结点需要记录下双亲结点的位置

      • 看重不同的关系，例如兄弟关系，孩子关系等，可以在结点出记录下对应关系的结点位置

    • 孩子表示法

      • 结点孩子排列起来，以单链表作为存储结构；头指针组成线性表，顺序结构存储img

      • 孩子双亲表示法，在结点中添加双亲指针img

    • 孩子兄弟表示法

      • 每个结点记录第一个孩子指针以及右边一个兄弟的指针img

  • 二叉树

    • 特点

      • 每个结点最多两棵子树

      • 左右子树有次序

      • 能区分左右子树

    • 特殊二叉树

      • 斜树

      • 满二叉树

      • 完全二叉树

    • 性质

      • 在二叉树的第i层上，至多有2^(i-1)个结点(i>=1)

      • 深度为k的二叉树至多有2^k-1个结点

      • 对于任何一棵二叉树T，如果叶子结点数为n0，度为2的结点数为n1，则n0 = n2 + 1

      • 具有n个结点的完全二叉树的深度为[log2,n] + 1

      • 如果对一棵有n个结点的完全二叉树的结点按层序编号

    • 存储结构

      • 顺序存储结构

        • 适合完全二叉树img

        • 不适合其他结点不规则的树，如左右斜树

      • 二叉链表img

    • 遍历算法

      • 前序遍历img

      • 中序遍历img

      • 后序遍历img

    • 线索二叉树

      • 二叉树的线索化

        • 没有左孩子，存放前序结点

        • 没有右孩子，存放后继结点

      • 遍历

        • 按顺序找左结点或者右结点

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

      • 树转二叉树img

      • 森林转换二叉树img

    • 赫夫曼树

      带权路径长度WPL最小的二叉树

      • 构造img

      • 赫夫曼编码
        已知字符集和频率集，根据频率来构造赫夫曼树。规定左分支代表0，右分支代表1，则从根结点到叶子结点经过路径分支组成的0，1序列为对应编码

      • 压缩和解压

图

由顶点的有穷非空集合和顶点之间的边的集合组成，G(V, E)，G代表图，V代表顶点集合，E代表边集合

  • 定义

    • 无向边和无向图
      G=(V, {E})，E={(A,B)…}

    • 有向边和有向图
      G=(V, {E})，E={<A,B>…}

    • 简单图

      • 不存在顶点到其自身的边

      • 一条边不重复出现

    • 无向完全图
      无向图中，任意两个顶点都存在边

    • 有向完全图
      有向图中，任意两个顶点都存在边

    • 网
      图的边或弧相关的数叫做权，带权的图

  • 存储结构

    • 矩阵

      • 邻接矩阵（有向图）img

      • 对称矩阵（无向图）img

    • 表

      • 邻接表（无向）img

      • 邻接表（有向）img

    • 十字链表

      • 优点

        • 结合了邻接表和逆邻接表，容易计算入度和出度

        • 时间复杂度和邻接表相同

        • 适合于有向图

    • 邻接多重表

    • 边集数组

  • 遍历

    • 深度优先遍历（DFS）
      原则上从顶点开始，只要不是重复的就沿着右手边走，走完一圈后，还有一些顶点没有遍历到，所以原路返回，在每一个点再检查是否有其他点没有走到，类似于树的前序遍历。核心思想也是递归原则。

    • 广度优先遍历（BFS）
      从顶点开始，将顶点设置为第一层，和顶点相关的点设置为第二层，以此类推

  • 最小生成树

    • 普里姆算法
      从已到达点（如果没有，则只有顶点）中，选择一条权重最小且能到达一个新顶点的路径，这样选择出来的路径

    • 克鲁斯卡尔算法

  • 最短路径

    • 迪杰特斯拉算法

    • 佛洛依德算法*
      D[v][w] = min{ D[v][w] , D[v][k] + D[k][w] }