公交线路优化路径的查询

课程设计报告课程：《数据结构》题目：___公交线路优化路径的查询___二〇一〇年六月实验目的和要求1、实验目的：【问题描述】对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为：线路编号：起始站名(该站坐标)；经过的站点1名(该站坐标)；经过的站点2名(该站坐标)；……；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱。车速。该线路平均经过多少时间来一辆。例如：63：A(32,45)；B(76,45)；C(76,90)；……；N(100,100)。1元。1/每分钟。5分钟。假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。不考虑乘客上下车的时间。对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的路径；任何两个站点之间最省时间的路径。2、实验要求：【设计要求】①根据上述公交线路的输入格式，定义并建立合适的图模型。②针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名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时间。具体程序设计代码#defineINF65535//定义一个最大数定为无穷值#includestdio.h#includemalloc.h#includeSEdit.h#defineMAX227typedefintcostAdj[MAX+1][MAX+1];//图邻接矩阵从开始记数intPath[MAX+1][MAX+1];//图邻接矩阵从开始记数typedefstructunDiGraph{intnumVerts;//结点costAdjcost;//邻接矩阵}unDiGraph,*UNG;//图的定义//构造带权(费用)图返回首地址G：unDiGraph*CreateCostG(){unDiGraph*G;inti,j;if(!(G=(unDiGraph*)malloc(sizeof(unDiGraph))))//为G分配存储空间。{return(NULL);}for(i=1;iMAX+1;i++){for(j=1;jMAX+1;j++){G-cost[i][j]=INF;//初始化使G-cost[i][j]为无穷。}}G-numVerts=227;for(i=1;iMAX+1;i++){for(j=1;jMAX+1;j++){G-cost[i][j]=G-cost[j][i]=1;}}/*G-cost[1][6]=G-cost[6][1]=96;G-cost[1][2]=G-cost[2][1]=84;G-cost[2][3]=G-cost[3][2]=51;G-cost[3][4]=G-cost[4][3]=53;G-cost[4][5]=G-cost[5][4]=40;G-cost[5][6]=G-cost[6][5]=90;G-cost[5][8]=G-cost[8][5]=67;G-cost[5][7]=G-cost[7][5]=67;G-cost[6][7]=G-cost[7][6]=60;G-cost[7][9]=G-cost[9][7]=25;G-cost[3][11]=G-cost[11][3]=69;G-cost[11][12]=G-cost[12][11]=13;G-cost[12][10]=G-cost[10][12]=67;G-cost[3][10]=G-cost[10][3]=34;G-cost[13][10]=G-cost[10][13]=65;G-cost[13][5]=G-cost[5][13]=118;*/return(G);}//构造带权(时间)图返回首地址G：unDiGraph*CreateTimeG(){unDiGraph*G;inti,j;if(!(G=(unDiGraph*)malloc(sizeof(unDiGraph))))//为G分配存储空间。{return(NULL);}for(i=1;iMAX+1;i++){for(j=1;jMAX+1;j++){G-cost[i][j]=INF;//初始化使G-cost[i][j]为无穷。}}G-numVerts=227;for(i=1;iMAX+1;i++){for(j=1;jMAX+1;j++){G-cost[i][j]=G-cost[j][i]=5;//初始化使G-cost[i][j]为无穷。}}/*G-cost[1][6]=G-cost[6][1]=9;G-cost[1][2]=G-cost[2][1]=8;G-cost[2][3]=G-cost[3][2]=5;G-cost[3][4]=G-cost[4][3]=5;G-cost[4][5]=G-cost[5][4]=4;G-cost[5][6]=G-cost[6][5]=9;G-cost[5][7]=G-cost[7][5]=6;G-cost[5][8]=G-cost[8][5]=6;G-cost[6][7]=G-cost[7][6]=6;G-cost[7][9]=G-cost[9][7]=2;G-cost[3][11]=G-cost[11][3]=6;G-cost[11][12]=G-cost[12][11]=1;G-cost[12][10]=G-cost[10][12]=6;G-cost[3][10]=G-cost[10][3]=3;G-cost[13][10]=G-cost[10][13]=6;G-cost[13][5]=G-cost[5][13]=11;*/return(G);}//通过城市的序号i输出对应城市名称voidpr(inti){switch(i)//运用switch语句。{case(1):printf();break;case(2):printf(安湖路口);break;case(3):printf();break;case(4):printf(北大客运中心);break;case(5):printf(北大路口);break;case(6):printf(北大路中);break;case(7):printf(北湖安居小区);break;case(8):printf(北湖路北);break;case(9):printf(北湖市场);break;case(10):printf(北湖衡阳路口);break;case(11):printf(北湖东二里);break;case(12):printf(北湖路口);break;case(13):printf(北际路口);break;case(14):printf(北大江北路口);break;case(15):printf(北湖东市场);break;case(16):printf(滨湖广场);break;case(17):printf();break;case(18):printf(朝阳济南路口);break;case(19):printf(朝阳花园);break;case(20):printf(长岗民主路口);break;case(21):printf(长岗市场);break;case(22):printf(长岗三里路口);break;case(23):printf(茶花园望园路口);break;case(24):printf(茶花碧湖路口);break;case(25):printf(长湖金湖路口);break;case(26):printf(长湖滨湖路口);break;case(27):printf(长岗路中);break;case(28):printf();break;case(29):printf(大学清川路口);break;case(30):printf(大岭路口);break;case(31):printf(动物园);break;case(32):printf(电力学校);break;case(33):printf(大学路口);break;case(34):printf(东博机电城);break;case(35):printf(大树脚);break;case(36):printf(大会堂);break;case(37):printf(东葛路口);break;case(38):printf(东葛中路);break;case(39):printf(东葛葛村路口);break;case(40):printf(东葛东路);break;case(41):printf(东葛长湖路口);break;case(42):printf();break;case(43):printf(二塘立交);break;case(44):printf(二公里);break;case(45):printf();break;case(46):printf(广西民族大学);break;case(47):printf(广西大学西门);break;case(48):printf(广西大学);break;case(49):printf(广西大学附中);break;case(50):printf(工业学校);break;case(51):printf(广西大学东门);break;case(52):printf(工人新村);break;case(53):printf(广西民族医院);break;case(54):printf(广西艺术学院);break;case(55):printf(古城路口);break;case(56):printf(古城建政路口);break;case(57):printf(葛村路口);break;case(58):printf();break;case(59):printf(火炬路);break;case(60):printf(衡阳北大路口);break;case(61):printf(火炬路一支);break;case(62):printf(衡阳地洞路口);break;case(63):printf(衡阳路口);break;case(64):printf(衡阳友爱路口);break;case(65):printf(衡阳路中);break;case(66):printf(火车站);break;case(67):printf(衡阳园湖路口);break;case(68):printf(虎邱);break;case(69):printf(会展中心);break;case(70):printf();break;case(71):printf(经济管理干部学院);break;case(72):printf(解放路口);break;case(73):printf(江北永宁路口);break;case(74):printf(建政东路);break;case(75):printf(金茶花公园);break;case(76):printf(金湖路口);break;case