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

1、石家庄铁道大学实习报告实习报告实验名称：基本算法演示程序日期：2017年7月7日姓名：李琛学号：20153204班级：信1501-2指导教师：陈娜1.实验题目4、Prim算法输入：无向图（顶点序列，边序列）功能要求：输出最小生成树的各组成边及最小生成树的权值5、Kruskal算法输入：无向图（顶点序列，边序列）功能要求：输出最小生成树的各组成边及最小生成树的权值6、Floyd算法输入：有向图（顶点序列，有向边序列）功能要求：输出各顶点对间最短路径和路径长度7、Dijkstra算法输入：有向图（顶点序列，有向边序列），起始顶点功能要求：输出起始顶点到其它各顶点的最短路径和路径长度2.需求分析4、

2、Prim算法输入：无向图（顶点序列，边序列）功能要求：输出最小生成树的各组成边及最小生成树的权值5、Kruskal算法输入：无向图（顶点序列，边序列）功能要求：输出最小生成树的各组成边及最小生成树的权值6、Floyd算法输入：有向图（顶点序列，有向边序列）功能要求：输出各顶点对间最短路径和路径长度7、Dijkstra算法输入：有向图（顶点序列，有向边序列），起始顶点功能要求：输出起始顶点到其它各顶点的最短路径和路径长度3.概要设计4、Prim算法structAMGraphp/顶点表/邻接矩阵/图的当前点数和边数VerTexTypevexsMVNumArcTypearcsMVNumMVNumin

3、tvexnum,arcnum;/Prim算法辅助结构体structcloseVerTexTypeadjvex;1/16石家庄铁道大学实习报告ArcTypelowcost;)；#defineMaxInt32767#defineMVNum00typedefcharVerTexType;typedefintArcType;5、Kruskal算法#defineMaxInt32767#defineMVNur100typedefcharVerTexType;typedefintArcType;structAMGraphk(VerTexTypevexsMVNumArcTypearcsMVNumMVNumin

4、tvexnum,arcnum;);/kruskal算法辅助结构体structEdge(VerTexTypeHead;VerTexTypeTail;ArcTypelowcost;);6、Floyd算法#defineMaxInt32767#defineMVNum00typedefcharVerTexType;typedefintArcType;intD100100,Path100100;structAMGraphf(VerTexTypevexsMVNumArcTypearcsMVNumMVNumintvexnum,arcnum;);7、Dijkstra算法#defineMaxInt32767#de

5、fineMVNum00typedefcharVerTexType;typedefintArcType;intS100,D100,min,Path100;structAMGraphd(/极大值/最大顶点数/顶点类型为字符型/边的权值为整型/极大值/最大顶点数/顶点类型为字符型/边的权值为整型/顶点表/邻接矩阵/图的当前点数和边数/极大值/最大顶点数/顶点类型为字符型/边的权值为整型/顶点表/邻接矩阵/图的当前点数和边数/极大值/最大顶点数/顶点类型为字符型/边的权值为整型2/16/顶点表/邻接矩阵/图的当前点数和边数kruskaldiijkstrafloyd石家庄铁道大学实习报告VerTexTy

6、pevexsMVNumArcTypearcsMVNujfiMVNujyiintvexnum,arcnum;)；函数曾今调用关系4.详细设计Head.h#pragmaonce#include<iostream>#include<string>usingnamespacestd;/图的邻接矩阵存储表示/极大值/最大顶点数/顶点类型为字符型/边的权值为整型#defineMaxInt32767#defineMVNum00typedefcharVerTexType;typedefintArcType;voidprim();voidkruskal();voiddijkstra();

7、voidfloyd();3/16石家庄铁道大学实习报告Main.cpp#include"head.h"voidmain()(inta=1;cout<<"请输入想要运行的算法序号："<<endl;cout<<"1、prim算法"<<endl;cout<<"2、kruskal算法"<<endl;cout<<"3、dijkstra算法"<<endl;cout<<"4、floyd算法&q

