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

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

2、节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容7医院选址问题1)问题描述n个村庄之间的交通图可以用有向网图来表示，图中边<vi, vj>上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？2

3、) 基本要求(1) 建立模型，设计存储结构；(2) 设计算法完成问题求解；(3) 分析算法的时间复杂度。3) 设计思想医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。设图G=（V，E），对任一顶点k，称E(k)=maxd(i, k)（iV）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。如图7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。abcde1253214顶点偏心度a ¥b 6b 8d 5e 7 (a) (b) 图7 带权有向图及各顶点的偏心度医院选址问题的算法用伪代码描述如下：1对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的

4、矩阵；2对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；3具有最小偏心度的顶点即为所求。四、参考文献1王红梅数据结构清华大学出版社2王红梅数据结构学习辅导与实验指导清华大学出版社一 严蔚敏，吴伟民数据结构（C语言版）清华大学出版社一、需求分析输入村庄的个数、名称，输入村庄间路的个数以及每条路的长度（权值）；程序根据权值以及路来求解得出医院的地址。医院的地址要求：每个村庄到医院的路径最长的值要最小。二、问题求解在现实中我会以其中为终点以同样的速度在每个村庄走到终点的时间记录下最长的时间为该点为终点时的一个值。难后比较那个点为终点时所用的时间值是最小的。 a b c d ea 1 3 5 7

5、b 2 4 6c 3 2 4d 1 3 7e 6 8 5三、总体设计医院选址输入函数输出函数计算最短路径求偏心度四、详细设计输入函数：Hospital<T>:Hospital(T a,int n,int e)vertexNum=n;arcNum=e;int i,j,k,value;for(i=0;i<vertexNum;i+)adjlisti.vertex=ai;adjlisti.firstedge=NULL;for(k=0;k<arcNum;k+)cout<<"输入边所依附的两个顶点的序号"<<endl;cin>>

6、;i>>j;cout<<"输入边的权值"<<endl;cin>>value;ArcNode *s=new ArcNode;s->adjvex=j;s->info=value;s->next=adjlisti.firstedge;adjlisti.firstedge=s;计算最短路径：/求最短路径的长度for(i=0;i<countrynum;i+)for(j=0;j<countrynum;j+)for(k=0;k<countrynum;k+)if(valueij>0)if(valuei

7、k+valuekj<valueij&&valueik>0&&valuekj>0)valueij=valueik+valuekj;elseif(valueik>0&&valuekj>0)valueij=valueik+valuekj;求偏心度：/对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度for(j=0;j<countrynum;j+)for(i=0;i<countrynum;i+)if(sum<valueij&&valueij!=9999)sum=valueij;pj=sum;sum=0;输出函数：cout<<"医院地址应该选在："<<adjlistm.vertex<<endl;五、调试与测试在测试中权值的初始话以及最短路径的计算时出现没赋值、赋值出错等问题。if(valueij>0)来确定是否用k的中间值来求解求解最短路径。六、关键源程序清单和执行结果测试所用