常用数据结构
L0xOtAnv94Y.jpg
一、序列
- 数组：顺序存储，随机访问
- 链表：链表存储，顺序访问
- 栈
- 队列
- 串
二、树
1）二叉树
2）遍历二叉树
- 前序（先中间，再左边，后右边）
- 中序（先左边，再中间，后右边）
- 后序（先左边，再右边，后中间）
3）线索二叉树
用二插链表实现的二叉树，将那些没有使用的左右指针指向前驱和后继（前驱和后继就是遍历后（例如用中序遍历）的数据序列某一个数据的前面和后面的数据），形成的二叉树为线索二叉树。一般用在经常遍历和利用前驱和后继查找结构的情况。
4）赫夫曼树：用于压缩
5）二叉排序树
根节点的左子树若不为空，则左子树所有节点都小于根节点。根节点的右子树若不为空，则右子树所有节点都大于根结点。根节点的左右子树不为空，则其都是二叉平衡树。
6）平衡二叉树
一颗左右子树高度差至多等于1的二叉排序树。添加节点的时候，根据不平衡子树左旋右，保证最后的树是平衡的。优点：查找，插入，删除时间复杂度都是：O（logn）
7）多路查找树
结点的孩子不止为两个，结点存的值补位一个。如2-3树，2-3-4树，B树，B+树
8）红黑树
也称二叉排序树。利用一个结点的属性表明这个结点是红是黑。查找等同于二叉排序树。插入和删除利用这个颜色属性来保证操作之后树还是平衡的。所以查找，插入和删除的时间复杂度都是：O(logn)。统计性能比平衡二叉树好
9）堆
二叉树，分为大顶堆，小顶堆。大顶堆的要求是每个节点的值都不大于其父节点的值，小顶堆放过来。
三、堆
1）五种构造图的方式
2）遍历：
- 深度优先：一个劲的朝一个方向使劲，当重复了就返回
- 广度优先：先从一个顶点触发，拿到这个顶点，再把与这个顶点相关的顶点放入队列，再从队列取数据，再把与这个新取的顶点相关的顶点（非重复过的顶点）放入队列，依次同理操作
3）最小生成树
- 普里姆（Prim）算法：O(n2)
- 克鲁斯卡尔（Kruskal）算法:O(e*loge)
4）最短路径
- 迪杰斯特拉（Dijkstra）算法O(n3)
- 弗洛伊德（Floyd）算法O(n3)
5)拓扑排序
- AOV网：用顶点表示活动，用弧表示优先关系的有向图
- 拓扑排序算法：O(n+e) n个顶点e条边
6）关键路径
- AOE网：用顶点表示时间，用有向边表示活动，用边的权值表示持续的时间的有向图
- 关键算法路径：O(n+e)
四、查找
1）顺序表查找
- 从第一个开始顺序查找
2）有序表查找
- 折半查找，
- 插值查找：对于均匀分布的数据，用差值查找方便
- 斐波那契查找
3）线性索引查找
- 稠密索引（每个记录有关键码，对关键码排序形成的表）
- 倒排索引（次关键码，记录号表）
- 分块索引（将记录分成多少块，块间有序，块内无序，上一个块的最大关键码小于下一个块的所有关键码）
4）散列表(Hash表)查找 处理冲突
- 开放定址法：一个地址已被入住，再找下一个空的地址
- 再散列：用多个散列函数，一个函数查找重复，再用另一个
- 链地址法：冲突了，在这个位置用链表连起来
- 公共溢出方法：用另一个hash表存储冲突的数据
五、排序（从小到达）
1）冒泡
从最后一个数据开始，让最小一个数据冒泡到第一个位置。然后第二小冒泡到第二位置。O(n2)
2）选择
从n-i-1个数据中选择最小的，找到后将其与i位置调换，重复此操作。O(n2)
3）插入
先用第一个数据放到给定位置，然后取出第二个数据，与已排序好的数据比较，插入到此有序序列的对应位置。O(n2)
4）希尔
以某个增量i为基准，先依次将k与k+i位置比较决定是否交换，然后k++。得到一个基本有序的序列，然后减小i，再进行k与k+i位置比较决定是否交换，然后k++。操作完继续i减少，直到i<=1,并操作一遍后结束。得到的序列就是有序的。O(n3/2)
5）堆
将序列构成一个堆，然后取走堆顶，让剩下的数据再构成一个堆，再依次重复操作取走。O(n*logn)
6）归并
n个数据分成n个表，肯定每个表有序，然后两两合并成n/2个有序表，再两两合并成有序，重复操作，直到只有一个表。O(n*logn)
7）快速
先通过一顿操作，将序列变成前面一部分记录都比后一部分记录小，然后分别对这两部分记录同理操作，最后，最小的一部分只有两个数（也有是一个数的，那肯定有序），小的在前面肯定有序，最后，就得知整个序列是有序的。O(n*logn)
六、时间复杂度
时间复杂度logn的出现一般是将整体分成各个子部分，然后子部分没成功，将子部分再分成子部分。复杂度一般出现在递归中或循环嵌套中
