数据结构课程设计最终版

任务分工成绩姓名学号设计题目:校园平面图 在地图上从一个地点到另一个地点，给出一条最短路径，各个地点之(1)将地图作为带权无向图，顶点表示学校的各个地点，边表示各地(2)将地图信息存入一文件中，程序运行时可自动读入文件建立相关(3)按操作要求显示对应的最短路径和长度。本程序开发环境为VisualStudio2010校园平面图模型是由场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表场所，用图的边代表场所之间的路径，结点值代表场所信息，边的权值代表场所间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询场所信息和求一个场所到另一个场所的最短路径长度及路线为方便操作，所以给每个场所一个代码用结构体类型实现。计算路径长度和最短路线时可用首先求出长度最短的一条最短路径，然后参照它求出长度次短的一条v部求出为00101243用机器可表示的最大正数maxValue代表)。设第一条最短路径为(v0,vk),其中k满足：mindistiviVvV则可想而知，它或者是(v0,vj),或者(v0,vk，vj)。其长度或者是从v0到一般情况下下一条最短路径总是在“由已产生的最短路径在扩充一条径(v0,....,vk)的终点是vk，则有：dist[k]=min{dist[i]|vi=V-S}如果不是这样，设在路径(v0,...,vk)上存在另一顶点vp=V-S,使得 G.getWeight(k,i)是边(vk,vi)上的权值。以边表示两个地点之间的路径，边上的权值表示两地的距离，为查询者提供任意场所的问路查询，即查询任意两个场所之间的一条最短路径。输入:邵逸夫大楼55米五号教学楼10米二号教学楼350米10米坡湖后勤部学生公寓70米紫荆公寓1700米工商银行门(1)查询：输入一个地点到另一个地点，能够调用最短路径算法的函数计 (2)显示：有选择菜单，可调用主函数实现。输出的路径和相应长度都由(3)退出系统：选择可退出程序。(4)清屏处理：选择可清屏。()主函数：intmain(){chark;cout<<"******************************************************************\n";cout<<"*\n";*\n";cout<<"******************************************************************\n";while(1){cin>>k;switch(k){case'1':shortestdistance();\n"<<endl;case'2':;case'3':}}}(2)主要函数成员：typedefstruct;{charname[20];charnumber[15];};;Elemtype;typedefstruct{Elemtypedate;}typedefstruct{Vertexvexs[MaxVertexNum];//ntne}MGraph;(3)最短路径函数：voidfloyd(){intijk;for(i=1;i<=T;i++){for(j=1;j<=T;j++){shortest[i][j]=MGr.edges[i][j];path[i][j]=0;}for(k=1;k<=T;k++){for(i=1;i<=T;i++){for(j=1;j<=T;j++){if(shortest[i][j]>(shortest[i][k]+shortest[k][j])){shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;}//end_if;}}}//end_for;}voiddisplay(inti,intj)aib=j;if(shortest[i][j]!=MAXCOST){fij{cout<<b;while(path[i][j]!=0)cout<<"<-"<<path[i][j];fijj=path[i][j];i=path[j][i];}cout<<"<-"<<a;}{cout<<a;while(path[i][j]!=0)cout<<"->"<<path[i][j];fijj=path[i][j];i=path[j][i];}cout<<"->"<<b;}}}(1)功能显示((2)路经查询(3)清屏处理(4)退出程序通过这次课程设计，让我们获益颇多，就理论知识来讲，我们把原来不是很熟练的东西变得熟知于心，这告诉我们，大学的学习不仅仅局限于课堂，课外更要自己温习才能掌握，特别是编程类的学科，看着明白但不一定做起来就轻松，需要一个实践的过程，而这个过程就可以看出平时学习的漏洞所在，就拿这次编程而言，我们遇到了很多困难，多次调试程序仍不能运行，最终通过询问他人和百度解决了部分问题，我们平时在纸上殷人昆数据结构(面向对象方法与语言描述)(第二版)北京：清华大学出版社#include<iostream>#include<string>usingnamespacestd;#defineMaxVertexNum50#defineMAXCOST9999#defineT11typedefstruct{charname[20];charnumber[15];}Elemtype;typedefstruct{Elemtypedate;}Vertex;typedefstruct{Vertexvexs[MaxVertexNum];unsignedintedges[MaxVertexNum][MaxVertexNum];ntne}MGraph;MGraphMGr;intshortest[MaxVertexNum][MaxVertexNum];intpath[MaxVertexNum][MaxVertexNum];voidinit(){inti,j;MGr.vexs[1].num=1;strcpy(MGr.vexs[1].date.number,"001");MGr.vexs[2].num=2;strcpy(MGr.vexs[2].date.number,"002");MGr.vexs[3].num=3;strcpy(MGr.vexs[3].date.number,"003");MGr.vexs[4].num=4;strcpy(MGr.vexs[4].date.number,"004");MGr.vexs[5].num=5;strcpy(MGr.vexs[5].date.number,"005");MGr.vexs[6].num=6;strcpy(MGr.vexs[6].date.number,"006");MGr.vexs[7].num=7;strcpy(MGr.vexs[7].date.number,"007");MGr.vexs[8].num=8;strcpy(MGr.vexs[8].date.number,"008");MGr.vexs[9].num=9;strcpy(MGr.vexs[9].date.number,"009");MGr.vexs[10].num=10;strcpy(MGr.vexs[10].date.number,"010");MGr.vexs[11].num=11;strcpy(MGr.vexs[11].date.number,"011");for(i=1;i<=T;i++){for(j=1;j<=T;j++){MGr.edges[i][j]=MAXCOST;}}for(i=1;i<=T;i++){shortest[i][i]=0;}MGr.edges[1][2]=MGr.edges[2][1]=200;MGr.edges[1][3]=MGr.edges[3][1]=10;MGr.edges[1][10]=MGr.edges[10][1]=500;MGr.edges[2][5]=MGr.edges[5][2]=70;MGr.edges[2][8]=MGr.edges[8][2]=1700;MGr.edges[3][4]=MGr.edges[4][3]=150;MGr.edges[3][5]=MGr.edges[5][3]=350;MGr.edges[3][10]=MGr.edges[10][3]=130;MGr.edges[4][6]=MGr.edges[6][4]=200;MGr.edges[4][9]=MGr.edges[9][4]=10;MGr.edges[5][7]=MGr.edges[7][5]=320;MGr.edges[6][7]=MGr.edges[7][6]=1080;MGr.edges[7][8]=MGr.edges[8][7]=120;MGr.edges[9][10]=MGr.edges[10][9]=55;MGr.edges[9][11]=MGr.edges[11][9]=322;MGr.edges[10][11]=MGr.edges[11][10]=210;MGr.edges[1][1]=MGr.edges[2][2]=MGr.edges[3][3]=MGr.edges[4][4]=MGr.edges[5][5]=MGr.edges[6][6]=0;MGr.edges[7][7]=MGr.edges[8][8]=MGr.edges[9][9]=MGr.edges[10][10]=MGr.edges[1}voidfloyd(){intijk;for(i=1;i<=T;i++){for(j=1;j<=T;j++){shortest[i][j]=MGr.edges[i][j];path[i][j]=0;}}for(k=1;k<=T;k++){for(i=1;i<=T;i++){for(j=1;j<=T;j++){if(shortest[i][j]>(shortest[i][k]+shortest[k][j])){shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;path[j][i]=k;}}}}}voiddisplay(inti,intj){aib=j;if(shortest[i][j]!=MAXCOST){fij{cout<<b;while(path[i][j]!=0){cout<<"<-"<<path[i][j];fijj=path[i][j];i=path[j][i];}cout<<"<-"<<a;}{cout<<a;while(path[i][j]!=0){cout<<"->"<<path[i][j];fijj=path[i][j];i=path[j][i];}cout<<"->"<<b;}}}intshortestdistance(){inti,j;cin>>i>>j;{}<endl;{floyd();display(i,j);}return0;}intmain(){chark;cout<<"*******