医院选址问题.doc

课程设计任务书20112012学年第1学期电子与信息工程 系 计算机科学与技术 专业 班级课程设计名称： 数据结构课程设计 设计题目： 医院选址问题 完成期限：自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周一、 设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、 设计要求 1. 重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；2. 按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；3. 学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；4. 认真编写课程设计报告。三、 设计内容医院选址问题1. 问题描述n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？2. 基本要求(1) 建立模型，设计存储结构；(2) 设计算法完成问题求解；(3) 分析算法的时间复杂度。3. 设计思想医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。设图G=（V，E），对任一顶点k，称E(k)=maxd(i, k)（iV）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。如图7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。123451253214顶点偏心度a b 6b 8d 5e 7 (a) (b) 图7 带权有向图及各顶点的偏心度医院选址问题的算法用伪代码描述如下：1对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；2对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；3具有最小偏心度的顶点即为所求。【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？ 答：通过将图存储的方法很多，这儿用数组，简单化数据，可以更好的编号和运行程序。四、 参考文献1王红梅数据结构清华大学出版社2王红梅数据结构学习辅导与实验指导清华大学出版社3严蔚敏，吴伟民数据结构（C语言版）清华大学出版社2目录一、需求分析1二、概要设计1三、详细设计2四、调试分析4五、核心源程序清单和执行结果6六、感想与体会10一、 需求分析1 程序的功能；从n个村庄中选择一个村庄新建一所医院，使这所医院离所有村庄都比较近。2 输入输出的要求；输入：每个村庄的起点、终点和距离。输出：离所有村庄都比较近的医院位置3 测试数据。 123451253214顶点偏心度a b 6b 8d 5e 7 (a) (b) 图1 带权有向图及各顶点的偏心度上图为测试数据二、 概要设计该程序使用数组存储矩阵，即顺序表存储结构。开始A：输入村庄数B：输入道路数C：create函数得到原始邻接矩阵Floyd算法将每一对顶点的路径编程最短路径minp函数找出最小偏心度的村庄程序结束三、 详细设计/Floyd算法将每一对顶点的路径编程最短路径void Floyd(int distM,int m)int i,j;for(int k=0;km;k+) for(i=0;im;i+)for(j=0;jm;j+)if(distik+distkjdistij)distij=distik+distkj;coutendl每对顶点路径最短的邻接矩阵为：endlendl;cout=endl;for(i=0;im;i+)for(j=0;jm;j+)if(distij!=100)cout ;coutdistij ;coutendl;cout=endl;/Minp函数求最小偏心度的村庄void minp(int cM,int m) int inmaxM;int i,j;for(i=0;im;i+)inmaxi=0;for(j=0;jm;j+) int t=0;for(i=0;im;i+)if(tcij)t=cij;inmaxj=t;coutendl村庄的偏心度依次为：;for(i=0;im;i+) coutinmaxi ;coutendl;int max=inmax0;int l;for(i=0;im;i+) /比较inmax数组中元素的大小，并输出最小元素下标+1,即为建医院的地点if(inmaximax)max=inmaxi;l=i;cout所以医院应该建在村庄l+1中endl;void create(int n,int l,int cM) coutendl =endl;int i,j,weight;for(i=0;in;i+)for(j=0;jn;j+) cij=Maxint;cii=0;for(int k=0;kl;k+)cout请输入第k+1ijweight; if(in|in|jMaxint|weight0)cout输入非法，请重输该边的所有值endl;goto C;ci-1j-1=weight;cout =endlendl;cout整理得到原始邻接矩阵为：endl;cout=endl;for(i=0;in;i+)for(j=0;jn;j+)if(cij!=100)cout ;coutcij ;coutendl;cout=endlendl;四、 调试分析通过题目所给例子进行测试和分析，最终得到结构如下截图：五、 核心源程序清单和执行结果09710207郑朋（数据结构）.cpp/ 09710207郑朋（数据结构）.cpp : 定义控制台应用程序的入口点。/#include stdafx.hint _tmain(int argc, _TCHAR* argv)return 0;#includeusing namespace std;const int Maxint=100;const int M=50; /定义村庄个数的最大值void Floyd(int distM,int m)/Floyd算法将每一对顶点的路径编程最短路径int i,j;for(int k=0;km;k+) for(i=0;im;i+)for(j=0;jm;j+)if(distik+distkjdistij)distij=distik+distkj;coutendl每对顶点路径最短的邻接矩阵为：endlendl;cout=endl;for(i=0;im;i+)for(j=0;jm;j+)if(distij!=100)cout ;coutdistij ;coutendl;cout=endl;void minp(int cM,int m) /该函数用于找出最小偏心度的村庄int inmaxM;int i,j;for(i=0;im;i+)inmaxi=0;for(j=0;jm;j+) /inmax数组用来保存最短路径,即邻接矩阵每一列的最大值，也就是每个村庄的偏心度int t=0;for(i=0;im;i+)if(tcij)t=cij;inmaxj=t;coutendl村庄的偏心度依次为：;for(i=0;im;i+) coutinmaxi ;coutendl;int max=inmax0;int l;for(i=0;im;i+) /比较inmax数组中元素的大小，并输出最小元素下标+1,即为建医院的地点if(inmaximax)max=inmaxi;l=i;cout所以医院应该建在村庄l+1中endl;void create(int n,int l,int cM) coutendl =endl;int i,j,weight;for(i=0;in;i+)for(j=0;jn;j+) cij=Maxint;cii=0;for(int k=0;kl;k+)cout请输入第k+1ijweight; if(in|in|jMaxint|weight0)cout输入非法，请重输该边的所有值endl;goto C;ci-1j-1=weight;cout =endlendl;cout整理得到原始邻接矩阵为：endl;cout=endl;for(i=0;in;i+)for(j=0;jn;j+)if(cij!=100)cout ;coutcij ;coutendl;cout=endlendl;void main()coutendl;cout 医院选址问题，请按以下步骤操作endl;cout =endlendl;cout将所有村庄和道路分别从编号（即、.）endl;int arcMM; /用于存储图的邻接矩阵int m;A: coutm;if(mM|m0)cout对不起，输入的数值不合法，请重新输入！endlendl;goto A;int e;B: coute;if(e(m*(m-1)|e0)cout对不起，输入的数值不合法！endlendl;goto B;create(m,e,arc);Floyd(arc,m);minp(arc,m); cout=运行结束=endl;cout endl;cout / endl;cout / endl;cout / 祝老师同学们：endl;cout .-. endl;cout . a_a . 春节愉快合家欢乐！endl;cout =(_)= endl;cout . ._I_. . 心想事成红包拿来！endl;cout _/.-._ endl;cout #(_)# endl;六、 感想与体会编程是一件很枯燥的事情，但也