2數(shù)據(jù)結(jié)構(gòu)-全國(guó)交通咨詢(xún)模擬系統(tǒng)實(shí)驗(yàn)報(bào)告

./全國(guó)交通咨詢(xún)模擬一、設(shè)計(jì)目的掌握線(xiàn)性表、棧、圖結(jié)構(gòu)和對(duì)文件的操作,學(xué)習(xí)屏幕編輯和菜單技術(shù),掌握用最短路徑與其搜索算法編制較綜合性的程序,能用圖的鄰接存儲(chǔ)結(jié)構(gòu)求解最優(yōu)路線(xiàn)問(wèn)題,解決有關(guān)實(shí)際問(wèn)題。得到軟件設(shè)計(jì)技能的訓(xùn)練。二、問(wèn)題描述交通咨詢(xún)模擬。根據(jù)旅客的不同需要,要考慮到旅客希望在旅途中的時(shí)間盡可能短、希望旅費(fèi)盡可能省等的要求。三、基本要求1、對(duì)城市信息<城市名、城市間的里程>進(jìn)行編輯：具備添加、修改、刪除功能；2、對(duì)城市間的交通工具：火車(chē)。對(duì)列車(chē)時(shí)刻表進(jìn)行編輯：里程、和列車(chē)班次的添加、修改、刪除；3、提供兩種最優(yōu)決策：最快到達(dá)或最省錢(qián)到達(dá)。全程只考慮一種交通工具,可以不考慮回程；4、咨詢(xún)以用戶(hù)和計(jì)算機(jī)對(duì)話(huà)方式進(jìn)行,要注意人機(jī)交互的屏幕界面。由用戶(hù)選擇最優(yōu)決策原則和交通工具,輸入起始站、終點(diǎn)站、出發(fā)時(shí)間,輸出信息：最快需要多長(zhǎng)時(shí)間才能到達(dá)與旅費(fèi),或者最少需要多少旅費(fèi)才能到達(dá)與時(shí)間,并詳細(xì)說(shuō)明依次于何時(shí)何地乘坐哪一趟列車(chē)何時(shí)到達(dá)何地。四、具體實(shí)現(xiàn)1、思路<1>數(shù)據(jù)存儲(chǔ)。城市信息<城市名、代碼>、交通信息<城市間的里程、各航班和列車(chē)時(shí)刻>存儲(chǔ)于磁盤(pán)文件。在實(shí)驗(yàn)中本想用文本儲(chǔ)存數(shù)據(jù),但操作不熟悉,而是改用圖的鄰接矩陣儲(chǔ)存原始信息,而后用數(shù)組進(jìn)行添加刪改<2>數(shù)據(jù)的邏輯結(jié)構(gòu)。根據(jù)設(shè)計(jì)任務(wù)的描述,其城市之間的旅游交通問(wèn)題是典型的圖結(jié)構(gòu),可看作為無(wú)向圖,圖的頂點(diǎn)是城市,邊是城市之間所耗費(fèi)的時(shí)間〔要包括中轉(zhuǎn)站的時(shí)間〕或旅費(fèi)。<3>數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。采用鄰接表和鄰接矩陣都可作為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),這里建議采用鄰接矩陣作為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。<4>用不同的功能模塊對(duì)城市信息和交通信息進(jìn)行編輯。添加、修改、刪除功能可用菜單方式或命令提示方式。只要能方便的對(duì)城市信息和交通信息進(jìn)行管理即可,但要注意人機(jī)界面,具體實(shí)現(xiàn)由學(xué)生自行設(shè)計(jì),也可參考有關(guān)程序<屆時(shí)在網(wǎng)上提供>。這些工作有不小的工作量。<5>最優(yōu)決策功能模塊①讀入城市信息和交通信息,用鄰接表生成含權(quán)網(wǎng)絡(luò),表頭數(shù)組中的元素存放城市名與對(duì)方城市到達(dá)該元素所代表城市的所有信息；表頭數(shù)組中的元素所對(duì)應(yīng)的單鏈表存放與該元素所代表的城市有交通聯(lián)系的城市<代碼、里程、列車(chē)車(chē)次>。②根據(jù)具體最優(yōu)決策的要求,用floyd算法求出出發(fā)城市到其它各城市的最優(yōu)值<最短時(shí)間或最小的費(fèi)用>,搜索過(guò)程中所經(jīng)過(guò)城市的局部最優(yōu)信息都保存在鄰接表的表頭數(shù)組中。其目的城市所代表的元素中就保存了所需的最優(yōu)決策結(jié)果。其相應(yīng)的初始值可為∞,并在表頭數(shù)組對(duì)應(yīng)的城市元素中保存響應(yīng)的信息。③主程序可以有系統(tǒng)界面、菜單；也可用命令提示方式；選擇功能模塊執(zhí)行,要求在程序運(yùn)行過(guò)程中可以反復(fù)操作。2、數(shù)據(jù)結(jié)構(gòu)本程序運(yùn)用了關(guān)于圖這種數(shù)據(jù)結(jié)構(gòu)。他的抽象數(shù)據(jù)類(lèi)型定義如下：typedefstructunDiGraph{ intnumVerts;//結(jié)點(diǎn) costAdjcost;//鄰接矩陣}unDiGraph,*UNG;基本操作：unDiGraph*CreateCostG<>操作結(jié)果：構(gòu)造帶權(quán)<費(fèi)用>圖。unDiGraph*CreateTimeG<>操作結(jié)果：構(gòu)造帶權(quán)〔時(shí)間〕圖。構(gòu)造飛機(jī)帶權(quán)<費(fèi)用>圖。PathMat*Floyed<unDiGraph*D>操作結(jié)果：Floyed函數(shù)求任意兩點(diǎn)的最短路徑。3、算法思想圖1.火車(chē)路程表7047046513491579138523688125112553XXXXXXXXXXXX圖城市之間火車(chē)行駛表并利用Floyed函數(shù)求帶權(quán)圖兩點(diǎn)之間的最短路徑。通過(guò)對(duì)帶權(quán)費(fèi)用圖和帶權(quán)時(shí)間圖求最短路徑,就可以最短道從一城市到另一城市之間最省時(shí)間和最省費(fèi)用的走法。為了簡(jiǎn)潔直觀(guān),本設(shè)計(jì)對(duì)課本內(nèi)的交通網(wǎng)進(jìn)行了簡(jiǎn)化,原來(lái)的25個(gè)城市縮減為13個(gè)。但是基本實(shí)現(xiàn)了設(shè)計(jì)的目的。滿(mǎn)足了基本要求。4、程序模塊程序是用dos版做的界面。主界面包括1.選擇火車(chē)最短時(shí)間路線(xiàn)2.選擇火車(chē)最節(jié)約費(fèi)用路線(xiàn)3.選擇坐飛機(jī)4.管理員程序確5.退出本程序程序的模塊為#include<windows.h>#include<stdio.h>#include<crtdbg.h>#include<string.h>#include<iostream.h>#include<malloc.h>#defineINF10000//定義一個(gè)最大數(shù)定為無(wú)窮值#defineMAX7staticintcnumber=7;staticintk=0;staticintv=0,z=0;//定義靜態(tài)變量typedefstructzhu//定義結(jié)構(gòu)體zhu{ intccost;//定義結(jié)構(gòu)變量 intctime;}zhu;zhum[20],x[20],n[20];//定義數(shù)組為structzhu類(lèi)型數(shù)組,且三個(gè)數(shù)組分別儲(chǔ)存添加后的數(shù)據(jù),且表示花費(fèi)m,起點(diǎn)n,和終點(diǎn)xtypedefintcostAdj[MAX+1][MAX+1];//定義圖的鄰接矩陣,并從1開(kāi)始intPath[MAX+1][MAX+1];//路程矩陣,表示經(jīng)過(guò)存放的點(diǎn)ktypedefstructunDiGraph{ intnumV;//結(jié)點(diǎn) costAdjcost;//鄰接矩陣}unDiGraph,*UNG;typedefstructcedit{ chara[10];}cedit;ceditadd[10];costAdjB,L;//功能一輸出相應(yīng)的城市信息intpr<inti,intj>//pr函數(shù)表輸出功能{ inth=0; if<j==0> { h=i; } elseif<j==1> { cin>>add[i].a; } switch<h>{ case<0>:cout<<""; break; case<1>:cout<<"XX"; break; case<2>:cout<<"XX";break;case<3>:cout<<"XX"; break;case<4>:cout<<"XX"; break;case<5>:cout<<"XX"; break;case<6>:cout<<"XX"; break;case<7>:cout<<""; break; } return1;}voidpri<>//聲明pri函數(shù),即利用pr函數(shù)輸出代碼為i的城市信息{ inti; cout<<"城市以與其代碼"<<endl; cout<<"**************************************"<<endl; for<i=1;i<=cnumber;i++> { cout<<i<<"."; pr<i,0>; } cout<<"****************************************"<<endl;}//構(gòu)造CostG圖,表示其費(fèi)用unDiGraph*CreateCostG<into>//火車(chē)的花費(fèi)的存貯和編輯功能{ unDiGraph*G; inti; intj;//定義的i,j做循環(huán)變量 inta=0,b=0,f=1,h=1;//f變量初始為1,h初始值為1,a=0,b=0臨時(shí)表示開(kāi)始城市代碼以與目的城市代碼if<!<G=<unDiGraph*>malloc<sizeof<unDiGraph>>>>//為G圖分配存儲(chǔ)空間。 { return<NULL>; }for<i=1;i<=cnumber;i++> { for<j=1;j<=cnumber;j++> { G->cost[i][j]=INF;//初始化矩陣cost每一項(xiàng),使其無(wú)窮大 } }G->numV=cnumber;G->cost[1][6]=G->cost[6][1]=90;G->cost[1][2]=G->cost[2][1]=84;G->cost[2][3]=G->cost[3][2]=51;G->cost[2][5]=G->cost[5][2]=67;G->cost[3][4]=G->cost[4][3]=53;G->cost[4][5]=G->cost[5][4]=40;G->cost[4][7]=G->cost[7][4]=88;G->cost[5][6]=G->cost[6][5]=90;G->cost[5][7]=G->cost[7][5]=67;G->cost[6][7]=G->cost[7][6]=60;if<o> { while<h==1>//h初始值為1 { v=v+1;//V為全局靜態(tài)變量,初始值為0,v表示編輯的火車(chē)花費(fèi)的組數(shù),三個(gè)編輯數(shù)組中的存放代碼 pri<>; cout<<"火車(chē)花費(fèi)編輯"<<endl; cout<<"請(qǐng)輸入開(kāi)始城市的代碼"<<endl; cin>>a; cout<<"請(qǐng)輸入目的城市的代碼"<<endl; cin>>b; cout<<"請(qǐng)輸入你的兩地花費(fèi)"<<endl; cin>>m[v].ccost; n[v].ccost=a; x[v].ccost=b; cout<<"請(qǐng)選擇"<<endl; cout<<"*********************************************************"<<endl; cout<<"1：繼續(xù)更改城市費(fèi)用"<<endl; cout<<"0:返回上一級(jí)菜單"<<endl; cout<<"*********************************************************"<<endl; cin>>h; switch<h>{ case1: h=1; break; case0: h=0; break; default:{ cout<<"選擇出錯(cuò)"<<endl; } } } }f=v+1;//初始定義變量f為1,全局變量v為0,即1=0+1while<v++>//v++代表的意思 { G->cost[n[v].ccost][x[v].ccost]=m[v].ccost; }v=f;return<G>;}//構(gòu)造TimeG圖,表示其花費(fèi)時(shí)間unDiGraph*CreateTimeG<into>//火車(chē)的時(shí)間的存貯和編輯功能{ unDiGraph*G; inti,j;//循環(huán)變量 inta=0,b=0,f,h=1;//a,b表增加城市的代碼 if<!<G=<unDiGraph*>malloc<sizeof<unDiGraph>>>>//為G分配存儲(chǔ)空間。 { return<NULL>; } for<i=1;i<=cnumber+1;i++> { for<j=1;j<=cnumber+1;j++> { G->cost[i][j]=INF;//初始化使G->cost[i][j]為無(wú)窮。 } } G->numV=cnumber;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[2][5]=G->cost[5][2]=3; G->cost[3][4]=G->cost[4][3]=5; G->cost[4][5]=G->cost[5][4]=4; G->cost[4][7]=G->cost[7][5]=6; G->cost[5][6]=G->cost[6][5]=9; G->cost[5][7]=G->cost[7][5]=6; G->cost[6][7]=G->cost[7][6]=6;if<o> { while<h==1> { z=z+1;//全局靜態(tài)變量,初始值為0.即1=0+1 pri<>; cout<<"火車(chē)時(shí)間編輯"<<endl; cout<<"請(qǐng)輸入開(kāi)始城市的代碼"<<endl; cin>>a; cout<<"請(qǐng)輸入結(jié)尾城市的代碼"<<endl; cin>>b; cout<<"請(qǐng)輸入你的兩地時(shí)間"<<endl; cin>>m[z].ctime; n[z].ctime=a; x[z].ctime=b; cout<<"請(qǐng)選擇"<<endl; cout<<"*********************************************************"<<endl; cout<<"1：繼續(xù)更改城市時(shí)間"<<endl; cout<<"0:返回上一級(jí)菜單"<<endl; cout<<"*********************************************************"<<endl; cin>>h; switch<h>{ case1: h=1; break; case0: h=0; break; default:{ cout<<"選擇出錯(cuò)"<<endl; } } }}f=z+1;//全局靜態(tài)變量z,初始值為0 while<z++> { G->cost[n[z].ctime][x[z].ctime]=m[z].ctime; }z=f;return<G>;}//Floyed函數(shù)求任意兩點(diǎn)的最短路徑：voidFloyed<unDiGraph*D,unDiGraph*M>//圖DM{ inti,j,k,n;//i,j為循環(huán)變量,k表中間節(jié)點(diǎn)的變量 costAdjA,C;//AC為圖,臨時(shí)表示兩種最佳路線(xiàn)組成的矩陣,定義costAdjBL n=cnumber;for<i=1;i<=n;i++> { for<j=1;j<=n;j++> { A[i][j]=D->cost[i][j];//初始化矩陣A,C。 C[i][j]=M->cost[i][j]; Path[i][j]=-1; //初始化權(quán)矩陣p } } for<k=1;k<=n;k++>//k為逐步加入的中間結(jié)點(diǎn) { for<i=1;i<=n;i++>//i代表矩陣A中行號(hào) { for<j=1;j<=n;j++> { if<A[i][k]+A[k][j]<A[i][j]> { A[i][j]=A[i][k]+A[k][j]; C[i][j]=C[i][k]+C[k][j]; Path[i][j]=k;//若i經(jīng)過(guò)k到j(luò)比i到j(luò)小,則選擇經(jīng)過(guò)K個(gè)中間點(diǎn)之后,i,j兩點(diǎn)的最佳路徑。 B[i][j]=A[i][j];//構(gòu)造AC兩個(gè)任意節(jié)點(diǎn)上的最優(yōu)路徑所建造的矩陣,并分別賦給BL代表時(shí)間與花費(fèi) L[i][j]=C[i][j];} else { B[i][j]=A[i][j]; L[i][j]=C[i][j]; } } } }//endfor循環(huán) cout<<"\n最短路徑為:"<<endl;}///end-Floyed//為了求從i到j(luò)的最短路徑,只需要調(diào)用如下的過(guò)程：voidprn_pass<inti,intj>{ if<Path[i][j]!=-1> { prn_pass<i,Path[i][j]>;//輸出最短路徑經(jīng)過(guò)的所有點(diǎn)個(gè)數(shù)k pr<Path[i][j],0>; }}//求最少時(shí)間路徑。voidtime<>{ intBcity,Ecity;//起始成市和終點(diǎn)城市 intl,h=1;//定義變量lhdo{ pri<>;//輸出城市列表與相應(yīng)代碼。 cout<<"請(qǐng)輸入起始城市和目的城市的代碼,中間以空格隔開(kāi)"<<endl;cin>>Bcity; cin>>Ecity;//輸入起始城市和終點(diǎn)城市的代碼。 if<!<<0<Bcity&&Bcity<cnumber+1>&&<0<Ecity&&Ecity<cnumber+1>&&Bcity!=Ecity>> { cout<<"\n出錯(cuò)啦!!!輸入城市請(qǐng)?jiān)?-7之間,且兩城市代碼不能相等!!"<<endl; } Floyed<CreateTimeG<0>,CreateCostG<0>>;//調(diào)用Floyed函數(shù)。pr<Bcity,0>;//顯示起始城市。prn_pass<Bcity,Ecity>;//調(diào)用prn_pass函數(shù),顯示最短路徑經(jīng)過(guò)的城市。pr<Ecity,0>;//顯示終點(diǎn)城市。if<B[Bcity][Ecity]>8000||L[Bcity][Ecity]>8000> { cout<<"兩地間還沒(méi)有線(xiàn)路通過(guò)"<<endl; } else { cout<<"火車(chē)花的時(shí)間是"<<B[Bcity][Ecity]<<"小時(shí)"<<endl; } cout<<"輸入0.返回主菜單"<<endl;scanf<"%d",&l>;//h=l;}while<h==1>;}//求最少花費(fèi)路徑。voidmoney<>{ intBcity,Ecity;//起始成市和終點(diǎn)城市charl,h=1;do{ pri<>;//輸出城市列表與相應(yīng)代碼。 cout<<"請(qǐng)輸入起始城市和目的城市的代碼,中間以空格隔開(kāi)"<<endl;cin>>Bcity; cin>>Ecity;//輸入起始城市和終點(diǎn)城市的代碼。 if<!<<0<Bcity&&Bcity<cnumber+1>&&<0<Ecity&&Ecity<cnumber+1>&&Bcity!=Ecity>> { cout<<"\n出錯(cuò)啦!!!輸入城市請(qǐng)?jiān)?-7之間,且兩城市代碼不能相等!!"<<endl;//輸入出錯(cuò) } Floyed<CreateCostG<0>,CreateTimeG<0>>;//調(diào)用Floyed函數(shù)。 pr<Bcity,0>;//顯示起始城市。 prn_pass<Bcity,Ecity>;//調(diào)用prn_pass函數(shù),顯示最短路徑經(jīng)過(guò)的城市。 pr<Ecity,0>;//顯示終點(diǎn)城市。 if<L[Bcity][Ecity]>8000||B[Bcity][Ecity]>8000> { cout<<"兩地間還沒(méi)有線(xiàn)路通過(guò)"<<endl; } else { cout<<"火車(chē)花的錢(qián)是"<<B[Bcity][Ecity]<<"元"<<endl;}cout<<"輸入0.返回主菜單"<<endl;scanf<"%d",&l>;//h=l;}while<h==1>;}voidadd_city<>//對(duì)城市的增加{ staticinti=1; intj; cout<<"請(qǐng)輸入你要增加的城市的個(gè)數(shù)"<<endl; cin>>j; for<i=1;i<=j;i++> { cout<<"請(qǐng)輸入你要增加的城市名"<<endl; pr<i,1>;//將添加的內(nèi)容放置于add數(shù)組中,并以i為代碼 cnumber=cnumber+1; } cout<<"城市增加完畢"<<endl;}voidchose<>//選擇最少時(shí)間或最小花費(fèi){ inth; cout<<"1:最小花費(fèi)"<<endl; cout<<"2:最小時(shí)間"<<endl; cout<<"請(qǐng)選擇："<<endl; cin>>h; if<h==1>{ money<>; } else { time<>; }}voidedit_line<>//增加編輯火車(chē)的費(fèi)用{ CreateCostG<1>;}voidedit_hour<>//增加編輯火車(chē)的時(shí)間{ CreateTimeG<1>;}voidadministrator<>//管理員功能{ inth=1; while<h>{ cout<<"************************************************************"<<endl; cout<<"1:增加城市"<<endl; cout<<"2:添加或編輯火車(chē)費(fèi)用"<<endl; cout<<"3:添加或編輯火車(chē)時(shí)間"<<endl; cout<<"0:返回主菜單"<<endl; cout<<"************************************************************"<<endl; cout<<"請(qǐng)選擇"<<endl; cin>>h; switch<h>{case1:add_city<>; break;case2: edit_line<>; break;case3:edit_hour<>; break;case0: h=0; break;default: { cout<<"選擇出錯(cuò)！"<<endl; }}}}//主函數(shù)voidmain<>{ charn; intx; while<x!=0> {cout<<endl; cout<<"輸入你希望查詢(xún)的種類(lèi)代碼,你將得到最佳方案!"<<endl; cout<<"******************全國(guó)交通咨詢(xún)模擬系統(tǒng)******************"<<endl; cout<<"*主菜單*"<<endl; cout<<"*1.查看城市*"<<endl; cout<<"*2.選擇最短時(shí)間路線(xiàn)*"<<endl; cout<<"*3.選擇最節(jié)約費(fèi)用路線(xiàn)*"<<endl; co