医院选址问题（数据结构）大作业

计算机科学与技术专业数据结构大作业

一、 实验内容概述

n个村庄之间的交通图用有向加权图表示，图中的有向边表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。

图1 医院选址加权有向图

测试数据：针对图1，输入以下数据： 输入顶点数： 5 输入顶点对和弧的权值：

1 2 1

2 3 2 3 4 2 3 5 4 4 2 1 4 3 3 5 4 5 0 0 0

1

计算机科学与技术专业数据结构大作业

二、 实验目的概述

“数据结构”是计算机科学与技术专业一门十分重要的专业技术基础课，计算机科学各领域及有关的应用软件都要使用到各种数据结构。在我国，“数据结构与算法”已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构和算法都非常重视，对于从是计算机科学及其应用的科技工作者来说，数据结构与算法更是必须透彻的掌握的重要基础。

学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题，课程设计是加强学生实践能力的一个强有力的手段。作为一名计算机专业的学生，通过对计算机课程两年的学习，掌握C++和数据结构，在完成课程设计和变成过程中，要深化对数据结构与算法课程中的基本概念、理论和方法的理解，训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念，在老师的指导下完成最少换车次数问题，把自己所学的理论用具体的问题来解决，更加直接，易懂。提高程序设计与调试水平。

在通过学习数据结构，我们要掌握数据结构的各个算法，运用学过的算法去解决实际中的问题，将数据结构用用武之地，也能提高我们的运用能力和编写程序的能力，对我们的技能也有进一步的提高，对我们的未来之路铺路搭桥。

在这个实验中，我主要是类的成员函数去解决问题，除了学习到C语言的知识外，同样还学习到C++的知识，对我的知识也有很大扩展，将C和C++相结合，达到共同解决问题的目的。

在这个运用中，主要是学会类的定义以及使用，还有类的成员函数的定义和使用，通过用类的对象去调用类的成员函数，最后达到目的，这能够体现出面向对象的编程方法，与以往的面向过程的编程方法有很大的层次性的提高，达到提高思维能力。

三、 数据结构和算法的设计

该实验是通过计算得出在几个村庄中的其中一个村庄建立一个距离合适医院，使得附近各个村庄到这个医院的距离最短，很容易让我们想到用Floyd或者Dijkstra算法去解决问题。

但是用C++同样也可以实现，在C++中的类类似于C语言中的结构体，我们正好可以用C++中的类去解决问题，因此我们需要知道类中的一些基本成员，包括私有成员和公有成员，私有成员在类外是不允许访问的，只能通过类中的函数去访问，因此我们需要设置类内

2

计算机科学与技术专业数据结构大作业

成员，然后通过类内函数去访问类中的私有成员。

除了要明白类内的私有成员和公有成员外，同意还是要明白类内函数怎样在类外编写，这也是极其重要的，通过把类内函数在类外编写可以使类内代码大大的简短，更有利于读写。

最后还要明白构造函数的定义和用法，构造函数的函数名必须和类名一样。

本程序主要采用带权图来实现医院选址实现总体最优的一些功能。首先在main函数之前定义了一个类，然后在main函数运行时，根据相关的信息提示，分别输入村庄的个数，村庄名称，边数(各个村庄间是否有通路)，各个道路的起点和终点，以及各个点间的距离。在main()函数中，通过调用类的构造函数和类中的成员函数，使成员函数和构造函数相配合，最后算出相对的最短距离从而确定超市的最优地址，得出各个村庄到医院的距离。

首先，构造一个类的对象，然后再调用类的构造函数将数据初始化，其中包括将邻接矩阵初始化为最大值，输入顶点名称，再调用InsertVertex()函数插入顶点，边数、头顶点、尾顶点以及权值，再调用InsertEdge()插入权值。

再就是通过类对象调用类的Hospital()函数(医院选址函数)，就是在以邻接带权矩阵表示

n个村庄中，求医院建在何处，使离医院最远的村庄到医院最近。在这个函数中，首先求出任意两顶点间的最短路径，求各村庄离医院最近的医院选址，输出要建医院的村庄号及离医院最远的村庄到医院的距离，最后结束算法，完成医院选址问题，使离医院最远的村庄到医院最近。

四、 源程序清单

#include

#define MaxInt 10000//最大数 const int MaxNumEdges=50;

const int MaxNumVertices=10; //最大顶点数 class Graph {

private:

int vNum;//当前顶点数

int eNum;//当前边数

int Vertex[MaxNumVertices];//顶点数组

3

计算机科学与技术专业数据结构大作业

int Edge[MaxNumVertices][MaxNumVertices];//边数组

bool GetVertexPos(const int &vertex,int &i);//给出顶点vertex在图中的位置 public:

Graph(const int sz= MaxNumEdges);//构造函数 bool FindVertex(const int &vertex);

bool InsertVertex(const int & vertex);//插入一个顶点vertex

bool InsertEdge(const int v1,const int v2,const int weight);//插入一条边(v1,v2),该边上的权值为weight

void Hospital();//医院选址函数 };

Graph::Graph(const int sz): vNum(0), eNum(0) //构造函数 { int n,e;

