数据结构小学期-算法演示程序实验报告

石家庄铁道大学实习报告1/22实习报告实验名称：数据结构基本算法演示程序日期：2017年7月1日姓名：于博学号：20153236班级：信1501-2指导教师：陈娜1．实验题目1)Prim算法输入：无向图（顶点序列，边序列）功能要求：输出最小生成树的各组成边及最小生成树的权值2)Kruskal算法输入：无向图（顶点序列，边序列）功能要求：输出最小生成树的各组成边及最小生成树的权值3)Floyd算法输入：有向图（顶点序列，有向边序列）功能要求：输出各顶点对间最短路径和路径长度4)Dijkstra算法输入：有向图（顶点序列，有向边序列），起始顶点功能要求：输出起始顶点到其它各顶点的最短路径和路径长度2．需求分析本演示程序用C++编写，完成四个算法的实现,Prim算法，Kruskal算法，Floyd算法，Dijkstra算法①输入的形式和输入值的范围：整数，菜单项是1至5，其他输入根据图的实际情况。②输出的形式：输出最小生成树，树的各组成边，所有路径及源点到其他点的所有最短路径。③程序所能达到的功能：四个算法Prim算法，Kruskal算法，Floyd算法，Dijkstra算法的实现。④测试数据：A．输入3个点，3条边。B．输入135012202310三组点及权值。3．概要设计1)为了实现上述程序功能，需要定义树、线性表的抽象数据类型：ADTTree{数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}数据关系：R={ai,ai+1|ai,ai+1∈D}ADTLinkList{数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}数据关系：R={ai,ai+1|ai,ai+1∈D}基本操作：a)Prim算法ok(Tree&t,intk)初始条件：树结构已存在操作结果：作为判断函数的条件石家庄铁道大学实习报告2/22judge(Tree&t)初始条件：树结构已存在操作结果：判断树是否包含所有图的结点show_prim()初始条件：树结构已存在，prim算法运行成功操作结果：展示prim算法,输出最小生成树b)Kruskal算法Find(intx)初始条件：图已存在操作结果：查寻父节点Union(intx,inty)初始条件：图已存在操作结果：合并结点boolCom(Nodex,Nodey)初始条件：图已存在操作结果：判断结点权值show_kruskal()初始条件：图已存在，kruskal算法运行成功操作结果：展示kruskal算法，输出各组成边c)Floyd算法F_Creategraph(F_MGraph*F_MGraph)操作结果：创建图Floyd(F_MGraph*F_MGraph,int**iArrPath)初始条件：图已存在操作结果：运行弗洛伊德算法PrintResult(F_MGraph*F_MGraph,int**iArrPath)初始条件：图已存在操作结果：打印图的信息show_floyd()初始条件：图已存在，弗洛伊德算法运行成功操作结果：展示弗洛伊德算法d)Dijkstra算法createGraph(HeadNode*G,intnodeNum,intarcNum)操作结果：创建图printGraph(HeadNode*G,intnodeNum)初始条件：图已存在操作结果：打印图getWeight(HeadNode*G,intbegin,intend)初始条件：图已存在操作结果：得到出发点到终点权重Dijkstra(HeadNode*G,intnodeNum,intbegin)初始条件：图已存在，出发点已知操作结果：运行迪杰斯特拉算法printPath(HeadNode*G,intend)石家庄铁道大学实习报告3/22初始条件：图已存，迪杰斯特拉算法运行成功操作结果：打印路径show_Dijkstra()初始条件：图已存，迪杰斯特拉算法运行成功操作结果：展示迪杰斯特拉算法menu()操作结果：在屏幕上显示操作菜单2)本程序包含17个函数：主函数main()菜单函数menu()Prim算法判断函数ok()判断树是否包含所有图的结点judge()展示prim算法函数show_prim()Kruskal算法查寻父节点函数Find()合并结点函数Union()判断节点权值函数boolCom()展示kruskal算法函数show_kruskal()Floyd算法弗洛伊德创建图F_Creategraph()弗洛伊德算法函数Floyd()打印图信息函数PrintResult()展示弗洛伊德函数show_floyd()Dijistra算法创建图createGraph()迪杰斯特拉算法函数Dijkstra()打印路径函数printPath()展示迪杰斯特拉函数show_Dijkstra()各函数间关系如下：石家庄铁道大学实习报告4/224．详细设计//------------------------------------------Prim算法--------------------------------------------------////判断函数--是否树包含图的所有结点voidjudge(Tree&t){for(inti=1;it.v1;i++){for(intj=0;ji;j++){intm;m=t.v[j];for(intk=1;k=t.v1;k++){if(t.a[m][k]biaoji1){if(ok(t,k)){biaoji1=t.a[m][k];biaoji2=m;biaoji3=k;}}}}t.v[i]=biaoji3;t.e[2*i-1]=biaoji2;t.e[2*i]=biaoji3;}}//调用prim算法相关所有代码voidshow_prim(){cout请输入图的点数和边数endl;//输入提示cinnm;t.v1=n;//给树的结点总数和边的结点总数赋值t.e1=m;t.v=newint[n];//结点数组for(inti=0;in;i++)//循环初始化t.v[i]=0;t.e=newint[2*n-1];//边与结点数的关系for(inti=0;i2*n-1;i++)//循环初始化t.e[i]=0;t.a=newint*[n+1];for(inti=0;i=n;i++)t.a[i]=newint[n+1];cout请依次输入各边的两端点及权值endl;for(inti=1;i=n;i++)for(intj=1;j=n;j++)t.a[i][j]=10000;//初始化为无穷大for(inti=1;i=m;i++){//for循环输入石家庄铁道大学实习报告5/22cinm1m2count;t.a[m1][m2]=count;//无向网赋值t.a[m2][m1]=count;}judge(t);//判断是否有全部叶子节点cout最小生成树为：endl;for(inti=1;in;i++){x=t.e[2*i-1];y=t.e[2*i];coutx-yt.a[x][y]endl;sum+=t.a[x][y];}cout最小生成树的权值之和为：sumendl;}//--------------------------------------kruskal算法------------------------------------------------------//intFind(intx){//查if(x==Father[x])returnx;elsereturnFind(Father[x]);}voidUnion(intx,inty){//并Father[x]=y;}intTop,Edge;boolCom(Nodex,Nodey){returnx.Weighty.Weight;}dequeNodeMap;//调用克鲁斯卡尔的相关代码voidshow_kruskal(){cout请输入结点个数及边数：endl;cinTopEdge;cout请依次输入两点及权值：endl;for(i=1;i=Top;i++)for(j=1;j=Top;j++){cinx;if(ji&&x!=100){y.Next=j;y.Priority=i;y.Weight=x;Map.push_back(y);}}sort(Map.begin(),Map.end(),Com);石家庄铁道大学实习报告6/22for(i=1;i=Top;i++){Father[i]=i;}cout树的各组成边有：endl;for(i=0;iMap.size();i++){if(count==Top-1)break;if(Find(Map[i].Priority)!=Find(Map[i].Next)){Union(Map[i].Priority,Map[i].Next);count++;if(Map[i].PriorityMap[i].Next)coutMap[i].Next-Map[i].Priority-endl;elsecoutMap[i].Priority-Map[i].Nextendl;;}}}//--------------------------------------floyd算法---------------------------------------------------------------////图的创建voidF_Creategraph(F_MGraph*F_MGraph){cout请输入顶点数和边数endl;cinF_MGraph-VcountF_MGraph-Ecount;for(introw=1;row=F_MGraph-Vcount;row++){//初始化为无穷,即不连通for(intcol=1;col=F_MGraph-Vcount;col++){F_MGraph-edges[row][col]=MAX_VALUE;}}cout请输入起始结点最终结点权重endl;for(inti=1;i=F_MGraph-Ecount;i++){//赋值cinrowcolweight;F_MGraph-edges[row][col]=weight;}}//佛洛依德算法voidFloyd(F_MGraph*F_MGraph,int**iArrPath){for(inti=1;i=F_MGraph-Vcount;i++){for(intj=1;j=F_MGraph-Vcount;j++){iArrPath[i][j]=i;}}//初始化路径表for(intk=1;k=F_MGraph-Vcount;k++){for(inti=1;i=F_MGraph-Vcount;i++){for(intj=1;j=F_MGraph-Vcount;j++){if(F_MGraph-edges[i][k]+F_MGraph-edges[k][j]石家庄铁道大学实习报告7/22F_MGraph-edges[i][j]){F_MGraph-edges[i][j]=F_MGraph-edges[i][k]+F_MGraph-edges[k][j];iArrPath[i][j]=iArrPath[k][j];}}}}}//打印佛洛依德算法最短路径voidPrintResult(F_MGraph*F_MGraph,int**iArrPath){cout起点-终点\t距离\t\t最短路径endl;for(inti=1;i=F_MGraph-Vcount;i++){for(intj=1;j=F_MGraph-Vcount;j++){if(i!=j){couti