数据结构—课程设计—校园导航问题报告

数学与计算机学院课程设计说明书课程名称:数据结构-课程设计课程代码:8404181题目:校园导航问题年级/专业/班:学生姓名:学号:开始时间:年月日完成时间:年月日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日校园导航问题数据结构课程设计任务书学院名称：数学与计算机学院课程代码：8404181专业：年级：一、设计题目校园导航问题二、主要内容设计西华大学的平面图，至少包括10个以上的场所，找出从任意场所到达另一场所的最短路径。三、具体要求及应提交的材料1．每个同学以自己的学号和姓名建一个文件夹，如：“312009080611101张三”。里面应包括：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）、任务书和课程设计说明书的电子文档。2．打印的课程设计说明书（注意：在封面后夹入打印的“任务书”以后再装订）。四、主要技术路线提示涉及无向图的操作。该设计共分三部分，一是建立西华大学平面图的存储结构，二是解决单源点最短路径问题，最后再实现任意一对场所之间的最短路径问题。五、进度安排共计两周时间，建议进度安排如下：选题，应该在上机实验之前完成需求分析、概要设计可分配4学时完成详细设计可分配4学时校园导航问题调试和分析可分配10学时。2学时的机动，可用于答辩及按教师要求修改课程设计说明书。注：只用课内上机时间一般不能完成设计任务，所以需要学生自行安排时间做补充。六、推荐参考资料(不少于3篇)［1］苏仕华等编著，数据结构课程设计，机械工业出版社，2007［2］严蔚敏等编著，数据结构（C语言版），清华大学出版社，2003［3］严蔚敏等编著，数据结构题集（C语言版），清华大学出版社，2003指导教师签名日期年月日系主任审核日期年月日校园导航问题校园导航问题摘要：程序设计目的是用哈斯图方式计算两个旅游点的最短距离以及路线。编程所实现的功能除了可以查询两个旅游点的最短距离以及最短的路线，还可以看到旅游点的介绍，以及逛遍所有旅游点所能组成的所有路线可能，实现全面查询。关键字：景点；路线；距离；校园导航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];//图中的顶点，即为景点ArcCellarcs[NUM][NUM];//图中的边，即为景点间的距离intvexnum,arcnum;//顶点数，边数}MGraph;//定义图的类型-1-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;//定义边的类型typedefstructVertexType{intnumber;//景点编号-2-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':introduce();printf(\n\n\t\t\t%-25s\n\n,G.vex[0].description);-3-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');}charMenu()//主菜单//{-4-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);printf(\t\t2、按照景点名称查询\n);printf(\t\te、返回\n);-5-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();getchar();break;-6-}}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();getchar();}-7-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){f