c語(yǔ)言公交最優(yōu)路徑查詢(xún)數(shù)據(jù)結(jié)構(gòu)

《數(shù)據(jù)結(jié)構(gòu)》

課程設(shè)計(jì)說(shuō)明一、課程設(shè)計(jì)的基本要求根據(jù)上述公交線(xiàn)路的輸入格式，定義并建立合適的圖模型。針對(duì)上述公交線(xiàn)路，能查詢(xún)獲得任何兩個(gè)站點(diǎn)之間最便宜的路徑，即輸入站名S，T后，可以輸出從S到T的最便宜的路徑，輸出格式為：線(xiàn)路X：站名S，…，站名M1；換乘線(xiàn)路X：站名M1，…，站名M2；…；換乘線(xiàn)路X：站名MK，…，站名T。共花費(fèi)x元。針對(duì)上述公交線(xiàn)路，能查詢(xún)獲得任何兩個(gè)站點(diǎn)之間最省時(shí)間的路徑（不考慮在中間站等下一輛線(xiàn)路的等待時(shí)間），即輸入站名S，T后，可以輸出從S到T的考慮在中間站等下一輛線(xiàn)路的等待時(shí)間的最省時(shí)間的路徑，輸出格式為:線(xiàn)路X：站名S，…，站名M1；換乘線(xiàn)路X：站名M1，…，站名M2；…；換乘線(xiàn)路X：站名MK，…，站名T。共花費(fèi)X時(shí)間。針對(duì)上述公交線(xiàn)路，能查詢(xún)獲得任何兩個(gè)站點(diǎn)之間最省時(shí)間的路徑（要考慮在中間站等下一輛線(xiàn)路的等待時(shí)間），即輸入站名S，T后，可以輸出從S到T的考慮在中間站等下一輛線(xiàn)路的等待時(shí)間的最省時(shí)間的路徑，輸出格式為:線(xiàn)路X：站名S，…，站名M1；換乘線(xiàn)路X：站名M1，…，站名M2；…；換乘線(xiàn)路X：站名MK，…，站名T。共花費(fèi)X時(shí)間。二、課程設(shè)計(jì)的主要內(nèi)容（包含分工）主要內(nèi)容：首先將多有要用到的結(jié)構(gòu)體全部定義完全，在課程設(shè)計(jì)的進(jìn)程安排2010年01月10日之前：完成所有要用到的結(jié)構(gòu)體的定義。2010年01月11日——01月12日：完成建立合適的圖模型以及信息的初始化。2010年01月15日前：將初始化的所有的信息與建立的圖模型完全連接起來(lái)，寫(xiě)調(diào)整函數(shù)將每一條路線(xiàn)的車(chē)的信息存放到所有的節(jié)點(diǎn)里去。2010年1月16日——2010年1月18日：完成按時(shí)間和價(jià)格的最優(yōu)的方法選擇路線(xiàn)。2010年1月19日——2010年1月20日：完成所有的程序。2010年1月21日答辯具體分工：XX（組長(zhǎng)）：①，定義所有將要用到的結(jié)構(gòu)體，編寫(xiě)函數(shù)實(shí)現(xiàn)根據(jù)公交路線(xiàn)信息修改站點(diǎn)信息的功能，利用Floyd算法找出按時(shí)間的所有兩站之間的最優(yōu)路徑，編寫(xiě)時(shí)間最優(yōu)的路線(xiàn)選擇（不考慮等待時(shí)間），編寫(xiě)時(shí)間最優(yōu)的路線(xiàn)選擇（考慮等待時(shí)間）XX:①，初始化所有信息，建立圖模型，編寫(xiě)價(jià)格最優(yōu)的路線(xiàn)選擇，界面優(yōu)化2010年01月11日《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告（模板）_正文1、目的求公交線(xiàn)路上優(yōu)化路徑的查詢(xún)。2、需求分析程序需要根據(jù)乘客的需要來(lái)查詢(xún)的出符合要求的信息在程序運(yùn)行的過(guò)程中根據(jù)提示進(jìn)行輸入；程序輸出所有符合要求的最優(yōu)的路線(xiàn)以供乘客選擇；程序能查詢(xún)?nèi)我鈨烧局g按時(shí)間和按價(jià)格的最優(yōu)路線(xiàn)查詢(xún)；3、概要設(shè)計(jì)先建圖，再用Floyd函數(shù)求出任意兩個(gè)結(jié)點(diǎn)之間的最優(yōu)路徑，后調(diào)用shortest函數(shù)進(jìn)行求時(shí)間最優(yōu)的路徑，結(jié)束后在main函數(shù)里面提供選擇界面，可以進(jìn)行時(shí)間和價(jià)格最優(yōu)路線(xiàn)的查詢(xún)分別為Select_Time函數(shù)和Select_Money函數(shù)4、詳細(xì)設(shè)計(jì)1）、定義結(jié)構(gòu)體typedefstruct{intselectbusnum;charstation1,station2;intselectbusprice,selectbusgap;}Selects;〃存儲(chǔ)按條件選擇的最優(yōu)選擇路線(xiàn)的信息typedefstruct{charStaName;charLocation[128];}StationInfo;〃站點(diǎn)的信息，每個(gè)站點(diǎn)中存放的信息有名字和位置]typedefstruct{VRTypeadj;/因?yàn)槭怯邢驁D，adj用來(lái)存放權(quán)值，存放的是兩個(gè)結(jié)點(diǎn)之間的時(shí)間值InfoType*info;//存放弧的信息}ArCell,adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];〃adj[v][w]數(shù)組即v和w之間的權(quán)值typedefstruct{intnum;〃車(chē)輛的路線(xiàn)號(hào)intprice;〃每路車(chē)的票價(jià)intgap;〃每?jī)纱伟l(fā)車(chē)之間的時(shí)間間隔intspeed;〃車(chē)速intstopnum;〃每輛車(chē)經(jīng)過(guò)的車(chē)站的總數(shù)Stationinfopass[MAX_VERTEX_NUM];//每一路車(chē)經(jīng)過(guò)的站點(diǎn)的信息}BusInfo;〃車(chē)輛信息typedefstruct{charStaName;charLocation[32];intstopbusnum;Businfostopbus[MAX_BUS_NUM];}VertexType;//每個(gè)結(jié)點(diǎn)存放的信息，包括了站名，位置，經(jīng)過(guò)的車(chē)輛數(shù)以及經(jīng)過(guò)的該站點(diǎn)的所有的車(chē)輛的信息2)調(diào)整函數(shù)AdjustvoidAdjust(MGraph&G,VertexType*S){inti;for(i=0;i<MAX_VERTEX_NUM;i++)G.vexs[i].StaName=S[i].StaName;}將所有初始化的值與圖聯(lián)系起來(lái)，把初始化的點(diǎn)的名字傳給圖中各個(gè)節(jié)點(diǎn)的StaName。voidAdjust_2(Businfo*bus,MGraph&G){inti,j,t[8]={0,0,0,0,0,0,0,0},p;for(i=0;i<MAX_VERTEX_NUM;i++)for(j=0;j<MAX_BUS_NUM;j++)for(p=0;p<bus[j].stopnum;p++)if(G.vexs[i].StaName==bus[j].pass[p].StaName){G.vexs[i].stopbusnum++;G.vexs[i].stopbus[t[i]].num=bus[j].num;G.vexs[i].stopbus[t[i]].price=bus[j].price;G.vexs[i].stopbus[t[i]].gap=bus[j].gap;G.vexs[i].stopbus[t[i]].speed=bus[j].speed;t[i]++;}}將所有的初始化的點(diǎn)的信息以及bus的信息傳遞給圖，每個(gè)結(jié)點(diǎn)中記錄了經(jīng)過(guò)該站的所有的車(chē)輛的信息，bus[j].pass[p]是用來(lái)存放該車(chē)經(jīng)過(guò)的站的信

