数据结构

自用数据结构408导图、空闲地址既向同义词开放，又向非同义词开放、H(key)为散列表;m表示散列表表长;di为增量序列、避免非同义词发生冲突，用链式存储同义词，便于插入和删除。

数据结构

• 逻辑结构
  • 线性结构
    • 线性表
      • 顺序结构
        • 顺序表
      • 链式结构
        • 单链表
          • 操作
            • 增
            • 删
            • 改
            • 查
        • 双链表
          • 操作
            • 增
            • 删
            • 改
            • 查
        • 循环链表
          • 操作
            • 增
            • 删
            • 改
            • 查
        • 静态链表
          • 操作
            • 增
            • 删
            • 改
            • 查
    • 栈
      • 概念
      • 顺序结构
      • 链式结构
    • 队列
      • 概念
      • 顺序结构
      • 链式结构
    • 栈和队列的应用
      • 栈
        • 括号匹配
        • 表达式求值
          • 
        • 递归
      • 队列
        • 层次遍历
          • 树的层次遍历
          • 图的广度优先遍历
        • 计算机系统
    • 数组特殊矩阵
      • 特殊矩阵的压缩存储
        • 对称矩阵（方阵）
          • 
        • 三角矩阵
          • 
        • 三对角矩阵（带状矩阵）
          • 
      • 稀疏矩阵
    • 串
      • 定义
        • 顺序存储
        • 链式存储
      • 概念
        • 主串
        • 子串
        • 模式串
      • 实现
      • 串的模式匹配
        • 简单模式匹配算法（Index算法）
          • 逐个与模式串对比，最坏时间复杂度O(nm)
        • KMP算法
          • 核心：模式串的匹配值的分析（不算高频考点也并不难，重复做题几次即可）
  • 非线性结构
    • 树形结构
      • 定义
        • 概念
          • 
        • 性质
          • 
            • 区分：
      • 二叉树
        • 概念
          • 定义
            • 二叉树的五种情况
              • 
            • 特殊的二叉树
              • 满二叉树
              • 完全二叉树
              • 概要
              • 二叉排序树
                • 左<根<右
              • 平衡二叉树
                • 树上任一结点等等左子树和右子树的深度（高度）之差不超过1
            • 二叉树的性质
              • 
                • N0=N2+1
                • N=N0+N1+N2
                • N=B+1；B=N1+2N2
          • 存储结构
            • 顺序存储
              • 
            • 链式存储
              • 
        • 操作
          • 遍历
            • 先序遍历
              • 先序和后序不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系
            • 中序遍历
            • 后序遍历
          • 线索二叉树
            • 
              • 方便找前驱和后继
        • 应用
          • 并查集
            • 用森林表示全集合，用树表示互不相交的子集
            • 操作
              • 查根
              • 并树
                • 优化：小树并大树
          • 哈夫曼树
            • 定义
              • 带权路径长度（WPL）最小的二叉树称为哈弗曼树（最优二叉树）
            • 哈弗曼编码
              • 固定长度编码和可变长度编码（其中前缀编码）
      • 树和森林
        • 概念
          • 定义
          • 存储结构
            • 双亲表示法（顺序）
              • 
            • 孩子表示法（顺序+链式）
            • 孩子兄弟表示法（链式）
            • 
        • 操作
          • 遍历
            • 
          • 与二叉树的转换
            • 
        • 应用
          • 并查集
    • 图
      • 定义
        • 有向图、无向图
        • 简单图、多重图
        • 子图
        • 连通、连通图和连通分量（无向图）
          • 无向图中，点V能到点W，称为连通
          • 图中任意两个顶点都是连通的
          • 无向图中的极大连通子图，少一条边就使得成为非连通图
        • 强连通图、强连通分量（有向图）
          • 有来有回称为强连通，可以连成环
          • 图中任意两点都是强连通，称为强连通图
          • 极大强连通子图称为该有向图的强连通分量
        • 生成树、生成森林
        • 顶点的度，入度和出度
        • 边的权和网
        • 稀疏图、稠密图
        • 路径、路径长度，距离和回路
        • 简单路径、简单回路
          • 无环，只有一个环
      • 存储结构
        • 邻接矩阵法
          • 
        • 邻接表法
          • 
        • 邻接多重表
          • 
        • 十字链表
          • 
      • 遍历
        • DFS深度优先遍历
        • BFS广度优先遍历
      • 应用
        • 最小生成树（无向图）
          • 概念
            • 只有N－1条边，且权值最小
          • Prim算法
            • 加点，直到连通
              • O(V^2)，适用于边稠密
                • 
          • Kruskal算法
            • 选边，直到连通
              • O(|E|log|E|)，适用于边稀疏
                • 
        • 最短路径
          • 单源最短路径
            • BFS（无权图）
              • 层次遍历
            • Dijkstra算法（带权图）
              • 每一轮可以多添加一条边
                • 
          • 各顶点之间最短路径
            • Floyd算法
              • 求任意两点之间的最短路径，每迭代一次就多考虑一个顶点
                • 
        • 拓扑排序
          • AOV网
            • 每次选入度为零的点输出（从头输出）
              • 子主题
        • 关键路径
          • AOE网
            • 概念
              • 事件最早发生时间
              • 事件的最迟发生时间
              • 指顶点的时间限制
              • 活动的最早开始时间
              • 活动的最迟开始时间
              • 指边的时间限制
              • 一个活动的最迟开始时间和其最早开始时间的差额
                • 指活动完成的时间余量，为零时表示该活动为关键活动
            • 
