《医院选址问题(数据结构)大作业》由会员分享，可在线阅读，更多相关《医院选址问题(数据结构)大作业（9页珍藏版）》请在金锄头文库上搜索。
1、一、 实验内容概述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二、 实验目的概述“数据结构”是计算机科学与技术专业一门十分重要的专业技术基础课，计算机科学各领域及有关的应用软件都要使用到各种数据结构。在我国，“数据结构与算法”已经作为
2、理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构和算法都非常重视，对于从是计算机科学及其应用的科技工作者来说，数据结构与算法更是必须透彻的掌握的重要基础。 学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题，课程设计是加强学生实践能力的一个强有力的手段。作为一名计算机专业的学生，通过对计算机课程两年的学习，掌握C+和数据结构，在完成课程设计和变成过程中，要深化对数据结构与算法课程中的基本概念、理论和方法的理解，训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念，在老师的指导下完成最少换车次数问题，把自己所学的理论
3、用具体的问题来解决，更加直接，易懂。提高程序设计与调试水平。在通过学习数据结构，我们要掌握数据结构的各个算法，运用学过的算法去解决实际中的问题，将数据结构用用武之地，也能提高我们的运用能力和编写程序的能力，对我们的技能也有进一步的提高，对我们的未来之路铺路搭桥。在这个实验中，我主要是类的成员函数去解决问题，除了学习到C语言的知识外，同样还学习到C+的知识，对我的知识也有很大扩展，将C和C+相结合，达到共同解决问题的目的。在这个运用中，主要是学会类的定义以及使用，还有类的成员函数的定义和使用，通过用类的对象去调用类的成员函数，最后达到目的，这能够体现出面向对象的编程方法，与以往的面向过程的编程方
4、法有很大的层次性的提高，达到提高思维能力。三、 数据结构和算法的设计该实验是通过计算得出在几个村庄中的其中一个村庄建立一个距离合适医院，使得附近各个村庄到这个医院的距离最短，很容易让我们想到用Floyd或者Dijkstra算法去解决问题。但是用C+同样也可以实现，在C+中的类类似于C语言中的结构体，我们正好可以用C+中的类去解决问题，因此我们需要知道类中的一些基本成员，包括私有成员和公有成员，私有成员在类外是不允许访问的，只能通过类中的函数去访问，因此我们需要设置类内成员，然后通过类内函数去访问类中的私有成员。除了要明白类内的私有成员和公有成员外，同意还是要明白类内函数怎样在类外编写，这也是极
5、其重要的，通过把类内函数在类外编写可以使类内代码大大的简短，更有利于读写。最后还要明白构造函数的定义和用法，构造函数的函数名必须和类名一样。本程序主要采用带权图来实现医院选址实现总体最优的一些功能。首先在main函数之前定义了一个类，然后在main函数运行时，根据相关的信息提示，分别输入村庄的个数，村庄名称，边数(各个村庄间是否有通路)，各个道路的起点和终点，以及各个点间的距离。在main()函数中，通过调用类的构造函数和类中的成员函数，使成员函数和构造函数相配合，最后算出相对的最短距离从而确定超市的最优地址，得出各个村庄到医院的距离。首先，构造一个类的对象，然后再调用类的构造函数将数据初始化
6、，其中包括将邻接矩阵初始化为最大值，输入顶点名称，再调用InsertVertex()函数插入顶点，边数、头顶点、尾顶点以及权值，再调用InsertEdge()插入权值。再就是通过类对象调用类的Hospital()函数(医院选址函数)，就是在以邻接带权矩阵表示n个村庄中，求医院建在何处，使离医院最远的村庄到医院最近。在这个函数中，首先求出任意两顶点间的最短路径，求各村庄离医院最近的医院选址，输出要建医院的村庄号及离医院最远的村庄到医院的距离，最后结束算法，完成医院选址问题，使离医院最远的村庄到医院最近。四、 源程序清单#include#define MaxInt 10000/最大数 const
7、int MaxNumEdges=50; const int MaxNumVertices=10; /最大顶点数 class Graph private: int vNum;/当前顶点数 int eNum;/当前边数 int VertexMaxNumVertices;/顶点数组 int EdgeMaxNumVerticesMaxNumVertices;/边数组 bool GetVertexPos(const int &vertex,int &i);/给出顶点vertex在图中的位置 public: Graph(const int sz= MaxNumEdges);/构造函数 bool FindV
8、ertex(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;isz;i+)
9、 for(int j=0;jsz;j+) if(i=j) Edgeij=0;/顶点到自身权值为0 else Edgeij=10000;/邻接矩阵初始化为最大值 printf(请输入顶点数,注意本程序最多为10个!n); scanf(%d,&n); printf(请依次输入顶点名称:n); for(int i=0;in;i+)/依次输入顶点，插入图中 scanf(%d,&name); InsertVertex(name); vNum+; printf(请输入边数:n); scanf(%d,&e); printf(以下输入边信息:n); for(int i=0;ie;i+) printf(请输入第
10、%d边头顶点:n,i+1); scanf(%d,&head); printf(请输入该边尾顶点：n); scanf(%d,&tail); printf(请输入该边权值：n); scanf(%d,&weight); if(!InsertEdge(head,tail,weight) printf(不存在该边，请重输！n); continue; bool Graph:FindVertex(const int& vertex)/给出顶点vertex在图中的位置 for (int i = 0; i vNum; i+) if (vertex = Vertexi) return true; return f
11、alse; bool Graph: GetVertexPos(const int &vertex,int &i)/给出顶点vertex在图中的位置 for (i = 0; i vNum; i+) if (vertex = Vertexi) return true; return false; bool Graph:InsertVertex(const int & vertex)/插入一个顶点vertex if (FindVertex(vertex) return false; VertexvNum = vertex; return true; bool Graph:InsertEdge(con
12、st int v1,const int v2,const int weight)/插入一条边(v1,v2),该边上的权值为weight int k=0,j=0; if(GetVertexPos(v1,k) & GetVertexPos(v2,j) Edgekj=weight; eNum+; Edgejk=weight; eNum+; return true; else return false; void Graph:Hospital() /在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。 int k,i,j,s; for (k=0;kvNum;k+) /求任意两顶点间的最短路径 for (i=0;ivNum;i+) for (j=0;jvNum;j+) if (Edgeik+EdgekjEdgeij) Edgeij=Edgeik+Edgekj; int m=MaxInt; /设定m为机器内最大整数。 printf(*n); /以下为求各村离医院最近的医院选址 int min=MaxInt ; /设定机器最大数作村庄间距离之和的初值。 k=0; /k设医院位置。 for (j=0;jvNum;j+) m=0 ; for (i=0;
