医院选址问题

1课程设计任务书2011—2012学年第1学期电子与信息工程系计算机科学与技术专业班级课程设计名称：数据结构课程设计设计题目：医院选址问题完成期限：自2012年1月2日至2012年1月6日共1周一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求1.重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；2.按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；3.学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；4.认真编写课程设计报告。三、设计内容医院选址问题1.问题描述n个村庄之间的交通图可以用有向网图来表示，图中边vi,vj上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？2.基本要求(1)建立模型，设计存储结构；(2)设计算法完成问题求解；(3)分析算法的时间复杂度。3.设计思想医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。设图G=（V，E），对任一顶点k，称E(k)=max{d(i,k)}（i∈V）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。如图7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。123451253214顶点偏心度ab6b8d5e7(a)(b)2医院选址问题的算法用伪代码描述如下：1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；3．具有最小偏心度的顶点即为所求。【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？答：通过将图存储的方法很多，这儿用数组，简单化数据，可以更好的编号和运行程序。四、参考文献1．王红梅．数据结构．清华大学出版社2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社目录一、需求分析.....................................................1二、概要设计.....................................................1三、详细设计.....................................................2四、调试分析.....................................................4五、核心源程序清单和执行结果.....................................6六、感想与体会..................................................101一、需求分析1．程序的功能；从n个村庄中选择一个村庄新建一所医院，使这所医院离所有村庄都比较近。2．输入输出的要求；输入：每个村庄的起点、终点和距离。输出：离所有村庄都比较近的医院位置3．测试数据。上图为测试数据二、概要设计该程序使用数组存储矩阵，即顺序表存储结构。123451253214顶点偏心度ab6b8d5e7(a)(b)图1带权有向图及各顶点的偏心度开始A：输入村庄数B：输入道路数C：create函数得到原始邻接矩阵Floyd算法将每一对顶点的路径编程最短路径2三、详细设计//Floyd算法将每一对顶点的路径编程最短路径voidFloyd(intdist[][M],intm){inti,j;for(intk=0;km;k++)for(i=0;im;i++)for(j=0;jm;j++)if(dist[i][k]+dist[k][j]dist[i][j])dist[i][j]=dist[i][k]+dist[k][j];coutendl每对顶点路径最短的邻接矩阵为：endlendl;cout=====================endl;for(i=0;im;i++){for(j=0;jm;j++){if(dist[i][j]!=100)cout;coutdist[i][j];}coutendl;}cout=====================endl;}//Minp函数求最小偏心度的村庄voidminp(intc[][M],intm){minp函数找出最小偏心度的村庄程序结束3intinmax[M];inti,j;for(i=0;im;i++)inmax[i]=0;for(j=0;jm;j++){intt=0;for(i=0;im;i++){if(tc[i][j])t=c[i][j];}inmax[j]=t;}coutendl村庄的偏心度依次为：;for(i=0;im;i++)coutinmax[i];coutendl;intmax=inmax[0];intl;for(i=0;im;i++)//比较inmax数组中元素的大小，并输出最小元素下标+1,即为建医院的地点if(inmax[i]max){max=inmax[i];l=i;}cout所以医院应该建在村庄l+1中endl;}voidcreate(intn,intl,intc[][M]){coutendl============================================================endl;inti,j,weight;for(i=0;in;i++){for(j=0;jn;j++)c[i][j]=Maxint;c[i][i]=0;}for(intk=0;kl;k++){cout请输入第k+1条道路的起点、终点和它的长度(中间用空格隔开):;4C:cinijweight;if(in||i0||jn||j0||weightMaxint||weight0){cout输入非法，请重输该边的所有值endl;gotoC;}c[i-1][j-1]=weight;}cout================================================================endlendl;cout整理得到原始邻接矩阵为：endl;cout=============================endl;for(i=0;in;i++){for(j=0;jn;j++){if(c[i][j]!=100)cout;coutc[i][j];}coutendl;}cout==============================endlendl;}四、调试分析通过题目所给例子进行测试和分析，最终得到结构如下截图：56五、核心源程序清单和执行结果09710207郑朋（数据结构）.cpp//09710207郑朋（数据结构）.cpp:定义控制台应用程序的入口点。//#includestdafx.hint_tmain(intargc,_TCHAR*argv[]){7return0;}#includeiostreamusingnamespacestd;constintMaxint=100;constintM=50;//定义村庄个数的最大值voidFloyd(intdist[][M],intm)//Floyd算法将每一对顶点的路径编程最短路径{inti,j;for(intk=0;km;k++)for(i=0;im;i++)for(j=0;jm;j++)if(dist[i][k]+dist[k][j]dist[i][j])dist[i][j]=dist[i][k]+dist[k][j];coutendl每对顶点路径最短的邻接矩阵为：endlendl;cout=====================endl;for(i=0;im;i++){for(j=0;jm;j++){if(dist[i][j]!=100)cout;coutdist[i][j];}coutendl;}cout=====================endl;}voidminp(intc[][M],intm)//该函数用于找出最小偏心度的村庄{intinmax[M];inti,j;for(i=0;im;i++)inmax[i]=0;for(j=0;jm;j++)//inmax数组用来保存最短路径,即邻接矩阵每一列的最大值，也就是每个村庄的偏心度{8intt=0;for(i=0;im;i++){if(tc[i][j])t=c[i][j];}inmax[j]=t;}coutendl村庄的偏心度依次为：;for(i=0;im;i++)coutinmax[i];coutendl;intmax=inmax[0];intl;for(i=0;im;i++)//比较inmax数组中元素的大小，并输出最小元素下标+1,即为建医院的地点if(inmax[i]max){max=inmax[i];l=i;}cout所以医院应该建在村庄l+1中endl;}voidcreate(intn,intl,intc[][M]){coutendl============================================================endl;inti,j,weight;for(i=0;in;i++){for(j=0;jn;j++)c[i][j]=Maxint;c[i][i]=0;}for(intk=0;kl;k++){cout请输入第k+1条道路的起点、终点和它的长度(中间用空格隔开):;9C:cinijweight;if(in||i0||jn||j0||weightMaxint||weight0){cout输入非法，请重输该边的所有值endl;gotoC;}c[i-1][j-1]=weight;}cout================================================================endlendl;cout整理得到原始邻接矩阵为：endl;cout=============================endl;for(i=0;in;i++){for(j=0;jn;j++){if(c[i][j]!=100)cout;coutc[i][j];}coutendl;}cout==============================endlendl;}voidmain(){coutendl;cout☆医院选址问题，请按以下步骤操作☆endl;cout================================endlendl;cout将所有村庄和道路分别从编号（即、、.···）endl;intarc[M][M];//用于存储图的邻接矩阵intm;A:cout1.请输入村庄个数：;cinm;if(mM||m0){cout对不起，输入的数值不合法，请重新输入！endlendl;gotoA;10}inte;B:cout2.请输入图中有几条道路：;cine;if(e(m*(m-1))||e0){cout对不起，输入的数值不合法！endlendl;goto