数据结构校园导航程序设计
- 格式：doc
- 大小：349.00 KB
- 文档页数：15
一、设计题目：实验题目：设计你的学校的平面图，至少包括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 final[20], D[20], p[20][20];cout<<"编号地点名称简介 "<<endl;for(v=0;v<G->vexnum;v++)cout<<G->vexs[v].num<<""<<G->vexs[v].name<<" "<<G->vexs[v].introduction<<endl; while(flag){cout<<"请输入一个起始地点编号:";cin>>v0;if(v0<0||v0>G->vexnum){cout<<"地点编号不存在!请重新输入地点编号:";cin>>v0;}if(v0>=0&&v0<G->vexnum)flag=0;}for(v=0;v<G->vexnum;v++){final[v]=0;D[v]=G->arcs[v0][v].adj;for(w=0;w<G->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;i<G->vexnum;i++){min=infinity;for(w=0;w<G->vexnum;w++)if(!final[w])if(D[w]<min){v=w;min=D[w];}final[v]=1;for(w=0;w<G->vexnum;w++)if(!final[w]&&(min+G->arcs[v][w].adj<D[w])) {D[w]=min+G->arcs[v][w].adj;for(x=0;x<G->vexnum;x++)p[w][x]=p[v][x];p[w][w]=1;}}for(v=0;v<G->vexnum;v++){if(v0!=v) cout<<G->vexs[v0].name;for(w=0;w<G->vexnum;w++){if(p[v][w]&&w!=v0) cout<<"->"<<G->vexs[w].name; t++;}if(t>G->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、退出程序界面。
七、心得体会：程序设计前应该设计好系统实现的目的，系统大概流程。
这个系统在设计前就是要是实现校园地图的设计，地点与地点间的的路径、权值等；数据结构的存储、和算法的实现；但觉的一个人设计程序系统实验量大，难以一下确定方向，所以应该推广团队合作、分工，因为一个人的思维得到发散。
附录：系统相关代码：#define infinity 10000#define max_vertex_num 40#define MAX 40#include<string.h>#include <iostream.h>typedef struct ArCell{int adj; //路径长度}ArCell,AdjMatrix[max_vertex_num][max_vertex_num];typedef struct //图中顶点表示主要地点，存放地点的编号、名称、简介等信息，{char name[30];int num;char introduction[100];//简介}infotype;typedef struct{infotype vexs[max_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;i<G.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,"学校的主要教学楼。