息。定義的整型數(shù)組t[8]是用來(lái)對(duì)每輛車(chē)經(jīng)過(guò)的站的個(gè)數(shù)進(jìn)行計(jì)數(shù)的。3)建立圖模型intLocateVex(MGraphG,charu){inti;for(i=0;i<Gvexnum;i++){if(u==Gvexs[i].StaName)returni;}if(i=G.vexnum){printf("Erroru!\n");return1;}return0;}LocateVex函數(shù)在下面建圖函數(shù)中調(diào)用的時(shí)候是用來(lái)找到v1，v2結(jié)點(diǎn)分別在G向量中的位置的。voidCreateMGraph(BusInfo*bus,VertexType*S,MGraph&G){voidAdjust(MGraph&G,VertexType*S);voidAdjust_1(BusInfo*bus,VertexType*S);voidAdjust_2(BusInfo*bus,MGraph&G);//申明要調(diào)用的函數(shù)Adjust(G,S);Adjust_2(bus,G);Adjust_1(bus,S);inti,j,t;G.vexnum=8;G.arcnum=11;charv1,v2,a[11][2]={{'A','B'},{'A','D'},{'A',F},{'B','C'},{'D','C'},{'D',E},{F,E},{'C','G'},{'F',G},{'E','H'},{'G',E}};intb[11]={8,5,6,3,2,10,7,4,5,15,20};//根據(jù)初始化的數(shù)據(jù)構(gòu)建弧的權(quán)值(時(shí)for(i=0;i<G.vexnum;i++)間)for(j=0;j<Gvexnum;j++)G.arcs[i][j].adj=INFINITY;//INFINITY宏定義的最大值表示距離for(t=0;t<11;t++){v1=a[t][0];v2=a[t][1];i=LocateVex(Gv1);j=LocateVex(Gv2);G.arcs[i][j].adj=b[t];//將v1，v2賦值為弧的兩端的結(jié)點(diǎn)//i表示v1v1=a[t][0];v2=a[t][1];i=LocateVex(Gv1);j=LocateVex(Gv2);G.arcs[i][j].adj=b[t];//j表示v2在G向量結(jié)點(diǎn)數(shù)組中的位置//將數(shù)組b中的時(shí)間值賦給i到j(luò)的弧上}return;}建立圖模型將所有的初始化的數(shù)據(jù)放到圖的每項(xiàng)中。4)test函數(shù)voidTest(BusInfo*bus,MGraphG){inti,j;for(i=0;i<MAX_BUS_NUM;i++){printf("路線(xiàn)％d票價(jià)％d間隔％d分鐘車(chē)速%dkm/h",bus[i].num,bus[i].price,bus[i].gap,bus[i].speed);printf("經(jīng)過(guò)的站為:")；for(j=0;j<bus[i].stopnum;j++)printf("%c%s”,bus[i].pass[j].StaName,bus[i].pass[j].Location);printf("\n");}for(i=0;i<MAX_VERTEX_NUM;i++){printf("站名％c坐標(biāo)％s\n”,S[i].StaName,S[i].Location);for(j=0;j<S[i].stopbusnum;j++){printf("?？科?chē)及相關(guān)信息：路線(xiàn)%d票價(jià)％d間隔%d分鐘車(chē)速％d千米每分”，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,Gvexs[i].stopbus[j].speed);printf("\n");}}}Test函數(shù)是用來(lái)測(cè)試建立圖之后，原來(lái)初始化的數(shù)據(jù)是否已經(jīng)成功的存放進(jìn)圖。Show_FLOYD函數(shù)voidShow_FLOYD(){Test(bus,G);〃先將圖線(xiàn)輸出便于后面的查看CreateMGraph(bus,S,G);〃建圖PrintMGraph(G);Test(bus,G);〃圖是用鄰接矩陣的方法來(lái)建的，所以用在inti,j,k,l,m,n;〃這里的PrintMGraph函數(shù)是用來(lái)輸出矩陣的for(i=0;i<Gvexnum;i++)G.arcs[i][i].adj=0;//ShortestPath_FLOYD()要求對(duì)角元素值為0printf("鄰接矩陣:\n");for(i=0;i<G.vexnum;i++)//直接有路徑的輸出時(shí)間，沒(méi)有的在輸出INFINITY{for(j=0;j<Gvexnum;j++)printf("%6d”,G.arcs[i][j]);printf("\n");}ShortestPath_FLOYD(G&p,&d);〃調(diào)用函數(shù)來(lái)找出按時(shí)間所有的的最短路徑printf("d矩陣:\n");for(i=0;i<Gvexnum;i++){for(j=0;j<G.vexnum;j++)〃用二維數(shù)組來(lái)輸出對(duì)應(yīng)的矩陣中的權(quán)值printf("%6d”,d[i][j]);printf("\n");for(i=0;i<Gvexnum;i++)for(j=0;j<Gvexnum;j++){if(d[i][j]!=100)一printf("%c至0%c的最短時(shí)間為%d分\n”,G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);}printf("p矩陣:\n");〃p矩陣用來(lái)存放路線(xiàn)信息從i到j(luò)的具體路線(xiàn)l=G.vexnum;for(i=0;i<Gvexnum;i++){for(j=0;j<Gvexnum;j++){if(i!=j){m=0;//占位空格for(k=0;k<G.vexnum;k++)if(p[i][j][k]=1)printf("%c”,G.vexs[k].StaName);elsem++;for(n=0;n<m;n++)〃輸出占位空格printf(-");〃如果兩個(gè)結(jié)點(diǎn)之間找不到可以直接通的路}//線(xiàn)則在相應(yīng)的位置上輸出空格}printf("\n");}printf("按回車(chē)鍵繼續(xù)");a=getchar();system("cls");〃輸出信息過(guò)多，清屏一次}用于輸出所有的兩個(gè)結(jié)點(diǎn)的時(shí)間信息以及從每個(gè)點(diǎn)到其他任意一個(gè)點(diǎn)的具體路線(xiàn)ShortestPath_FLOYD函數(shù)voidShortestPath_FLOYD(MGraphG,PathMatrix*P,DistancMatrix*D){//用Floyd算法求有向網(wǎng)G中各對(duì)頂點(diǎn)v和w之間的最短路徑P[v][w]及其//帶權(quán)長(zhǎng)度D[v][w]。若P[v][w][u]為T(mén)RUE,則u是從v到w當(dāng)前求得最短intu,v,w,i;for(v=0;v<G.vexnum;v++)//各對(duì)結(jié)點(diǎn)之間初始已知路徑及距離for(w=0;w<Gvexnum;w++){(*D)[v][w]=G.arcs[v][w].adj;//D矩陣用來(lái)存放每一條弧的權(quán)值即時(shí)間值for(u=0;u<G.vexnum;u++)(*P)[v][w][u]=FALSE;if((*D)[v][w]<INFINITY)//當(dāng)權(quán)值小于最大值時(shí)說(shuō)明從v到w有直接路徑{(*P)[v][w][v]=TRUE;//v,w之間有直接路徑就將(*P)[v][w][v]賦值為1(*P)[v][w][w]=TRUE;}}for(u=0;u<G.vexnum;u++)for(v=0;v<G.vexnum;v++)for(w=0;w<Gvexnum;w++)if((*D)[v][u]+(*D)[u][w]<(*D)[v][w])〃從v經(jīng)u到w的一條路徑更短{(*D)[v][w]=(*D)[v][u]+(*D)[u][w];for(i=0;i<G.vexnum;i++)(*P)[v][w][i]=(*P)[v][u][i]||(*P)[u][w][i];}}此函數(shù)是用來(lái)求出每個(gè)點(diǎn)到另外的任意一個(gè)點(diǎn)的按時(shí)間的最優(yōu)的路徑，對(duì)于有兩個(gè)結(jié)點(diǎn)相鄰但路徑的時(shí)間是否是最短進(jìn)行判斷并挑選出時(shí)間的最優(yōu)的路徑，下面的選擇函數(shù)則是在將這些路徑比較和挑選。Select_Time函數(shù)voidSelect_Time(){charv1,v2;inti,j,k,m,n=0,t=0,flag=0,loc1,loc2,num[MAX_BUS_NUM]={1,1,1,1,1,1};/*num數(shù)組用來(lái)做標(biāo)記用，已做過(guò)標(biāo)記為0，沒(méi)做夠標(biāo)記為1*/chara[MAX_VERTEX_NUM];/*a[]字符數(shù)組用來(lái)存放從v1到v2的最短路徑所經(jīng)過(guò)的都有的站點(diǎn)名字*/printf(-請(qǐng)輸入起始站點(diǎn)和目的點(diǎn)\n");scanf("%c%c",&v1,&v2);for(i=0;i<Gvexnum;i++){if(v1=G.vexs[i].StaName)〃找到與名字v1對(duì)應(yīng)的結(jié)點(diǎn){loc1=i;〃用來(lái)存放出發(fā)點(diǎn)v1在圖中的位置printf("站名％c坐標(biāo)％s\n",G.vexs[i].StaName,G.vexs[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){〃找出所有v2點(diǎn)停靠的車(chē)輛的信息printf("?？科?chē)及相關(guān)信息：路線(xiàn)％d票價(jià)％d間隔％d分鐘車(chē)速％d千米每分”，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf("\n經(jīng)過(guò)的站為:")；for(m=0;m<bus[j].stopnum;m++)printf("%c%s”,Gvexs[i].stopbus[j].pass[m].StaName,G.vexs[i].stopbus[j].pass[m].Location);〃將所有v2點(diǎn)停靠的車(chē)輛的信息輸出printf("\n");

}if(v2==G.vexs[i].StaName){loc2=i;〃用來(lái)存放出發(fā)點(diǎn)v2在圖中的位置printf("站名%c坐標(biāo)％s\n",S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){〃找出所有v2點(diǎn)?？康能?chē)輛的信息printf("?？科?chē)及相關(guān)信息：路線(xiàn)％d票價(jià)％d間隔％d分鐘車(chē)速％d千米每分”，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,Gvexs[i].stopbus[j].speed);printf("\n經(jīng)過(guò)的站為:")；for(m=0;m<bus[j].stopnum;m++)〃將所有v2點(diǎn)?？康能?chē)輛的信息輸出printf("\n");}printf("%c%s”,Gvexs[i].stopbus[j].pass[m].StaName,Gvexs[i].stopbus[j].pass[m].Location);}}printf("\n*****************結(jié)果****************\n\n");for(i=0;i<MAX_BUS_NUM;i++){for(j=0;j<bus[i].stopnum;j++)if(v1==bus[i].pass[j].StaName||v2==bus[i].pass[j].StaName){〃判斷在該車(chē)都經(jīng)過(guò)的站點(diǎn)中有沒(méi)有是v1或v2的t++;//用來(lái)標(biāo)記一條最短路徑中的v1，v2出現(xiàn)情況if(t==2)//〃將所有v2點(diǎn)?？康能?chē)輛的信息輸出printf("\n");}{printf("直達(dá)路線(xiàn)%d票價(jià)%d間隔%d分鐘車(chē)速%dkm/h?？浚站”，bus[i].num,bus[i].price,bus[i].gap,bus[i].speed,bus[i].stopnum);printf("\n經(jīng)過(guò)的站為:")；for(m=0;m<bus[i].stopnum;m++)printf("%c%s”,bus[i].pass[m].StaName,bus[i].pass[m].Location);printf("\n");t=0;flag=1;//此處的t=0是t=2的情況重置便于下個(gè)循環(huán)的實(shí)現(xiàn)}}t=0;//此處是將t=1是的情況重置用于下一個(gè)大循環(huán)的實(shí)現(xiàn)}i=LocateVex(Gv1);〃找出v1在圖中的位置j=LocateVex(Gv2);〃找出v2在圖中的位置if(d[i][j]!=INFINITY)//當(dāng)i，j之間有最短路徑時(shí)輸出下面信息printf("%c至0%c的最短時(shí)間為%d分\n”,G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);if(flag!=1){〃標(biāo)記flag當(dāng)為1時(shí)i和j直接有弧，有直接從i到j(luò)的車(chē)printf("兩站直接沒(méi)有車(chē)直達(dá)，可以選擇換乘!!\n");printf("經(jīng)過(guò)的站點(diǎn)")；for(t=0;tvG.vexnum;t++)if(p[i][j][t]=1)printf("%c",G.vexs[t].StaName);printf("\n");t=0;for(m=0;mv=Gvexnum;m++)if(p[i][j][m]=1)〃當(dāng)p[i][j][m]為1時(shí)說(shuō)明i,j之間有直接的路徑{a[t]=G.vexs[m].StaName;t++;}//將每個(gè)結(jié)點(diǎn)的名字存放到a[]里for(m=0;mvt-1;m++){loc1=LocateVex(Ga[m]);loc2=LocateVex(Ga[m+1]);//先定義連續(xù)的兩輛車(chē)for(i=0;ivG.vexs[loc1].stopbusnum;i++)for(j=0;jvGvexs[loc2].stopbusnum;j++)if(G.vexs[loc1].stopbus[i].num=G.vexs[loc2].stopbus[j].num){//判斷連續(xù)的兩個(gè)站是否有直接相連的一路車(chē)flag=m+1;〃如果有則記下m+1for(k=0;kvbus[i].stopnum;k++)if(G.vexs[loc1].stopbus[i].pass[k].StaName==a[flag])flag++;//如果經(jīng)過(guò)locl的車(chē)同時(shí)經(jīng)過(guò)下一個(gè)站個(gè)flag++if(num[G.vexs[loc1].stopbus[i].num]!=0){printf("乘坐％d路車(chē)在％。站上車(chē)在％。站下車(chē)\n",G.vexs[loc1].stopbus[i].num,a[m],a[flag-1]);num[G.vexs[loc1].stopbus[i].num]=0;/*表示已經(jīng)做過(guò)了這輛車(chē)，則標(biāo)記為0*/}}}}}根據(jù)輸入的站名來(lái)選擇時(shí)間上最優(yōu)的路線(xiàn)。Select_Money函數(shù)voidSelect_Money(){charv1,v2,ch;SelectsB[10];inti,j,k=0,m,n=0,t=0,flag=0,loc1,loc2,num[MAX_BUS_NUM],min=0;chara[MAX_VERTEX_NUM];/*a[]字符數(shù)組用來(lái)存放從v1到v2的最短路徑所經(jīng)過(guò)的都有的站點(diǎn)名字*/printf(-請(qǐng)輸入起始站點(diǎn)和目的點(diǎn)\n");scanf("%c%c",&v1,&v2);

printf("***************站點(diǎn)信息*************\n");for(i=0;i<Gvexnum;i++){if(v1==G.vexs[i].StaName){loc1=i;〃找出v1站點(diǎn)的位置printf("站名%c坐標(biāo)％s\n",S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf("?？科?chē)及相關(guān)信息：路線(xiàn)%d票價(jià)%d元間隔%d分鐘車(chē)速%d千米每分"，//輸出經(jīng)過(guò)該站點(diǎn)的所有的車(chē)的信息G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf("\n經(jīng)過(guò)的站為:")；for(m=0;m<bus[j].stopnum;m++)printf("%cm].Location);%s”,Gvexs[i].stopbus[j].pass[m].StaName,Gvexs[i].stopbus[j].pass[printf("\n");}}if(v2==G.vexs[i].StaName){loc2=i;〃找出v1站點(diǎn)的位置printf("站名%c坐標(biāo)％s\n",S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf("?？科?chē)及相關(guān)信息：路線(xiàn)%d票價(jià)%d元間隔%d分鐘車(chē)速%d千米每分"，//輸出多有經(jīng)過(guò)v2的車(chē)的信息G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,Gvexs[i].stopbus[j].speed);printf("\n經(jīng)過(guò)的站為:")；printf("%cm].Location);printf("%c%s”,Gvexs[i].stopbus[j].pass[m].StaName,Gvexs[i].stopbus[j].pass[m].Location);printf("\n");}}}printf("\n");printf("***************結(jié)果****************\n");for(i=0;i<MAX_BUS_NUM;i++)〃尋找最優(yōu)路徑{for(j=0;j<bus[i].stopnum;j++)if(v1==bus[i].pass[j].StaNamellv2==bus[i].pass[j].StaName)t++;〃標(biāo)記t,當(dāng)t為1是說(shuō)明條件只滿(mǎn)足了一個(gè)if(t==2)//當(dāng)t為2時(shí)說(shuō)明上述兩個(gè)條件都滿(mǎn)足{printf("直達(dá)路線(xiàn)％d票價(jià)％d元間隔％d分鐘車(chē)速%dkm/h?？浚站"，//t為2說(shuō)明兩個(gè)站都在這路車(chē)?yán)镎业搅薭us[i].num,bus[i].price,bus[i].gap,bus[i].speed,bus[i].stopnum);printf("\n經(jīng)過(guò)的站為:")；for(m=0;m<bus[i].stopnum;m++)printf("%c%s”,bus[i].pass[m].StaName,bus[i].pass[m].Location);printf("\n");t=0;flag=1;num[n]=i;n++;}}t=0;}if(flag==1)//flag標(biāo)記說(shuō)明v1，v2之間有直接通的一路車(chē){min=100;//將min最小先賦值為100用于下面的循環(huán)for(m=0;m<n;m++)if(bus[num[m]].price<min)min=m;printf("最省車(chē)費(fèi)%d\n",bus[num[min]].price);printf("選擇路線(xiàn)％d票價(jià)％d元間隔％d分鐘車(chē)速%dkm/h停靠％d站”，bus[min].num,bus[min].price,bus[min].gap,bus[min].speed,bus[min].stopnum);printf("\n經(jīng)過(guò)的站為:")；for(m=0;m<bus[min].stopnum;m++)printf("%c%s”,bus[min].pass[m].StaName,bus[min].pass[m].Location);printf("\n");}if(flag!=1){min=0;//將min賦值為0，由于兩站之間沒(méi)有直通車(chē)用于下面多i=LocateVex(Gv1);〃輛車(chē)的比較j=LocateVex(Gv2);printf("兩站直接沒(méi)有車(chē)直達(dá)，可以選擇換乘!!\n");printf("經(jīng)過(guò)的站點(diǎn)")；for(t=0;tvG.vexnum;t++)if(p[i][j][t]==1)printf("%c",G.vexs[t].StaName);printf("\n");t=0;for(m=0;mv=Gvexnum;m++)if(p[i][j][m]==1){a[t]=G.vexs[m].StaName;t++;}for(m=0;mvt-1;m++){loc1=LocateVex(Ga[m]);loc2=LocateVex(Ga[m+1]);//先定義連續(xù)的兩個(gè)站for(i=0;i<G.vexs[loc1].stopbusnum;i++)for(j=0;j<Gvexs[loc2].stopbusnum;j++)if(G.vexs[loc1].stopbus[i].num=G.vexs[loc2].stopbus[j].num){〃判斷連續(xù)的兩個(gè)站是否有是同一路車(chē)B[k].selectbusnum=G.vexs[loc1].stopbus[i].num;B[k].station1=a[m];B[k].station2=a[m+1];B[k].selectbusprice=Gvexs[loc1].stopbus[i].price;B[k].selectbusgap=Gvexs[loc1].stopbus[i].gap;k++;//將該路車(chē)的信息存放到Select結(jié)構(gòu)體數(shù)組B[]中}}flag=k;for(i=0;i<flag;i++)for(j=i+1;j<flag;j++)if(B[i].selectbusnum==B[j].selectbusnum&&B[i].station2==B[j].station1){B[j].selectbusnum=0;ch=B[i].station2;B[i].station2=B[j].station2;for(t=j+1;t<flag;t++)if(B[t].station1==ch)B[t].selectbusnum=0;}〃由于將每?jī)蓚€(gè)結(jié)點(diǎn)有弧的車(chē)全都存放進(jìn)了數(shù)組B[]中可能存/〃在著重復(fù)的項(xiàng)，此循環(huán)則是用于將重復(fù)的車(chē)輛信息合并for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)min=min+B[t].selectbusprice;/*先將搜有能連接來(lái)那個(gè)地的所有的車(chē)的價(jià)格全部相加*/for(t=0;t<flag;t++)if(B[t].selectbusnum!=0&&B[t].station1==B[t+1].station1){if(B[t].selectbusgap<B[t+1].selectbusgap){min=min-B[t+1].selectbusprice;/*兩兩比較，將費(fèi)用最少的找出，將高于最少的費(fèi)用的其他同一路的車(chē)的價(jià)格減掉則剩下了費(fèi)用最優(yōu)的的路線(xiàn)組合*/B[t+1].selectbusnum=0;}〃求出兩個(gè)站點(diǎn)的最少費(fèi)用else{min=min-B[t+1].selectbusprice;B[t].selectbusnum=0;}}for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)//輸出符合要求的信息printf("乘坐%d路車(chē)在%c站上車(chē)在%c站下車(chē)票價(jià)%d元間隔％d分鐘\n”,B[t].selectbusnum,B[t].station1,B[t].station2,B[t].selectbusprice,B[t].selectbusgap);printf("最省路費(fèi)為%d元\n",min);}printf("結(jié)束查詢(xún)!謝謝使用!!\n");}9)main函數(shù)voidmain(){inti;chara;Show_FLOYD();printf(-請(qǐng)選擇檢索內(nèi)容\n1去兩地時(shí)間最短路線(xiàn)查詢(xún)\n2去兩地路費(fèi)最省路線(xiàn)查\n3結(jié)束查詢(xún)\n");scanf("%d",&i);a=getchar();//吸收緩沖區(qū)里的回車(chē)符system("cls");〃由于界面顯示太多項(xiàng)，清屏一次switch(i){case1:printf("選擇1去兩地時(shí)間最短\n");Select_Time();break;case2:printf("選擇2去兩地路費(fèi)最省\n");Select_Money();break;case3:printf("結(jié)束查詢(xún)!謝謝使用!!\n");break;default:printf("輸入錯(cuò)誤!!\n");〃界面}}5、調(diào)試分析程序調(diào)試時(shí)，如果沒(méi)有根據(jù)提示正確輸入，界面上會(huì)出現(xiàn)提示出錯(cuò)的提示，可以到程序中找出錯(cuò)誤并進(jìn)行改正。6、測(cè)試結(jié)果

BCBCDBCDECDCDEDEBCDEFC&EFDEFEFBCGCCBCDHCPHDHEH，..按回車(chē)鍵進(jìn)入查詢(xún),■■進(jìn)入查詢(xún)界面根據(jù)需求查詢(xún):SE9!■）（1｛）（1｛）（1｛）（1｛）（釜竟釜竟~［者［先：|圣才令專(zhuān)?內(nèi)谷：）（）（）（廈）（）（）（■）（，）（3）C）C）C）C1＞去兩地爵間參盅豺查詢(xún)SE9!L去兩地蹌費(fèi)簧眷盛線(xiàn)查詢(xún)3＞緒來(lái)查宜請(qǐng)輸入極的選ffi：1提示是否需要把等待時(shí)間加在一起查詢(xún):兩站直掾沒(méi)有車(chē)著擺頂以選擇換乘?!經(jīng)過(guò)的塞京齡班選擇呈否要考慮等車(chē)的時(shí)間J是^否成功查詢(xún):cDEHcDEH在在在.5汆車(chē)車(chē)車(chē)fOnthLLLLUVc，rrn冒站站臂Escc4w郭在在在嗯-any的Is辱琨查3脂坐坐坐束g按價(jià)格進(jìn)行查詢(xún):線(xiàn)查詢(xún)

線(xiàn)查詢(xún)索詹r醬線(xiàn)查詢(xún)

線(xiàn)查詢(xún)索詹r醬1戒2選間費(fèi)￥=一一兩衲束伯

-$在.A攵輸請(qǐng)查詢(xún)成功:口n車(chē)中豐留昭1517、用戶(hù)使用說(shuō)明在用戶(hù)首次進(jìn)入查詢(xún)時(shí)就會(huì)出現(xiàn)提示，用戶(hù)可以根據(jù)具體的提示來(lái)進(jìn)行下一步的操作。

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)考核評(píng)估標(biāo)準(zhǔn)通過(guò)程序設(shè)計(jì)及答辯方式，并結(jié)合學(xué)生的動(dòng)手能力（編程及調(diào)試程序能力）、獨(dú)立分析解決問(wèn)題的能力、創(chuàng)新精神、總結(jié)報(bào)告、答辯水平、學(xué)習(xí)態(tài)度以及題目難易程度綜合考評(píng)，成績(jī)分優(yōu)、良、中、及格和不及格五等。課程設(shè)計(jì)的量化評(píng)分成績(jī)見(jiàn)表（1）《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)量化評(píng)分標(biāo)準(zhǔn)（每人一頁(yè)）學(xué)生姓名：趙杰學(xué)生學(xué)號(hào)08030334指標(biāo)最高分評(píng)分要素評(píng)分設(shè)計(jì)技術(shù)水平20程序運(yùn)行情況良好，結(jié)構(gòu)設(shè)計(jì)合理，算法說(shuō)明清晰，理論分析與計(jì)算正確，實(shí)驗(yàn)數(shù)據(jù)無(wú)誤，通用性和可擴(kuò)充性強(qiáng)實(shí)際動(dòng)手能力20獨(dú)立完成設(shè)計(jì)，能夠迅速準(zhǔn)確的進(jìn)行調(diào)試和糾錯(cuò)研究成果與專(zhuān)業(yè)知識(shí)10對(duì)研究的問(wèn)題能較深刻分析或者有獨(dú)到見(jiàn)解，很好地掌握了有關(guān)基礎(chǔ)理論與專(zhuān)業(yè)知識(shí)，總結(jié)報(bào)告認(rèn)識(shí)深刻寫(xiě)作與總結(jié)提煉能力10報(bào)告結(jié)構(gòu)嚴(yán)謹(jǐn)，邏輯嚴(yán)密，論述層次清晰，語(yǔ)言流暢，表達(dá)準(zhǔn)確，重點(diǎn)突出，文獻(xiàn)綜述10有較完善的文獻(xiàn)綜述，能夠正確查閱參考文獻(xiàn)資料規(guī)范化程度10提交的電子文檔及打印文檔的書(shū)寫(xiě)、存放完全符合規(guī)范化要求答辯情況10能簡(jiǎn)明扼要地闡述設(shè)計(jì)的主要內(nèi)容，能準(zhǔn)確流利地回答各種問(wèn)題學(xué)習(xí)態(tài)度10端正的學(xué)習(xí)態(tài)度及認(rèn)真刻苦程度等總分注意:本評(píng)分標(biāo)準(zhǔn)適用于數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)；總分滿(mǎn)分為100分，成績(jī)參考標(biāo)準(zhǔn)為：優(yōu)秀（100>XN90）；良好（90>XN80）；中等（80>XN70）；及格（70>XN60）；不及格（X<60）；發(fā)現(xiàn)有拷貝舞弊現(xiàn)象者，一律直接退回不作檢查，兩次舞弊者按不及格處理。每組學(xué)生至少要回答三個(gè)以上的問(wèn)題，有兩個(gè)以上問(wèn)題回答不清楚者，一律不及格。課程設(shè)計(jì)報(bào)告不交或不規(guī)范者一律不及格。《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)考核評(píng)估標(biāo)準(zhǔn)通過(guò)程序設(shè)計(jì)及答辯方式，并結(jié)合學(xué)生的動(dòng)手能力（編程及調(diào)試程序能力）、獨(dú)立分析解決問(wèn)題的能力、創(chuàng)新精神、總結(jié)報(bào)告、答辯水平、學(xué)習(xí)態(tài)度以及題目難易程度綜合考評(píng)，成績(jī)分優(yōu)、良、中、及格和不及格五等。課程設(shè)計(jì)的量化評(píng)分成績(jī)見(jiàn)表（1）《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)量化評(píng)分標(biāo)準(zhǔn)（每人一頁(yè)）學(xué)生姓名：朱陳立學(xué)生學(xué)號(hào)08030337指標(biāo)最高分評(píng)分要素評(píng)分設(shè)計(jì)技術(shù)水平20程序運(yùn)行情況良好，結(jié)構(gòu)設(shè)計(jì)合理，算法說(shuō)明清晰，理論分析與計(jì)算正確，實(shí)驗(yàn)數(shù)據(jù)無(wú)誤，通用性和可擴(kuò)充性強(qiáng)實(shí)際動(dòng)手能力20獨(dú)立完成設(shè)計(jì)，能夠迅速準(zhǔn)確的進(jìn)行調(diào)試和糾錯(cuò)研究成果與專(zhuān)業(yè)知識(shí)10對(duì)研究的問(wèn)題能較深刻分析或者有獨(dú)到見(jiàn)解，很好地掌握了有關(guān)基礎(chǔ)理論與專(zhuān)業(yè)知識(shí)，總結(jié)報(bào)告認(rèn)識(shí)深刻寫(xiě)作與總結(jié)提煉能力10報(bào)告結(jié)構(gòu)嚴(yán)謹(jǐn)，邏輯嚴(yán)密，論述層次清晰，語(yǔ)言流暢，表達(dá)準(zhǔn)確，重點(diǎn)突出，文獻(xiàn)綜述10有較完善的文獻(xiàn)綜述，能夠正確查閱參考文獻(xiàn)資料規(guī)范化程度10提交的電子文檔及打印文檔的書(shū)寫(xiě)、存放完全符合規(guī)范化要求答辯情況10能簡(jiǎn)明扼要地闡述設(shè)計(jì)的主要內(nèi)容，能準(zhǔn)確流利地回答各種問(wèn)題學(xué)習(xí)態(tài)度10端正的學(xué)習(xí)態(tài)度及認(rèn)真刻苦程度等總分注意:本評(píng)分標(biāo)準(zhǔn)適用于數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)；總分滿(mǎn)分為100分，成績(jī)參考標(biāo)準(zhǔn)為：優(yōu)秀（100>XN90）；良好（90>XN80）；中等（80>XN70）；及格（70>XN60）；不及格（X<60）；發(fā)現(xiàn)有拷貝舞弊現(xiàn)象者，一律直接退回不作檢查，兩次舞弊者按不及格處理。每組學(xué)生至少要回答三個(gè)以上的問(wèn)題，有兩個(gè)以上問(wèn)題回答不清楚者，一律不及格。課程設(shè)計(jì)報(bào)告不交或不規(guī)范者一律不及格。答辯問(wèn)題：1，優(yōu)化問(wèn)題是很重要的問(wèn)題，許多問(wèn)題比如數(shù)據(jù)挖掘問(wèn)題就可以看作一個(gè)優(yōu)化問(wèn)題，請(qǐng)你談?wù)剬?duì)優(yōu)化問(wèn)題的認(rèn)識(shí)？回答：數(shù)據(jù)挖掘，在人工智能領(lǐng)域，習(xí)慣上又稱(chēng)為數(shù)據(jù)庫(kù)中知識(shí)發(fā)現(xiàn)（KnowledgeDiscoveryinDatabase,KDD），也有人把數(shù)據(jù)挖掘視為數(shù)據(jù)庫(kù)中知識(shí)發(fā)現(xiàn)過(guò)程的一個(gè)基本步驟。在數(shù)據(jù)庫(kù)中根據(jù)大量的信息，尋找最優(yōu)的模型，完成優(yōu)化。通過(guò)優(yōu)化可以應(yīng)用到很多領(lǐng)域，從而增加效益。優(yōu)化問(wèn)題在現(xiàn)實(shí)生活中有許多應(yīng)用但基本思想是貪婪算法，即每一步都是最優(yōu)的，整體就是最優(yōu)的。例如笛杰斯特拉，普里母算法等。通過(guò)優(yōu)化，可以找到解決問(wèn)題的最優(yōu)方法。2,你用什么標(biāo)準(zhǔn)選擇公交線(xiàn)路上的優(yōu)化路徑？回答：在本程序中采用了時(shí)間和價(jià)格作為選擇標(biāo)準(zhǔn)來(lái)進(jìn)行查詢(xún)，由于時(shí)間是在每?jī)蓚€(gè)站點(diǎn)之間的，對(duì)應(yīng)圖中的就是每條弧的權(quán)值，利用Floyd算法可以求到每一組站點(diǎn)之間的最優(yōu)路徑。按價(jià)格算的話(huà)，乘一次車(chē)給一次錢(qián)，換乘時(shí)才需要另外加錢(qián)，所以不能用Floyd算法來(lái)求價(jià)格的最優(yōu)路徑，所以在每個(gè)結(jié)點(diǎn)里存放進(jìn)經(jīng)過(guò)的所有的車(chē)的信息包括價(jià)格，在挑選車(chē)的時(shí)候可以將價(jià)格來(lái)進(jìn)行比較挑選出最優(yōu)路徑。3,通過(guò)課程設(shè)計(jì)，你有那些收獲，你對(duì)認(rèn)為數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)該怎樣去做？回答：通過(guò)這次的課程設(shè)計(jì)，讓我們更多的了解了貪婪算法的思想，更多的了解了Floyd算法的運(yùn)用，在時(shí)間和價(jià)格最優(yōu)的路線(xiàn)的挑選中就是運(yùn)用了貪婪算法的思想，即每一步都占一點(diǎn)小的便宜，走最優(yōu)的路線(xiàn)，到最后就可以得到從出發(fā)點(diǎn)到目的地的最優(yōu)的路線(xiàn)了。做課程設(shè)計(jì)，首先要把自己的思想理清，確定自己的程序?qū)⒁獙?shí)現(xiàn)的是什么功能，再去找到理論依據(jù)，找到了理論依據(jù)后，就可以著手去寫(xiě)代碼了。先將實(shí)現(xiàn)功能的主要的程序?qū)懗鰜?lái)，再由主要的程序向更加優(yōu)化的方面考慮，去添加一些輔助的程序，最后調(diào)試時(shí)加以修改更正就可以了。#includestdio.hincludestring.hinclude〃stdlib.h〃include〃conio.h〃#defineTRUE1#defineFALSE0#include<limits.h>/*INT_MAX等*/defineINFINITY100defineMAX_VERTEX_NUM8defineMAX_BUS_NUM6typedefintPathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefintDistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefintInfoType;typedefintVRType;PathMatrixp;DistancMatrixd;typedefstruct{intselectbusnum;charstation1,station2;intselectbusprice,selectbusgap;}Selects;typedefstruct{charStaName;charLocation[128];}StationInfo;typedefstruct{VRTypeadj;InfoType*info;}ArCell,adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct(intnum;intprice;intgap;//間隔intspeed;intstopnum;StationInfopass[MAX_VERTEX_NUM];}BusInfo;typedefstruct(charStaName;charLocation[32];intstopbusnum;BusInfostopbus[MAX_BUS_NUM];}VertexType;VertexTypeS[MAX_VERTEX_NUM]={{'A',〃（11,11）〃},{'B',〃（22,33）〃},{'C',〃（12,23）〃},{'D',〃（24,45）〃},{'E',〃（41,57）〃},{'F',〃（78,34）〃},{'G',〃（32,56）〃},{'H',〃（86,64）〃}};typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];adjMatrixarcs;intvexnum,arcnum;}MGraph;MGraphG;BusInfobus[MAX_BUS_NUM]={{1,2,10,4,4,{{'A',〃（11,11）〃},{'B',〃（22,33）〃},{'C',〃（12,23）〃},{'G',〃（32,56）〃}}},{2,1,5,4,4,{{'A',〃（11,11）〃},{'C',〃（12,23）〃},{'D',〃（24,45）〃},{'H',〃（86,64）〃}}},{3,2,10,4,4,{{'A',〃(11,11)〃},{'D',〃(24,45)〃},{'E',〃(41,57)〃},{'H',〃(86,64)〃}}},{4,1,5,4,4,{{'A',〃(11,11)〃},{'E',〃(41,57)〃},{'F',〃(78,34)〃},{'G',〃(32,56)〃}}},{5,1,10,4,3,{{'A',〃(11,11)〃},{'C',〃(12,23)〃},{'E',〃(41,57)〃}}},{6,2,8,4,4,{{'A',〃(11,11)〃},{'E',〃(41,57)〃},{'F',〃(78,34)〃},{'H',〃(86,64)〃}}}}；voidTest(BusInfo*bus,MGraphG){inti,j;for(i=0;i<MAX_BUS_NUM;i++){printf(〃路線(xiàn)%d票價(jià)%d元間隔%d分鐘車(chē)速%dkm/h〃，bus[i].num,bus[i].price,bus[i].gap,bus[i].speed);printf(〃經(jīng)過(guò)的站為：〃)；for(j=0;j<bus[i].stopnum;j++)printf("%c%s〃，bus[i].pass[j].StaName,bus[i].pass[j].Location);printf(〃\n〃)；}for(i=0;i<MAX_VERTEX_NUM;i++){printf(〃站名％c坐標(biāo)%s\n〃,S[i].StaName,S[i].Location);for(j=0;j<S[i].stopbusnum;j++){printf(-?？科?chē)及相關(guān)信息：路線(xiàn)％d票價(jià)%d間隔%d分鐘車(chē)速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf(〃\n〃)；}}}intLocateVex(MGraphG,charu){inti;for(i=0;i<G.vexnum;i++){if(u==G.vexs[i].StaName)returni;}if(i==G.vexnum){printf("Erroru!\n");return1;}return0;}//////////////////////////////////////////////////voidCreateMGraph(BusInfo*bus,VertexType*S,MGraph&G){voidAdjust(MGraph&G,VertexType*S);voidAdjust_1(BusInfo*bus,VertexType*S);voidAdjust_2(BusInfo*bus,MGraph&G);Adjust(G,S);Adjust_2(bus,G);Adjust_1(bus,S);inti,j,t;G.vexnum=8;G.arcnum=14;charv1,v2,a[14][2]={{'A','B'},{'A','D'},{'A','C'},{'A','E'},{'B','C'},{'C','D'},{'D','E'},{'E','F'},{'C','G'},{'D','H'},{'E','H'},{'F','G'},{'C','E'}};for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[i][j].adj=INFINITY;for(t=0;t<11;t++){v1=a[t][0];v2=a[t][1];i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j].adj=b[t];}return;}voidPrintMGraph(MGraphG){inti,j;printf("OutputVertices:");for(i=0;i<MAX_VERTEX_NUM;i++)printf("%c",G.vexs[i].StaName);printf("\n");printf("OutputAdjMatrix:\n");for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)printf(〃%4d〃,G.arcs[i][j]);printf(〃\n〃)；}return;}voidAdjust(MGraph&G,VertexType*S){inti;for(i=0;i<MAX_VERTEX_NUM;i++)G.vexs[i].StaName=S[i].StaName;}voidAdjust_2(BusInfo*bus,MGraph&G){inti,j,m,t[8]={0,0,0,0,0,0,0,0},p;for(i=0;i<MAX_VERTEX_NUM;i++)G.vexs[i].stopbusnum=0;for(i=0;i<MAX_VERTEX_NUM;i++)for(j=0;j<MAX_BUS_NUM;j++)for(p=0;p<bus[j].stopnum;p++)if(G.vexs[i].StaName==bus[j].pass[p].StaName)G.vexs[i].stopbusnum++;G.vexs[i].stopbus[t[i]].num=bus[j].num;G.vexs[i].stopbus[t[i]].price=bus[j].price;G.vexs[i].stopbus[t[i]].gap=bus[j].gap;G.vexs[i].stopbus[t[i]].speed=bus[j].speed;for(m=0;m<bus[j].stopnum;m++){G.vexs[i].stopbus[t[i]].pass[m].StaName=bus[j].pass[m].StaName;strcpy(G.vexs[i].stopbus[t[i]].pass[m].Location,bus[j].pass[m].Location);}t[i]++;}}voidAdjust_1(BusInfo*bus,VertexType*S)inti,j,t[8]={0,0,0,0,0,0,0,0},p,m;for(i=0;i<MAX_VERTEX_NUM;i++)S[i].stopbusnum=0;for(i=0;i<MAX_VERTEX_NUM;i++)for(j=0;j<MAX_BUS_NUM;j++)for(p=0;p<bus[j].stopnum;p++)if(S[i].StaName==bus[j].pass[p].StaName){S[i].stopbusnum++;S[i].stopbus[t[i]].num=bus[j].num;S[i].stopbus[t[i]].price=bus[j].price;S[i].stopbus[t[i]].gap=bus[j].gap;S[i].stopbus[t[i]].speed=bus[j].speed;for(m=0;m<bus[j].stopnum;m++){S[i].stopbus[t[i]].pass[m].StaName=bus[j].pass[m].StaName;strcpy(S[i].stopbus[t[i]].pass[m].Location,bus[j].pass[m[.Location);t[i]++;}}voidShortestPath_FLOYD(MGraphG,PathMatrix*P,DistancMatrix*D){/*用Floyd算法求有向網(wǎng)G中各對(duì)頂點(diǎn)v和w之間的最短路徑P[v][w]及其*//*帶權(quán)長(zhǎng)度D[v][w]。若P[v][w][u]為T(mén)RUE，則u是從v到w當(dāng)前求得最短*/intu,v,w,i;for(v=0;v<G.vexnum;v++)/*各對(duì)結(jié)點(diǎn)之間初始已知路徑及距離*/for(w=0;w<G.vexnum;w++){(*D)[v][w]=G.arcs[v][w].adj;for(u=0;u<G.vexnum;u++)(*P)[v][w][u]=FALSE;if((*D)[v][w]<INFINITY)/*從v到w有直接路徑*/(*P)[v][w][v]=TRUE;(*P)[v][w][w]=TRUE;}}for(u=0;u<G.vexnum;u++)for(v=0;v<G.vexnum;v++)for(w=0;w<G.vexnum;w++)if((*D)[v][u]+(*D)[u][w]<(*D)[v][w])/*從v經(jīng)u到w的一條路徑更短*/{(*D)[v][w]=(*D)[v][u]+(*D)[u][w];for(i=0;i<G.vexnum;i++)(*P)[v][w][i]=(*P)[v][u][i]||(*P)[u][w][i];}}voidShow_FLOYD(){//Test(bus,G);CreateMGraph(bus,S,G);PrintMGraph(G);Test(bus,G);inti,j,k,l,m,n;chara;for(i=0;i<G.vexnum;i++)G.arcs[i][i].adj=0;//ShortestPath_FLOYD()要求對(duì)角元素值為0printf("鄰接矩陣:\n〃)；for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)printf(〃%6d〃,G.arcs[i][j]);printf(〃\n〃)；}ShortestPath_FLOYD(G,&p,&d);printf(〃d矩陣:\n〃)；for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)printf(〃％6d〃，d[i][j]);printf(〃\n〃)；for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++){if(d[i][j]!=100)printf("%c到%c的最短時(shí)間為％d分\n〃，G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);}printf(〃p矩陣:\n〃)；l=G.vexnum;for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){if(i!=j){m=0;//占位空格for(k=0;k<G.vexnum;k++)if(p[i][j][k]==1)printf(〃％c〃,G.vexs[k].StaName);elsem++;for(n=0;n<m;n++)//輸出占位空格printf("");}printf(〃\n〃)；}printf（〃按回車(chē)鍵進(jìn)入查詢(xún)\n\n〃）；a=getchar();system(〃cls〃)；}/////////////////////////////////////////////////////////////////voidSelect_Time(){charv1,v2,ch;SelectsB[10];inti,j,k=0,m,n=0,t=0,flag=0,loc1,loc2,num[MAX_BUS_NUM]={1,1,1,1,1,1};chara[MAX_VERTEX_NUM];printf(〃請(qǐng)輸入起始站點(diǎn)和目的點(diǎn)\n〃)；scanf(〃％c%c〃，&v1,&v2);printf(〃***************站點(diǎn)信息*************\n〃)；for(i=0;i<G.vexnum;i++){if(v1==G.vexs[i].StaName){loc1=i;printf("站名％c坐標(biāo)％s\n〃,S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf("停靠汽車(chē)及相關(guān)信息：路線(xiàn)％d票價(jià)%d元間隔%d分鐘車(chē)速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf(〃\n經(jīng)過(guò)的站為：〃)；for(m=0;m<bus[j].stopnum;m++)printf(〃%c%s〃，G.vexs[i].stopbus[j].pass[m].StaName,G.vexs[i].stopbus[j].pass[m].Location);}}if(v2==G.vexs[i].StaName){loc2=i;printf(〃站名％c坐標(biāo)％s\n〃,S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf(〃停靠汽車(chē)及相關(guān)信息：路線(xiàn)％d票價(jià)%d元間隔%d分鐘車(chē)速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf(〃\n經(jīng)過(guò)的站為：〃)；for(m=0;m<bus[j].stopnum;m++)printf(〃%c%s〃，G.vexs[i].stopbus[j].pass[m].StaName,G.vexs[i].stopbus[j].pass[m].Location);}ch=getchar();system(〃cls〃)；printf(〃***************結(jié)果****************\n〃)；for(i=0;i<MAX_BUS_NUM;i++){for(j=0;j<bus[i].stopnum;j++)if(v1==bus[i].pass[j].StaName||v2==bus[i].pass[j].StaName){t++;if(t==2){printf("直達(dá)路線(xiàn)％d票價(jià)％d元間隔％d分鐘車(chē)速%dkm/h?？?d站〃，bus[i].num,bus[i].price,bus[i].gap,bus[i].speed,bus[i].stopnum);printf("\n經(jīng)過(guò)的站為：")；for(m=0;m<bus[i].stopnum;m++)printf("%c%s〃，bus[i].pass[m].StaName,bus[i].pass[m].Location);printf(〃\n〃)；t=0;flag=1;}}t=0;}i=LocateVex(G,v1);j=LocateVex(G,v2);//if(d[i][j]!=INFINITY)//printf("%c到%c的最短時(shí)間為％d分\n〃，G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);if(flag!=1){printf("兩站直接沒(méi)有車(chē)直達(dá),可以選擇換乘??！\n〃)；printf("經(jīng)過(guò)的站點(diǎn)")；for(t=0;t<G.vexnum;t++)if(p[i][j][t]==1)printf(〃％c〃,G.vexs[t].StaName);printf(〃\n〃)；t=0;for(m=0;m<=G.vexnum;m++)if(p[i][j][m]==1){a[t]=G.vexs[m].StaName;t++;}for(m=0;m<t-1;m++){loci二LocateVex(G,a[m]);loc2二LocateVex(G,a[m+1]);for(i=0;i<G.vexs[loc1].stopbusnum;i++)for(j=0;j<G.vexs[loc2].stopbusnum;j++)if(G.vexs[loc1].stopbus[i].num==G.vexs[loc2].stopbus[j].num){B[k].selectbusnum二G.vexs[loc1].stopbus[i].num;B[k].station1=a[m];B[k].station2=a[m+1];B[k].selectbusprice二G.vexs[loc1].stopbus[i].price;B[k].selectbusgap二G.vexs[loc1].stopbus[i].gap;k++;}flag=k;for(i=0;i<flag;i++)for(j=i+1;j<flag;j++)if(B[i].selectbusnum==B[j].selectbusnum&&B[i].station2==B[j].stationl){B[j].selectbusnum=0;ch=B[i].station2;B[i].station2=B[j].station2;for(t=j+1;t<flag;t++)if(B[t].station1==ch)B[t].selectbusnum=0;}}printf("選擇是否要考慮等車(chē)的時(shí)間\n1/是2/否\n〃);scanf(〃%d〃,&m);ch=getchar();system(〃cls〃)；if(m==1){i=LocateVex(G,v1);j=LocateVex(G,v2);for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)d[i][j]=d[i][j]+B[t].selectbusgap;for(t=0;t<flag;t++)if(B[t].selectbusnum!=0&&B[t].station1==B[t+1].station1)if(B[t].selectbusgap<B[t+1].selectbusgap){d[i][j]=d[i][j]-B[t+1].selectbusgap;B[t+1].selectbusnum=0;}else{d[i][j]=d[i][j]-B[t].selectbusgap;B[t].selectbusnum=0;}printf("%c到%c的最短時(shí)間為％d分\n〃，G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)printf("乘坐％d路車(chē)在％c站上車(chē)在％c站下車(chē)票價(jià)%d元間隔%d分鐘\n”,B[t].selectbusnum,B[t].station1,B[t].station2,B[t].selectbusprice,B[t].selectbusgap);}if(m==2){i=LocateVex(G,v1);j=LocateVex(G,v2);if(d[i][j]!=INFINITY)printf("%c到%c的最短時(shí)間為％d分\n〃，G.vexs[i].StaName,G.vexs[j].StaName,d[i][j]);for(t=0;t<flag;t++)if(B[t].selectbusnum!=0)printf("乘坐％d路車(chē)在％c站上車(chē)在％c站下車(chē)票價(jià)%d元間隔%d分鐘\n”,B[t].selectbusnum,B[t].station1,B[t].station2,B[t].selectbusprice,B[t].selectbusgap);}printf（"結(jié)束查詢(xún)!謝謝使用!!\n"）;}////////////////////////////////////////////////////////////////////////////////voidSelect_Money(){charv1,v2,ch;SelectsB[10];inti,j,k=0,m,n=0,t=0,flag=0,loc1,loc2,num[MAX_BUS_NUM],min=0;chara[MAX_VERTEX_NUM];printf("請(qǐng)輸入起始站點(diǎn)和目的點(diǎn)\n〃)；scanf(〃％c%c〃，&v1,&v2);printf(〃***************站點(diǎn)信息*************\n〃)；for(i=0;i<G.vexnum;i++){if(v1==G.vexs[i].StaName){loc1=i;printf("站名％c坐標(biāo)％s\n〃,S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++)printf("?？科?chē)及相關(guān)信息：路線(xiàn)％d票價(jià)%d元間隔%d分鐘車(chē)速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i].stopbus[j].price,G.vexs[i].stopbus[j].gap,G.vexs[i].stopbus[j].speed);printf(〃\n經(jīng)過(guò)的站為：〃)；for(m=0;m<bus[j].stopnum;m++)printf(〃%c%s〃，G.vexs[i].stopbus[j].pass[m].StaName,G.vexs[i].stopbus[j].pass[m].Location);printf(〃\n〃)；}}if(v2==G.vexs[i].StaName){loc2=i;printf(〃站名％c坐標(biāo)％s\n〃,S[i].StaName,S[i].Location);for(j=0;j<G.vexs[i].stopbusnum;j++){printf("?？科?chē)及相關(guān)信息：路線(xiàn)％d票價(jià)%d元間隔%d分鐘車(chē)速%d千米每分〃，G.vexs[i].stopbus[j].num,G.vexs[i]