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

.一、设计题目：实验题目：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。二、 需求分析实验设计的是实现一个简易的校园导航平面图。本课题实现校园多个场所（至少10个）的最短路径求解。（1） 输入的形式和输入值的范围：本系统主要数据类型为字符型和整形，字符型主要包括地点编号，地点名称，地点简介，功能编号；输入功能编号与单位编号进行操作。 (2) 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。(3) 程序所能达到的功能：可以为学生或旅客了解我校大概地点位置以及路径，主要功能：1.浏览校园地点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。a.首先看到的是校园导航系统的菜单：b查看浏览路线等待输入起始地点：C选择出发点与目的地等待输入起始地点与目的地编号（中间用空格隔开）：d参看地点信息等待输入地点编号：三、概要设计 本系统包含菜单（menu），显示信息（show），弗洛伊德算法(floyd)，迪杰斯特拉算法(shotpath_dj)，查找地点信息等程序段(search)。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示地点信息，弗洛伊德算法主要实现求两地点之间最短路径，迪杰斯特拉算法实现找两地点之间所有路径，查找地点信息主要实现显示某一地点信息。系统首先通过主程序调用void main( );进入系统主菜单函数，根据用户的选择可分别进入：1.浏览各地点及简介；2.查看所有游览路径；3.选择出发点和目的地求出最短路径；4.查看地点信息；5.退出系统。选择“1”项，显示十个地点的有关信息，包括地点编号，地点名称，地点简介。选择“2”项，会进入输入起始地点编号的界面，输入正确编号后会显示起始地点到其余九个地点的所有路径。选择“3”项，会进入输入起始地点与目的地点的界面，输入起始地点与目的地点，并有空格隔开就得到两地点之间的最短路径。选择“4”项，会进入输入要查看的地点的界面，输入地点编号后会显示该地点的有关信息。选择“5”项，就会退出程序。下图为程序总框架图，表示函数之间的函数关系：四、 系统详细设计 （1）十个校园地点图： 0：正大门 1：南三栋 2：西区篮球场 3：食堂 4：教三栋 5：图书馆 6：北区食堂 7：医务室 8：软件楼 9：北门 （2）主程序流程图： （3）迪结斯特拉算法实现的顶点V1到其他顶点的最短路径：void ShortPath_Dj(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020;cout编号 地点名称 简介 endl; for(v=0;vvexnum;v+) roductionendl; while(flag) coutv0; if(v0G-vexnum) coutv0; if(v0=0&v0vexnum) flag=0; for(v=0;vvexnum;v+) finalv=0; Dv=G-arcsv0v.adj; for(w=0;wvexnum;w+) pvw=0; if(Dvinfinity) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=infinity; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvw.adjarcsvw.adj; for(x=0;xvexnum;x+) pwx=pvx; pww=1; for(v=0;vvexnum;v+) if(v0!=v) ; for(w=0;wvexnum;w+) if(pvw&w!=v0) ; t+; if(tG-vexnum-1&v0!=v) cout 总路线长Dvendl; 五、 调试分析 （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、退出程序界面。七、心得体会：程序设计前应该设计好系统实现的目的，系统大概流程。这个系统在设计前就是要是实现校园地图的设计，地点与地点间的的路径、权值等；数据结构的存储、和算法的实现；但觉的一个人设计程序系统实验量大，难以一下确定方向，所以应该推广团队合作、分工，因为一个人的思维得到发散。附录：系统相关代码：#define infinity 10000 #define max_vertex_num 40#define MAX 40#include#include typedef struct ArCellint adj; /路径长度ArCell,AdjMatrixmax_vertex_nummax_vertex_num;typedef struct /图中顶点表示主要地点，存放地点的编号、名称、简介等信息，char name30;int num;char introduction100;/简介infotype;typedef structinfotype vexsmax_vertex_num;AdjMatrix arcs;int vexnum,arcnum;MGraph;MGraph b;MGraph InitGraph();void Menu();void show(MGraph *G);void ShortPath_Dj(MGraph * G);void Floyd(MGraph *G);void Search(MGraph *G);MGraph InitGraph()/定义地点编号，名称及简介 MGraph G; int i,j; G.vexnum=10; /十个地点（十个顶点） G.arcnum=14; /邻接矩阵 for(i=0;iG.vexnum;i+) G.vexsi.num=i; /各地点的代码，名称及简介 strcpy(G.,正大 门); strcpy(G.roduction,朝南.旁边为211路车经过站点。); strcpy(G.,南区 六栋); strcpy(G.roduction,软件学生宿舍。); strcpy(G.,西区篮球场); strcpy(G.roduction,多个篮球场。); strcpy(G.,食 堂); strcpy(G.roduction,紧邻教三楼，共3层，前两层是食堂，后一层是大学生之家。); strcpy(G.,教 三 栋); strcpy(G.roduction,学校的主要教学楼。); strcpy(G.,图 书 馆); strcpy(G.roduction,一二楼均有阅览室 ，以上是自习室和各种藏书。); strcpy(G.,北区 食堂); strcpy(G.roduction,标准食堂，两层，清洁卫生。); strcpy(G.,医 务 室); strcpy(G.roduction,学生医务室。); strcpy(G.,软 件 楼); strcpy(G.roduction,软件工程学生实验楼以及一些教师办公室。); strcpy(G.,北 门); strcpy(G.roduction,学校北大门。); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.adj=infinity;/各地点之间的距离，没有的均为无穷大 G.arcs01.adj=50; G.arcs05.adj=35; G.arcs06.adj=15; G.arcs09.adj=100; G.arcs12.adj=5; G.arcs13.adj=20; G.arcs23.adj=10; G.arcs34.adj=15; G.arcs45.adj=20; G.arcs56.adj=20; G.arcs57.adj=25; G.arcs58.adj=45; G.arcs67.adj=5; G.arcs79.adj=35; G.arcs89.adj=75; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.adj=G.arcsij.adj; return G;void Menu() cout 校园导航系统 endl;cout 1.浏览各地点及简介 endl;cout 2.查看所有到达路径 endl;cout 3.选择出发点和目的地 endl;cout 4.查看地点信息 endl;cout 5.退出系统 endl;cout选择:;void show(MGraph *G)/显示地点编号、名称、简介 int v;cout编号 地点名称 简介 endl; for(v=0;vvexnum;v+)coutvexsv.num roductionendl;void ShortPath_Dj(MGraph * G)/迪结斯特拉算法实现的顶点V1到其他顶点的最短路径 int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020;cout编号 地点名称 简介 endl; for(v=0;vvexnum;v+)coutvexsv.num roductionendl; while(flag) coutv0; if(v0G-vexnum) coutv0; if(v0=0&v0vexnum) flag=0; for(v=0;vvexnum;v+) finalv=0; Dv=G-arcsv0v.adj; for(w=0;wvexnum;w+) pvw=0; if(Dvinfinity) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=infinity; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvw.adjarcsvw.adj; for(x=0;xvexnum;x+) pwx=pvx; pww=1; for(v=0;vvexnum;v+) if(v0!=v) ; for(w=0;wvexnum;w+) if(pvw&w!=v0) ; t+; if(tG-vexnum-1&v0!=v) cout 总路线长Dvendl; void Floyd(MGraph *G)/弗洛伊德算法 int v,u,i,w,k,j,flag=1,p101010,D1010;cout 编号 地点名称 简介 endl; for(v=0;vvexnum;v+)coutvexsv.num roductionendl; for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(Dvwinfinity) pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;ivexnum;i+) pvwi=pvui|puwi; while(flag) coutkj; if(kG-vexnum|jG-vexnu