最短村庄报告

1数据结构实验报告实验五实验题目：图子系统指导老师：专业班级：2013年5月23日2实验类型__综合__实验室_软件实验室一__一、实验题目图子系统二、实验目的和要求１．掌握图的存储思想及其存储实现２．掌握图的深度、广度优先遍历算法思想及其程序实现３．掌握图的常见应用算法的思想及其程序实现三、实验内容实验内容二：所有顶点对的最短路径1．设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。2．设计分析用有向加权图表示的交通图中，有向边vi,vj表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。该问题的实质是求解任意两顶点间的最短路径问题。即求出每个顶点到其他顶点的最短路径的最大值，最大值最小的顶点作为医院所在村庄。3．结构类型定义typedefcharvextype;/*顶点数据类型*/typedefintedgetype;/*边数据类型*/typedefstruct{vextypevex[maxsize];edgetypearc[maxsize][maxsize];intvexnum,arcnum;}Mgraph;四、实验步骤实验代码：#includestdio.h3#definemaxvertexnum100//将maxvertexnum的值赋为100typedefcharvertextype;//将char类型用vertextype表示typedefintedgetype;//将int用edgetype表示typedefstruct{vertextypevexs[maxvertexnum];//定义一维数组顶点vexs，用来存储图的顶点字母edgetypeedges[maxvertexnum][maxvertexnum];//定义二维数组用来存放边的值intn,e;//n表示顶点的数目，e表示边的数目}mgrgh;mgrghM;voidcreatemgrgh(mgrgh*g);voidshortlu(mgrgh*g);voidcreatemgrgh(mgrgh*g)//初始化图{inti,j,k,m;printf(*********************************************************\n);printf(请输入村庄的个数和到各村庄的道路数\n);scanf(%d%d,&g-n,&g-e);getchar();printf(*********************************************************\n);printf(请输入各个村庄的字母表示\n);for(i=0;ig-n;i++){g-vexs[i]=getchar();}for(i=0;ig-n;i++)//将村庄到各个村庄的路径都赋初值为0for(j=0;jg-n;j++){g-edges[i][j]=0;}printf(*********************************************************\n);printf(输入各个村庄到各村庄的路径大小值，其中输入的第三个值为权值\n);for(k=0;kg-e;k++)//将村庄到各个村庄的路径都都表示到矩阵上{scanf(%d%d%d,&i,&j,&m);g-edges[i][j]=m;g-edges[j][i]=m;}}voidshortlu(mgrgh*g)//求出最短路径{inti,j,min,k,x;inta[100]={0};4i=0;//利用循环，将各个村庄到各村庄的距离求出for(j=0;jg-n;j++){a[i]=a[i]+g-edges[i][j];}i=1;for(j=0;jg-n;j++){a[i]=a[i]+g-edges[i][j];}i=2;for(j=0;jg-n;j++){a[i]=a[i]+g-edges[i][j];}i=3;for(j=0;jg-n;j++){a[i]=a[i]+g-edges[i][j];}printf(*********************************************************\n);for(i=0;ig-n;i++){printf(村庄%c到各村庄之间的距离为%d\n,g-vexs[i],a[i]);}min=10000;for(j=0;jg-n;j++){if(a[j]min){k=a[j];a[j]=min;min=k;x=j;}}printf(*********************************************************\n);printf(村庄%c到各个村庄的距离最短为%d\n,g-vexs[x],min);printf(*********************************************************\n);printf(所以医院应该设在%c村庄处!\n,g-vexs[x]);}voidmain(){createmgrgh(&M);shortlu(&M);}程序运行结果截屏：1、输入村庄个数和总共的道路数：52、输入个村庄的字母表示：3、输入各个村庄到各村庄的路径大小值，其中输入的第三个值为道路长度：63、最终最短路径显示：7五、实验总结本实验过程中，我们小组通过一起的学习与讨论，以求得各村庄到其他村庄的距离为主题，对图的存储和应用有了更多的认识，在编写程序过程中，对于getchar的应用也有了更好的掌握，getchar能把回车符吃掉，所以以后必须谨慎小心应用。