课程设计报告《导航路径规划》.doc

江汉大学 课程设计报告 课程名称： 数据结构 设计题目： 导航路径规划 院 （系）： 数学与计算机科学学院 专 业： 数学与应用数学 班 级: 10级数学班 组 别：组长: 裴志威201008101127 组员: 李伟 201008101128 分 工：李伟负责编写函数Menu用来显示界面及选择操作；函数Browser用来显示城市名称和编号；函数InitGraph用来录入城市的具体信息 裴志威负责报告书整体规划及编写函数ShortestPath_DJJ用来算出一个城市到其他城市之间的最短路径，并可以看出总路程；函数Floyd用来算出出发点到目的地的最短路线并显示路费 目? 录 一 、 系统功能和结构 1.1 程序设计目的 给定全国公路网络系统(自定义,要求城市个数=20)，根据导航策略（时间最短，里程最短）给出路径规划。系统运行界面自行设计。 1.2 需求分析 城市之间的道路可以有高速公路、普通公路，对图中所有道路必须标识是高速还是普通公路。 两个城市之间可以有高速和普通公路同时存在，且各自里程数可以不同。 约定：两城市之间有高速则高速通行时间最短；全国高速收费标准统一(￥0.5元/km)；普通公路不收费。 用户以人机对话方式输入旅行起始、终止城市名（或者代码）,选择导航策略(缺省策略是里程最短)，程序输出从起点到终点的路径，总路径长度和所需通行费用 任意两个城市之间的通行路径都是存在的(可以有多条)。 必须考虑某些城市之间只有一条道路（高速或者普通公路）的情况； 全国公路网络数据以文件方式输入，但系统可以实现对道路信息的编辑修改（增加、删除、修改道路属性(类型、里程数) 1.3?概要设计 1.3.1???主要数据结构描述 1最短路径（从某个源点到其余各个顶点的最短路径） void ShortestPath_DJJ(MGraph * G) { int v,w,i,min,t=0,x,flag=1; int final[30],D[30],p[30][30]; cout编号 城市endl; for(v=0;vG-vexnum;v++) coutG-vexs[v].num G-vexs[v].nameendl; cout*****************************endl;*/ while(flag) { cout请输入一个起始点编号; cinv0; if(v00||v0G-vexnum) { cout城市不在此列举的城市中！请重新输入起点编号：; cinv0; } if(v0=0v0G-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;//v0属于最短路径的终点的集合 //开始循环，每次求的v0到某个v顶点的最短路径，并加v到集合中 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-ve