数据结构思维导图

一张图带你了解数据结构。数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。该导图是基于严蔚敏的数据结构一书。 如果有帮到你，不妨动动手指帮我点赞呀！

数据结构

• 概述
  • 数据
    • 数据元素是基本单位
    • 数据项是数据的最小单位
  • 算法
    • 特征
      • 有穷性
      • 正确性
      • 可行性
      • 输入
      • 输出
    • 设计要求
      • 正确性
      • 可读性
      • 健壮性
      • 效率与低存储需求
  • 时间复杂度
    • 区别logn，n，n^2,1
  • 空间复杂度
• 线性表
  • 顺序表
    • 结构特点
      • 存在唯一的第一个数据元素
      • 存在最后一个数据元素
      • 除第一个，每个都有一个前驱
      • 除第一个，每个都有一个后继
    • 顺序表示和实现
  • 单链表
    • 结点插入
    • 结点删除
  • 静态链表
  • 循环链表
  • 双向链表
    • 结点插入
    • 结点删除
  • 受限线性表
    • 栈
      • 应用
        • 后序求值
        • 中序转后序
        • 中序转前序（前序求值）
    • 队列
      • 循环队列的实现
• 数组和广义表
  • 存储
  • 对称矩阵的压缩
• 树和二叉树
  • 基础概念
    • 结点
    • 度
      • 结点的子树数
    • 叶子结点
      • 度为0的结点
    • 森林
  • 树
    • 二叉树
      • 五种基本形态
        • 空二叉树
        • 仅有根结点的二叉树
        • 右子树为空的二叉树
        • 左右子树均非空的二叉树
        • 左子树为空的二叉树
      • 性质
        • 1.第i层至多有2的i-1次方个结点
        • 2.深度为k，至多有2的k次方减一个结点
        • 3.N0=N2+1
        • 具有n个结点的完全二叉树的深度为㏒n－1（底为2）
        • 完全二叉树左右孩子与根结点的关系
      • 存储结构
        • 链式存储结构
          • 在含有n个结点的二叉链表中有2n个链域，有n+1个空链域
      • 遍历
        • 先序遍历
          • 先访问根结点
        • 中序遍历
          • 中间访问根结点
        • 后序遍历
          • 最后访问根结点
      • 线索化及其存储结构
        • 添加两个标志域，标志为0指向孩子，标志为1指向后继
    • 一般树
      • 树和二叉树的转化
        • 孩子兄弟表示法
      • 遍历
        • 先根遍历
          • 先访问根结点，然后依次先根遍历子树
        • 后根遍历
          • 先依次后根遍历子树，然后访问根结点
    • 森林
      • 森林与二叉树的转化
        • 孩子兄弟表示法
      • 遍历
        • 先序遍历
          • 访问森林中第一棵树的根结点 先序遍历第一棵树中根结点的子树森林 先序遍历除去第一棵树的森林
        • 中序遍历
          • 类似
    • 最优二叉树（赫夫曼树）
      • WPL的计算
• 图
  • 图的概念
  • 图的存储结构
    • 邻接矩阵
    • 邻接表
    • 十字链表
    • 邻接多重表
  • 图的遍历
    • DFS
    • BFS
  • 最小生成树
    • Prim
    • Kruskal
  • 有向无环图
    • 拓扑排序
    • AOV
    • AOE
      • 关键路径
      • 最短路径
        • 迪杰斯特拉算法
        • 弗洛伊德算法
• 查找
  • 查找概念
  • 静态查找
  • 折半查找
    • 判定树
  • 二叉排序树
  • 平衡二叉树
    • LL
    • LR
    • RR
    • RL
  • hash表
    • 构造方法
      • 掌握除留余数法
    • 处理冲突的方法
      • 开放定址法
        • 掌握线性探测再散列
      • 再哈希法
      • 链地址法
      • 建立公共溢出区
    • 查找效率
      • 哈希函数
      • 处理冲突的方法
        • 平均查找长度
      • 哈希表的装填因子
        • α=表中填入的记录数/哈希表的长度
• 查找
  • 插入排序
    • 直接插入排序
    • 2-路插入排序
    • 表插入排序
  • 希尔排序
    • 不稳定排序
  • 冒泡排序
  • 快速排序
    • 平均时间性能最好
  • 选择排序
    • 简单选择排序
    • 堆排序
  • 归并排序
  • 基数排序
    • 稳定排序