数据结构交通系统实验

1、数据结构实验报告20112012学年第一学期2009级计算机科学与技术专业班级：学号：姓名：一、实验目的根据数据结构课本图7.33交通图编写交通咨询系统二、实验要求使用邻接表或邻接矩阵的存储结构，根据需要输出从图中任意地点到其他任意地点的最短路径和最短距离。三、实验内容采用邻接矩阵的存储结构，将两个直接相连的城市之间的距离和票价存入矩阵之中（假设只有一种交通方式）。用一维数组存入城市名称。程序最关键部分为查询算法，实验采用迪杰斯拉特算法。迪杰斯拉特算法按路径长度递增的次序，逐步产生最短路径。首先求出长度最短的一条最短路径，然后参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点

2、的最短路径全部求出为止。引入辅助向量sN，pathN,distN。s中存放已经求出的最短路径的终点，初始化s时使si=0。初始状态时，s中只有一个源点，若源点在一维数组的位置为v，则sv=1。以后每求出一条最短路径就将其对应的s的值置为1。当所有的si的值为1时算法结束。Disti用于记载当前找到的从源点v到其它顶点的最短路径长度，它的每个分量disti表示当前所找到的从始点v到每个终点vi的最短路径的长度。它的初态为：若从源点v到vi有弧，则disti为弧上的权值；否则置disti为（程序中用最大正数INF代表）。假设已查到最短路径的终点为v0,下次最短路径的终点是vk，则这条路径或者是（v

3、0，vk），或者是（v0，vj，vk）。它的长度或者是从v0到vk的弧上的权值，或者是Dj和从vj到vk的弧上的权值之和因此，在每次求得一条最短路径之后，将Svj置为1,然后修改其distk:distk=Mindistk,distj+G.arcsjk.date（G.arcsjk.costG.arcsjk.date为路径的距离，G.arcsjk.coat为路径的票价。数组path保存从源点v到终点vi当前最短路径中的前一个顶点的编号。主程序通过switch语句控制程序执行的功能。程序的功能有：查询最短路径、查询最省钱路径、修改路径信息、删除路径、添加路径、添加站点、删除站点、显示某一城市到其余城

4、市之间的最短路径、输出直接相邻站点的信息。查询功能利用迪杰斯拉特算法实现，修改路径、删除路径、添加路径只需要在邻接矩阵对应位置赋值即可。添加站点：在存储城市名的一维数组G.versi.city里存入新的站点名称并相应修改路径信息即可。删除站点：将G.versi.city赋值为NULL,并将所有与该站点直接相连的路径信息删除。四、程序源代码迪杰斯拉特算法：voidDijkstra（MGraphG,intv）intdistN,pathN;intsN,pN;intmindis,i,j,u,pre;for（i=0;iN;+i）disti=G.arcsvi.date;si=0;if(G.arcsvi.d

5、ateINF)pathi=v;elsepathi=-1;/fosv=1;pathv=0;for(i=0;iN;+i)mindis=INF;u=-1;for(j=0;jN;+j)if(sj=0&distjmindis)u=j;mindis=distj;if(u!=-1)su=1;for(j=0;jN;j+)if(sj=0)if(G.arcsuj.dateINF&distu+G.arcsuj.date=0)distj=distu+G.arcsuj.date;pathj=u;/if/iffor(i=0;iG.vnum;i+)if(i!=v)if(strcmp(G.vexsi.city,)!=0)co

6、utG.vexsv.city-G.vexsi.city;if(si=1&disti0)cout路径长度为：disti;pre=i;intk=0;while(pre!=v)pk=pre;k+;if(pre=-1)j=0;break;pre=pathpre;/whilepk=pre;cout0;f-)coutG.vexspf.city-;coutG.vexsp0.cityendl;/ifelsecout不存在路径endl;/if/for查找站点在G.vers里的位置：intlocal(MGraphG,char*va)intf=-1;for(intm=0;mG.vnum;m+)if(strcmp(v

7、a,G.vexsm.city)=0)f=m;break;returnf;修改路径：cout请输入所添加路径起点va;a=local(G,va);if(a0)cout输入站点不存在，请检查站点名是否都正确endl;break;cout请输入所添加路径终点vb;b=local(G,vb);if(b0)cout输入站点不存在，请检查站点名是否都正确endl;break;if(G.arcsab.dateINF)cout该路径已经存在，请检查站点名是否都正确va;a=local(G,va);if(a=-1)cout输入站点不存在，请检查站点名是否都正确endl;break;cout请输入所删除路径终点v

