2數(shù)據(jù)結構-全國交通咨詢模擬系統(tǒng)實驗報告

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