数据结构校园导航程序设计

一、设计题目：实验题目：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。二、需求分析实验设计的是实现一个简易的校园导航平面图。本课题实现校园多个场所（至少10个）的最短路径求解。（1）输入的形式和输入值的范围：本系统主要数据类型为字符型和整形，字符型主要包括地点编号，地点名称，地点简介，功能编号；输入功能编号与单位编号进行操作。(2)输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。(3)程序所能达到的功能：可以为学生或旅客了解我校大概地点位置以及路径，主要功能：1.浏览校园地点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。a.首先看到的是校园导航系统的菜单：b．查看浏览路线等待输入起始地点：C．选择出发点与目的地等待输入起始地点与目的地编号（中间用空格隔开）：d．参看地点信息等待输入地点编号：三、概要设计本系统包含菜单（menu），显示信息（show），弗洛伊德算法(floyd)，迪杰斯特拉算法(shotpath_dj)，查找地点信息等程序段(search)。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示地点信息，弗洛伊德算法主要实现求两地点之间最短路径，迪杰斯特拉算法实现找两地点之间所有路径，查找地点信息主要实现显示某一地点信息。系统首先通过主程序调用voidmain();进入系统主菜单函数，根据用户的选择可分别进入：1.浏览各地点及简介；2.查看所有游览路径；3.选择出发点和目的地求出最短路径；4.查看地点信息；5.退出系统。选择“1”项，显示十个地点的有关信息，包括地点编号，地点名称，地点简介。选择“2”项，会进入输入起始地点编号的界面，输入正确编号后会显示起始地点到其余九个地点的所有路径。选择“3”项，会进入输入起始地点与目的地点的界面，输入起始地点与目的地点，并有空格隔开就得到两地点之间的最短路径。选择“4”项，会进入输入要查看的地点的界面，输入地点编号后会显示该地点的有关信息。选择“5”项，就会退出程序。下图为程序总框架图，表示函数之间的函数关系：四、系统详细设计（1）十个校园地点图：0：正大门1：南三栋2：西区篮球场3：食堂4：教三栋5：图书馆6：北区食堂7：医务室8：软件楼9：北门（2）主程序流程图：（3）迪结斯特拉算法实现的顶点V1到其他顶点的最短路径：voidShortPath_Dj(MGraph*G){intv,w,i,min,t=0,x,flag=1,v0;intfinal[20],D[20],p[20][20];cout编号地点名称简介endl;for(v=0;vG-vexnum;v++)coutG-vexs[v].numG-vexs[v].nameG-vexs[v].introductionendl;while(flag){cout请输入一个起始地点编号:;cinv0;if(v00||v0G-vexnum){cout地点编号不存在!请重新输入地点编号:;cinv0;}if(v0=0&&v0G-vexnum)flag=0;}for(v=0;vG-vexnum;v++){final[v]=0;D[v]=G-arcs[v0][v].adj;for(w=0;wG-vexnum;w++)p[v][w]=0;if(D[v]infinity){p[v][v0]=1;p[v][v]=1;}}D[v0]=0;final[v0]=1;for(i=1;iG-vexnum;i++){min=infinity;for(w=0;wG-vexnum;w++)if(!final[w])if(D[w]min){v=w;min=D[w];}final[v]=1;for(w=0;wG-vexnum;w++)if(!final[w]&&(min+G-arcs[v][w].adjD[w])){D[w]=min+G-arcs[v][w].adj;for(x=0;xG-vexnum;x++)p[w][x]=p[v][x];p[w][w]=1;}}for(v=0;vG-vexnum;v++){if(v0!=v)coutG-vexs[v0].name;for(w=0;wG-vexnum;w++){if(p[v][w]&&w!=v0)cout-G-vexs[w].name;t++;}if(tG-vexnum-1&&v0!=v)cout总路线长D[v]endl;}}五、调试分析（1）经验和体会：C++数据结构程序设计需要的是严谨的态度和思维，不容一点随意，格式的对错，类型的一致，嵌套和调用实现的目的，这些都要明确，首先要设计这个程序要有你想导航的大概地图，即校园的蓝图。然后利用相应的数据结构算法实现查找路径和最短路径，最后用menu函数实现系统入口调用算法求路径。六、使用说明和测试结果打开系统，首先会进入系统的主菜单：1.浏览各地点及简介2.查看所有游览路线3.选择出发点和目的地4.查看地点信息5.退出系统用户可以进行如下操作：1、如果你想浏览各地点及简介的话，请输入“1”，并回车。此时界面上将显示出各地点的编号、名称及其简介。2、如果你想查看某一地点的所有路径，可选择2操作。输入“2”，并回车。此时，系统会提示你输入某地点的编号。输入编号后，回车，便可以看到该地点到其他地点的所有路径。若输入的地点编号错误就会有提示重新输入。3、如果你想查看两个地点之间的最短路线的，可选择3操作。输入“3”，并回车。此时，系统会提示你要输入起始地点与终点的编号。输入编号后，回车，此时，便可以见到这两个地点之间的最短路径。4、如果你想查看具体某些地点的简介及信息，可以选择4操作。输入“4”，并回车。此时，系统会提示全部地点的对应的编号，选择你要查看的地点信息，输入其编号，回车，此时，屏幕上将会显示出该地点的各种信息。若输入的地点编号错误就会有提示重新输入。5、如果你想退出程序，可以选择“5“。测试结果1、菜单界面2、进入“浏览各地点及简介”后，输出地点信息的界面。3、进入“查看所有游览了路线“后，输入”0“到其他9个地点的路径：4、进入“选择出发点和目的地”，输入出发点1和目的点9后输出的的最佳路线的界面。5、进入“查看地点信息”，输入要查看的地点编号，输出地点信息的界面。6、输入要查询的地点编号错误，提示重新输入。7、退出程序界面。七、心得体会：程序设计前应该设计好系统实现的目的，系统大概流程。这个系统在设计前就是要是实现校园地图的设计，地点与地点间的的路径、权值等；数据结构的存储、和算法的实现；但觉的一个人设计程序系统实验量大，难以一下确定方向，所以应该推广团队合作、分工，因为一个人的思维得到发散。附录：系统相关代码：#defineinfinity10000#definemax_vertex_num40#defineMAX40#includestring.h#includeiostream.htypedefstructArCell{intadj;//路径长度}ArCell,AdjMatrix[max_vertex_num][max_vertex_num];typedefstruct//图中顶点表示主要地点，存放地点的编号、名称、简介等信息，{charname[30];intnum;charintroduction[100];//简介}infotype;typedefstruct{infotypevexs[max_vertex_num];AdjMatrixarcs;intvexnum,arcnum;}MGraph;MGraphb;MGraphInitGraph();voidMenu();voidshow(MGraph*G);voidShortPath_Dj(MGraph*G);voidFloyd(MGraph*G);voidSearch(MGraph*G);MGraphInitGraph()//定义地点编号，名称及简介{MGraphG;inti,j;G.vexnum=10;//十个地点（十个顶点）G.arcnum=14;//邻接矩阵for(i=0;iG.vexnum;i++)G.vexs[i].num=i;//各地点的代码，名称及简介strcpy(G.vexs[0].name,正大门);strcpy(G.vexs[0].introduction,朝南.旁边为211路车经过站点。);strcpy(G.vexs[1].name,南区六栋);strcpy(G.vexs[1].introduction,软件学生宿舍。);strcpy(G.vexs[2].name,西区篮球场);strcpy(G.vexs[2].introduction,多个篮球场。);strcpy(G.vexs[3].name,食堂);strcpy(G.vexs[3].introduction,紧邻教三楼，共3层，前两层是食堂，后一层是大学生之家。);strcpy(G.vexs[4].name,教三栋);strcpy(G.vexs[4].introduction,学校的主要教学楼。);strcpy(G.vexs[5].name,图书馆);strcpy(G.vexs[5].introduction,一二楼均有阅览室，以上是自习室和各种藏书。);strcpy(G.vexs[6].name,北区食堂);strcpy(G.vexs[6].introduction,标准食堂，两层，清洁卫生。);strcpy(G.vexs[7].name,医务室);strcpy(G.vexs[7].introduction,学生医务室。);strcpy(G.vexs[8].name,软件楼);strcpy(G.vexs[8].introduction,软件工程学生实验楼以及一些教师办公室。);strcpy(G.vexs[9].name,北门);strcpy(G.vexs[9].introduction,学校北大门。);for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)G.arcs[i][j].adj=infinity;//各地点之间的距离，没有的均为无穷大G.arcs[0][1].adj=50;G.arcs[0][5].adj=35;G.arcs[0][6].adj=15;G.arcs[0][9].adj=100;G.arcs[1][2].adj=5;G.arcs[1][3].adj=20;G.arcs[2][3].adj=10;G.arcs[3][4].adj=15;G.arcs[4][5].adj=20;G.arcs[5][6].adj=20;G.arcs[5][7].adj=25;G.arcs[5][8].adj=45;G.arcs[6][7].adj=5;G.arcs[7][9].adj=35;G.arcs[8][9].adj=75;for(i=0;iG.vexnum;i++)for(j=0;jG.vexnum;j++)G.arcs[j][i].adj=G.arcs[i][j].adj;returnG;}voidMenu(){cout校园导航系统endl;cout1.浏览各地点及简介endl;cout2.查看所有到达路径endl;cout3.选择出发点和目的地endl;cout4.查看地点信息endl;cout5.退出系统endl;cout选择:;}voidshow(MGraph*G)//显示地点编号、名称、简介{intv;cout编号地点名称简介endl;for(v=0;vG-vexnum;v++)