据结构实验五图子系统

《据结构实验五图子系统》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构实验报告实验五实验题目：图子系统指导老师：王春红专业班级：计算机科学与技术系1105班姓名：李慧2011100521杜丽20111005122白莹2011100523王媛20111005292013年5月23日实验类型综合实验室_软件实验室一__一、实验题目图子系统二、实验目的和要求5１．掌握图的存储思想及其存储实现２．掌握图的深度、广度优先遍历算法思想及其程序实现３．掌握图的常见应用算法的思想及其程序实现。三、实验内容实验内容二：所有顶点对的最短路径1．设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村

2、庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。2．设计分析用有向加权图表示的交通图中，有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。该问题的实质是求解任意两顶点间的最短路径问题。即求出每个顶点到其他顶点的最短路径的最大值，最大值最小的顶点作为医院所在村庄。3．结构类型定义typedefcharvextype;/*顶点数据类型*/typedefintedgetype;/*边数据类型*/typedefstruct{ vextypevex[maxsize]; edgetypearc[maxsi

3、ze][maxsize];intvexnum,arcnum;}Mgraph;小组分工：组长：王媛定义结构体和主函数组员：李慧voidjuzhen(Mgraph*G)白莹、杜丽voidpanduan(Mgraph*G)四、实验步骤程序如下：#include#include#definemax100#definemin0typedefintedgetype;typedefcharvextype;typedefstruct{vextypever[4];edgetypeedge[4][4];5intedgenum,vernu

4、m;}Mgraph;voidjuzhen(Mgraph*G){inti,j;printf("四个村庄的邻接矩阵为:");for(i=0;i<4;i++)for(j=0;j<4;j++)scanf("%d",&G->edge[i][j]);}voidpanduan(Mgraph*G){inta[4],b[4],c[4];inti,j,t,t2,p,q,n,k;for(i=0;i<4;i++){a[0]=0;a[1]=0;a[2]=0;a[3]=0;a[i]=1;for(j=0;j<4;j++){b[j]=G->edge[i][j];}t=max;for

5、(k=0;k<4;k++){if(b[k]0){for(k=0;k<4;k++){if(a[k]==0)if(b[k]>(b[p]+G->edge[p][k]))b[k]=b[p]+G->edge[p][k];}t=max;for(k=0;k<4;k++)5{if(b[k]

6、p,b[p]);}t2=min;for(k=0;k<4;k++){if(t2c[k]){t=c[k];n=k;}}switch(n){case0:printf("医院设在0村庄!");printf("0到最远村庄的最近距离为:%d",t);break;case1:printf("医院设在1村庄!");printf("1到最远村庄的最近距离为:%d",t);break;case2:printf("医院设在2村庄

7、!");printf("2到最远村庄的最近距离为:%d",t);break;5case3:printf("医院设在3村庄!");printf("3到最远村庄的最近距离为:%d",t);break;}}main(){Mgraph*G;G=(Mgraph*)malloc(sizeof(Mgraph));juzhen(G);panduan(G);}实验结果如下：四、实验总结这次实验和之前的实验相比有一定的难度，需要对实验的思路特别清晰，在其中设定的变量有些多，要特别注意，其中遇到了很多的问题，通过请教同学老师最终得出了结果！5