• 存储结构
  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储
• 数据运算
  • 定义
    • 针对逻辑结构，指出运算的功能
  • 实现
    • 针对存储结构，指出运算的具体操作步骤
• 算法
  • 查找
    • 概念
      • 平均查找长度是所有查找过程中进行关键字的比较次数的平均值
    • 线性结构
      • 顺序查找
        • 一般线性表的顺序查找
        • 有序表的顺序查找
      • 折半查找
        • 概念
          • 二分查找，仅适用于有序的顺序表
        • 三个指针low/mid/high
          • 折半查找判定树，层数即表示比较次数
        • log2(n+1)-1
      • 分块查找
    • 树形结构
      • 二叉排序树BST
        • 概念
          • 左<根<右
        • 操作
          • 查找
          • 插入
          • 删除
        • ASL
          • 好：log2N
          • 坏：N
      • 二叉平衡树
        • 概念
          • 高度差：平衡因子（－1，0，1）
        • 操作
          • 查找
          • 插入
          • 删除
          • LL、RR、LR、RL
        • ASL
          • log2N
      • 红黑树RBT
      • B树（多路平衡查找树）
        • 概念
          • 
          • 
        • 操作
          • 
          • 
          • 
          • 
      • B+树
        • 示意图
          • 
        • 概念
          • 
      • 
    • 散列结构
      • 散列表
        • 构造方法
          • 直接定址法
            • 
          • 除留余数法
            • 
          • 数字分析法
            • 
          • 平方取中法
            • 
        • 冲突处理
          • 开放地址发
            • 概念
              • 空闲地址既向同义词开放，又向非同义词开放
            • Hi=(H(key)+di)%m
              • H(key)为散列表;m表示散列表表长;di为增量序列
            • Hi=(H(key)+di)%m
              • 线性探测法
              • 平方探测法
              • 双散列法
              • 伪随机序列法
          • 拉链法
            • 避免非同义词发生冲突，用链式存储同义词，便于插入和删除
        • 性能分析
          • 
          • 
    • 效率指标
      • 平均查找长度
        • 查找成功
        • 查找失败
  • 排序
    • 概念
      • 稳定性
        • 对应关键字相同的元素的前后位置能否保持不变
      • 衡量标准：时间、空间复杂度
      • 最少比较次数应考虑最坏情况？
    • 内部排序
      • 插入排序
        • 直接插入排序
          • 挨个对比插入
        • 折半插入排序
          • 子主题
        • 希尔排序
          • 根据增量划分小组，缩小增量直到两两交换
          • 组内使用直插
      • 交换排序
        • 冒泡排序
          • 从前往后（从后往前）两两对比交换
        • 快速排序
          • 选定pivot每次都会确定至少一个元素最终位置，再进行递归
      • 选择排序
        • 简单选择排序
          • 直接对比选择
        • 堆排序
          • 大根堆
            • 根>=左右
              • 自下而上初步调整为大跟堆
          • 小根堆
            • 根<=左右
      • 归并排序
      • 基数排序
        • 最高位优先（MSD）
        • 最低位优先（LSD）
      • 各种内部排序算法的比较和应用
        • 比较
        • 应用
    • 外部排序
      • 多路归并排序
      • 败者树
      • 置换－选择排序（生成初始归并段）
      • 最佳归并树
  • 概念
    • 度量
      • 时间复杂度
        • 
      • 空间复杂度