数据结构与算法

数据结构与算法 数据结构是计算机中存储、组织数据的方式。 数据结构是一种具有一定逻辑关系,在计算机中应用某种存储结构,并且封装了相应操作的数据元素集合。

算法与数据结构

• 线性表
  • 链式线性表有头节点(标兵)
    • 第一个节点是phead->next或head.next
  • 栈
    • 递归程序非递归实现不一定需要栈
      • 可以用DP的思想
• 图
  • 图的顶点集非空,因此没有空图
  • 连通分量
    • 极大连通子图
  • 回路就是环
    • 环一定不是简单路径
    • 简单回路除端点外,中间节点不重复
  • 简单路径的顶点不重复
  • 邻接矩阵
    • 一般主对角线上元素为0
    • 不联通为无穷大
  • 关键路径
    • 最早开始时间ve()
    • 最晚开始时间vl()
    • 活动最早开始时间e()
      • 源点的最早开始时间
    • 活动最晚开始时间l()
      • 汇点的最晚开始时间减去活动时间
    • 活动时间余量d()
      • 表示该活动的时间余量,余量为0的活动在关键路径上
    • 缩短所有关键路径的公共边才能缩短工期
    • 延长任一关键边就能延长工期
• KMP
  • 部分匹配表
    • 子串所有前缀的公共前后缀长度组成的表
  • next[]
  • nextval[]
• 排序
  • 希尔排序
    • 一种插入排序
    • 逐渐缩小增量,组内使用直接插入排序
  • 外部排序
    • 多路平衡归并
      • 每趟处理后段数变为celing(m/k)，k是路数
• 查找
  • 平均查找长度
    • 二分查找
      • 画出搜索树
        • 又称二叉判定树
      • 失败节点的父节点的平均高度
      • 成功就是算平均深度
    • Hash表查找
• 树
  • B树与B+树
    • B树
      • m阶B树的定义
        • 每个节点至多m棵子树,m-1个关键字
        • 非空B树根节点至少2棵子树
        • 非根节点至少ceiling(m/2)棵子树
          • 3,4-2
          • 5-3
        • 叶结点是查找失败的节点(实际不存在)
        • 终端结点指最底层的结点
        • 又称B-树
      • 每个元素仅出现一次
        • 数据在B树节点内部
      • 任意节点关键字恒有左右孩子
        • 任意关键字的前驱/后继恒在最低层
      • 插入时分裂
        • 中间元素升高,递归分裂
        • 分裂后, 左侧的节点恒是满的
          • 4阶B树节点分裂为2,1,1
      • 删除时合并
        • 总能转化成从底部开始的合并
        • 够借就从兄弟处借
        • 不够借就父关键字下降,终端点合并
          • 不够借就一定能合并
          • 阶为奇,合并后有m-1个关键字
          • 阶为偶,合并后有m-2个关键字
            • 注意偶数阶B树合并后的节点是非满的
        • 向根部合并
    • B+树
      • m阶B+树定义
        • 同样最多m棵子树,最少ceiling(m/2)棵子树
        • 但是关键字是对应孩子节点最大关键字
          • 因此也是m个
        • 叶结点有指向记录的指针
          • 叶节点水平链接,以便于遍历查找
          • 注意B+树的叶结点与B树叶结点的区别
  • 最小生成树
    • 当各边权重互不相同时,最小生成树唯一
    • 从不同顶点出发使用Prim算法构造的生成树不一定相同
    • 同一幅图的最小生成树边权值序列相同
  • 堆
    • 建堆
      • 数组遍历由后往前
  • AVL树
    • 删除再插入
      • 如果删除的节点是非叶节点，重新插入后树可能相同