数据结构课程设计-校园导航.doc

课 程 设 计 报 告 课程名称 数据结构课程设计 题 目 校园导航 指导教师 设计起始日期 学 院 计算机学院 系 别 计算机科学与工程 学生姓名 班级/学号 成 绩 需求分析 本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 校园导航 b．查看浏览路线等待输入起始景点： C．选择出发点与目的地 等待输入起始景点与目的地编号： d．参看景点信息等待输入景点编号： 概要设计 本系统包含一个文件。设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法，查找景点信息等程序段。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示景点信息，弗洛伊德算法主要实现求两景点之间最短路径，迪杰斯特拉算法实现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。 系统首先通过主程序调用void main( );进入系统主菜单函数，根据用户的选择可分别进入：1.浏览各景点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看景点信息；5.退出系统。 选择“浏览各景点及简介”项，显示十个景点的有关信息，包括景点编号，景点名称，景点简介。 选择“查看所有游览路线”项，会进入输入起始景点编号的界面，输入正确编号后会显示起始景点到其余九个景点的最短路线的方案。 选择“选择出发点和目的地”项，会进入输入起始景点与目的景点的界面，输入起始景 点与目的景点，并有空格隔开就得到两景点之间的最佳路径。 选择“查看景点信息”项，会进入输入要查看的景点的界面，如入后会显示该景点的有关信息。 选择“退出系统”项，就会退出程序。 详细设计 （1）十三个单位的图 0： 前门 1：图书馆 2：教二楼 3：实验楼 4：操场 5：教一楼 6：食堂 7： 水房 8：学一公寓 9：学二公寓 10：学三公寓 11：学四公寓 12：后门 （2）主程序流程图： （3）弗洛伊德的算法： void Floyd(MGraph *G) { int v,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];//定义参数 for(v=0;vG-vexnum;v++) for(w=0;wG-vexnum;w++) { D[v][w]=G-arcs[v][w].adj; for(u=0;uG-vexnum;u++) p[v][w][u]=0; if(D[v][w]INFINITY) { p[v][w][v]=1;p[v][w][w]=1; } } for(u=0;uG-vexnum;u++) for(v=0;vG-vexnum;v++) for(w=0;wG-vexnum;w++) if(D[v][u]+D[u][w]D[v][w]) { D[v][w]=D[v][u]+D[u][w]; for(i=0;iG-vexnum;i++) p[v][w][i]=p[v][u][i]||p[u][w][i]; } while(flag) { cout请输入出发点和目的地的编号（用空格隔开）:; cinkj; if(k0||kG-vexnum||j0||jG-vexnum) //判断输入的景点编号正确与否 { cout景点编号不存在!请重新输入出发点和目的地的编号:; cinkj; } if(k=0kG-vexnumj=0jG-vexnum) flag=0; } coutG-vexs[k].name; //输出景点名称 for(u=0;uG-vexnum;u++) if(p[k][j][u]k!=uj!=u) //输出路线 cout--G-vexs[u].name; cout--G-vexs[j].name; cout 总路线长D[k][j]endl; //输出总路线长度 } 调试分析 （1） 在程序设计中遇到了输出景点信息的表不整齐，用setw（）解决了；默认的界面太小，不能完整的看到输出信息，用了system(mode