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

XX铁道大学实习报告/实习报告实验名称：基本算法演示程序日期：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算法structAMGraphp{VerTexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的当前点数和边数};//Prim算法辅助结构体structclose{VerTexTypeadjvex;ArcTypelowcost;};#defineMaxInt32767//极大值#defineMVNum100//最大顶点数typedefcharVerTexType;//顶点类型为字符型typedefintArcType;//边的权值为整型5、Kruskal算法#defineMaxInt32767//极大值#defineMVNum100//最大顶点数typedefcharVerTexType;//顶点类型为字符型typedefintArcType;//边的权值为整型structAMGraphk{VerTexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的当前点数和边数};//kruskal算法辅助结构体structEdge{VerTexTypeHead;VerTexTypeTail;ArcTypelowcost;};6、Floyd算法#defineMaxInt32767//极大值#defineMVNum100//最大顶点数typedefcharVerTexType;//顶点类型为字符型typedefintArcType;//边的权值为整型intD[100][100],Path[100][100];structAMGraphf{VerTexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的当前点数和边数};7、Dijkstra算法#defineMaxInt32767//极大值#defineMVNum100//最大顶点数typedefcharVerTexType;//顶点类型为字符型typedefintArcType;//边的权值为整型intS[100],D[100],min,Path[100];structAMGraphd{VerTexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的当前点数和边数};函数曾今调用关系4．详细设计Head.h#pragmaonce#include<iostream>#include<string>usingnamespacestd;//图的邻接矩阵存储表示#defineMaxInt32767//极大值#defineMVNum100//最大顶点数typedefcharVerTexType;//顶点类型为字符型typedefintArcType;//边的权值为整型voidprim<>;voidkruskal<>;voiddijkstra<>;voidfloyd<>;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算法"<<endl;while<a!=0> { cout<<"请输入："; cin>>a;switch<a> {case1: prim<>;break;case2: kruskal<>;break;case3: dijkstra<>;break;case4: floyd<>;break; } }}Prim.cpp#include"head.h"structAMGraphp{VerTexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的当前点数和边数};//Prim算法辅助结构体structclose{VerTexTypeadjvex;ArcTypelowcost;};intLocateVex<AMGraphpG,VerTexTypeu>{inti=0;while<G.vexs[i]!=u>i++;returni;}//使用邻接矩阵表示法创建无向图intCreateUDN<AMGraphp&G>{inti,j,k,w;charv1,v2; cout<<"输入顶点数和边数:"; cin>>G.vexnum>>G.arcnum;//输入总顶点数,总边数for<i=0;i<G.vexnum;++i>//依次输入点的信息 { cout<<"输入第"; cout<<i+1; cout<<"顶点信息:"; cin>>G.vexs[i]; }for<i=0;i<G.vexnum;++i>//权值初始化为最大值for<j=0;j<G.arcnum;++j>G.arcs[i][j]=MaxInt;for<k=0;k<G.arcnum;++k>//构造邻接矩阵 { cout<<"输入边的两点信息:";//输入两点信息 cin>>v1>>v2; i=LocateVex<G,v1>; j=LocateVex<G,v2>; cout<<"输入权值:";//输入权值 cin>>w;G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j]; }return0;}//Prim算法最小生成树的构造voidMinispanTree_prim<AMGraphpG,inta,AMGraphp&T>{intk=a-1,i,j,m,lowcost;//规定从第a个顶点开始closeclosedge[100];//辅助数组的声明T.vexnum=G.vexnum;//T的初始化for<i=0;i<G.vexnum;i++>T.vexs[i]=G.vexs[i];for<i=0;i<G.vexnum;i++>for<j=0;j<G.vexnum;j++>T.arcs[i][j]=-1;for<i=0;i<G.vexnum;i++> { closedge[i].adjvex=k; closedge[i].lowcost=G.arcs[k][i]; } closedge[k].lowcost=0;//把第0个结点并入最小生成树for<m=1;m<G.vexnum;m++> { lowcost=MaxInt;for<i=1;i<G.vexnum;i++> {if<lowcost>closedge[i].lowcost&&closedge[i].lowcost!=0&&closedge[i].lowcost!=-1> { lowcost=closedge[i].lowcost; k=i; } }T.arcs[closedge[k].adjvex][k]=lowcost;//在T中存最小生成树的边T.arcs[k][closedge[k].adjvex]=lowcost; closedge[k].lowcost=0;//把第k个结点并入最小生成树for<i=1;i<G.vexnum;i++> {if<<G.arcs[k][i]<closedge[i].lowcost&&G.arcs[k][i]!=-1>||closedge[i].lowcost==-1> { closedge[i].lowcost=G.arcs[k][i]; closedge[i].adjvex=k; } } }}//邻接矩阵输出voidAMGout<AMGraphpT>{inti,j,k; cout<<"点的信息分别为："<<endl;for<i=0;i<T.vexnum;i++> cout<<T.vexs[i]<<""; cout<<endl; cout<<"邻接矩阵为："<<endl;for<j=0;j<T.vexnum;j++> {for<k=0;k<T.vexnum;k++> {if<T.arcs[j][k]>=32767||T.arcs[j][k]<0> cout<<"*"<<"";else cout<<T.arcs[j][k]<<""; } cout<<endl; } }//调用函数voidprim<>{AMGraphpM;AMGraphpN; CreateUDN<M>; AMGout<M>;inta; cout<<"请输入开始的点:"; cin>>a; MinispanTree_prim<M,a,N>; cout<<"最小生成树为："<<endl; AMGout<N>;}Kruskal.cpp#include"head.h"structAMGraphk{VerTexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的当前点数和边数};//kruskal算法辅助结构体structEdge{VerTexTypeHead;VerTexTypeTail;ArcTypelowcost;};//顶点定位intLocateVex<AMGraphkG,VerTexTypeu>{inti=0;while<G.vexs[i]!=u>i++;returni;}//创建无向图intCreateUD<AMGraphk&G>{inti,j,k,w;charv1,v2; cout<<"输入顶点数和边数:"; cin>>G.vexnum>>G.arcnum;//输入总顶点数,总边数for<i=0;i<G.vexnum;++i>//依次输入点的信息 { cout<<"输入第"; cout<<i+1; cout<<"顶点信息:"; cin>>G.vexs[i]; }for<i=0;i<G.vexnum;++i>//权值初始化为最大值for<j=0;j<G.arcnum;++j> {G.arcs[i][j]=MaxInt; }for<k=0;k<G.arcnum;++k>//构造邻接矩阵 { cout<<"输入边的两点信息:";//输入两点信息 cin>>v1>>v2; i=LocateVex<G,v1>; j=LocateVex<G,v2>; cout<<"输入权值:";//输入权值 cin>>w;G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j]; }return0;}intVexset[MVNum];voidkruskal<>{Edgea[100];AMGraphkG; CreateUD<G>;inti,j,k=0;for<i=0;i<G.arcnum;i++> {for<j=i+1;j<G.arcnum;j++> {if<G.arcs[i][j]>0&&G.arcs[i][j]<MaxInt> { a[k].Head=G.vexs[i]; a[k].Tail=G.vexs[j]; a[k].lowcost=G.arcs[i][j]; k++; } } }intv1,v2,vs1,vs2;Edgeb;for<i=0;i<G.arcnum;i++> {for<j=i+1;j<G.arcnum;j++> {if<a[i].lowcost>a[j].lowcost> { b=a[i]; a[i]=a[j]; a[j]=b; } } }for<i=0;i<G.vexnum;i++> { Vexset[i]=i; }for<i=0;i<G.arcnum;i++> { v1=LocateVex<G,a[i].Head>; v2=LocateVex<G,a[i].Tail>; vs1=Vexset[v1]; vs2=Vexset[v2];if<vs1!=vs2> { cout<<a[i].Head<<""<<a[i].Tail<<endl;for<j=0;j<G.vexnum;j++> {if<Vexset[j]==vs2> Vexset[j]=vs1; } } }}Dijkstra.cpp#include"head.h"intS[100],D[100],min,Path[100];structAMGraphd{VerTexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的当前点数和边数};intLocateVex<AMGraphdG,VerTexTypeu>{inti=0;while<G.vexs[i]!=u>i++;returni;}intCreateUD<AMGraphd&G>{inti,j,k,w;charv1,v2; cout<<"输入顶点数和边数:"; cin>>G.vexnum>>G.arcnum;//输入总顶点数,总边数for<i=0;i<G.vexnum;++i>//依次输入点的信息 { cout<<"输入第"; cout<<i+1; cout<<"顶点信息:"; cin>>G.vexs[i]; }for<i=0;i<G.vexnum;++i>//权值初始化为最大值for<j=0;j<G.vexnum;++j> {G.arcs[i][j]=MaxInt; }for<k=0;k<G.arcnum;++k>//构造邻接矩阵 { cout<<"输入边的两点信息:";//输入两点信息 cin>>v1>>v2; i=LocateVex<G,v1>; j=LocateVex<G,v2>; cout<<"输入权值:";//输入权值 cin>>w;G.arcs[i][j]=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++> { S[v]=false; D[v]=G.arcs[v0][v];if<D[v]<MaxInt> Path[v]=0;else Path[v]=-1; } S[v0]=true; D[v0]=0;for<i=1;i<n;i++> { min=MaxInt;for<w=0;w<n;w++> {if<!S[w]&&D[w]<min> { v=w; min=D[w]; } } S[v]=true;for<w=0;w<n;w++> {if<!S[w]&&<D[v]+G.arcs[v][w]<D[w]>> { D[w]=D[v]+G.arcs[v][w]; Path[w]=v; } } }intx=0; cout<<"点到各点的最短路径长度"<<endl;while<S[x]> { cout<<D[x]<<""; x++; } cout<<endl; x=0; cout<<"各终点的前驱点"<<endl;while<S[x]> { cout<<Path[x]+1<<""; x++; } cout<<endl;}Floyd.cpp#include"head.h"intD[100][100],Path[100][100];structAMGraphf{VerTexTypevexs[MVNum];//顶点表ArcTypearcs[MVNum][MVNum];//邻接矩阵intvexnum,arcnum;//图的当前点数和边数};intLocateVex<AMGraphfG,VerTexTypeu>{inti=0;while<G.vexs[i]!=u>i++;returni;}intCreateUD<AMGraphf&G>{inti,j,k,w;charv1,v2; cout<<"输入顶点数和边数:"; cin>>G.vexnum>>G.arcnum;//输入总顶点数,总边数for<i=0;i<G.vexnum;++i>//依次输入点的信息 { cout<<"输入第"; cout<<i+1; cout<<"顶点信息:"; cin>>G.vexs[i]; }for<i=0;i<G.vexnum;++i>//权值初始化为最大值for<j=0;j<G.arcnum;++j> {G.arcs[i][j]=MaxInt; }for<k=0;k<G.arcnum;++k>