408王道数据结构强化——应用题（三）

2022-11-27 278

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 408王道数据结构强化——应用题

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.拓扑排序

从AOV网中选择一个没有前驱的顶点输出
在AOV网中删除该顶点和所有以它为起点的顶点
重复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;
}