医院选址问题(数据结构)大作业.pdf

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