数据结构与算法

Chapter6 图

图的存储
```
邻接矩阵与邻接表存储
```

有向图的拓扑排序

1找到入度为0的顶点，该点指向的其他点入度减一（擦去指向）
2这些入度减一（擦去指向）的顶点中，选取入度为0的顶点
重复，直到找不到入度为0的顶点。

图的遍历

深度优先DFS：从一个节点开始，向下层遍历，直到无法向下，回退至可向下遍历的点，直到所有节点被访问

广度优先BFS：从一个节点开始，遍历它的所有邻接点，再从第一个邻接点开始，如此循环

最小生成树（不唯一）

Prim求最小生成树(顶点开始发散)

    1从顶点开始，选取权值最小的边，最小边顶点加入生成树。
    2再寻找生成树内权值最小的边，最小边顶点加入生成树，循环。

Kruskal求最小生成树（加入最小边）

    1将所有的边按照权值从小到大排序
    2依次将边从小到大加入生成树
    3若加入的边使树形成回路，则舍去
    直至所有定点加入生成树

Chapter7 查找算法

顺序查找，求ASL

二分查找（折半查找）

如果序列长度为奇数，则二分中间位置确定，为中间数，两侧等长
如果序列长度为偶数，则二分中间位置为n/2取整，为小一边的数，两侧差1

散列查找（线性探测法，平方探测，链地址法），求ASL

线性探测：冲突后+1移位寻找空位
平方探测：冲突后1^2,-1^2,2^2,-2^2，...以此类推
链地址：冲突后，添加链表

冲突一次，该数据的查找次数+1,初始查找次数为1
ASL平均查找长度=sum（各数据查找次数）/数据个数

Chapter8 排序算法

插入排序类

直接插入：选取确定序列后的一个元素，向前寻找插入位置

希尔排序：按照步长，分为多个小组进行直接插入排序

交换排序类

冒泡排序：从前向后冒，一趟确定一个

快速排序：位置待定法，前后指针比较交换，一趟确定一个

选择排序类

简单选择排序：

    在待查找序列中选择最小的值，放入已确定序列末尾，一趟确定一个

堆排序：

    大顶堆：每个节点的值都 大于 或等于其子节点的值，用于升序排列
    小顶堆：每个节点的值都 小于 或等于其子节点的值，用于降序排列

    1构建二叉树堆
    2按照大/小顶堆规律，从最底层最小子树开始，向上传递子树内最大/小值
    3最底层完成后，最底层子树规模扩大一层，再向上一层传递子树内最大/小值
    4传递后应该再调整小一层规模的子树，确保每个节点大于孩子
    5循环至整个二叉树层全包含，并且向下调整完成

归并排序

分而治之，大序列分小序列排序，排序后小序列间进行排序，组成大序列，循环

基数排序

不需要比较的排序。适合大数据量
排序思想：根据数字的个位进行排序，再根据数字十位排序，百位排序，以此类推

排序算法的时间复杂度，空间复杂度