int name,tail,head; int weight; for(int i=0;i

if(i==j)

Edge[i][j]=0;//顶点到自身权值为0 else

Edge[i][j]=10000;//邻接矩阵初始化为最大值 }

printf(\请输入顶点数,注意本程序最多为10个!\\n\ scanf(\

printf(\请依次输入顶点名称:\\n\

for(int i=0;i

scanf(\ InsertVertex(name); vNum++; }

printf(\请输入边数:\\n\ scanf(\

printf(\以下输入边信息:\\n\ for(int i=0;i

4

计算机科学与技术专业数据结构大作业

printf(\请输入第%d边头顶点:\\n\ scanf(\

printf(\请输入该边尾顶点：\\n\ scanf(\

printf(\请输入该边权值：\\n\ scanf(\

if(!InsertEdge(head,tail,weight)) {

printf(\不存在该边，请重输！\\n\ continue; } } }

bool Graph::FindVertex(const int& vertex) //给出顶点vertex在图中的位置 {

for (int i = 0; i < vNum; i++) if (vertex == Vertex[i]) return true; return false; }

bool Graph:: GetVertexPos(const int &vertex,int &i) //给出顶点vertex在图中的位置 {

for (i = 0; i < vNum; i++) if (vertex == Vertex[i]) return true; return false; }

bool Graph::InsertVertex(const int & vertex) //插入一个顶点vertex {

if (FindVertex(vertex)) return false; Vertex[vNum] = vertex; return true; }

bool Graph::InsertEdge(const int v1,const int v2,const int weight)

5

计算机科学与技术专业数据结构大作业

//插入一条边(v1,v2),该边上的权值为weight {

int k=0,j=0;

if(GetVertexPos(v1,k) && GetVertexPos(v2,j)) {

Edge[k][j]=weight; eNum++; Edge[j][k]=weight; eNum++; return true; } else

return false; }

void Graph::Hospital()

//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。 {

int k,i,j,s;

for (k=0;k

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

printf(\ //以下为求各村离医院最近的医院选址

int min=MaxInt ; //设定机器最大数作村庄间距离之和的初值。 k=0; //k设医院位置。 for (j=0;j

for (i=0;im) {

min=m;

k=j;

} //取顶点间的距离之和的最小值。

6

计算机科学与技术专业数据结构大作业

}//for

printf(\各村离医院最近的医院选址,要建医院的村庄号:%d\\n\//输出要建医院的村庄号

//输出要建医院的村庄号及离医院最远的村庄到医院的距离 for(j=0;j

printf(\该村庄离%d村庄最短距离为:%d\\n\}//算法结束 int main() {

Graph Town(MaxNumVertices); Town.Hospital(); return 0; }

五、 程序调试及测试结果

请输入顶点数，注意本程序最多为10个！5

请输入顶点名称： 1 2

3

4

5

以下输入边信息：

7

请输入第1边顶点：1 请输入该边尾顶点：2 请输入该边权值：1 请输入第2边头顶点：2 请输入该边尾顶点：3 请输入该边权值：1 请输入第3边顶点：3 请输入该边尾顶点：4 请输入该边权值：2 请输入第边4边顶点：4 请输入该边尾顶点：3

7

计算机科学与技术专业数据结构大作业

请输入该边权值：3 请输入第边5边顶点：4 请输入该边尾顶点：2 请输入该边权值：1 请输入第边6边顶点：3 请输入该边尾顶点：5 请输入该边权值：4 请输入第边7边顶点：5 请输入该边尾顶点：5 请输入该边权值：4

****************************

各村离医院最近的医院选址，要建医院的村庄号：2 该村庄离1村庄最短距离为：1 该村庄离3村庄最短距离是：2 该村庄离4村庄最短距离是：1 该村庄离5村庄最短距离是：6

六、 结论

计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术等计算机应用领域中，都是对数据进行加工处理的过程。因此，要设计出一个结构好效率高的程序，必须研究数据的特性及数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打好“数据结构”这门课程的扎实基础。

通过大型作业，让我们可以运用结合以前学过的知识去解决现实中的问题，该实验不仅是运用到C语言的知识，还运用了C++的只是，把C语言和C++相结合，很大的提高了我们的编程能力，同时也让我们学会互相结合各种编程语言去解决问题，还能够实验提高我们的实践能力，对我们个人能力的培养也具有很大的作用。

8

计算机科学与技术专业数据结构大作业

计算机对我们的现实世界、现实生活具有很大的作用，人们能够通过计算机去解决现实的问题，我们正好通过编程去解决，对现在来说也是很大的帮助。

在数据结构的学习过程中，我们的能力有很大的提高，对我们的未来是一个很大的帮助，对我们的编程积累很大的经验。

我感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的能力。

另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。

七、 参考文献

【1】赵文静 祁飞等编著 《数据结构与算法》,科学出版社,2005.08 . 【2】赵文静编著 《数据结C++语言描述》，西安交通大学出版社,1999 .

【3】Clifford A.Shaffer编著《数据结构与算法分析》（C++版）,电子工业出版社，2002.7 【4】严蔚敏等编著，数据结构（C语言版），清华大学出版社,1997.4

【5】王国均主编，唐国民、苏晓萍、马渝副主编，《数据结构—C语言描述》，科学出版社，2005.08.

【6】谭浩强编著，《C++程序设计》，清华大学出版社，2004.06.

【7】唐国民、沈尔云编著，《C语言程序设计》，中国铁道出版社，2006.10. 【8】唐浩强主编，《C程序设计(第三版)》，清华大学出版社，2005.07

指导教师： 日期： 实验成绩：

9

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