医院选址问题

课程设计任务书

2011—2012学年第1学期

电子与信息工程 系 计算机科学与技术 专业 班级 课程设计名称： 数据结构课程设计 设计题目： 医院选址问题

完成期限：自 2012 年 1 月 2 日至 2012 年 1 月 6 日共 1 周

一、 二、

设计目的 设计要求

熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。

1. 重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； 2. 按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者

与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；

3. 学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表； 4. 认真编写课程设计报告。 三、

设计内容 医院选址问题 1. 问题描述

n个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄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 1 2 1 2 3 3 4 4 5 5 顶点 a b b d e 偏心度 ? 6 8 5 7 1

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

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

【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？

答：通过将图存储的方法很多，这儿用数组，简单化数据，可以更好的编号和运行程序。 四、

参考文献

1．王红梅．数据结构．清华大学出版社

2．王红梅．数据结构学习辅导与实验指导．清华大学出版社 3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社

2

目录

一、 二、 三、 四、 五、 六、

需求分析..................................................... 1 概要设计..................................................... 1 详细设计..................................................... 2 调试分析..................................................... 4 核心源程序清单和执行结果..................................... 6 感想与体会.................................................. 10

一、 需求分析

从n个村庄中选择一个村庄新建一所医院，使这所医院离所有村庄都比较近。

1． 程序的功能； 2． 输入输出的要求；

输入：每个村庄的起点、终点和距离。 输出：离所有村庄都比较近的医院位置 3． 测试数据。 2 3 4 顶点 偏心度 a ? 1 1 2 2 3 5 b 6 1 4 5 b 8 d 5 e 7 (a) (b) 图1 带权有向图及各顶点的偏心度

上图为测试数据 二、

概要设计

该程序使用数组存储矩阵，即顺序表存储结构。

开始

A：输入村庄数

B：输入道路数

C：create函数得到原始邻接矩阵

Floyd算法将每一对顶点的路径编程最

短路径

1

minp函数找出最小偏心度的村庄 程序结束 三、

详细设计

//Floyd算法将每一对顶点的路径编程最短路径 void Floyd(int dist[][M],int m) { int i,j;

for(int k=0;k

dist[i][j]=dist[i][k]+dist[k][j];

cout<

cout<<\ cout<

}

cout<

}

cout<<\

}

//Minp函数求最小偏心度的村庄

void minp(int c[][M],int m) {

2

int inmax[M]; int i,j;

for(i=0;i

for(j=0;j

int t=0;

for(i=0;i

if(t

inmax[j]=t; }

cout<

int max=inmax[0]; int l;

for(i=0;i

max=inmax[i]; l=i; }

cout<<\所以医院应该建在村庄\中\}

void create(int n,int l,int c[][M]) {

cout<

============================================================\ int i,j,weight; for(i=0;i

for(j=0;j

for(int k=0;k

cout<<\请输入第\条道路的起点、终点和它的长度(中间用空格隔开):\

3

C: cin>>i>>j>>weight;

if(i>n||i<0||j>n||j<0||weight>Maxint||weight<0) {

cout<<\输入非法，请重输该边的所有值\ goto C; }

c[i-1][j-1]=weight; }

cout<<\

================================================================\ cout<<\整理得到原始邻接矩阵为：\

cout<<\ for(i=0;i

for(j=0;j

if(c[i][j]!=100) cout<<\

cout<

cout<

cout<<\} 四、

调试分析

通过题目所给例子进行测试和分析，最终得到结构如下截图：

4

5

五、

核心源程序清单和执行结果

09710207郑朋（数据结构）.cpp

// 09710207郑朋（数据结构）.cpp : 定义控制台应用程序的入口点。 //

#include \

int _tmain(int argc, _TCHAR* argv[]) {

6

}

return 0;

#include using namespace std; const int Maxint=100;

const int M=50; //定义村庄个数的最大值

void Floyd(int dist[][M],int m)//Floyd算法将每一对顶点的路径编程最短路径 { }

void minp(int c[][M],int m) //该函数用于找出最小偏心度的村庄 {

int inmax[M]; int i,j; for(i=0;i

inmax[i]=0;

for(j=0;j

7

int i,j;

for(int k=0;k

for(i=0;i

for(j=0;j

if(dist[i][k]+dist[k][j]

dist[i][j]=dist[i][k]+dist[k][j];

cout<

cout<<\

for(j=0;j

cout<

if(dist[i][j]!=100)

cout<<\cout<

的最大值，也就是每个村庄的偏心度

}

}

int t=0; for(i=0;i

inmax[j]=t;

if(t

cout<

cout<

for(i=0;i

if(inmax[i]

cout<<\所以医院应该建在村庄\中\

max=inmax[i]; l=i;

素下标+1,即为建医院的地点

void create(int n,int l,int c[][M]) {

cout<

for(int k=0;k

cout<<\请输入第\条道路的起点、终点和它的长度(中间用空格隔开):\

8

============================================================\

for(j=0;j

c[i][j]=Maxint;

C: }

}

cin>>i>>j>>weight; { }

c[i-1][j-1]=weight;

cout<<\输入非法，请重输该边的所有值\goto C;

if(i>n||i<0||j>n||j<0||weight>Maxint||weight<0)

cout<<\

cout<<\整理得到原始邻接矩阵为：\cout<<\for(i=0;i

cout<<\

for(j=0;j

cout<

if(c[i][j]!=100)

cout<<\cout<

================================================================\

void main() {

cout<

cout<<\☆医院选址问题，请按以下步骤操作☆\cout<<\cout<<\将所有村庄和道路分别从编号（即、、.···）\int arc[M][M]; //用于存储图的邻接矩阵 int m; cin>>m; if(m>M||m<0) {

cout<<\对不起，输入的数值不合法，请重新输入！\goto A;

9

A: cout<<\请输入村庄个数：\

}

} int e; cin>>e;

if(e>(m*(m-1))||e<0) { }

create(m,e,arc); Floyd(arc,m); minp(arc,m);

cout<<\运行结束========================\cout<<\

cout<<\/' \\\\ //\\\\ \cout<<\ \\\\ // `\\ \

cout<<\ \\\\ // 祝老师同学们：\cout<<\ .-'^'-. \

cout<<\ .' a___a `. 春节愉快合家欢乐！\cout<<\ == (___) == \

cout<<\ '. ._I_. .' 心想事成红包拿来！\cout<<\ ____/.`-----'.\\____ \cout<<\[###(__)#### \

cout<<\对不起，输入的数值不合法！\goto B;

B: cout<<\请输入图中有几条道路：\

六、 感想与体会

编程是一件很枯燥的事情，但也是一件很有意义的事情，经过一个星期的设计学习，

使我对C++语言和数据结构有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，首先是自己在指法上还不行，经常按错字母，通过学习也有所改进；再有对C++语言的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C++语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。

10

本文来源：https://www.bwwdw.com/article/uw0x.html