数据结构

数据结构的知识点来啦！数据结构的知识但复杂难懂，很多人在期末复习时都无从下手，下图从数据结构基本概念 、线性表 、栈和队列、树与二叉树 、 查找技术 等知识点进行详细的归纳与总结，期末考试轻松拿高分！

数据结构

• 数据结构基本概念
  • 数据
  • 数据元素
    • 最小的数据元素是数据项
  • 数据结构
    • 逻辑结构
    • 存储结构
      • 順式存储结构
      • 链接存储结构
• 线性表
  • 顺序表
  • 单链表
• 栈和队列
  • • 先进后出
    • 栈顶
      • 可插可删
    • 栈底
      • 不可操作
  • 队列
    • 先进先出
    • 队头
      • 出队
    • 队尾
      • 入队
• 树与二叉树
  • 二叉树
    • 几种特殊的二叉树
      • 斜树
      • 满二叉树
      • 完全二叉树
    • 二叉树的遍历
      • 前序
      • 中序
      • 后序
      • 层序
    • 二叉树的存储结构
      • 順式存储结构
      • 二叉链表
  • 最优二叉树
    • 哈夫曼算法
      • 带全路径长度
        • 路径长度与结点权值乘积之和
      • 哈夫曼树（最优二叉树）
        • 带全路径长最小
        • n 个叶子结点的哈夫曼树有 2n-1 个结点
        • 构造哈夫曼树
          • 递归取最小两个权值结点合并
    • 哈夫曼编码
      • 等长编码
        • n 个字符需要 log2 n
      • 不等长编码
  • 堆与优先队列
    • • 每个结点的值都小于或等于其左右孩子的值（小根堆），反之则为大根堆
• • 图的逻辑结构
    • 基本术语
      • 度 入度 出度
      • 无向完全图
        • n 个顶点的无向完全图有 n ✖️ （ n-1 ） /2 条边
      • 有向完全图
        • n 个顶点的有向完全图有 n ✖️ （ n-1 ）条边
      • 连通图
        • 无向图任意顶点均有路径
      • 连通分量
        • 无向非连通图的最大连通子图
      • 强连通图与强连通分量
        • 类比上述 强适用于有向图的场景
    • 图的遍历
      • 深度优先遍历 DFT
        • 依次
      • 广度优先遍历 BFT
        • 按层
  • 图的存储结构
    • 邻接矩阵
      • 深度遍历与广度遍历的时间复杂度均为 O （ n^2
      • 空间代价为 O （ n^2
    • 邻接表
      • 查找顶点所有邻接点所需时间为 O （ e ） 深度遍历与广度遍历的时间复杂度均为 O （ n+e
      • 空间代价为 O （ n+e
  • 最小生成树
    • Prim 算法
      • 从起点出发，依次找最近
    • Kruskal 算法
      • 加入最短边，合并，直到连通为止
  • 最短路径
    • Dijkstra 算法
      • 按长度递增次序产生最短路径
  • 有向无环图
    • AOV 网与拓扑排序
      • AOV
        • 顶点表示活动，弧表示活动之间的优先关系
      • 拓扑排序
        • 从起点到终点的一个序列即为拓扑排序
    • AOE 网关键路径
      • AOE
        • 对比 AOV 网，路径带权
      • 关键路径
        • 最早开始时间与最晚开始时间相等的活动所在的路径
      • 关键活动
        • 关键路径上的活动
• 查找技术
  • 线性表查找技术
    • 顺序查找 O （ n
    • 折半查找 O （ log2n
  • 树表查找技术
    • 二叉排序树
      • 左子树所有结点值小于根结点
      • 右子树所有结点值大于根结点
      • 左右子树也是二叉排序树
      • 查找性能在 O （ log2n ） O （ n ）之间
    • 平衡二叉树
      • 根结点的左右子树深度最多差
      • 根结点的左右子树也是平衡二叉树
      • 不平衡情况调整
        • LL
          • 顺时针旋转，改子树位置
        • RR
          • 逆时针旋转，改子树位置
        • LR
          • 左子树逆时针，再改子树位置
            • 整体顺时针，改子树位置
        • RL
          • 右子树顺时针，再改子树位置
            • 整体逆时针，改子树位置
  • 散列表查找技术
    • 散列函数
      • 直接定址法
      • 除留取余法
      • 平方取中法
    • 处理冲突的方法
      • 开放定址法
        • 平均查找长度
• 排序技术
  • 插入排序
    • 直接插入排序
      • 适用于基本有序序列
    • 希尔排序
  • 交换排序
    • 起泡排序
    • 快速排序
  • 选择排序
    • 简单选择排序
    • 堆排序
  • 归并排序
    • 二路归并排序
      • 适用个数较多序列
  • 时间复杂度
    • 直接插入排序 简单选择排序 起泡排序
      • O（n^2
    • 堆排序 快速排序 归并排序
      • O（nlog2n
    • 希尔排序
      • O（n^2）～O（nlog2n
  • 空间复杂度
    • 归并排序
      • O（n
    • 快速排序
      • O（log2n）～O（n
    • 其他
      • O（1
  • 稳定性
    • 稳定
      • 直接插入排序 起泡排序 归并排序
    • 不稳定
      • 希尔排序 快速排序 简单选择排序 堆排序