无敌大牛牛无敌

数据结构

ACM(68) GitHub(1) Java学习(1) Python(40) SQL(2) Web前端(21) work(1) 代码那点事(4) 机器学习(1) 牛客21天训练（大二部）(7) 计算机组成原理(9) 计算机网络(1) 软件使用和环境搭建(15)

/ 注册

全部文章 / 数据结构（共40篇）

Floyd-傻子也能看懂的弗洛伊德算法

暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。上图中有4个城市8条公路，公路上的数字表示这条公路的长短。请注意这些公路是单...

2020-12-21

0 478

求最小生成树-Prim（普里姆算法）

普里姆算法时间复杂度为O(V^2)，适用于稠密图 #include <iostream> using namespace std; #define Maxsize 100 typedef char VertexType; typedef int EdgeType; typedef st...

2020-12-21

0 410

求最小生成树-Kruskal（克鲁斯卡尔算法）

克鲁斯卡尔算法时间复杂度与排序算法sort有关，适合于稀疏图。 #include <iostream> using namespace std; #define Maxsize 100 typedef char VertexType; typedef int EdgeType; typ...

2020-12-21

0 412

单源最短路径-Dijkstra（迪杰斯特拉算法）

迪杰斯特拉算法时间复杂度为O(n^2)，其中n为顶点个数。该算法用于求单源最短路径。并且图中的边不允许带负权值。 #include <iostream> using namespace std; #define Maxsize 100 typedef char VertexTyp...

2020-12-21

0 525

最短路径-Floyd（佛洛伊德算法）

佛洛伊德算法时间复杂度为O(n^3)，其中n为顶点的个数。 Floyd可求出任何一对顶点之间的最短路径。允许图中有带负权值的边，但是不允许有包含带负权值的边组成的回路。 #include <iostream> using namespace std; #define Maxsize...

2020-12-21

0 788

DAG图之拓扑排序

DAG图也成为有向无环图，拓扑排序的时间复杂度为O(V+E)，其中V、E分别为顶点和边的个数。 #include <iostream> using namespace std; #define Maxsize 100 typedef char VertexType; typedef i...

2020-12-21

1 405

让你秒懂的折半查找（二分查找）

折半查找又称二分查找，只能适用于有序的顺序表。 //折半查找 int Bsearch(int R[],int low,int high,int key){ int min; while(low<=high){ mid=(low+high)/2; //取中间位置 if(R[mid]...

2020-12-21

0 608

堆排序分析（大根堆为例，由小到大排序）

时间复杂度为O(nlogn)，思路就是从最后一个非叶结点开始，依次往回遍历每个结点，将以该结点为根的子树建立成大根堆，直到遍历到整棵完全二叉树的根结点时为止，此时整棵树为大根堆。以当前结点为根的子树建立大根堆： //向下调整,将该结点的子树变成大根堆 void AdjustDown(int ...

2020-12-21

0 748

超详细！各种内部排序算法的比较

先来个表格总结直观展示下： <caption> 各种内部排序算法的性质 </caption> 算法种类时间复杂度空间复杂度稳定性最好情况...

2020-12-21

0 561

利用堆排序查找数组中第K小的元素方法

先从数组A[ ]中取前k个元素建立大根堆，然后再遍历剩下的n-k个元素，如果大于或者等于堆顶，则舍弃；如果小于堆顶，则将其与堆顶替换，并将换下来的堆顶舍弃，然后重新向下调整为大根堆，最后堆顶即为所求。时间复杂度为O(nlogk) /*给定数组A[n]，设计最优算法查找第k小元素，最优算...

2020-12-21

0 486