8、uot;<<endl;while(a!=0)(cout<<"请输入:"cin>>a;switch(a)(case1:prim();break;case 2:kruskal();break;case 3:dijkstra();break;case 4: floyd();break;Prim.cpp#include"head.h"structAMGraphp(/顶点表/邻接矩阵/图的当前点数和边数VerTexTypevexsMVNumArcTypearcsMVNumMVNumintvexnum,arcnum;/Prim算法

9、辅助结构体structclose(VerTexTypeadjvex;ArcTypelowcost;intLocateVex(AMGraphpGVerTexTypeu)4/16/输入总顶点数，总边数/依次输入点的信息/权值初始化为最大值/构造邻接矩阵/输入两点信息/输入权值石家庄铁道大学实习报告(inti=0;while(Gvexsi!=u)i+;returni;)/使用邻接矩阵表示法创建无向图intCreateUDN(AMGraphp&G)(inti,j,k,w;charv1,v2;cout<<"输入顶点数和边数："；cin>>Gvexnum

10、>>Garcnum;for(i=0;i<Gvexnum;+i)(cout<<"输入第"cout<<i+1;cout<<"顶点信息：”；cin>>Gvexsi;)for(i=0;i<Gvexnum;+i)for(j=0;j<Garcnum;+j)Garcsij=MaxInt;for(k=0;k<Garcnum;+k)(cout<<"输入边的两点信息：”;cin>>v1>>v2;i=LocateVex(Gv1);j=LocateVex(Gv

11、2);cout<<"输入权值："；cin>>w;Garcsij=w;Garcs皿i=Garcsij;)return0;)/Prim算法最小生成树的构造voidMinispanTree_prim(AMGraphpGinta,AMGraphp&T)(intk=a-1,i,j,m,lowcost;/规定从第a个顶点开始closeclosedge100;/辅助数组的声明T.vexnum=Gvexnum;/T的初始化for(i=0;i<Gvexnum;i+)T.vexsi=Gvexsi;5/16石家庄铁道大学实习报告for(i=0;i<Gv

12、exnum;i+)for(j=0;j<Gvexnum;j+)T.arcsij=-1;for(i=0;i<Gvexnum;i+)closedgei.adjvex=k;closedgei.lowcost=Garcski;closedgek.lowcost=0;/把第0个结点并入最小生成树for(m=1;m<Gvexnum;m+)lowcost=MaxInt;for(i=1;i<Gvexnum;i+)if(lowcost>closedgei.lowcost&&closedgei.lowcost!=0&&closedgei.lowcost!

13、=-1)lowcost=closedgei.lowcost;k=i;T.arcsclosedgek.adjvexk=lowcost;/在T中存最小生成树的边T.arcskclosedgek.adjvex=lowcost;closedgek.lowcost=0;/把第k个结点并入最小生成树for(i=1;i<Gvexnum;i+)if(Garcski<closedgei.lowcost&&Garcski!=-1)|closedgei.lowcost=-1)closedgei.lowcost=Garcski;closedgei.adjvex=k;/邻接矩阵输出voidA

14、MGout(AMGraphpT)inti,j,k;cout<<"点的信息分别为："<<endl;for(i=0;i<T.vexnum;i+)cout<<T.vexsi<<""cout<<endl;6/16石家庄铁道大学实习报告cout<<"邻接矩阵为："<<endl;for(j=0;j<T.vexnum;j+)for(k=0;k<T.vexnum;k+)(if(T.arcs皿k>=32767|T.arcs皿k<0)cout

15、<<"*"<<""elsecout<<T,arcsjk<<"")cout<<endl;)/调用函数voidprim()(AMGraphpM;AMGraphpN;CreateUDN(M);AMGout(M);inta;cout<<"请输入开始的点:"cin>>a;MinispanTree_prim(M,a,N);cout<<"最小生成树为："<<endl;AMGout(N);)Kruskal

16、.cpp#include"head.h"structAMGraphk(/顶点表/邻接矩阵/图的当前点数和边数VerTexTypevexsMVNumArcTypearcsMVNumMVNuJmintvexnum,arcnum;);/kruskal算法辅助结构体structEdge(VerTexTypeHead;VerTexTypeTail;ArcTypelowcost;);/顶点定位7/16石家庄铁道大学实习报告intLocateVex(AMGraphkGVerTexTypeu)(inti=0;while(Gvexsi!=u)i+;returni;/创建无向图intCreat

17、eUD(AMGraphk&Q(inti,j,k,w;charv1,v2;cout<<"输入顶点数和边数："；cin>>Gvexnum>>Garcnum;for(i=0;i<Gvexnum;+i)(cout<<"输入第"cout<<i+1;cout<<"顶点信息：”；cin>>Gvexsi;for(i=0;i<Gvexnum;+i)for(j=0;j<Garcnum;+j)(Garcsij=MaxInt;for(k=0;k<Garc

18、num;+k)(cout<<"输入边的两点信息：”；cin>>v1>>v2;i=LocateVex(Gv1);j=LocateVex(Gv2);cout<<"输入权值:"cin>>w;Garcsij=w;Garcs皿i=Garcsij;return0;intVexsetMVNufnvoidkruskal()(Edgea100;AMGraphkG;/输入总顶点数，总边数/依次输入点的信息/权值初始化为最大值/构造邻接矩阵/输入两点信息/输入权值8/16石家庄铁道大学实习报告CreateUD(G);inti,

19、j,k=0;for(i=0;i<G.arcnum;i+)(for(j=i+1;j<G.arcnum;j+)(if(G.arcsij>0&&G.arcsij<(ak.Head=G.vexsi;ak.Tail=G.vexsjak.lowcost=G.arcsij;k+;intv1,v2,vs1,vs2;Edgeb;for(i=0;i<G.arcnum;i+)(for(j=i+1;j<G.arcnum;j+)(if(ai.lowcost>aj.lowcost)(b=ai;ai=aj;aj=b;for(i=0;i<G.vexnum;i+)

20、(Vexseti=i;for(i=0;i<G.arcnum;i+)(v1=LocateVex(G,ai.Head);v2=LocateVex(G,ai.Tail);vs1=Vexsetv1;vs2=Vexsetv2;if(vs1!=vs2)(cout<<ai.Head<<""<<ai.Tailfor(j=0;j<G.vexnum;j+)(MaxInt)<<endl;9/16石家庄铁道大学实习报告if(Vexsetj=vs2)Vexsetj=vs1;)Dijkstra.cpp#include"head.h&

21、quot;intS100,D100,min,Path100;structAMGraphdVerTexTypevexsMVNumpArcTypearcsMVNujfiMVNumintvexnum,arcnum;);intLocateVex(AMGraphdGVerTexTypeu)inti=0;while(Gvexsi!=u)i+;returni;)intCreateUD(AMGraphd&Qinti,j,k,w;charv1,v2;cout<<"输入顶点数和边数："；cin>>Gvexnum>>Garcnum;for(i=0;i&

22、lt;Gvexnum;+i)cout<<"输入第"cout<<i+1;cout<<"顶点信息：”；cin>>Gvexsi;)for(i=0;i<Gvexnum;+i)for(j=0;j<Gvexnum;+j)Garcsij=MaxInt;)for(k=0;k<Garcnum;+k)cout<<"输入边的两点信息：”；cin>>v1>>v2;/顶点表/邻接矩阵/图的当前点数和边数/输入总顶点数，总边数/依次输入点的信息/权值初始化为最大值/构造邻接矩阵/输

23、入两点信息10/16石家庄铁道大学实习报告i=LocateVex(Gv1);/输入权值j=LocateVex(Gv2);cout<<"输入权值:"cin>>w;Garcsij=w;return0;voiddijkstra()AMGraphdG;CreateUD(G);inti,n,v,v0,w;cout<<"请输入起始点："<<endl;cin>>v0;v0=v0-1;n=G.vexnum;for(v=0;v<n;v+)Sv=false;Dv=G.arcsv0v;if(Dv<MaxI

24、nt)Pathv=0;elsePathv=-1;Sv0=true;Dv0=0;for(i=1;i<n;i+)min=MaxInt;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)11/16石家庄铁道大学实习报告(Dw=Dv+G.arcsvw;Pathw=v;)intx=0;cout<<"点到各点的最短路径长度"<<endl;while(Sx)(cout<&l

25、t;Dx<<""x+;)cout<<endl;x=0;cout<<"各终点的前驱点"<<endl;while(Sx)(cout<<Pathx+1<<""x+;)cout<<endl;)Floyd.cpp#include"head.h"intD100100,Path100100;structAMGraphf(/顶点表/邻接矩阵/图的当前点数和边数VerTexTypevexsMVNumArcTypearcsMVNujfiMVNujyii

26、ntvexnum,arcnum;);intLocateVex(AMGraphfGVerTexTypeu)(inti=0;while(Gvexsi!=u)i+;returni;)intCreateUD(AMGraphf&G)(inti,j,k,w;charv1,v2;cout<<"输入顶点数和边数："；12/16石家庄铁道大学实习报告/输入总顶点数，总边数/依次输入点的信息cin>>Gvexnum>>Garcnum;for(i=0;i<Gvexnum;+i)(cout<<"输入第"cout<

27、;<i+1;cout<<"顶点信息：”；cin>>Gvexsi;/权值初始化为最大值/构造邻接矩阵/输入两点信息/输入权值for(i=0;i<Gvexnum;+i)for(j=0;j<Garcnum;+j)(Garcsij=MaxInt;for(k=0;k<Garcnum;+k)(cout<<"输入边的两点信息：”；cin>>v1>>v2;i=LocateVex(Gv1);j=LocateVex(Gv2);cout<<"输入权值："；cin>>w;

28、Garcsij=w;return0;voidfloyd()(AMGraphfG;CreateUD(G);inti,j,k;for(i=0;i<G.vexnum;i+)(for(j=0;j<G.vexnum;j+)(Dij=G.arcsij;if(Dij<MaxInt)Path皿=i;elsePathij=-1;for(k=0;k<G.vexnum;k+)(for(i=0;i<G.vexnum;i+)13/16石家庄铁道大学实习报告(for(j=0;j<G.vexnum;j+)(if(Dik+Dkj<Dij)(Dij=Dik+Dkj;Pathij=Pathkj;for(i=0;i<G.vexnum;i+)(for(j=0;j<G.vexnum;j+)(if(Dij=MaxInt)cout<<"*"<<""elsecout<&l