医院选址问题数据结构大作业.docVIP

实验内容概述 n个村庄之间的交通图用有向加权图表示，图中的有向边vi，vj表示第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 实验目的概述 “数据结构”是计算机科学与技术专业一门十分重要的专业技术基础课，计算机科学各领域及有关的应用软件都要使用到各种数据结构。在我国，数据结构与算法”已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构和算法都非常重视，对于从是计算机科学及其应用的科技工作者来说，数据结构与算法更是必须透彻的掌握的重要基础 学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题，课程设计是加强学生实践能力的一个强有力的手段。作为一名计算机专业的学生，通过对计算机课程两年的学习，掌握C++和数据结构，在完成课程设计和变成过程中，要深化对数据结构与算法课程中的基本概念、理论和方法的理解，训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念，在老师的指导下完成最少换车次数问题，把自己所学的理论用具体的问题来解决，更加直接，易懂。提高程序设计与调试水平。Floyd或者Dijkstra算法本程序主要采用带权图来实现选址实现总体最优的一些功能。首先在main函数之前定义了一个类，然后在main函数运行时，根据相关的信息提示，分别输入，。，最后算出相对的最短距离从而确定超市的最优地址。InsertVertex()函数插入顶点，边数、头顶点、尾顶点以及权值，再调用InsertEdge()插入权值。 再就是通过类对象调用类的Hospital()函数(医院选址函数)，就是在以邻接带权矩阵表示n个村庄中，求医院建在何处，使离医院最远的村庄到医院最近。在这个函数中，首先求出任意两顶点间的最短路径，求各村庄离医院最近的医院选址，输出要建医院的村庄号及离医院最远的村庄到医院的距离，最后结束算法，完成医院选址问题，使离医院最远的村庄到医院最近。 源程序清单 #includestdio.h #define MaxInt 10000//最大数 const int MaxNumEdges=50; const int MaxNumVertices=10; //最大顶点数 class Graph { private: int vNum;//当前顶点数 int eNum;//当前边数 int Vertex[MaxNumVertices];//顶点数组 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;isz;i++) for(int j=0;jsz;j++) { if(i==j) Edge[i][j]=0;//顶点到自身权值为0