数据结构程序设计医院选址问题

1、数据结构-程序设计一医院选址 问题问题医院选址问题起止日期：2011年12月12日 至2011年12月16日学生姓名班级成绩指导教师（签字）电子与信息工程系2011年12月16日天津城市建设学院课程设计任务书2011-2012学年第1学期电子与信息工程 系 软件工程 专业 班级课程设计名称：数据结构课程设计设计题目：医院选址问题 完成期限：自2011年12月12日至2011年12月16日共1周设计依据、要求及主要内容（可另加附页）：、设计目的熟悉各种数据结构和运算，会使用数据结构的基 本操作解决一些实际问题。二、设计要求（1）重视课程设计环节，用严谨、科学和踏实 的工作态度对待课程设计的每一项

2、任务；（2）按照课程设计的题目要求，独立地完成各 项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者 皆以零分计入本课程设计成绩。凡发现实验报告或源 程序雷同，涉及的全部人员皆以零分计入本课程设计 成绩；（3）学生在接受设计任务后，首先要按设计任务 书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容7.医院选址问题问题描述liiJn个村庄之间的交通图可以用有向网图来表示， 图中边v四v上的权值表示从村庄i到村庄/的道路 长度。现在要从这n个村庄中选择一个村庄新建一所 医院，问这所医院应建在哪个村庄，才能使所有的村 庄离医院都比较近？基本要求建立模型，设计存储结构；设计算法完成问题求解

3、；分析算法的时间复杂度。设计思想医院选址问题实际是求有向图中心点的问题。首 先定义顶点的偏心度。设图 G=( V, E ),对任一顶点 A,称 E(k) =maxd (i, k) (iV)为顶点k的偏心度。显然，偏心度最小 的顶点即为图G的中心点。如图7(a)所示是一个带权有向图，其各顶点的偏 心度如图(b)所示。顶偏心a_b_6_b_8d5e7(b)医院选址问题的算泱用制通描述如下：.对加权有向图，调用Floyd算法，求每对顶 点间最短路径长度的矩阵；.对最短路径长度矩阵的每列求大值，即得到 各顶点的偏心度；.具有最小偏心度的顶点即为所求。四、参考文献1.王红梅.数据结构.清华大学出版社2

4、.王红梅.数据结构学习辅导与实验指导.清 华大学出版社一.严蔚敏，吴伟民.数据结构（C语言版）.清 华大学出版社一、需求分析二顶点偏心度a8b6b8d5G!7总体设计林gg输入村庄的个数、名称，输入村庄间路的个数以 及每条路的长度（权值）；程序根据权值以及路来求解得出医院的地址。=/=J医院的地址要求:每个村庄到医院的路径最长的 值要最小。二、问题求解在现实中我会以其中为终点以同样的速度在每 个村庄走到终点的时间记录下最长的时间为该点为 终点时的一个值。难后比较那个点为终点时所用的时 间值是最小的。 TOC o 1-5 h z abcdea13 5 7b2 4 6c324d 137e685入偏

5、出函最心函四、1详细H设计输入函数：-.“.n 、Hospital:Hospital(T a, int n, int e)IvertexNum=n;arcNum=e;int i,j,k,value;for (i=0;ivertexNum;i+)adjlisti.vertex=ai;adjlisti.firstedge=NULL;for(k=0;karcNum;k+)cout输入边所依附的两个顶点的序号ij;cout输入边的权值value;ArcNode *s=new ArcNode;s-adjvex=j;s-info=value;s-next=adjlisti.firstedge;adjlis

6、ti.firstedge=s;计算最短路径：求最短路径的长度for(i=0;icountrynum;i+)for(j=0;jcountrynum;j+)for(k=0;k0)if(valueik+valuekj0&valuekj0) valueij=valueik+valuekj;elseif(valueik0&valuekj0) valueij=valueik+valuekj;求偏心度：对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度for (j=0;jcountrynum;j+) for(i=0;icountrynum;i+)if(sumvalueij&valueij!=9999)sum=valueij;pj=sum;sum=0;输出函数：cout医院地址应该选在：adjlistm.vertex0)来确定是否用k的中间值来求解求解最短路径。六、关键源程序清单和执行结果测试所用数据：一jl 一 _string countryname5= a , b , c , d , e ;int countrynum=5,road=7;腋入边所依附的两个顶点的序号0 1隔入边的权值1输入边所依附的两个顶点的序号边的权值输入边所依附的两个顶点的序号抄地的权