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

江汉大学课程设计报告课程名称： 数据结构 设计题目： 导航路径规划 院 （系）： 数学与计算机科学学院 专 业： 数学与应用数学 班 级: 10级数学班 组 别：组长: 裴志威201008101127 组员: 李伟 201008101128分 工：李伟负责编写函数Menu用来显示界面及选择操作；函数Browser用来显示城市名称和编号；函数InitGraph用来录入城市的具体信息裴志威负责报告书整体规划及编写函数ShortestPath_DJJ用来算出一个城市到其他城市之间的最短路径，并可以看出总路程；函数Floyd用来算出出发点到目的地的最短路线并显示路费目 录一 、 系统功能和结构1.1 程序设计目的给定全国公路网络系统(自定义,要求城市个数=20)，根据导航策略（时间最短，里程最短）给出路径规划。系统运行界面自行设计。1.2 需求分析(1) 城市之间的道路可以有高速公路、普通公路，对图中所有道路必须标识是高速还是普通公路。(2) 两个城市之间可以有高速和普通公路同时存在，且各自里程数可以不同。(3) 约定：两城市之间有高速则高速通行时间最短；全国高速收费标准统一(￥0.5元/km)；普通公路不收费。(4) 用户以人机对话方式输入旅行起始、终止城市名（或者代码）,选择导航策略(缺省策略是里程最短)，程序输出从起点到终点的路径，总路径长度和所需通行费用(5) 任意两个城市之间的通行路径都是存在的(可以有多条)。(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 endl;cout*endl;*/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+)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)G-vexnum-1&v0!=v)cout 总路线长Dvendl; /输入的城市到其他城市的最短路径；2floyd函数（每一对顶点之间的最短路径）void 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+DuwDvw)&(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;;for(u=0;uvexnum;u+)if(pkju&k!=u&j!=u)arcskj.dis=0)coutarcskj.dis=1)cout高速公路;else cout出错;;cout总路线长Dkj 路费”打掉了“”导致出现好多条错误或者是函数名或者变量名平错了，用下面的错误提示就找到出错的地方，解决了根本就好多错误随之没有了；每个函数写好了后再放在一起保证大局；总的觉得要动手起来，问题是慢慢的解决，不知道的可以翻书或者百度。这其中我慢慢学会了动手编程，改错等，也进一步了解了最短路径。具体代码：#define INFINITY 10000#define MAX_VERTEX_NUM 40#define MAX 40#include#include#includeusing namespace std;#includetypedef 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;/顶点数，边数MGraph;MGraph b;MGraph InitGraph(void);void Menu(void);void Browser(MGraph *G);void ShortestPath_DJJ(MGraph *G);void Floyd(MGraph *G);/void Search(MGraph *G); main()system(mode con:cols=100 lines=40);int i;b=InitGraph();Menu();cini;while(i!=4)switch(i)case 1:system(cls);Browser(&b);Menu();break; case 2:system(cls);ShortestPath_DJJ(&b);Menu();break;case 3:system(cls);Floyd(&b);Menu();break;case 4:exit(1);break;default:break;cini;return 0;MGraph InitGraph(void)MGraph G;int i,j;G.vexnum=25;G.arcnum=28;for(i=0;iG.vexnum;i+)G.vexsi.num=i;strcpy(G.,乌鲁木齐);strcpy(G.,兰州);strcpy(G.,西宁);strcpy(G.,呼和浩特);strcpy(G.,北京);strcpy(G.,西安);strcpy(G.,郑州); strcpy(G.,成都); strcpy(G.,昆明); strcpy(G.,贵阳); strcpy(G.,株洲); strcpy(G.,武汉); strcpy(G.,南昌); strcpy(G.,天津); strcpy(G.,徐州); strcpy(G.,上海); strcpy(G.,福州); strcpy(G.,广州); strcpy(G.,深圳); strcpy(G.,柳州); strcpy(G.,南宁);strcpy(G.,沈阳);strcpy(G.,长春);strcpy(G.,哈尔滨);strcpy(G.,大连);for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY;G.arcsij.dis=INFINITY;G.arcs01.adj=1892;G.arcs01.dis=1;/G.arcsij.dis=1表示为高速公路 G.arcs12.adj=216; G.arcs12.dis=0;/G.arcsij.dis=0表示为普通公路G.arcs13.adj=1145;G.arcs13.dis=1;G.arcs15.adj=676;G.arcs15.dis=0;G.arcs34.adj=668;G.arcs34.dis=0;G.arcs413.adj=137;G.arcs413.dis=0; G.arcs46.adj=695;G.arcs46.dis=1;G.arcs56.adj=511;G.arcs56.dis=0;G.arcs57.adj=842;G.arcs57.dis=0;G.arcs611.adj=534;G.arcs611.dis=0;G.arcs78.adj=1100;G.arcs78.dis=1;G.arcs89.adj=639;G.arcs89.dis=0;G.arcs910.adj=902;G.arcs910.dis=1;G.arcs919.adj=607;G.arcs919.dis=0;G.arcs1011.adj=409;G.arcs1011.dis=0;G.arcs1012.adj=367;G.arcs1012.dis=0;G.arcs1017.adj=675;G.arcs1017.dis=0; G.arcs1019.adj=672;G.arcs1019.dis=0;G.arcs1215.adj=825;G.arcs1215.dis=0;G.arcs1216.adj=622;G.arcs1216.dis=1;G.arcs1314.adj=674;G.arcs1314.dis=0;G.arcs1321.adj=704;G.arcs1321.dis=0;G.arcs1415.adj=651;G.arcs1415.dis=1;G.arcs1718.adj=140;G.arcs1718.dis=1;G.arcs1920.adj=255;G.arcs1920.dis=0; G.arcs2124.adj=397;G.arcs2124.dis=0;G.arcs2122.adj=305;G.arcs2122.dis=0;G.arcs2223.adj=242;G.arcs2223.dis=1;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)G.arcsji.adj=G.arcsij.adj;G.arcsji.dis=G.arcsij.dis;return G;void Menu()cout 导航路径规划 endl;cout*endl;cout* 1、 城市预览 *endl;cout* 2、 里程最短 *endl;/cout* 3、 时间最短 *endl;cout* 3、 公路通行费用最省 *endl;cout* 4、 退出 *endl;cout*endl;coutOption-:;void Browser(MGraph *G)int v;cout*endl;cout编号 城市endl;for(v=0;vvexnum;v+)coutvexsv.num endl;cout*endl;void ShortestPath_DJJ(MGraph * G)int v,w,i,min,t=0,x,flag=1,v0/*min1*/;int final30,D30,p3030/*C30*/;/*cout*endl;cout编号 城市endl;for(v=0;vvexnum;v+)coutvexsv.num endl;cout*endl;*/while(flag)coutv0;if(v0G-vexnum)coutv0;if(v0=0&v0vexnum)flag=0;for(v=0;vvexnum;v+)finalv=0;Dv=G-arcsv0v.adj;/从起始地点到其他城市的距离/Cv=Dv*(G-arcsv0v.dis)*0.5;for(w=0;wvexnum;w+)pvw=0;/设空路径if(DvINFINITY/*&CvINFINITY*/)pvv0=1;pvv=1;Dv0=0;/初始化finalv0=1;/v0属于最短路径的终点的集合/开始循环，每次求的v0到某个v顶点的最短路径，并加v到集合中for(i=1;ivexnum;i+)min=INFINITY;/min1=INFINITY;for(w=0;wvexnum;w+)if(!finalw)if(Dwmin/*&Cwmin1*/)v=w;min=Dw;/*min1=Cw;*/finalv=1;for(w=0;wvexnum;w+)if(!finalw&(min+G-arcsvw.adjarcsvw.disarcsvw.adj;/Cw=min1+G-arcsvw.dis;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) /*arcsvw.adjarcsvw.dis=1)coutarcsvw.dis=0)cout普通公路