3.图

3.1.最小生成树（Prim和Kruskal）

408数据结构学习笔记——图的应用_江南江南江南丶的博客-CSDN博客_408数据结构

MST不唯一优先使用Kurskal

1.Prim算法：每次选择一个新的未连通的顶点（选点）

①从某一个顶点开始构建最小生成树，依次加入当前剩余顶点中代价最小的顶点，直到加入所有顶点

②时间复杂度：O(| |)

③适用：稠密图

2.Kruskal：每次选择未被选取过且权值最低的边（选边）

①每次选择代价最小的一条边，使该边的两个顶点相通，但是，如果原本就相通的两个顶点的边就不选，直到所有顶点相通

②时间复杂度：O( )

③适用：稀疏图

3.2.最短路径（Dijkstra和Flyod）

408数据结构学习笔记——图的应用_江南江南江南丶的博客-CSDN博客_408数据结构

1.Dijkstra（单源最短路径）：每次选择一个当前已知最短路径的顶点加入顶点集，然后再经过改顶点更新路径

①选择v1：

②选择v6：

③选择v5：

④选择v2：

⑤选择v4

⑥选择v3：

时间复杂度：O（ ）

不适用：权值出现负值

2.floyd（多源最短路径）：依次选择图中的顶点加入路径，若经过改顶点到达其他顶点的权值更低，则将该顶点加入到达该点的路径

空间复杂度：创建两个二维数组O(n2)

时间复杂度：三个for循环O(n3)

3.3.有向无环图

3.3.1.描述算式

3.3.2.拓扑排序

1. 从AOV网中选择一个没有前驱的顶点输出
2. 在AOV网中删除该顶点和所有以它为起点的顶点
3. 重复1、2直到AOV网中没有顶点

1→2→4→3→5

3.3.3.关键路径

408数据结构学习笔记——图的应用_江南江南江南丶的博客-CSDN博客_408数据结构

3.4.图的数据结构

1.邻接矩阵（顺序存储）：无向图是实对称矩阵

#define MAXVEX 100    //最大顶点数
typedef struct Graph {
    char vexData[MAXVEX];    //一维数组，存放顶点数据
    int Edge[MAXVEX][MAXVEX];    //二维数组，存放邻接矩阵
    int vexNum, edgeNum;    //顶点数和弧数
}Graph;

2.邻接表（链式存储）

6.2.2图的存储结构——邻接表法_123_YQH的博客-CSDN博客_邻接表法

#define MAXVEX 100
typedef struct EdgeNode {    //邻接边
    struct EdgeNode *next;    //指向邻接的下一条边
    int adjVex;    //该邻接边对应的数组下标
}EdgeNode;
typedef struct VexNode{    //邻接顶点
    int data;    //该结点的数据
    EdgeNode *firstEdge;    //指向该顶点第一条邻接边
}VexNode, AdjList[MAXVEX];
typedef struct Graph{    //邻接表
    AdjList adjList;    //申明一个VexNode类型长度为MAXVERTEXNUM的一维数组存储顶点
    int vexNum, edgeNum;    //该表的顶点数和弧数
}Graph;

4.查找

4.1.顺序查找

408数据结构学习笔记——顺序查找、折半查找、分块查找_江南江南江南丶的博客-CSDN博客_顺序查找效率

从头到尾逐一对比元素

int Ssq_Search(int arr[], int key, int n){
    int i;
    for (i = 0; i < n && arr[i] != key; i++ ) {
        if (arr[i] == key ) return i;
    }
    return -1;
}

4.2.折半查找

1.算法思想：申明一个mid指针始终指向数组的正中心元素，判断该元素是否为key元素；若是则返回mid（该元素的数组下标）；若不是则判断大小去左右子树查找

该查找方法要求以数组（支持随机访问），并且有序

int Binary_Search(int arr[], int n, int key) {
    int low = 0, high = n - 1, mid;    //初始化low和high指针
    while (low <= high) {    //当low > high 时结束循环
        mid = (low + high) / 2; //每轮循环将mid重置
        if (arr[mid] == key) return mid;    //mid和key相等，返回mid数组下标
        else if (arr[mid] < key) low = mid + 1;    //key比mid更大，则去右边
        else high = mid - 1;    //key比左子树更小，则去左边
    }
    return -1;    //循环内没有return则说明数组中没有该元素，返回-1
}

2.ASL：需要注意一点，查找失败的情况下仅需找到存在的最底层叶子结点，不需要找到空结点

3.时间空间复杂度（顺序查找和折半查找的时间复杂度对比）

4.3.分块查找

1.手算模拟过程

2.ASL

4.4.二叉搜索树和二叉排序树

408数据结构学习笔记——二叉排序树、二叉平衡树、红黑树_江南江南江南丶的博客-CSDN博客_二叉排序树和红黑树

1.算法思想：和折半查找类似

2.代码实现：

BiTNode* Search(BiTree T, int key) {
    BiTNode *p = T;
    while (p && p->value != key) {
        if (p->value > key) p = p->lchild;
        else p = p->rchild;
    }
    return p;
}

3.ASL

4.时间复杂度：计算方式与折半查找相同，特别注意查找失败情况下

4.5.散列表

408数据结构学习笔记——B树、B+树、散列表_江南江南江南丶的博客-CSDN博客

1.处理冲突的方法

①线性探测：注意散列因子求散列表长的方式计算散列表查找成功和查找不成功的平均查找长度（利用线性探测法处理冲突）_叫我蘑菇先生的博客-CSDN博客_线性探测法查找失败的平均查找长度

②拉链

2.ASL

①线性探测：注意查找失败时，只需计算散列函数的初始可能取值的个数，即mod 7 只计算开始的 0 - 6号散列表元素各自到第一个空元素的和（并非整个散列表）

②拉链：注意查找失败时，空指针不算一次查找次数

4.6.kmp算法

408数据结构学习笔记——串、朴素模式匹配、kmp算法及其改进_江南江南江南丶的博客-CSDN博客

1.next数组

2.next[j]的定义（next[1] = 0，next[2] = 1）

3.nextval（next[next[j]]）

5.排序

1.记忆口诀：

马士兵说：30秒让你记住所有排序算法-宋词记忆法_哔哩哔哩_bilibili

选泡插，快归堆希统计基：选择，冒泡，插入；快速，归并，堆，希尔，桶，计数，基数

恩方恩老恩一三，对恩加K恩乘K：选择，冒泡，插入为O（n2）；快速，归并，堆为O（nlogn）；希尔为O（n1.3）；桶和计数（不要求）为一对的O（n+K）；基数为O（n * K）

不稳稳稳不稳稳，不稳不稳稳稳稳：分别按上面对应

2.

408数据结构学习笔记——直接插入排序、折半排序、希尔排序_江南江南江南丶的博客-CSDN博客

408数据结构学习笔记——简单选择排序、堆排序_江南江南江南丶的博客-CSDN博客

408数据结构学习笔记——冒泡排序、快速排序_江南江南江南丶的博客-CSDN博客

408数据结构学习笔记——归并排序、基数排序_江南江南江南丶的博客-CSDN博客

408数据结构学习笔记——外部排序_江南江南江南丶的博客-CSDN博客

3.对比次数、稳定性、时间/空间复杂度、手绘过程（希尔、堆、基数）