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

计算机科学与技术专业数据结构大作业PAGEPAGE2实验内容概述n个村庄之间的交通图用有向加权图表示，图中的有向边<vi，vj>表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。图1医院选址加权有向图测试数据：针对图1，输入以下数据：输入顶点数：5输入顶点对和弧的权值：121232342354421433545000实验目的概述“数据结构”是计算机科学与技术专业一门十分重要的专业技术基础课，计算机科学各领域及有关的应用软件都要使用到各种数据结构。在我国，“数据结构与算法”已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构和算法都非常重视，对于从是计算机科学及其应用的科技工作者来说，数据结构与算法更是必须透彻的掌握的重要基础。学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题，课程设计是加强学生实践能力的一个强有力的手段。作为一名计算机专业的学生，通过对计算机课程两年的学习，掌握C++和数据结构，在完成课程设计和变成过程中，要深化对数据结构与算法课程中的基本概念、理论和方法的理解，训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念，在老师的指导下完成最少换车次数问题，把自己所学的理论用具体的问题来解决，更加直接，易懂。提高程序设计与调试水平。在通过学习数据结构，我们要掌握数据结构的各个算法，运用学过的算法去解决实际中的问题，将数据结构用用武之地，也能提高我们的运用能力和编写程序的能力，对我们的技能也有进一步的提高，对我们的未来之路铺路搭桥。在这个实验中，我主要是类的成员函数去解决问题，除了学习到C语言的知识外，同样还学习到C++的知识，对我的知识也有很大扩展，将C和C++相结合，达到共同解决问题的目的。在这个运用中，主要是学会类的定义以及使用，还有类的成员函数的定义和使用，通过用类的对象去调用类的成员函数，最后达到目的，这能够体现出面向对象的编程方法，与以往的面向过程的编程方法有很大的层次性的提高，达到提高思维能力。数据结构和算法的设计该实验是通过计算得出在几个村庄中的其中一个村庄建立一个距离合适医院，使得附近各个村庄到这个医院的距离最短，很容易让我们想到用Floyd或者Dijkstra算法去解决问题。但是用C++同样也可以实现，在C++中的类类似于C语言中的结构体，我们正好可以用C++中的类去解决问题，因此我们需要知道类中的一些基本成员，包括私有成员和公有成员，私有成员在类外是不允许访问的，只能通过类中的函数去访问，因此我们需要设置类内成员，然后通过类内函数去访问类中的私有成员。除了要明白类内的私有成员和公有成员外，同意还是要明白类内函数怎样在类外编写，这也是极其重要的，通过把类内函数在类外编写可以使类内代码大大的简短，更有利于读写。最后还要明白构造函数的定义和用法，构造函数的函数名必须和类名一样。本程序主要采用带权图来实现医院选址实现总体最优的一些功能。首先在main函数之前定义了一个类，然后在main函数运行时，根据相关的信息提示，分别输入村庄的个数，村庄名称，边数(各个村庄间是否有通路)，各个道路的起点和终点，以及各个点间的距离。在main()函数中，通过调用类的构造函数和类中的成员函数，使成员函数和构造函数相配合，最后算出相对的最短距离从而确定超市的最优地址，得出各个村庄到医院的距离。 首先，构造一个类的对象，然后再调用类的构造函数将数据初始化，其中包括将邻接矩阵初始化为最大值，输入顶点名称，再调用InsertVertex()函数插入顶点，边数、头顶点、尾顶点以及权值，再调用InsertEdge()插入权值。 再就是通过类对象调用类的Hospital()函数(医院选址函数)，就是在以邻接带权矩阵表示n个村庄中，求医院建在何处，使离医院最远的村庄到医院最近。在这个函数中，首先求出任意两顶点间的最短路径，求各村庄离医院最近的医院选址，输出要建医院的村庄号及离医院最远的村庄到医院的距离，最后结束算法，完成医院选址问题，使离医院最远的村庄到医院最近。源程序清单#include<stdio.h>#defineMaxInt10000//最大数constintMaxNumEdges=50;constintMaxNumVertices=10;//最大顶点数classGraph{private:intvNum;//当前顶点数inteNum;//当前边数intVertex[MaxNumVertices];//顶点数组intEdge[MaxNumVertices][MaxNumVertices];//边数组boolGetVertexPos(constint&vertex,int&i);//给出顶点vertex在图中的位置public:Graph(constintsz=MaxNumEdges);//构造函数boolFindVertex(constint&vertex);boolInsertVertex(constint&vertex);//插入一个顶点vertexboolInsertEdge(constintv1,constintv2,constintweight);//插入一条边(v1,v2),该边上的权值为weightvoidHospital();//医院选址函数};Graph::Graph(constintsz):vNum(0),eNum(0)//构造函数{intn,e;intname,tail,head;intweight;for(inti=0;i<sz;i++)for(intj=0;j<sz;j++){if(i==j)Edge[i][j]=0;//顶点到自身权值为0elseEdge[i][j]=10000;//邻接矩阵初始化为最大值}printf("请输入顶点数,注意本程序最多为10个!\n");scanf("%d",&n);printf("请依次输入顶点名称:\n");for(inti=0;i<n;i++)//依次输入顶点，插入图中{scanf("%d",&name);InsertVertex(name);vNum++;}printf("请输入边数:\n");scanf("%d",&e);printf("以下输入边信息:\n");for(inti=0;i<e;i++){printf("请输入第%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;}}}boolGraph::FindVertex(constint&vertex)//给出顶点vertex在图中的位置{for(inti=0;i<vNum;i++)if(vertex==Vertex[i])returntrue;returnfalse;}boolGraph::GetVertexPos(constint&vertex,int&i)//给出顶点vertex在图中的位置{for(i=0;i<vNum;i++)if(vertex==Vertex[i])returntrue;returnfalse;}boolGraph::InsertVertex(constint&vertex)//插入一个顶点vertex{if(FindVertex(vertex))returnfalse;Vertex[vNum]=vertex;returntrue;}boolGraph::InsertEdge(constintv1,constintv2,constintweight)//插入一条边(v1,v2),该边上的权值为weight{intk=0,j=0;if(GetVertexPos(v1,k)&&GetVertexPos(v2,j)){Edge[k][j]=weight;eNum++;Edge[j][k]=weight;eNum++;returntrue;}elsereturnfalse;}voidGraph::Hospital()//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。{intk,i,j,s;for(k=0;k<vNum;k++)//求任意两顶点间的最短路径for(i=0;i<vNum;i++)for(j=0;j<vNum;j++)if(Edge[i][k]+Edge[k][j]<Edge[i][j])Edge[i][j]=Edge[i][k]+Edge[k][j];intm=MaxInt;//设定m为机器内最大整数。printf("********************************************\n");//以下为求各村离医院最近的医院选址intmin=MaxInt;//设定机器最大数作村庄间距离之和的初值。k=0;//k设医院位置。for(j=0;j<vNum;j++){m=0;for(i=0;i<vNum;i++)m=m+Edge[i][j];//顶点到其它顶点最短距离的距离之和if(min>m){min=m;k=j;}//取顶点间的距离之和的最小值。}//forprintf("各村离医院最近的医院选址,要建医院的村庄号:%d\n",k+1);//输出要建医院的村庄号//输出要建医院的村庄号及离医院最远的村庄到医院的距离for(j=0;j<vNum;j++)if(j!=k)printf("该村庄离%d村庄最短距离为:%d\n",j+1,Edge[k][j]);}//算法结束intmain(){GraphTown.Hospital();return0;}程序调试及测试结果请输入顶点数，注意本程序最多为10个！5请输入顶点名称：1 2 3 4 5以下输入边信息：7请输入第1边顶点：1请输入该边尾顶点：2请输入该边权值：1请输入第2边头顶点：2请输入该边尾顶点：3请输入该边权值：1请输入第3边顶点：3请输入该边尾顶点：4请输入该边权值：2请输入第边4边顶点：4请输入该边尾顶点：3请输入该边权值：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++相结合，很大的提高了我们的编程能力，同时也让我们学会互相结合各种编程语言去解决问题，还能够实验提高我们的实践能力，对我们个人能力的培养也具有很大的作用。计算机对我们的现实世界、现实生活具有很大的作用，人们能够通过计算机去解决现实的问题，我们正好通过编程去解决，对现在来说也是很大的帮助。在数据结构的学习过程中，我们的能力有很大的提高，对我们的未来是一个很大的帮助，对我们的编程积累很大的经验。我感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够综合