数据结构实验报告
实验五
实验题目：图子系统 指导老师：王春红
专业班级：计算机科学与技术系1105班 姓 名：李慧2011100521杜丽20111005122
2013年 5月23日
白莹2011100523王媛2011100529
实验类型 综合 实验室_软件实验室一__
一、实验题目
1
图子系统
二、实验目的和要求
１．掌握图的存储思想及其存储实现
２．掌握图的深度、广度优先遍历算法思想及其程序实现 ３．掌握图的常见应用算法的思想及其程序实现 。
三、实验内容
实验内容二：所有顶点对的最短路径
1．设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。 2．设计分析
用有向加权图表示的交通图中，有向边
typedef char vextype;/*顶点数据类型*/ typedef int edgetype;/*边数据类型*/ typedef struct {
vextype vex[maxsize];
edgetype arc[maxsize][maxsize]; int vexnum,arcnum; }Mgraph; 小组分工：
组长：王媛 定义结构体和主函数 组员：李慧 void juzhen(Mgraph *G)
白莹、杜丽void panduan(Mgraph *G)
四、 实验步骤
程序如下：
#include
typedef int edgetype; typedef char vextype; typedef struct
2
{
vextype ver[4];
edgetype edge[4][4]; int edgenum,vernum; }Mgraph;
void juzhen(Mgraph *G) {
int i,j;
printf(\四个村庄的邻接矩阵为:\\n\ for(i=0;i<4;i++) for(j=0;j<4;j++)
scanf(\}
void panduan(Mgraph *G) {
int a[4],b[4],c[4]; int i,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(k=0;k<4;k++) {
if(b[k] t=b[k]; p=k; } } a[p]=1; printf(\到%d的最短路径为：%d\\n\ q=2; while(q>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]; 3 } t=max; for(k=0;k<4;k++) { if(b[k] t=b[k]; p=k; } } a[p]=1; q--; printf(\到%d的最短路径为：%d\\n\ } t2=min; for(k=0;k<4;k++) { if(t2 t2=b[k]; } c[i]=t2; } }//i的循环结束 t=max; for(k=0;k<4;k++) { if(t>c[k]) { t=c[k]; n=k; } } switch(n) { case 0: printf(\医院设在0村庄!\ printf(\到最远村庄的最近距离为:%d\\n\ break; case 1: printf(\医院设在1村庄!\ printf(\到最远村庄的最近距离为:%d\\n\ break; case 2: 4 printf(\医院设在2村庄!\ printf(\到最远村庄的最近距离为:%d\\n\ break; case 3: printf(\医院设在3村庄!\ printf(\到最远村庄的最近距离为:%d\\n\ break; } } main() { Mgraph *G; G=(Mgraph*)malloc(sizeof(Mgraph)); juzhen(G); panduan(G); } 实验结果如下： 五、 实验总结 这次实验和之前的实验相比有一定的难度，需要对实验的思路特别清晰，在其中设定的变量有些多，要特别注意，其中遇到了很多的问题，通过请教同学老师最终得出了结果！ 5