数据结构-医院选址问题

数据结构-医院选址问题数据结构-医院选址问题全文共19页，当前为第1页。数据结构-医院选址问题全文共19页，当前为第1页。课程设计报告书课程名称数据结构设计题目社区医院选址问题专业班级***************************学号****姓名***指导教师****数据结构数据结构-医院选址问题全文共19页，当前为第2页。数据结构-医院选址问题全文共19页，当前为第3页。数据结构-医院选址问题全文共19页，当前为第3页。1设计目的：数据结构是计算机科学与技术、信息管理专业的重要的专业基础课，是计算机系统软件和应用软件开发的重要理论和技术。本次课程设计内容主要用到图的结构。所以课程设计目要求掌握图的理论、图的邻接矩阵存储方式、顶点对这间的最短路径算法设计、及图在实践中的简单应用。2设计任务：已知有向图，图中各顶点代表居民区，有向边代表交通路线。权表示路程(公里)。要在居民区建立一家医院。要求各居民区到医院的路径尽可能短，请设计医院建在哪个居民区比较合适。 0341 40341 4 3 13 13 12 12 62 52 15数据结构数据结构-医院选址问题全文共19页，当前为第4页。3设计内容:图中各顶点代表居民区，边上的权代表各居民区的路程。要解决选地址问题，必须确定最短路径。求各顶点到其它顶点的最短路径，并求各居民区之间往返路径的和。对各居民区的最短路径和进行比较，和最小的则为首选地址。问题的实现,采用顶点对之间最短路径算法，对各居民区的最短路径进行计算。1：求出邻接矩阵2：求出邻接表3：求出最短路径的邻接矩阵4：求各顶点到其它顶点的最短路径的和5：求出其它顶点到各顶点的最短路径的和6：求出往返最短路径的和7：对各居民区的最短路径和进行比较，和最小的则为首选地址。4结果分析：数据结构-医院选址问题全文共19页，当前为第5页。数据结构-医院选址问题全文共19页，当前为第5页。输出邻接矩阵 for(i=0;i<n;i++) { for(intj=0;j<n;j++) { cout<<t.arcs[i][j]<<""; } cout<<endl; } cout<<endl;输出邻接表 for(i=0;i<n;i++) { for(j=0;j<n;j++) {数据结构-医院选址问题全文共19页，当前为第6页。数据结构-医院选址问题全文共19页，当前为第6页。 { intnext=t.path[i][j]; cout<<j; cout<<"<--"<<i<<""<<t.a[i][j]<<""; } } cout<<endl; }输出最短路径的邻接矩阵for(i=0;i<n;i++) { for(j=0;j<n;j++) { cout<<t.a[i][j]<<""; } cout<<endl;数据结构-医院选址问题全文共19页，当前为第7页。数据结构-医院选址问题全文共19页，当前为第7页。输出点到所有点的路程的和 for(i=0;i<n;i++) { sum1[i]=0; for(intj=0;j<n;j++) { if(i!=j) { cout<<t.a[i][j]<<":"; intnext=t.path[i][j]; cout<<j;数据结构-医院选址问题全文共19页，当前为第8页。数据结构-医院选址问题全文共19页，当前为第8页。{ cout<<"<--"<<next; next=t.path[i][next]; } cout<<"<--"<<i<<endl; sum1[i]+=t.a[i][j]; } } cout<<"点"<<i<<"到所有点的路程和为："<<sum1[i]<<endl; }数据结构数据结构-医院选址问题全文共19页，当前为第9页。逆输出所有点到点路径的和for(i=0;i<n;i++) { sum2[i]=0; for(j=0;j<n;j++) { if(i!=j) { cout<<t.a[j][i]<<":"; intnext=t.path[j][i]; cout<<i;数据结构-医院选址问题全文共19页，当前为第10页。数据结构-医院选址问题全文共19页，当前为第10页。 { cout<<"<--"<<next; next=t.path[j][next]; } cout<<"<--"<<j<<endl; } sum2[i]+=t.a[j][i]; } cout<<"所有的点到"<<i<<"路程和为："<<sum2[i]<<endl; }输出所有点往返路程的和for(into=0;o<n;o++) { sum3[o]=sum1[o]+sum2[o]; cout<<"点"<<o<<"的往返路程的和为："<<sum3[o]<<endl; }数据结构-医院选址问题全文共19页，当前为第11页。数据结构-医院选址问题全文共19页，当前为第11页。 for(inth=0;h<n;h++) { if(sum3[h]<=min) { min=sum3[h]; l=h; } } cout<<"比较可得最短的路程为"<<min<<"应该在点"<<l<<"哪里建立医院。"<<endl;对各居民区的最短路径和进行比较，和最小的则为首选地址5总结：数据结构-医院选址问题全文共19页，当前为第12页。通过这次的课程设计我了解到了，C++程序设计是一种要求特别细腻的工作，一个逗号或空格都能影响整个程序的工作运行，要求我们非常细心。深深了解到细节决定程序的成败。它让我记住了学习C++需要认真负责的态度去对待。通过一个星期以来的程序设计使我的专业知识更加巩固了，填补了以前不懂得知识盲点。编程需要兴趣和动手实践，毛泽东也曾说过实践是检验真理的唯一标准，开发出新的程序，创新思维也非常重要。通过这次的程序设计使我更加喜爱编程这项工作，虽然很辛苦但是把程序完成之后的那份喜悦。是外人难以感受的。数据结构-医院选址问题全文共19页，当前为第12页。参考文献[1]肖宏启,刘昌明.数据结构（C语言版）[M].第1版.北京：电子工业出版社,2010附录：程序代码#include<iostream.h>constintn=5;constinte=10;intsum1[5];intsum2[5];intsum3[5];intj=0;intmin;intl;#definemax32767classGraph{数据结构-医院选址问题全文共19页，当前为第13页。数据结构-医院选址问题全文共19页，当前为第13页。 intarcs[n+1][n+1];inta[n+1][n+1]; intpath[n+1][n+1]; voidfloyd(Graph&t,constintn); };voidGraph::floyd(Graph&t,constintn){ for(inti=0;i<n;i++) for(intj=0;j<n;j++) { t.a[i][j]=t.arcs[i][j]; if((i!=j)&&(a[i][j]<max)) t.path[i][j]=i; elset.path[i][j]=0; } for(intk=0;k<n;k++) { for(i=0;i<n;i++) for(intj=0;j<n;j++) if(t.a[i][k]+t.a[k][j]<t.a[i][j]) { t.a[i][j]=t.a[i][k]+t.a[k][j]; t.path[i][j]=t.path[k][j]; } } for(i=0;i<n;i++) {数据结构-医院选址问题全文共19页，当前为第14页。数据结构-医院选址问题全文共19页，当前为第14页。 { if(i!=j) { intnext=t.path[i][j]; cout<<j; cout<<"<--"<<i<<""<<t.a[i][j]<<""; } } cout<<endl; } cout<<endl; for(i=0;i<n;i++) { for(j=0;j<n;j++) { cout<<t.a[i][j]<<""; } cout<<endl; } cout<<endl;for(i=0;i<n;i++) { sum1[i]=0; for(intj=0;j<n;j++) { if(i!=j) { cout<<t.a[i][j]<<":";数据结构-医院选址问题全文共19页，当前为第15页。数据结构-医院选址问题全文共19页，当前为第15页。 cout<<j; while(next!=i){ cout<<"<--"<<next; next=t.path[i][next]; } cout<<"<--"<<i<<endl; sum1[i]+=t.a[i][j]; } } cout<<"点"<<i<<"到所有点的路程和为："<<sum1[i]<<endl; } for(i=0;i<n;i++) { sum2[i]=0; for(j=0;j<n;j++) { if(i!=j) { cout<<t.a[j][i]<<":"; intnext=t.path[j][i]; cout<<i; while(next!=j) { cout<<"<--"<<next; next=t.path[j][next]; } cout<<"<--"<<j<<endl;数据结构-医院选址问题全文共19页，当前为第16页。数据结构-医院选址问题全文共19页，当前为第16页。 sum2[i]+=t.a[j][i]; } cout<<"所有的点到"<<i<<"路程和为："<<sum2[i]<<endl; } for(into=0;o<n;o++) { sum3[o]=sum1[o]+sum2[o]; cout<<"点"<<o<<"的往返路程的和为："<<sum3[o]<<endl; } min=sum3[0]; for(inth=0;h<n;h++) { if(sum3[h]<=min) { min=sum3[h]; l=h; } } cout<<"比较可得在点"<<l<<"那里建立医院"<<min<<"为最短的路程"<<endl;}voidmain(){ 数据结构-医院选址问题全文共19页，当前为第17页。数据结构-医院选址问题全文共19页，当前为第17页。 for(i=0;i<n;i++) for(j=0;j<n;j++) if(i==j)t.arcs[i][j]=0; elset.arcs[i][j]=max; for(intk=0;k<e;k++) { cin>>i>>