数据结构-基本算法演示程序附源码

-实习报告实验名称：基本算法演示程序日期：2017年 7月 7日*：李琛*：20153204班级：信1501-2指导教师：陈娜1实验题目4、Prim 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值 5、Kruskal 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值 6、Floyd 算法 输入：有向图（顶点序列，有向边序列） 功能要求：输出各顶点对间最短路径和路径长度 7、Dijkstra 算法 输入：有向图（顶点序列，有向边序列），起始顶点 功能要求：输出起始顶点到其它各顶点的最短路径和路径长度2需求分析 4、Prim 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值 5、Kruskal 算法 输入：无向图（顶点序列，边序列） 功能要求：输出最小生成树的各组成边及最小生成树的权值 6、Floyd 算法 输入：有向图（顶点序列，有向边序列） 功能要求：输出各顶点对间最短路径和路径长度 7、Dijkstra 算法 输入：有向图（顶点序列，有向边序列），起始顶点 功能要求：输出起始顶点到其它各顶点的最短路径和路径长度3概要设计 4、Prim 算法 structAMGraphpVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;/Prim算法辅助结构体structcloseVerTe*Type adjve*;ArcType lowcost;*defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型5、Kruskal 算法 *defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型structAMGraphkVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;/kruskal算法辅助结构体structEdgeVerTe*Type Head;VerTe*Type Tail;ArcType lowcost;6、Floyd 算法 *defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型int D100100, Path100100;structAMGraphfVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;7、Dijkstra 算法 *defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型int S100, D100, min, Path100;structAMGraphdVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;函数曾今调用关系4详细设计 Head.h*pragmaonce*include*includeusingnamespace std;/图的邻接矩阵存储表示*defineMa*Int 32767 /极大值*defineMVNum 100 /最大顶点数typedefcharVerTe*Type; /顶点类型为字符型typedefintArcType; /边的权值为整型void prim();void kruskal();void dijkstra();void floyd();Main.cpp*includehead.hvoid main()int a=1;cout 请输入想要运行的算法序号：endl;cout 1、prim算法endl;cout 2、kruskal算法 endl;cout 3、dijkstra算法 endl;cout 4、floyd算法 endl; while (a != 0)cout a;switch (a)case 1:prim(); break;case 2:kruskal(); break;case 3:dijkstra(); break;case 4:floyd(); break;Prim.cpp*includehead.hstructAMGraphpVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;/Prim算法辅助结构体structcloseVerTe*Type adjve*;ArcType lowcost;int LocateVe*(AMGraphpG, VerTe*Typeu)int i = 0;while (G.ve*si != u) i+;return i;/使用邻接矩阵表示法创建无向图int CreateUDN(AMGraphp &G)int i, j, k,w;char v1, v2;cout G.ve*num G.arum; /输入总顶点数，总边数for (i = 0; i G.ve*num; +i) /依次输入点的信息cout 输入第;cout i+1;cout G.ve*si;for (i = 0; i G.ve*num; +i) /权值初始化为最大值for (j = 0; j G.arum; +j)G.arcsij=Ma*Int;for (k = 0; k G.arum; +k) /构造邻接矩阵cout v1 v2;i = LocateVe*(G, v1);j = LocateVe*(G, v2);cout w;G.arcsij = w;G.arcsji = G.arcsij; return 0;/Prim算法最小生成树的构造void MinispanTree_prim(AMGraphpG, inta, AMGraphp &T)int k = a-1, i, j, m, lowcost;/规定从第a个顶点开始close closedge100;/辅助数组的声明T.ve*num = G.ve*num; /T的初始化for (i = 0; iG.ve*num; i+)T.ve*si = G.ve*si; for (i = 0; iG.ve*num; i+)for (j = 0; jG.ve*num; j+) T.arcsij = -1;for (i = 0; iG.ve*num; i+)closedgei.adjve* = k;closedgei.lowcost = G.arcski;closedgek.lowcost = 0;/把第0个结点并入最小生成树for (m = 1; mG.ve*num; m+)lowcost = Ma*Int; for (i = 1; iclosedgei.lowcost&closedgei.lowcost != 0 & closedgei.lowcost != -1)lowcost = closedgei.lowcost; k = i;T.arcsclosedgek.adjve*k = lowcost;/在T中存最小生成树的边T.arcskclosedgek.adjve* = lowcost;closedgek.lowcost = 0;/把第k个结点并入最小生成树for (i = 1; iG.ve*num; i+)if (G.arcskiclosedgei.lowcost&G.arcski != -1) | closedgei.lowcost = -1)closedgei.lowcost = G.arcski;closedgei.adjve* = k;/邻接矩阵输出void AMGout(AMGraphpT)int i ,j,k;cout 点的信息分别为：endl;for (i = 0; i T.ve*num; i+)cout T.ve*si ;cout endl;cout 邻接矩阵为： endl;for (j = 0; j T.ve*num; j+)for (k = 0; k = 32767 | T.arcsjk0)cout * ;elsecout T.arcsjk ;cout endl;/调用函数void prim()AMGraphp M; AMGraphp N;CreateUDN(M);AMGout(M);int a;cout a;MinispanTree_prim(M, a, N);cout 最小生成树为：endl;AMGout(N);Kruskal.cpp*includehead.hstructAMGraphkVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;/kruskal算法辅助结构体structEdgeVerTe*Type Head;VerTe*Type Tail;ArcType lowcost;/顶点定位int LocateVe*(AMGraphkG, VerTe*Typeu)int i = 0;while (G.ve*si != u) i+;return i;/创建无向图int CreateUD(AMGraphk &G)int i, j, k, w;char v1, v2;cout G.ve*num G.arum; /输入总顶点数，总边数for (i = 0; i G.ve*num; +i) /依次输入点的信息cout 输入第;cout i + 1;cout G.ve*si;for (i = 0; i G.ve*num; +i) /权值初始化为最大值for (j = 0; j G.arum; +j)G.arcsij = Ma*Int;for (k = 0; k G.arum; +k) /构造邻接矩阵cout v1 v2;i = LocateVe*(G, v1);j = LocateVe*(G, v2);cout w;G.arcsij = w;G.arcsji = G.arcsij;return 0;int Ve*setMVNum;void kruskal()Edge a100;AMGraphk G;CreateUD(G);int i, j, k = 0;for (i = 0; i G.arum; i+)for (j = i+1; j 0 & G.arcsijMa*Int)ak.Head = G.ve*si;ak.Tail = G.ve*sj;ak.lowcost = G.arcsij;k+;int v1, v2, vs1, vs2;Edge b;for (i = 0; i G.arum; i+)for (j = i+1; j aj.lowcost)b = ai;ai = aj;aj = b;for (i = 0; i G.ve*num; i+)Ve*seti = i;for (i = 0; i G.arum; i+)v1 = LocateVe*(G, ai.Head);v2 = LocateVe*(G, ai.Tail);vs1 = Ve*setv1;vs2 = Ve*setv2;if (vs1 != vs2)cout ai.Head ai.Tail endl;for (j = 0; j G.ve*num; j+)if (Ve*setj = vs2)Ve*setj = vs1;Dijkstra.cpp*includehead.hint S100, D100, min, Path100;structAMGraphdVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;int LocateVe*(AMGraphdG, VerTe*Typeu)int i = 0;while (G.ve*si != u) i+;return i;int CreateUD(AMGraphd &G)int i, j, k, w;char v1, v2;cout G.ve*num G.arum; /输入总顶点数，总边数for (i = 0; i G.ve*num; +i) /依次输入点的信息cout 输入第;cout i + 1;cout G.ve*si;for (i = 0; i G.ve*num; +i) /权值初始化为最大值for (j = 0; j G.ve*num; +j)G.arcsij = Ma*Int;for (k = 0; k G.arum; +k) /构造邻接矩阵cout v1 v2;i = LocateVe*(G, v1);j = LocateVe*(G, v2);cout w;G.arcsij = w;return 0;void dijkstra()AMGraphd G;CreateUD(G);int i,n, v, v0,w;cout 请输入起始点： v0;v0 = v0 - 1;n = G.ve*num;for (v = 0; v n; v+)Sv = false;Dv = G.arcsv0v;if (Dv Ma*Int) Pathv = 0;elsePathv = -1;Sv0 = true;Dv0 = 0;for (i = 1; i n; i+)min = Ma*Int;for (w = 0; w n; w+)if (!Sw & Dw min)v = w;min = Dw;Sv = true;for (w = 0; w n; w+)if (!Sw & (Dv + G.arcsvw Dw)Dw = Dv + G.arcsvw;Pathw = v;int * = 0;cout 点到各点的最短路径长度 endl;while (S*)cout D* ;*+;cout endl;* = 0;cout 各终点的前驱点 endl;while (S*)cout Path*+1 ;*+;cout endl;Floyd.cpp*includehead.hint D100100, Path100100;structAMGraphfVerTe*Type ve*sMVNum; /顶点表ArcType arcsMVNumMVNum; /邻接矩阵int ve*num, arum; /图的当前点数和边数;int LocateVe*(AMGraphfG, VerTe*Typeu)int i = 0;while (G.ve*si != u) i+;return i;int CreateUD(AMGraphf &G)int i, j, k, w;char v1, v2;cout G.ve*num G.arum; /输入总顶点数，总边数for (i = 0; i G.ve*num; +i) /依次输入点的信息cout 输入第;cout i + 1;cout G.ve*si;for (i = 0; i G.ve*num; +i) /权值初始化为最大值for (j = 0; j G.arum; +j)G.arcsij = Ma*Int;for (k = 0; k G.arum; +k) /构造邻接矩阵cout v1 v2;i = LocateVe*(G, v1);j = LocateVe*(G, v2);cout w;G.arcsij = w;return 0;void floyd()AMGraphf G;CreateUD(G);int i, j, k;for ( i = 0; i G.ve*num; i+)for ( j = 0; j G.ve*num; j+)Dij = G.arcsij;if (Dij Ma*Int) Pathij = i;else Pathij = -1;for ( k = 0; k G.ve*num; k+)for ( i = 0; i G.ve*num; i+)for ( j = 0; j G.ve*num; j+)if (Dik + Dkj Dij)Dij = Dik + Dkj;Pathij = Pathkj;for (i = 0; i G.ve*num; i+)for ( j = 0; j G.ve*num; j+)if (Dij = Ma*Int)cout * ;elsecout Dij ;cout endl;for (i = 0; i G.ve*num; i+)for (j = 0; j G.ve*num; j+)if (Pathij = -1)cout * ;elsecout Pathij +1 ;cout endl;cout 请输入始终点： a b;cout 中间的路径点为：1)cout Pathab ;b = Pathab;5调试分析调试过程中出现了很比较多的问题，基本是课本上的代码出现的未知函数6使用说明在主菜单中，输入1，2，3，4来选择算法，按照程序的提示来输入等候结果7测试结果. z.