数据结构

总结梳理数据结构的重要知识点，内容涵盖了复杂度、线性表、散列表、树、图、位图与布隆过滤器、B+树、拓扑排序、动态规划、回溯算法、贪心算法、字符串匹配、二分查找、排序、递归、分治算法。一起努力学习吧！

数据结构

• 复杂度
• 线性表
  • 遍历方式只能前进或后退，通常存储相同类型
• 散列表（哈希表）
• 树
• 图
• 位图与布隆过滤器
• B+树
  • 树有两种节点结构，一种是叶子结点一种是非叶子结点。非叶节点个数介于m/2和m之间，叶节点之间是链表关系，有一个前驱和一个后继指针。根节点数目可以不超过m/2。m叉树用来存储索引，叶节点存储值。由于B+树一般比较大，因此多数是根节点放在内存中，叶节点（索引结构）放在硬盘上
  • 子主题
  • 为了方便在数据库中迅速查找和插入而基于二叉搜索树产生的一种节点数目大于2个的树
• 拓扑排序
  • 实现拓扑排序
    • Kahn算法
      • 采用贪心算法，如果S先于T执行，则添加一条S指向T的边，所以如果顶点入度为0，则该顶点可以被执行了。 具体算法流程为：先从图中找到一个入度为0的顶点，将其输出到拓扑排序的结果序列中（打印对应代码）。并且把这个顶点从图中删除，把这个顶点可达的顶点的入度都减1。执行上面过程知道所有顶点都被输出。
    • DFS算法
      • 这里使用的是对DFS的一种改进，需要遍历所有节点，而不是只找到一个顶点到另一个顶点的最短路径就停止 先输出顶点周围连接的顶点，再输出顶点自身
  • 应用
    • 图中环的检测
  • 点和点之间有依赖关系的排序，实现可以使用有向无环图，如A->B表示B依赖于A，A先于B执行
• 动态规划
  • 把问题分解为多个阶段，每个阶段对应一个决策。记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态的往前推进
• 回溯算法
• 贪心算法
• 字符串匹配
• 二分查找
  • 时间复杂度为O(logn)，针对大的数据规模，可以用递归或循环实现。只适用于数组，因为需要随机访问，不适用于链表。必须是有序数组，且必须是静态数据（没有频繁插入删除和更改），对于动态数据可以用二叉树或散列表
• 排序
  • 排序的稳定性：待排序序列中存在相等的值，如果相等的值在排序前后相对位置不变，则该排序具有稳定性 如：2，9，3，4，8，3 。排序后为2,3,3,4,8,9。两个3相对位置不变，则为稳定的
• 递归
  • 概要
• 分治算法