《课程设计报告《导航路径规划》》由会员分享，可在线阅读，更多相关《课程设计报告《导航路径规划》（30页珍藏版）》请在金锄头文库上搜索。
1、江汉大学课程设计报告课程名称： 数据结构 设计题目： 导航路径规划 院 （系）： 数学与计算机科学学院 专 业： 数学与应用数学 班 级: 10级数学班 组 别：组长: 裴志威201008101127 组员: 李伟 201008101128分 工：李伟负责编写函数Menu用来显示界面及选择操作；函数Browser用来显示城市名称和编号；函数InitGraph用来录入城市的具体信息裴志威负责报告书整体规划及编写函数ShortestPath_DJJ用来算出一个城市到其他城市之间的最短路径，并可以看出总路程；函数Floyd用来算出出发点到目的地的最短路线并显示路费目 录一 、 系统功能和结构1.1
2、程序设计目的给定全国公路网络系统(自定义,要求城市个数=20)，根据导航策略（时间最短，里程最短）给出路径规划。系统运行界面自行设计。1.2 需求分析(1) 城市之间的道路可以有高速公路、普通公路，对图中所有道路必须标识是高速还是普通公路。(2) 两个城市之间可以有高速和普通公路同时存在，且各自里程数可以不同。(3) 约定：两城市之间有高速则高速通行时间最短；全国高速收费标准统一(￥0.5元/km)；普通公路不收费。(4) 用户以人机对话方式输入旅行起始、终止城市名（或者代码）,选择导航策略(缺省策略是里程最短)，程序输出从起点到终点的路径，总路径长度和所需通行费用(5) 任意两个城市之间的通
3、行路径都是存在的(可以有多条)。(6) 必须考虑某些城市之间只有一条道路（高速或者普通公路）的情况；全国公路网络数据以文件方式输入，但系统可以实现对道路信息的编辑修改（增加、删除、修改道路属性(类型、里程数)1.3概要设计1.3.1主要数据结构描述1最短路径（从某个源点到其余各个顶点的最短路径）void ShortestPath_DJJ(MGraph * G)int v,w,i,min,t=0,x,flag=1;int final30,D30,p3030;cout编号 城市endl;for(v=0;vvexnum;v+)coutvexsv.num vexsv.nameendl;cout*end
4、l;*/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;/v0属于最短路径的终点的集合/开始循环，每次求的v0到某个v顶点的最短路径，并加v到集合中for(i=1;ivexnum;i+)min=INFINITY;for(w=0;wvexnum;w+)
5、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)coutvexsv0.name;for(w=0;wvexnum;w+) if(pvw&w!=v0)coutvexsw.nameG-vexnum-1&v0!=v)cout 总路线长Dvendl; /输入的城市到其他城市的最短路径；2floyd函数（每一对顶点之间的最短路径）void
6、Floyd(MGraph *G)int v,u,i,w,k,j,flag=1,p303030,D3030,C3030;cout*endl;cout编号 城市 endl;cout*endl;for(v=0;vvexnum;v+)for(w=0;wvexnum;w+)Dvw=G-arcsvw.adj;Cvw=Dvw*(G-arcsvw.dis)*0.5;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+DuwDv
7、w)&(Cvu+CuwCvw)Dvw=Dvu+Duw;Cvw=Cvu+Cuw;for(i=0;ivexnum;i+)pvwi=pvui|puwi;while(flag)coutkj;if(kG-vexnum|jG-vexnum)coutkj;if(k=0&kvexnum&j=0&jvexnum)flag=0;coutvexsk.name;for(u=0;uvexnum;u+)if(pkju&k!=u&j!=u)coutvexsu.namearcskj.dis=0)coutarcskj.dis=1)cout高速公路;else cout出错;coutvexsj.name;cout总路线长Dkj 路
8、费Ckj;1.3.2算法分析及程序流程图1浏览城市名字和编号2浏览一个城市到其他城市的最短路径 选择操作 进入界面3查看出发点到目的地的最短路径和路费4 退出二、 程序实现 2.1模块详细设计程序由MGraph InitGraph(void);void Menu(void);void Browser(MGraph *G);void ShortestPath_DJJ(MGraph *G);void Floyd(MGraph *G);几个函数构成函数Menu用来显示界面及选择操作函数Browser用来显示城市名称和编号函数ShortestPath_DJJ用来算出一个城市到其他城市之间的最短路径，并
9、可以看出总路程函数Floyd用来算出出发点到目的地的最短路线并显示路费函数InitGraph用来录入城市的具体信息：城市名称，边的信息（两个城市间的路程）2322211343024211465111571210916198172018 普通公路 高速公路0:乌鲁木齐1：兰州2：西宁3：呼和浩特4：北京5：西安6:郑州7：成都8：昆明9：贵阳10：株洲11：武汉12：南昌13：天津14：徐州15：上海16：福州17：广州18：深圳19：柳州20：南宁21：沈阳22：长春23：哈尔滨24：大连三、 调试与操作说明3.1 问题分析与解决1.最开始不知道怎么把路程和路费加进去；后来想到在typedef
10、 struct ArCellint dis;/是普通道路还是高速int adj;/路程ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structchar name30;/城市的名字int num;/城市的代号infotype;typedef structinfotype vexsMAX_VERTEX_NUM;/顶点信息AdjMatrix arcs;/边信息int vexnum,arcnum;/顶点数，边数中加进去如上2 不怎么熟悉文件用法不知道怎样调用数据，后来想到编写一个函数InitGraph将信息写进去，就不需要文件操作了3.2程序演示1进入界面2选择第一个操作浏览城市名称和编号 34四 、 设计体会与总结4.1程序不足及功能扩充1任意两个城市之间的通行路径都是存在的(可以有
