c语言公交最优路径查询数据结构附设计报告_完整代码.doc

数据结构课程设计说明2010.1常州工学院计算机信息工程学院 数据结构课程设计报告 题 目 公交路线上优化路径的查询年 级 2008级 专 业 软件工程 学生学号 08030334（组长） 学生学号 08030337 指导教师 王树峰 2010 年 01 月 11 日常州工学院计算机信息工程学院数据结构课程设计任 务 书设计名称： 公交线路上优化路径的查询 指导教师： 王树峰 下达时间： 2010-01-11 学生姓名： XXX （组长） 学 号： XXXXXXXXX学生姓名： XXXX 学 号： XXXXXXXX 专业： 软件工程一、课程设计的基本要求 根据上述公交线路的输入格式，定义并建立合适的图模型。 针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜的路径，输出格式为：线路x：站名S，站名M1；换乘线路x：站名M1，站名M2；换乘线路x：站名MK，站名T。共花费x元。 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（不考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，站名M1；换乘线路x：站名M1，站名M2；换乘线路x：站名MK，站名T。共花费x时间。 针对上述公交线路，能查询获得任何两个站点之间最省时间的路径（要考虑在中间站等下一辆线路的等待时间），即输入站名S，T后，可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径，输出格式为：线路x：站名S，站名M1；换乘线路x：站名M1，站名M2；换乘线路x：站名MK，站名T。共花费x时间。 二、课程设计的主要内容（包含分工）主要内容：首先将多有要用到的结构体全部定义完全，在课程设计的进程安排12010年01月10日之前： 完成所有要用到的结构体的定义。22010年01月11日01月12日： 完成建立合适的图模型以及信息的初始化。32010年01月15日前： 将初始化的所有的信息与建立的图模型完全连接起来，写 调整函数将每一条路线的车的信息存放到所有的节点里去。42010年1月16日2010年1月18日 ： 完成按时间和价格的最优的方法选择路线。 5. 2010年1月19日2010年1月20日： 完成所有的程序。 6. 2010年1月21日 答辩 具体分工：XX（组长）：，定义所有将要用到的结构体 ，编写函数实现根据公交路线信息修改站点信息的功能 ，利用Floyd算法找出按时间的所有两站之间的最优路径 ，编写时间最优的路线选择（不考虑等待时间） ，编写时间最优的路线选择（考虑等待时间）XX ：，初始化所有信息 ，建立图模型 ，编写价格最优的路线选择 ，界面优化2010年 01月11日数据结构课程设计报告（模板）一 正文1、目的 求公交线路上优化路径的查询 。2、需求分析程序需要根据乘客的需要来查询的出符合要求的信息在程序运行的过程中根据提示进行输入；程序输出所有符合要求的最优的路线以供乘客选择；程序能查询任意两站之间按时间和按价格的最优路线查询；3、 概要设计 先建图，再用Floyd函数求出任意两个结点之间的最优路径，后调用shortest函数进行求时间最优的路径，结束后在main函数里面提供选择界面，可以进行时间和价格最优路线的查询分别为Select_Time函数和Select_Money函数4、详细设计1）、定义结构体typedef struct int selectbusnum;char station1,station2;int selectbusprice,selectbusgap;Selects; /存储按条件选择的最优选择路线的信息 typedef structchar StaName;char Location128;StationInfo; /站点的信息，每个站点中存放的信息有名字和位置typedef struct VRType adj; /因为是有向图，adj用来存放权值，存放的是两个结点之间 的时间值 InfoType *info;/存放弧的信息 ArCell, adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/adjvw 数组即v 和w之间的权值typedef struct int num; /车辆的路线号int price ; /每路车的票价int gap; /每两次发车之间的时间间隔int speed; /车速int stopnum; /每辆车经过的车站的总数StationInfo passMAX_VERTEX_NUM; /每一路车经过的站点的信息BusInfo; /车辆信息typedef struct char StaName;char Location32;int stopbusnum;BusInfo stopbusMAX_BUS_NUM;VertexType; / 每个结点存放的信息，包括了站名，位置，经过的车辆数以及经过的该站点的所有的车辆的信息2）调整函数 Adjustvoid Adjust (MGraph &G,VertexType *S)int i;for (i=0;iMAX_VERTEX_NUM;i+)G.vexsi.StaName=Si.StaName; 将所有初始化的值与图联系起来， 把初始化的点的名字传给图中各个节点的StaName。void Adjust_2(BusInfo *bus,MGraph &G)int i,j,t8=0,0,0,0,0,0,0,0,p;for (i=0;iMAX_VERTEX_NUM;i+)for (j=0;jMAX_BUS_NUM;j+)for (p=0;pbusj.stopnum;p+)if (G.vexsi.StaName= =busj.passp.StaName)G.vexsi.stopbusnum+;G.vexsi.stopbusti.num=busj.num;G.vexsi.stopbusti.price=busj.price;G.vexsi.stopbusti.gap=busj.gap;G.vexsi.stopbusti.speed=busj.speed;ti+;将所有的初始化的点的信息以及bus的信息传递给图，每个结点中记录了经过该站的所有的车辆的信息，busj.passp是用来存放该车经过的站的信息。定义的整型数组t8是用来对每辆车经过的站的个数进行计数的。3）建立图模型int LocateVex(MGraph G,char u)int i;for(i=0;iG.vexnum;i+)if (u=G.vexsi.StaName)return i;if(i=G.vexnum) printf(Error u!n);return 1; return 0;LocateVex函数在下面建图函数中调用的时候是用来找到v1，v2结点分别在G向量中的位置的。void CreateMGraph(BusInfo *bus,VertexType *S,MGraph &G)void Adjust (MGraph &G,VertexType *S); void Adjust_1(BusInfo *bus,VertexType *S);void Adjust_2(BusInfo *bus,MGraph &G); /申明要调用的函数Adjust (G,S);Adjust_2(bus,G);Adjust_1(bus,S); int i,j,t;G.vexnum=8;G.arcnum=11;char v1,v2,a112=A,B,A,D,A,F,B,C,D,C,D,E,F,E,C,G,F,G,E,H,G,E;int b11=8,5,6,3,2,10,7,4,5,15,20; /根据初始化的数据构建弧的权值（时for (i=0;iG.vexnum;i+) 间）for (j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY;/ INFINITY宏定义的最大值表示距离for (t=0;t11;t+)v1=at0;v2=at1; /将v1，v2赋值为弧的两端的结点i=LocateVex(G,v1); /i表示v1在G向量结点数组中的位置j=LocateVex(G,v2); /j表示v2在G向量结点数组中的位置G.arcsij.adj=bt; /将数组b中的时间值赋给i到j的弧上return;建立图模型将所有的初始化的数据放到图的每项中。4）test函数void Test(BusInfo *bus,MGraph G) int i,j;for (i=0;iMAX_BUS_NUM;i+)printf(路线%d 票价%d 间隔%d分钟 车速%dkm/h ,busi.num,busi.price,busi.gap,busi.speed);printf(经过的站为:);for (j=0;jbusi.stopnum;j+) printf(%c%s,busi.passj.StaName,busi.passj.Location);printf(n);for (i=0;iMAX_VERTEX_NUM;i+)printf(站名%c 坐标%sn,Si.StaName,Si.Location);for (j=0;jSi.stopbusnum;j+)printf(停靠汽车及相关信息：路线%d 票价%d 间隔%d分钟 车速%d千米每分,G.vexsi.stopbusj.num,G.vexsi.stopbusj.price,G.vexsi.stopbusj.gap,G.vexsi.stopbusj.speed);printf(n); Test函数是用来测试建立图之后，原来初始化的数据是否已经成功的存放进图。5）Show_FLOYD函数 void Show_FLOYD() Test(bus,G); /先将图线输出便于后面的查看 CreateMGraph(bus,S,G); /建图PrintMGraph(G);Test(bus,G); /图是用邻接矩阵的方法来建的，所以用在 int i,j,k,l,m,n; /这里的PrintMGraph函数是用来输出矩阵的 for(i=0;iG.vexnum;i+) G.arcsii.adj=0; / ShortestPath_FLOYD()要求对角元素值为0 printf(邻接矩阵:n); for(i=0;iG.vexnum;i+) /直接有路径的输出时间，没有的在输出INFINITY for(j=0;jG.vexnum;j+) printf(%6d,G.arcsij); printf(n); ShortestPath_FLOYD(G,&p,&d); /调用函数来找出按时间所有的的最短路径 printf(d矩阵:n); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) /用二维数组来输出对应的矩阵中的权值 printf(%6d,dij); printf(n); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) if (dij!=100) printf( %c到%c的最短时间为%d分 n,G.vexsi.StaName,G.vexsj.StaName,dij); printf(p矩阵:n); / p矩阵用来存放路线信息从i到j的具体路线 l=G.vexnum; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) if(i!=j) m=0; / 占位空格 for(k=0;kG.vexnum;k+) if(pijk=1) printf(%c,G.vexsk.StaName); else m+; for(n=0;nm;n+) / 输出占位空格 printf( ); /如果两个结点之间找不到可以直接通的路 / 线则在相应的位置上输出空格 printf(n); printf(按回车键继续.);a=getchar();system(cls); /输出信息过多，清屏一次 用于输出所有的两个结点的时间信息以及从每个点到其他任意一个点的具体路线6）ShortestPath_FLOYD函数 void ShortestPath_FLOYD(MGraph G,PathMatrix *P,DistancMatrix *D) / 用Floyd算法求有向网G中各对顶点v和w之间的最短路径Pvw及其 / 带权长度Dvw。若Pvwu为TRUE,则u是从v到w当前求得最短 int u,v,w,i; for(v=0;vG.vexnum;v+) / 各对结点之间初始已知路径及距离 for(w=0;wG.vexnum;w+) (*D)vw=G.arcsvw.adj; /D矩阵用来存放每一条弧的权值即时间值 for(u=0;uG.vexnum;u+) (*P)vwu=FALSE; if(*D)vwINFINITY)/当权值小于最大值时说明从v到w有直接路径 (*P)vwv=TRUE; /v，w之间有直接路径就将 (*P)vwv赋值为1 (*P)vww=TRUE; for(u=0;uG.vexnum;u+) for(v=0;vG.vexnum;v+) for(w=0;wG.vexnum;w+) if(*D)vu+(*D)uw(*D)vw) / 从v经u到w的一条路径更短 (*D)vw=(*D)vu+(*D)uw; for(i=0;iG.vexnum;i+) (*P)vwi=(*P)vui|(*P)uwi; 此函数是用来求出每个点到另外的任意一个点的按时间的最优的路径，对于有两个结点相邻但路径的时间是否是最短进行判断并挑选出时间的最优的路径，下面的选择函数则是在将这些路径比较和挑选。7）Select_Time函数void Select_Time()char v1,v2;int i,j,k,m,n=0,t=0,flag=0,loc1,loc2,numMAX_BUS_NUM=1,1,1,1,1,1;/*num数组用来做标记用,已做过标记为0，没做够标记为1*/char aMAX_VERTEX_NUM;/ * a字符数组用来存放从v1到v2的最短路径所经过的都有的站点名字 * /printf(请输入起始站点和目的点n);scanf(%c%c,&v1,&v2);for(i=0;iG.vexnum;i+)if (v1=G.vexsi.StaName) /找到与名字v1对应的结点loc1=i; /用来存放出发点v1在图中的位置printf(站名%c 坐标%sn,G.vexsi.StaName,G.vexsi.Location);for (j=0;jG.vexsi.stopbusnum;j+) /找出所有v2点停靠的车辆的信息printf(停靠汽车及相关信息：路线%d 票价%d 间隔%d分钟 车速%d千米每分,G.vexsi.stopbusj.num,G.vexsi.stopbusj.price,G.vexsi.stopbusj.gap,G.vexsi.stopbusj.speed);printf(n经过的站为:);for (m=0;mbusj.stopnum;m+)printf(%c%s,G.vexsi.stopbusj.passm.StaName,G.vexsi.stopbusj.passm.Location); /将所有v2点停靠的车辆的信息输出 printf(n);if (v2=G.vexsi.StaName)loc2=i; /用来存放出发点v2在图中的位置printf(站名%c 坐标%sn,Si.StaName,Si.Location);for (j=0;jG.vexsi.stopbusnum;j+) /找出所有v2点停靠的车辆的信息printf(停靠汽车及相关信息：路线%d 票价%d 间隔%d分钟 车速%d千米每分,G.vexsi.stopbusj.num,G.vexsi.stopbusj.price,G.vexsi.stopbusj.gap,G.vexsi.stopbusj.speed);printf(n经过的站为:);for (m=0;mbusj.stopnum;m+)printf(%c%s,G.vexsi.stopbusj.passm.StaName,G.vexsi.stopbusj.passm.Location); /将所有v2点停靠的车辆的信息输出 printf(n);printf(n*结果*nn);for(i=0;iMAX_BUS_NUM;i+)for (j=0;jbusi.stopnum;j+)if (v1=busi.passj.StaName|v2=busi.passj.StaName) /判断在该车都经过的站点中有没有是v1或v2的t+;/用来标记一条最短路径中的v1，v2出现情况if (t=2)/t=2时则表示v1，v2两个结点都在该条最短路径中printf(直达路线%d 票价%d 间隔%d分钟 车速%dkm/h 停靠%d站,busi.num,busi.price,busi.gap,busi.speed,busi.stopnum);printf(n经过的站为:);for (m=0;mbusi.stopnum;m+)printf(%c%s,busi.passm.StaName,busi.passm.Location);printf(n); t=0;flag=1;/此处的t=0是t=2的情况重置便于下个循环的实现t=0;/此处是将t=1是的情况重置用于下一个大循环的实现i=LocateVex(G,v1); /找出v1在图中的位置j=LocateVex(G,v2); /找出v2在图中的位置if (dij!=INFINITY) /当i，j之间有最短路径时输出下面信息printf(%c到%c的最短时间为%d分n,G.vexsi.StaName,G.vexsj.StaName,dij);if(flag!=1) /标记flag当为1时i和j直接有弧，有直接从i到j的车printf(两站直接没有车直达,可以选择换乘!n);printf(经过的站点);for(t=0;tG.vexnum;t+) if(pijt=1) printf(%c,G.vexst.StaName);printf(n);t=0;for(m=0;m=G.vexnum;m+)if(pijm=1) /当pijm为1 时说明i，j之间有直接的路径at=G.vexsm.StaName;t+;/将每个结点的名字存放到a里for (m=0;mt-1;m+)loc1=LocateVex(G,am);loc2=LocateVex(G,am+1);/先定义连续的两辆车for (i=0;iG.vexsloc1.stopbusnum;i+)for (j=0;jG.vexsloc2.stopbusnum;j+)if(G.vexsloc1.stopbusi.num=G.vexsloc2.stopbusj.num)/判断连续的两个站是否有直接相连的一路车flag=m+1; /如果有则记下m+1for (k=0;kbusi.stopnum;k+) if (G.vexsloc1.stopbusi.passk.StaName=aflag) flag+;/如果经过locl的车同时经过下一个站个flag+if (numG.vexsloc1.stopbusi.num!=0) printf(乘坐%d路车 在%c 站上车 在%c 站下车n,G.vexsloc1.stopbusi.num,am,aflag-1);numG.vexsloc1.stopbusi.num=0;/ *表示已经做过了这辆车，则标记为0 */ 根据输入的站名来选择时间上最优的路线。8）Select_Money函数void Select_Money()char v1,v2,ch;Selects B10;int i,j,k=0,m,n=0,t=0,flag=0,loc1,loc2,numMAX_BUS_NUM,min=0;char aMAX_VERTEX_NUM;/ * a字符数组用来存放从v1到v2的最短路径所经过的都有的站点名字 * /printf(请输入起始站点和目的点n);scanf(%c%c,&v1,&v2);printf(*站点信息*n);for(i=0;iG.vexnum;i+)if (v1=G.vexsi.StaName)loc1=i; /找出v1站点的位置printf(站名%c 坐标%sn,Si.StaName,Si.Location);for (j=0;jG.vexsi.stopbusnum;j+)printf(停靠汽车及相关信息：路线%d 票价%d元 间隔%d分钟 车速%d千米每分, /输出经过该站点的所有的车的信息G.vexsi.stopbusj.num,G.vexsi.stopbusj.price,G.vexsi.stopbusj.gap,G.vexsi.stopbusj.speed);printf(n经过的站为:);for (m=0;mbusj.stopnum;m+)printf( %c %s,G.vexsi.stopbusj.passm.StaName,G.vexsi.stopbusj.passm.Location);printf(n);if (v2=G.vexsi.StaName)loc2=i; /找出v1站点的位置printf(站名%c 坐标%sn,Si.StaName,Si.Location);for (j=0;jG.vexsi.stopbusnum;j+)printf(停靠汽车及相关信息：路线%d 票价%d元 间隔%d分钟 车速%d千米每分, /输出多有经过v2的车的信息G.vexsi.stopbusj.num,G.vexsi.stopbusj.price,G.vexsi.stopbusj.gap,G.vexsi.stopbusj.speed);printf(n经过的站为:);for (m=0;mbusj.stopnum;m+)printf( %c %s,G.vexsi.stopbusj.passm.StaName,G.vexsi.stopbusj.passm.Location);printf(n);printf(n);printf(*结果*n);for(i=0;iMAX_BUS_NUM;i+) /寻找最优路径for (j=0;jbusi.stopnum;j+)if (v1=busi.passj.StaName|v2=busi.passj.StaName)t+; /标记t，当t为1是说明条件只满足了一个if (t=2) /当t为2时说明上述两个条件都满足printf(直达路线%d 票价%d元 间隔%d分钟 车速%dkm/h 停 靠%d站, /t为2说明两个站都在这路车里找到了busi.num,busi.price,busi.gap,busi.speed,busi.stopnum);printf(n经过的站为:);for (m=0;mbusi.stopnum;m+)printf(%c%s,busi.passm.StaName,busi.passm.Location);printf(n); t=0;flag=1;numn=i;n+;t=0;if(flag= =1) /flag标记说明v1，v2之间有直接通的一路车 min=100; /将min最小先赋值为100用于下面的循环for(m=0;mn;m+)if(busnumm.pricemin)min=m; printf(最省车费%dn,busnummin.price);printf(选择路线%d 票价%d元 间隔%d分钟 车速%dkm/h 停靠%d站,busmin.num,busmin.price,busmin.gap,busmin.speed,busmin.stopnum);printf(n经过的站为:);for (m=0;mbusmin.stopnum;m+)printf(%c%s,busmin.passm.StaName,busmin.passm.Location);printf(n); if(flag!=1) min=0; /将min赋值为0，由于两站之间没有直通车用于下面多i=LocateVex(G,v1); /辆车的比较j=LocateVex(G,v2);printf(两站直接没有车直达,可以选择换乘!n);printf(经过的站点);for(t=0;tG.vexnum;t+) if(pijt=1) printf(%c,G.vexst.StaName);printf(n);t=0;for(m=0;m=G.vexnum;m+)if(pijm=1) at=G.vexsm.StaName;t+;for (m=0;mt-1;m+)loc1=LocateVex(G,am);loc2=LocateVex(G,am+1);/先定义连续的两个站for (i=0;iG.vexsloc1.stopbusnum;i+)for (j=0;jG.vexsloc2.stopbusnum;j+)if(G.vexsloc1.stopbusi.num=G.vexsloc2.stopbusj.num)/判断连续的两个站是否有是同一路车Bk.selectbusnum=G.vexsloc1.stopbusi.num;Bk.station1=am;Bk.station2=am+1;Bk.selectbusprice=G.vexsloc1.stopbusi.price;Bk.selectbusgap=G.vexsloc1.stopbusi.gap;k+;/将该路车的信息存放到Select结构体数组B中flag=k;for(i=0;iflag;i+)for(j=i+1;jflag;j+)if(Bi.selectbusnum=Bj.selectbusnum&Bi.station2=Bj.station1)Bj.selectbusnum=0;ch=Bi.station2;Bi.station2=Bj.station2;for(t=j+1;tflag;t+)if(Bt.station1=ch)Bt.selectbusnum=0;/由于将每两个结点有弧的车全都存放进了数组B中可能存 / /在着重复的项，此循环则是用于将重复的车辆信息合并for(t=0;tflag;t+)if (Bt.selectbusnum!=0)min=min+Bt.selectbusprice; /*先将搜有能连接来那个地的所有的车的价格全部相加*/for(t=0;tflag;t+)if (Bt.selectbusnum!=0&Bt.station1=Bt+1.statio