校园导航问题报告

课程设计（数据结构）院、系计算机与软件学院专业网络工程姓名顾容宇徐鹏学号20091346087、20091346088指导教师郑玉二Ｏ一Ｏ年十二月二十五日-1-校园导航问题王耀南京信息工程大学计算机与软件学院，南京210044摘要：程序设计目的是用哈斯图方式计算两个旅游点的最短距离以及路线。编程所实现的功能除了可以查询两个旅游点的最短距离以及最短的路线，还可以看到旅游点的介绍，以及逛遍所有旅游点所能组成的所有路线可能，实现全面查询。关键字：景点；路线；距离；校园导航1．课程设计题目设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。2．分析2．1设计基础：要掌握最短路径的实现方式。2．2分析设计课题的要求，要求编程实现以下功能：（1）查询景点路径（2）查询景点信息（3）查看参观路线（4）查询各景点之间的距离2．3主控菜单设计为实现通信录管理的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出菜单项的内容和输入提示，如下：1．学校简介2．查询景点路径3.查询景点信息4.查看参观路线5.查询各景点之间的距离6.退出2．4设计课题已明确要求，有关的定义如下：typedefstructArcCell{intadj;//相邻接的景点之间的路程char*info;}ArcCell;//定义边的类型typedefstructVertexType{intnumber;//景点编号char*sight;//景点名称char*description;//景点描述}VertexType;//定义顶点的类型typedefstruct{VertexTypevex[NUM];//图中的顶点，即为景点-2-ArcCellarcs[NUM][NUM];//图中的边，即为景点间的距离intvexnum,arcnum;//顶点数，边数}MGraph;//定义图的类型3．步骤3.1函数调用图Main()创建图的函数CreateUDN（）主菜单Menu（）最短路径函数ShortestPath（）输出函数output（）查询景点信息search（）显示遍历结果display（）函数调用关系3.2主代码#includeiostream#includestring.h#includestdio.h#includestdlib.h#defineMax32767#defineNUM11typedefstructArcCell{intadj;//相邻接的景点之间的路程char*info;}ArcCell;//定义边的类型-3-typedefstructVertexType{intnumber;//景点编号char*sight;//景点名称char*description;//景点描述}VertexType;//定义顶点的类型typedefstruct{VertexTypevex[NUM];//图中的顶点，即为景点ArcCellarcs[NUM][NUM];//图中的边，即为景点间的距离intvexnum,arcnum;//顶点数，边数}MGraph;//定义图的类型MGraphG;//把图定义为全局变量intP[NUM][NUM];////longintD[NUM];//辅助变量存储最短路径长度intx[13]={0};voidCreateUDN(intv,inta);//创建图的函数voidpingmu();//屏幕输出函数voidintroduce();voidShortestPath(intnum);//最短路径函数voidoutput(intsight1,intsight2);//输出函数voidPrintMGraph();charMenu();//主菜单voidsearch();;//查询景点信息charSearchMenu();//查询子菜单voidHaMiTonian(int);//哈密尔顿图的遍历voidNextValue(int);voiddisplay();//显示遍历结果voidmain()//主函数{intv0,v1;charck;system(color0);CreateUDN(NUM,11);do{ck=Menu();switch(ck){case'1':-4-introduce();printf(\n\n\t\t\t%-25s\n\n,G.vex[0].description);getchar();getchar();break;case'2':system(cls);pingmu();printf(\n\n\t\t\t请选择起点景点（1～10）：);scanf(%d,&v0);printf(\t\t\t请选择终点景点（1～10）：);scanf(%d,&v1);ShortestPath(v0);//计算两个景点之间的最短路径output(v0,v1);//输出结果printf(\n\n\t\t\t\t请按回车键继续...\n);getchar();getchar();break;case'3':search();break;case'4':system(cls);pingmu();x[0]=1;HaMiTonian(1);printf(\n\n\t\t\t\t请按回车键继续...\n);getchar();getchar();break;case'5':PrintMGraph();printf(\n\n\t\t\t\t请按回车键继续...\n);getchar();getchar();break;};}while(ck!='e');}-5-charMenu()//主菜单//{charc;intflag;do{flag=1;system(cls);pingmu();introduce();printf(\n\t\t\n);printf(\t\t\n);printf(\t\t1.学校简介\n);printf(\t\t2.查询景点路径\n);printf(\t\t3.查询景点信息\n);printf(\t\t4.查看参观路线\n);printf(\t\t5.查询各景点之间的距离\n);printf(\t\te.退出\n);printf(\t\t\n);printf(\t\t\n);printf(\t\t\t\t请输入您的选择：);scanf(%c,&c);if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='e')flag=0;}while(flag);returnc;}charSearchMenu()//查询子菜单{charc;intflag;do{flag=1;system(cls);pingmu();introduce();printf(\n\t\t\n);printf(\t\t\n);printf(\t\t1、按照景点编号查询\n);-6-printf(\t\t2、按照景点名称查询\n);printf(\t\te、返回\n);printf(\t\t\n);printf(\t\t\n);printf(\t\t\t请输入您的选择：);scanf(%c,&c);if(c=='1'||c=='2'||c=='e')flag=0;}while(flag);returnc;}voidsearch()//查询景点信息{intnum;inti;charc;charname[20];do{system(cls);c=SearchMenu();switch(c){case'1':system(cls);introduce();pingmu();printf(\n\n\t\t请输入您要查找的景点编号：);scanf(%d,&num);for(i=0;iNUM;i++){if(num==G.vex[i].number){printf(\n\n\t\t\t您要查找景点信息如下:);printf(\n\n\t\t\t%-25s\n\n,G.vex[i].description);printf(\n\t\t\t按任回车返回...);getchar();-7-getchar();break;}}if(i==NUM){printf(\n\n\t\t\t没有找到！);printf(\n\n\t\t\t按回车键返回...);getchar();getchar();}break;case'2':system(cls);pingmu();introduce();printf(\n\n\t\t请输入您要查找的景点名称：);scanf(%s,name);for(i=1;iNUM;i++){if(!strcmp(name,G.vex[i].sight)){printf(\n\n\t\t\t您要查找景点信息如下:);printf(\n\n\t\t\t%-25s\n\n,G.vex[i].description);printf(\n\t\t\t按回车键返回...);getchar();getchar();break;}}if(i==NUM){printf(\n\n\t\t\t没有找到！);printf(\n\n\t\t\t按回车键返回...);getchar();-8-getchar();}break;}}while(c!='e');}voidCreateUDN(intv,inta)//创建图的函数{inti,j;G.vexnum=v;//初始化结构中的景点数和边数G.arcnum=a;for(i=1;iG.vexnum;++i)G.vex[i].number=i;//初始化每一个景点的编号//初始化没一个景点名及其景点描述G.vex[0].sight=学校简介;G.vex[1].sight=东大门;G.vex[2].sight=培训楼;G.vex[3].sight=气象楼;G.vex[4].sight=文德楼;G.vex[5].sight=明德楼;G.vex[6].sight=尚贤楼;G.vex[7].sight=电影院;G.vex[8].sight=北辰楼;G.vex[9].sight=图书馆;G.vex[10].sight=实验楼;//这里把所有的边假定为32767，含义是这两个景点之间是不可到达for(i=1;iG.vexnum;++i){for(j=1;jG.vexnum;++j){G.arcs[i][j].adj=Max;G.arcs[i][j].info=NULL;}}//下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，//所以要对图中对称的边同时赋值。G.arcs[1][4].adj=G.arcs[4][1].adj=200;G.arcs[1][3].adj=G.arcs[3][1].adj=150;G.arcs[3][5].adj=G.arcs[5][3].adj=100;-9-G.arcs[3][10].adj=G.arcs[10][3].adj=400;G.arcs[4][6].adj=G.arcs[6][4].adj=200;G.arcs[2][5].adj=G.arcs[5][2].adj=200;G.arcs[2][4].adj=G.arcs[4][2].adj=100;G.arcs[5][7].adj=G.arcs[7][5].adj=150;G.arcs[4][6].adj=G.arcs[6][4].adj=150;G.arcs[4][7].adj=G.arcs[7][4].adj=150;G.arcs[6][8].adj=G.arcs[8][6].adj=150;G.arcs[7][8].adj=G.arcs[8][7].adj=100;G.arcs[6][9].adj=G.arcs[9][6].adj=200;}//打印出邻接矩阵voidPrintMGraph(){inti,j;cout\n==========