8、b;b=local(G,vb);if(b=-1)cout输入站点不存在，请检查站点名是否都正确endl;break;if(G.arcsab.date=INF)cout该路径不存在或已删除，请检查站点名是否都正确endl;break;G.arcsab.date=INF;/INF表示为G.arcsba.date=INF;G.arcsab.cost=INF;G.arcsba.cost=INF;cout删除路径为：vavbendl;删除站点：while(hh)while(1)cout请输入所删除站点名称：va;a=local(G,va);if(a=-1)cout该站点不存在，请重新输入！;elsebr

9、eak;/判断站点是否已存在并控制重新输入for(inti=0;iCB;if(CB=N)hh=0;break;elseif(CB!=Y)cout输入错误，请重输！endl;elsebreak;/while添加站点;while(cg)while(1)cout请输入所添加站点名称：va;a=local(G,va);if(a=0)cout该站点已经存在，请重新输入！;elsebreak;/判断站点是否已存在并控制重新输入pc.city=(char*)malloc(20);strcpy(pc.city,va);t=G.vnum;G.vexst=pc;cout添加站点为：G.vexst.cityendl

10、;G.vnum=G.vnum+1;coutvv是否添加与该站点有关路径信息是Y否NCB;if(CB=N)break;elseif(CB!=Y)coutvv输入错误，请重输！vvendl;elsewhile(cx)coutvv请输入所添加路径终点vvendl;cinvb;b=local(G,vb);if(bv0)coutvv输入站点不存在，请检查站点名是否都正确vvendl;break;if(G.arcsab.datevINF)coutvv该路径已经存在，请检查站点名是否都正确vvendl;break;coutvv请输入所添加路径的距离vvendl;cinrange;coutvv请输入所添加路径

11、的花费vvendl;cinbudget;G.arcsab.date=range;G.arcsba.date=range;G.arcsba.cost=budget;G.arcsab.cost=budget;coutvv添加路径为：vvG.vexsa.cityv-G.vexsb.cityvvvG.arcsab.costvendl;五、运行结果：距离为：vvG.arcsab.datevv化费为:请选择DI概览图itRH删除站点L暑DE继续F退岀瞇续丽出时I南宁广外都贵阳株洲南昌昆明西女1剝*上海武汉兰Hi犬连天津西宁马兽木齐呼和浩特哈尔滨枚春t；：LOdt+2U11护灵虫第扌召tueOugxtis兰

12、I.exer路径改输C/站连自3曲、丄込的最短路径:Ofc概览图IT厂删除站点離霍鬲fl连站点的信息为%态H屯屯一67否古严上-2Y起终阳是径径贵为.路路基查杳一为XE-贵阳株洲武汉一郑州一北京天津TlillnirrI.tLoi?Ji-nn|、啤盅H汁）+汁一卅Mr片1-Z/9血ES9Zb8fr9匝sm_&4SAI159M0-ri-dII-a-:s1iJ1illJhjrtllit!9,111,EA-fi_1JITzAfl06EO0t+t60曽右凰IS-气-J-_#%bL.XBCTISS&9口孟亠EH显呈Imn盂壷蛊诸言吉孟玄丄莖鲨口工口京亠El宦丄工蒔盍盍盍丄昱尤里Q盍盍豈辿SL*n-HL-11LIItIFL哈尔浚长春路径为:24筐性2乂口爻口504.-si-*宀TJnfDTKOLKnJo-yb-M,0OTKdlk04DXKOLsj-工orKcm044B446-4不不在在在在在在在在在在mm在在在別路存存存存存存存存存存存存存存存存存存存存存昭KK不不不不不KKK不不不不不KKKK不重查羣密墓B囂蠹-長-!-愛-!=餐essanvkeytocontinue六、小结（不少于100字）通过此次试验，