《最短村庄报告》由会员分享，可在线阅读，更多相关《最短村庄报告（7页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验五实验题目：图子系统指导老师：专业班级： 2013年 5月23日实验类型_综合_ 实验室_软件实验室一_一、实验题目图子系统二、实验目的和要求 掌握图的存储思想及其存储实现 掌握图的深度、广度优先遍历算法思想及其程序实现 掌握图的常见应用算法的思想及其程序实现 三、实验内容实验内容二：所有顶点对的最短路径1设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。 2设计分析 用有向加权图表示的交通图中，有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路
2、的长度。该问题的实质是求解任意两顶点间的最短路径问题。即求出每个顶点到其他顶点的最短路径的最大值，最大值最小的顶点作为医院所在村庄。3结构类型定义typedef char vextype;/*顶点数据类型*/typedef int edgetype;/*边数据类型*/typedef structvextype vexmaxsize; edgetype arcmaxsizemaxsize; int vexnum,arcnum;Mgraph;四、 实验步骤实验代码：#include#define maxvertexnum 100 /将maxvertexnum的值赋为100typedef char
3、vertextype; /将char类型用vertextype表示typedef int edgetype; /将int用edgetype表示typedef structvertextype vexsmaxvertexnum; /定义一维数组顶点vexs，用来存储图的顶点字母edgetype edgesmaxvertexnummaxvertexnum; /定义二维数组用来存放边的值int n,e;/n表示顶点的数目，e表示边的数目mgrgh;mgrgh M;void createmgrgh(mgrgh *g);void shortlu(mgrgh *g);void createmgrgh(mg
4、rgh *g)/初始化图int i,j,k,m;printf(*n);printf(请输入村庄的个数和到各村庄的道路数n);scanf(%d%d,&g-n,&g-e);getchar();printf(*n);printf(请输入各个村庄的字母表示n);for(i=0;in;i+) g-vexsi=getchar(); for(i=0;in;i+)/将村庄到各个村庄的路径都赋初值为0for(j=0;jn;j+)g-edgesij=0;printf(*n);printf(输入各个村庄到各村庄的路径大小值，其中输入的第三个值为权值n);for(k=0;ke;k+) /将村庄到各个村庄的路径都都表示
5、到矩阵上scanf(%d%d%d,&i,&j,&m);g-edgesij=m;g-edgesji=m;void shortlu(mgrgh *g)/求出最短路径int i,j,min,k,x;int a100=0; i=0;/利用循环，将各个村庄到各村庄的距离求出for(j=0;jn;j+)ai=ai+g-edgesij;i=1;for(j=0;jn;j+)ai=ai+g-edgesij;i=2;for(j=0;jn;j+)ai=ai+g-edgesij;i=3;for(j=0;jn;j+)ai=ai+g-edgesij;printf(*n);for(i=0;in;i+)printf(村庄%c
6、到各村庄之间的距离为%dn,g-vexsi,ai);min=10000;for(j=0;jn;j+)if(ajvexsx,min);printf(*n);printf(所以医院应该设在%c村庄处!n,g-vexsx);void main() createmgrgh(&M);shortlu(&M);程序运行结果截屏：1、输入村庄个数和总共的道路数：2、输入个村庄的字母表示：3、输入各个村庄到各村庄的路径大小值，其中输入的第三个值为道路长度：3、最终最短路径显示：五、实验总结本实验过程中，我们小组通过一起的学习与讨论，以求得各村庄到其他村庄的距离为主题，对图的存储和应用有了更多的认识，在编写程序过程中，对于getchar的应用也有了更好的掌握，getchar能把回车符吃掉，所以以后必须谨慎小心应用。
