1、 数据结构课程设计 设计说明书 医院选址问题 起止日期： 2013 年 12 月 23 日 至 2013 年 12 月 27 日 学生姓名 班级 成绩 指 导 教 师 ( 签 字 ) 课程设计任务书 20132014 学年第学年第 1 学期学期 课程设计名称： 数据结构课程设计 设计题目： 医院选址问题 完成期限：自 2013 年 12 月 23 日至 2013 年 12 月 27 日共 1 周 设计依据、要求及主要内容（可另加附页） ： 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 在本课程设计过程中要求学生： （1）重视课程设计环节，用严谨
2、、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者 皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程 设计成绩。 （3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表。 （4）认真编写课程设计报告。 三、设计内容 1)1)问题描述问题描述 n 个村庄之间的交通图可以用有向网图来表示， 图中边上的权值表示从村庄 i 到村庄 j 的道路长 度。现在要从这 n 个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄 离医院都比较近？ 2)
3、 2) 基本要求基本要求 (1) 建立模型，设计存储结构； (2) 设计算法完成问题求解； (3) 分析算法的时间复杂度。 3) 3) 设计思想设计思想 医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。 设图 G=（V，E） ，对任一顶点 k，称 E(k)=maxd(i, k)（iV）为顶点 k 的偏心度。显然，偏心度最 小的顶点即为图 G 的中心点。 如图 7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。 医院选址问题的算法用伪代码描述如下： 1对加权有向图，调用 Floyd 算法，求每对顶点间最短路径长度的矩阵； 2对最短路径长度矩阵的每列求大值，即得到各顶点的
4、偏心度； 3具有最小偏心度的顶点即为所求。 四、参考文献 1、王红梅，数据结构，清华大学出版社 2、王红梅，数据结构学习辅导与实验指导，清华大学出版社 3、严蔚敏、吴伟民， 数据结构 C 语言版 ，清华大学出版社（配题集） a b c d e 1 2 5 3 2 1 4 顶点 偏心度 a b 6 c 8 d 5 e 7 (a) (b) 图 7 带权有向图及各顶点的偏心度 目 录目 录 1、设计目的 . 1 2、总体设计 . 1 3、详细设计 . 1 3.1、程序具体功能： 1 3.2、调试分析： 4 4、源程序和运行结果 . 4 4.1、源程序 4 4.2、运行结果 9 5、心得体会 . 9
5、6、参考文献 10 1 医院选址问题医院选址问题 1 1、设计目的、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 2 2、总体设计、总体设计 3 3、详细设计、详细设计 3.13.1、程序具体功能：、程序具体功能： 1输入函数 从键盘输入村庄的个数、道路的个数、以及各个村庄之间的距离，采用邻接矩阵存储，带有 相应的异常处理。 核心代码： void input() bool flag=true; while(flag) 医院选址问题医院选址问题 输入输入 求最短路径求最短路径 求最小偏心度求最小偏心度 输出输出 2 coutroad_number else cou
6、tcountry_namei; 2.求最短路径 对加权有向图，调用 Floyd 算法，求每对顶点间最短路径长度的矩阵。 核心代码： void MGraph:Floyd()/Floyd 算法 int i,j,k; for (i=1; ii; cinj; cinw; arcij=w; coutcountry_number)/异常检测 break; else coutroad_number else coutcountry_namei; void main( ) input(); MGraph MG(country_name, country_number,road_number); MG.Floyd(); cout“医院应该建在“country_nameMG.min()“村庄！“endl; 9 4.24.2、运行结果、运行结果 5 5、心
