C++数据结构医院选址课设

目录

一、问题描述 .................................................................................................... 2 二、基本要求 .................................................................................................... 2 三、概要设计 .................................................................................................... 2

1.数据结构的设计 .................................................................................... 2 2.算法的设计 ............................................................................................ 3 3.抽象数据类型的设计 ............................................................................ 3 四、 详细设计 .................................................................................................. 4 五、 运行与测试 .............................................................................................. 6

1.遇到的错误与解决 ................................................................................ 6 2.调试分析 ................................................................................................ 7 3.运行结果 ................................................................................................ 7 六、 总结与心得 .............................................................................................. 8 七、 程序清单 .................................................................................................. 9 参考文献.......................................................................................................... 15

一、

一、问题描述

n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？

二、基本要求

(1) 建立模型，设计存储结构； (2) 设计算法完成问题求解； (3) 分析算法的时间复杂度。

三、概要设计

1.数据结构的设计

医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。

设图G=（V，E），对任一顶点k，称E(k)=max{d(i, k)}（i∈V）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。

如图(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。

a 2 1 b 1 2 d c 3 5 4 e 顶点 a b b d e 偏心度 ? 6 8 5 7 (a) (b) 带权有向图及各顶点的偏心度

医院选址问题的算法用伪代码描述如下：

1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度矩阵； 2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度； 3．具有最小偏心度的顶点即为所求。

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

伪代码如下：

1)定义输入函数input，实现数据的输入，包括村庄的个数和名字以及路的条数

2)定义main（）函数，创建MGraph的对象MG来调用floyd和min算法，输出最后的结果

3.抽象数据类型的设计

用C++语言中的类实现基于邻接矩阵存储结构下图的抽象类数据类型定义。由于图中顶点的数据类型不确定，因此采用C++的模板机制。所以程序中定义了template的模板类。

四、详细设计

1.设计抽象类数据类型对应的C++类定义

定义了template的模板类采用C++的模板机制，因为顶点的数据类型不确定。 2.设计每个函数成员

1)定义输入函数input（），从键盘输入村庄的个数、道路的个数、以及各个村庄之间的距离，采用邻接矩阵存储，带有相应的异常处理。 核心代码如下： void input() {

bool flag=true; while(flag) {

cout<<\请输入村庄的个数：\if(cin>>country_number)//异常检测 break; else { } {

cout<<\请输入道路的条数：\

if(cin>>road_number&&road_number>0&&road_number<= country_number*(coun try_number-1)) break; else{

cout<<\输入有误！\cin.sync(); //清空流 cin.clear(); //清除流错误标记 continue; }

while(flag)

cout<<\输入有误！\cin.sync(); //清空流 cin.clear(); //清除流错误标记 continue; } }

for(int i=1;i<=country_number;i++){ cout<<\请输入第\个村庄的名字：\cin>>country_name[i]; } }

2)定义MGraph()构造函数实现输出有向图的原始邻接矩阵 核心代码如下：

cout<<\初始的邻接矩阵为：\for (i=1; i<=vertexNum; i++) for (j=1; j<=vertexNum; j++) {

cout<

}

3)定义floyd（）函数，每对顶点间最短路径长度的矩阵，实现最终邻接矩阵的输出。 核心代码如下：

void MGraph::Floyd()//Floyd算法 { int i,j,k;

for (i=1; i<=vertexNum; i++) for (j=1; j<=vertexNum; j++) {