数据结构-医院选址问题.pdf

课程设计报告书课程设计报告书课课程名称程名称 数据数据结结构构 设计题设计题目目 社区医院社区医院选选址址问题问题 专业专业班班级级*学学 号号 *姓姓 名名 *指指导导教教师师 *计算机科学与技术专业教研室计算机科学与技术专业教研室11 设计目的：数据结构是计算机科学与技术、信息管理专业的重要的专业基础课，是计算机系统软件和应用软件开发的重要理论和技术。本次课程设计内容主要用到图的结构。所以课程设计目要求掌握图的理论、图的邻接矩阵存储方式、顶点对这间的最短路径算法设计、及图在实践中的简单应用。2 设计任务：已知有向图，图中各顶点代表居民区，有向边代表交通路线。权表示路程(公里)。要在居民区建立一家医院。要求各居民区到医院的路径尽可能短，请设计医院建在哪个居民区比较合适。4431313121265153 3 设计内容设计内容:图中各顶点代表居民区，边上的权代表各居民区的路程。要解图中各顶点代表居民区，边上的权代表各居民区的路程。要解决选地址问题，必须确定最短路径。求各顶点到其它顶点的最短路径，并求决选地址问题，必须确定最短路径。求各顶点到其它顶点的最短路径，并求各居民区之间往返路径的和。对各居民区的最短路径和进行比较，和最小的各居民区之间往返路径的和。对各居民区的最短路径和进行比较，和最小的则为首选地址。问题的实现则为首选地址。问题的实现,采用顶点对之间最短路径算法，对各居民区的采用顶点对之间最短路径算法，对各居民区的041232最短路径进行计算。最短路径进行计算。1：求出邻接矩阵2：求出邻接表3：求出最短路径的邻接矩阵4：求各顶点到其它顶点的最短路径的和5：求出其它顶点到各顶点的最短路径的和6：求出往返最短路径的和7：对各居民区的最短路径和进行比较，和最小的则为首选地址。4 4 结果分析：结果分析：这步是输入数据输出邻接矩阵for(i=0;in;i+)for(int j=0;jn;j+)coutt.arcsij;3coutendl;coutendl;输出邻接表for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)int next=t.pathij;coutj;cout-i t.aij ;coutendl;输出最短路径的邻接矩阵for(i=0;in;i+)for(j=0;jn;j+)coutt.aij ;coutendl;4输出点到所有点的路程的和for(i=0;in;i+)sum1i=0;for(int j=0;jn;j+)if(i!=j)coutt.aij:;int next=t.pathij;coutj;while(next!=i)cout-next;next=t.pathinext;cout-iendl;sum1i+=t.aij;cout点i到所有点的路程和为：sum1iendl;5逆输出所有点到点路径的和for(i=0;in;i+)sum2i=0;for(j=0;jn;j+)if(i!=j)coutt.aji:;int next=t.pathji;couti;while(next!=j)cout-next;next=t.pathjnext;cout-jendl;sum2i+=t.aji;cout所有的点到i路程和为：sum2iendl;6输出所有点往返路程的和for(int o=0;on;o+)sum3o=sum1o+sum2o;cout点o的往返路程的和为：sum3oendl;min=sum30;for(int h=0;hn;h+)if(sum3h=min)min=sum3h;l=h;cout比较可得最短的路程为min 应该在点 l 哪里建立医院。endl;对各居民区的最短路径和进行比较，和最小的则为首选地址5 5 总结：总结：通过这次的课程设计我了解到了，C+程序设计是一种要求特别细腻的工作，一个逗号或空格都能影响整个程序的工作运行，要求我们非常细心。深深了解到细节决定程序的成败。它让我记住了学习 C+需要认真负责的态度去对待。通过一个星期以来的程序设计使我的专业知识更加巩固了，填补了以前不懂得知识盲点。编程需要兴趣和动手实践，毛泽东也曾说过实践是检验真理的唯一标准，开发出新的程序，创新思维也非常重要。通过这次的程序设计使我更加喜爱编程这项工作，虽然很辛苦但是把程序完成之后的那份喜悦。是外人难以感受的。通过这次的学习，邻接矩阵，邻接表，最短路径我已经掌握了7参考文献参考文献1 肖宏启,刘昌明.数据结构（C 语言版）M.第 1 版.北京：电子工业出版社,2010 附录：程序代码#includeconst int n=5;const int e=10;int sum15;int sum25;int sum35;int j=0;int min;int l;#define max 32767class Graphpublic:int arcsn+1n+1;int an+1n+1;int path n+1n+1;void floyd(Graph&t,const int n);8;void Graph:floyd(Graph&t,const int n)for(int i=0;in;i+)for(int j=0;jn;j+)t.aij=t.arcsij;if(i!=j)&(aijmax)t.pathij=i;else t.pathij=0;for(int k=0;kn;k+)for(i=0;in;i+)for(int j=0;jn;j+)if(t.aik+t.akjt.aij)t.aij=t.aik+t.akj;t.pathij=t.pathkj;for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)int next=t.pathij;9coutj;cout-i t.aij ;coutendl;coutendl;for(i=0;in;i+)for(j=0;jn;j+)coutt.aij ;coutendl;coutendl;for(i=0;in;i+)sum1i=0;for(int j=0;jn;j+)if(i!=j)coutt.aij:;int next=t.pathij;coutj;while(next!=i)cout-next;10next=t.pathinext;cout-iendl;sum1i+=t.aij;cout点i到所有点的路程和为：sum1iendl;for(i=0;in;i+)sum2i=0;for(j=0;jn;j+)if(i!=j)coutt.aji:;int next=t.pathji;couti;while(next!=j)cout-next;next=t.pathjnext;cout-jendl;sum2i+=t.aji;cout所有的点到i路程和为：sum2iendl;11for(int o=0;on;o+)sum3o=sum1o+sum2o;cout点o的往返路程的和为：sum3oendl;min=sum30;for(int h=0;hn;h+)if(sum3h=min)min=sum3h;l=h;cout比较可得在点l那里建立医院min 为最短的路程endl;void main()Graph t;int i,j,w;for(i=0;in;i+)for(j=0;jn;j+)if(i=j)t.arcsij=0;else t.arcsij=max;12for(int k=0;kijw;t.arcsij=w;for(i=0;in;i+)for(int j=0;jn;j+)coutt.arcsij;coutendl;coutendl;t.floyd(t,n);成绩评定成绩评定成绩成绩 教师签字教师签字13