《数据结构》课程设计报告

江西理工大学软件学院

《数据结构》课程设计报告

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 程序实行的接口