医院选址问题C语言实现.doc
文本预览下载声明
乡运城学ft
数据结构实验报告
实验五
实验题目:
图的操作
指导老师:
李萍
专业班级:
计算机科学与技术系1103班
姓 名:
张凯强( 2010100236 )
贺彦强( 2011100350 )
甄伟杰( 2011100349 )
靳 丽( 2011 100317 )
郭嘉欣( 2011100306 )
2013年5月23日
实验类型-验证实验室软件实验室一
实验类型-验证
一、 实验题冃
所有顶点对的最短路径
二、 实验目的和耍求
1 .掌握图的存储思想及其存储实现
掌握图的深度、广度优先遍历算法思想及其程序实现
掌握图的常见应用算法的思想及其程序实现
三、 实验内容
设置4个村庄之间的交通,村庄之间的距离用各边上的权值來表示。现 在要求从这4个村庄中选择一个村庄建一所医院,问这所医院应建在哪个村 庄,才能使离医院最远的村庄到医院最近。
设计分析
用有向加权图表示的交通图中,有向边<vi,vj>表示第i个村庄和第j个 村庄之间有道路,边上的权表示这条道路的长度。该问题的实质是求解任意 两顶点间的最短路径问题。即求出每个顶点到艾他顶点的最短路径的最大 值,最人值最小的顶点作为医院所在村庄。
结构类型定义
typedef char vextype;/*顶点数据类型*/
typedef int edgetype;A边数据类型*/ typedef struct
{
vcxtypc vex[maxsizc];
edgetype arc[maxsize][maxsize];
int vexnum, arcnum;
}Mgraph;
四、 实验步骤
1?打开 visual c++ 6. Oo
2?小组内进行讨论,确定组内分工。
?编写代码。
(小组内任务分配:)
张凯强(2010100236):主函数
贺彦强(2011100350):顶点定位函数 甄伟杰(2011100349):动态数组的建立 靳 丽(2011100317):最短路径求解函数 郭嘉欣(2011100306):图的建立函数
?调试运行。
五、 运行截图
测试一:
设计村庄分布图1:
121216
12
12
16
16
3
3
5
5
20
20
10
10
2 3 0 3 1111 为为为为 离离离离 巨巨巨巨 庄庄庄庄 远远远远 曰WWW販 离离离离
nu nH 院院院院 医医医咲 B--二B--二B--二B-二 3S3I3I3I 庄庄庄庄 tTTT A B c D 在在在在 当当当当
构造有向网G,请输入图的当前顶点数和弧数: 舊蕭入各个弧和权,构造邻接矩阵:
B
A
D
B
C
D
A
C
D
A
C
B
图成功建立!
C B 10
图成功建立!
霭髀蠶聲村庄建医院,离最远村庄的距离为丄0;
测试二
10105588151513131111
10
10
5
5
8
8
15
15
13
13
11
11
II
II
当在A 当在B 当在C 当在D
图成功建立!
离取远村庄的距离为d;
庄的距罔为15
1?
■ J ■ J ■ J ?J 远远远远 曰WWW甌 离离离离
0 0 0 0 院院院院
S选键
舊益入各个弧和权,构造邻接矩阵:
B
A
C
B
D
C
A
D
C
A
D
B
测试三:
设计村庄分布图3:
10
13
13
15 图成弟建立!
iuE
nn nn nn nnmm -me.
nn nn nn nn
mm -me. 远远远远 曰www取 离离离离
址豔黯籐A村庄建医院,离最远村庄的距离为丄3;
六、 实验总结
通过本次对图的操作,我们觉得用图解决问题比较复杂,不过 我们相信熟能生巧,我们一定在课下加强对图各个操作的练习,以达 到课程的要求。
七、 代码:
#includestdio.h
#includestdlib.h
#define INFINITY 1000000 〃最人值
#define maxsize 20 〃最大顶点个数
typedef enum Statusf NO?OK}Status;
typedef enum State{FALSE,TRUE} State;
typedef char vextype;// 顶点数据类型
typedef inf edgetype;//边权值类型
typedef struct MGraph {
vextype vex[maxsizej;
edgetype arcs [maxsize] [miixsize];
int vexnum,arcnum;
JMGraph;
int LocateVex(MGraph *Qvextype v)
{
int i;
for(i=0;iG-vexnum;i++)
{
if(G-vex[i]==v) return i;
}
}
Status Create(MG
显示全部