医院选址问题.doc

课程设计任务书 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)所示。 1 2 3 4 5 1 2 5 3 2 1 4 顶点 偏心度 a ¥ b 6 b 8 d 5 e 7 (a) (b) 图7 带权有向图及各顶点的偏心度 医院选址问题的算法用伪代码描述如下： 1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵； 2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度； 3．具有最小偏心度的顶点即为所求。 【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？ 答：通过将图存储的方法很多，这儿用数组，简单化数据，可以更好的编号和运行程序。 四、 参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社 3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 2 目录 一、 需求分析 1 二、 概要设计 1 三、 详细设计 2 四、 调试分析 4 五、 核心源程序清单和执行结果 6 六、 感想与体会 10 一、 需求分析 1． 程序的功能； 从n个村庄中选择一个村庄新建一所医院，使这所医院离所有村庄都比较近。 2． 输入输出的要求； 输入：每个村庄的起点、终点和距离。 输出：离所有村庄都比较近的医院位置 3． 测试数据。 1 2 3 4 5 1 2 5 3 2 1 4 顶点 偏心度 a ¥ b 6 b 8 d 5 e 7 (a) (b) 图1 带权有向图及各顶点的偏心度 上图为测试数据 二、 概要设计 该程序使用数组存储矩阵，即顺序表存储结构。 开始 A：输入村庄数 B：输入道路数 C：create函数得到原始邻接矩阵 Floyd算法将每一对顶点的路径编程最短路径 minp函数找出最小偏心度的村庄 程序结束 三、 详细设计 //Floyd算法将每一对顶点的路径编程最短路径 void Floyd(int dist[][M],int m) { int i,j; for(int k=0;k<m;k++) for(i=0;i<m;i++) for(j=0;j<m;j++) if(dist[i][k]+dist[k][j]<dist[i][j]) dist[i][j]=dist[i][k]+dist[k][j]; cout<<endl<<"每对顶点路径最短的邻接矩阵为："<<endl<<endl; cout<<"====================="<<endl; for(i=0;i<m;i++) { for(j=0;j<m;j++) { if(dist[i][j]!=100) cout<<" "; cout<<dist[i][j]<<" "; } cout<<endl; } cout<<"====================="<<endl; } //Minp函数求最小偏心度的村庄 void minp(int c[][M],int m) { int inmax[M]; int i,j; for(i=0;i<m;i++) inmax[i]=0; for(j=0;j<m;j++) { int t=0; for(i=0;i<m;i++) { if(t<c[i][j]) t=c[i][j]; } inmax[j]=t; } cout<<endl<<"村庄的偏心度依次为："; for(i=0;i<m;i++) cout<<inmax[i]<<" "; cout<<endl; int max=inmax[0]; int l; for(i=0;i<m;i++) //比较inmax数组中元素的大小，并输出最小元素下标+1,即为建医院的地点 if(inmax[i]<max) { max=inmax[i]; l=i; } cout<<"所以医院应该建在村庄"<<l+1<<"中"<<endl; } void create(int n,int l,int c[][M]) { cout<<endl<<" ============================================================"<<endl; int i,j,weight; for(i=0;i<n;i++) { for(j=0;j<n;j++) c[i][j]=Maxint; c[i][i]=0; } for(int k=0;k<l;k++) { cout<<"请输入第"<<k+1<<"条道路的起点、终点和它的长度(中间用空格隔开):"; C: cin>>i>>j>>weight; if(i>n||i<0||j>n||j<0||weight>Maxint||weight<0) { cout<<"输入非法，请重输该边的所有值"<<endl; goto C; } c[i-1][j-1]=weight; } cout<<" ================================================================"<<endl<<endl; cout<<"整理得到原始邻接矩阵为："<<endl; cout<<"============================="<<endl; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(c[i][j]!=100) cout<<" "; cout<<c[i][j]<<" "; } cout<<endl; } cout<<"=============================="<<endl<<endl; } 四、 调试分析 通过题目所给例子进行测试和分析，最终得到结构如下截图： 五、 核心源程序清单和执行结果 09710207郑朋（数据结构）.cpp // 09710207郑朋（数据结构）.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" int _tmain(int argc, _TCHAR* argv[]) { return 0; } #include<iostream> using namespace std; const int Maxint=100; const int M=50; //定义村庄个数的最大值 void Floyd(int dist[][M],int m)//Floyd算法将每一对顶点的路径编程最短路径 { int i,j; for(int k=0;k<m;k++) for(i=0;i<m;i++) for(j=0;j<m;j++) if(dist[i][k]+dist[k][j]<dist[i][j]) dist[i][j]=dist[i][k]+dist[k][j]; cout<<endl<<"每对顶点路径最短的邻接矩阵为："<<endl<<endl; cout<<"====================="<<endl; for(i=0;i<m;i++) { for(j=0;j<m;j++) { if(dist[i][j]!=100) cout<<" "; cout<<dist[i][j]<<" "; } cout<<endl; } cout<<"====================="<<endl; } void minp(int c[][M],int m) //该函数用于找出最小偏心度的村庄 { int inmax[M]; int i,j; for(i=0;i<m;i++) inmax[i]=0; for(j=0;j<m;j++) //inmax数组用来保存最短路径,即邻接矩阵每一列的最大值，也就是每个村庄的偏心度 { int t=0; for(i=0;i<m;i++) { if(t<c[i][j]) t=c[i][j]; } inmax[j]=t; } cout<<endl<<"村庄的偏心度依次为："; for(i=0;i<m;i++) cout<<inmax[i]<<" "; cout<<endl; int max=inmax[0]; int l; for(i=0;i<m;i++) //比较inmax数组中元素的大小，并输出最小元素下标