江西理工大学软件学院
《数据结构》课程设计报告
2016—2017学年第一学期
课程名称 数据结构 设计题目 医院选址问题 专业班级 物联网151班 姓 名 赵雨新 目录
任务描述 .................................................................................................................... 3 1、 问题描述： ................................................................................................... 3 2、 基本要求： ................................................................................................... 3 设计与实现 ................................................................................................................ 3 1.数据结构的设计................................................................................................... 3 2.算法的设计 .......................................................................................................... 4 3.抽象数据类型的设计 ........................................................................................... 5 4.源代码 ................................................................................................................. 5 运行测试 .................................................................................................................... 9 1.遇到的错误与解决 ............................................................................................... 9 2.调试分析 ............................................................................................................. 9 总结 ......................................................................................................................... 11 参考文献 .................................................................................................................. 11
任务描述
1、 问题描述：
要在n个村庄中选择一个村庄新建一所医院，问这所医院应该建在那个村庄，才能使得所有村庄离医院都比较近？
2、 基本要求：
（1） 建立模型，设计数据结构 （2） 设计算法完成问题的求解 （3） 分析算法的时间复杂度
设计与实现
1.数据结构的设计
医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。
设图G=（V，E），对任一顶点k，称E(k)=max{d(i, k)}（i∈V）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。
医院选址问题的算法用伪代码描述如下：
1． 2． 3．
对加权有向图，调用Floyd算法，求每对顶点间最短路径长度矩阵 对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度 具有最小偏心度的顶点即为所求
2.算法的设计
本程序从总体上划分为三个模块：
（1）MGraph.h定义一个头文件，包括了使邻接矩阵实现的一系列变量和数组。
伪代码如下:
1) 定义实现基于邻接矩阵结构的抽象数据类MGraph
2) 在public：里定义MGraph构造函数和floyd算法和min算法 3) 在private：里定义实现邻接矩阵的变量
（2）MGrah.cpp实现程序的具体功能
伪代码如下：
1) 结构函数MGraph()的实现，输出初始的邻接矩阵 2) 实现Floyd算法，输出最终的邻接矩阵 3) min()函数的实现，输出偏心度
（3）Main.cpp 程序实行的接口
相关推荐：
loading