1、全國交通咨詢模擬 一、設計目的掌握線性表、棧、圖結構和對文件的操作，學習屏幕編輯和菜單技術，掌握用最短路徑及其搜索算法編制較綜合性的程序，能用圖的鄰接存儲結構求解最優路線問題，解決有關實際問題。得到軟件設計技能的訓練。二、問題描述交通咨詢模擬。根據旅客的不同需要，要考慮到旅客希望在旅途中的時間盡可能短、希望旅費盡可能省等的要求。旅途用火車或飛機作為交通工具。用計算機編制程序，為旅客提供兩種最優決策的交通咨詢系統。三、根本要求1、對城市信息(城市名、城市間的里程)進行編輯：具備添加、修改、刪除功能；2、對城市間的兩種交通工具：飛機和火車。對飛機航班和列車時刻表進行編輯：里程、航班和列車班次的添加

2、、修改、刪除；3、提供兩種最優決策：最快到達或最省錢到達。全程只考慮一種交通工具，可以不考慮回程；4、旅途中的消耗的總時間應包括中轉站的等候時間。其中飛機至少二小時，火車至少一小時；5、咨詢以用戶和計算機對話方式進行，要注意人機交互的屏幕界面。由用戶選擇最優決策原那么和交通工具，輸入起始站、終點站、出發時間，輸出信息：最快需要多長時間才能到達及旅費，或者最少需要多少旅費才能到達及時間，并詳細說明依次于何時何地乘坐哪一趟班機或列車何時到達何地。四、實現提示1、算法思路(1) 數據存儲。城市信息(城市名、代碼)、交通信息(城市間的里程、各航班和列車時刻)存儲于磁盤文件。建議把城市信息存于文件前面，

3、交通信息存于文件的后面，用fread和fwrite函數操作。(2) 數據的邏輯結構。根據設計任務的描述，其城市之間的旅游交通問題是典型的圖結構，可看作為有向圖，圖的頂點是城市，邊是城市之間所消耗的時間要包括中轉站的等候時間或旅費。(3) 數據的存儲結構。采用鄰接表和鄰接矩陣都可作為數據的存儲結構，但當鄰接邊不多時，宜采用鄰接表，以提高空間的存儲效率。這里建議采用鄰接表作為數據的存儲結構。(4) 用不同的功能模塊對城市信息和交通信息進行編輯。添加、修改、刪除功能可用菜單方式或命令提示方式。只要能方便的對城市信息和交通信息進行管理即可，但要注意人機界面，具體實現由學生自行設計，也可參考有關程序(屆

4、時在網上提供)。這些工作有不小的工作量。(5) 最優決策功能模塊(fast or province)。 讀入城市信息和交通信息，用鄰接表生成含權網絡，表頭數組中的元素存放城市名及對方城市到達該元素所代表城市的所有信息；表頭數組中的元素所對應的單鏈表存放與該元素所代表的城市有交通聯系的城市(代碼、里程、航班、列車車次)。 根據具體最優決策的要求，用Dijkstra算法求出出發城市到其它各城市的最優值(最短時間或最小的費用)，搜索過程中所經過城市的局部最優信息都保存在鄰接表的表頭數組中。其目的城市所代表的元素中就保存了所需的最優決策結果。這過程中，要用隊列或棧保存局部最優決策值(局部最短的時間或最

5、省的費用)變小的城市，其相應的初始值可為，并在表頭數組對應的城市元素中保存響應的信息。開始時，棧(隊)中只有出發地城市，隨著對棧(隊)頂(首)城市有交通聯系的城市求得決策值(最短時間或最小的費用)，假設該值是局部最優值且該城市不在棧(隊)中，那么進棧(隊)，直至棧(隊)為空。 輸出結果。從目的城市出發，搜索到出發城市，所經過的城市均入棧，再逐一出棧棧中的城市，輸出保存在表頭數組中對應城市的信息(對方城市的出發信息，里程、時間、費用等)及最終結果。即輸出依次于何時何地乘坐幾點的飛機或火車于何時到達何地；最終所需的最快需要多長時間才能到達及旅費，或者最少需要多少旅費才能到達及時間。(6) 主程序可

6、以有系統界面、菜單；也可用命令提示方式；選擇功能模塊執行，要求在程序運行過程中可以反復操作。2、數據結構本程序運用了關于圖這種數據結構。他的抽象數據類型定義如下：typedef struct unDiGraph int numVerts; /結點 costAdj cost; /鄰接矩陣unDiGraph,*UNG;根本操作：unDiGraph* CreateCostG()操作結果：構造帶權(費用)圖。unDiGraph* CreateTimeG()操作結果：構造帶權時間圖。構造飛機帶權(費用)圖。PathMat *Floyed(unDiGraph *D)操作結果：Floyed函數 求任意兩點的

7、最短路徑。3、算法思想 本程序運用了圖的知識，構造了無向帶權費用圖和無向帶權時間圖。如圖1，圖2所示 圖1. 十三城市之間火車費用表權值表示費用 圖2. 十三城市之間火車行駛時間表 權值表示時間并利用Floyed函數求帶權圖兩點之間的最短路徑。通過對帶權費用圖和帶權時間圖求最短路徑，就可以最短道從一城市到另一城市之間最省時間和最省費用的走法。 為了簡潔直觀，本設計對課本內的交通網進行了簡化，原來的25個城市縮減為13個。但是根本實現了設計的目的。滿足了根本要求。4、程序模塊1 程序是用dos 版做的界面。23 程序的模塊為#include <windows.h>#include &

8、lt;stdio.h>#include <crtdbg.h>#include <string.h>#include<iostream.h> #include <malloc.h>/引用的文本件#define INF 65535 /定義一個最大數定為無窮值#define MAX 13typedef int costAdjMAX+1MAX+1;/圖鄰接矩陣從1開始記數int PathMAX+1MAX+1;/圖鄰接矩陣從1開始記數int o13,h;typedef struct unDiGraphint numVerts; /結點costAdj

9、cost; /鄰接矩陣unDiGraph,*UNG; /圖的定義costAdj B,L;void pr(int i)/選擇城市void pri()/輸出城市unDiGraph *CreateCostG()/構造帶權(費用)圖 返回首地址G：unDiGraph *CreateTimeG()/構造帶權(時間)圖 返回首地址G：unDiGraph *CreateFlyG()/飛機的相關信息void Floyed(unDiGraph *D,unDiGraph *M) /Floyed函數 求任意兩點的最短路徑：void prn_pass(int i,int j) /為了求從i到j的最短路徑，只需要調用如

10、下的過程void time()/求最少時間路徑。void money()/求最少花費路徑void administrator()/管理員功能void main()/main函數5、 主程序#include <windows.h>#include <stdio.h>#include <crtdbg.h>#include <string.h>#include<iostream.h> #include <malloc.h>#define INF 65535 /定義一個最大數定為無窮值#define MAX 23static in

11、t c_number=13;static int k=0;staticint v=0,z=0,r=0,t=0;typedef struct zhuint c_cost;int c_time;int f_cost;int f_time;zhu;zhu m20,x20,n20;typedef int costAdjMAX+1MAX+1;/圖鄰接矩陣從1開始記數int PathMAX+1MAX+1;/圖鄰接矩陣從1開始記數typedef struct unDiGraphint numVerts; /結點costAdj cost; /鄰接矩陣unDiGraph,*UNG; /圖的定義typedef s

12、truct c_editchar a10;c_edit;c_edit add10;costAdj B,L;int pr(int i,int j) int h=0;if (j=0) h=i;else if (j=1)cin>>addi.a;switch(h)/運用switch語句。 case(0):cout<<""break;case(1) : cout<<"成都 " break; case(2) : cout<<"西安 "break; case(3) : cout<<&quo

13、t;鄭州 "break; case(4) : cout<<"武漢 "break; case(5) : cout<<"株洲 "break; case(6) : cout<<"貴陽 "break; case(7) : cout<<"柳州 "break; case(8) : cout<<"廣州 "break; case(9) : cout<<"南寧 "break; case(10) : cout<

14、;<"徐州 "break;case(11) : cout<<"北京 "break; case(12) : cout<<"天津 "break; case(13) : cout<<"上海 "break;default: cout<<addi-13.a;return 1;/輸出城市列表及相應代碼void pri()int i;cout<<" 城市及其代碼"<<endl<<endl<<endl; cou

15、t<<" *"<<endl; for (i=1;i<=c_number;i+)cout<<i<<"."pr(i,0);cout<<endl<<" *"<<endl<<endl<<endl<<endl<<endl<<endl;/構造帶權(費用)圖 返回首地址G：unDiGraph *CreateCostG(int o)/火車的花費的存貯和編輯功能unDiGraph *G;int i,j;i

16、nt a=0,b=0,f,h=1;if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) /為G分配存儲空間。return(NULL);for(i=1;i<c_number+1;i+)for(j=1;j<c_number+1;j+)G->costij=INF; /初始化使G->costij為無窮。G->numVerts=c_number;G->cost16=G->cost61=96;G->cost12=G->cost21=84;G->cost23=G->cost32=51;G->cost3

17、4=G->cost43=53;G->cost45=G->cost54=40;G->cost56=G->cost65=90;G->cost58=G->cost85=67;G->cost57=G->cost75=67;G->cost67=G->cost76=60;G->cost79=G->cost97=25;G->cost311=G->cost113=69;G->cost1112=G->cost1211=13;G->cost1210=G->cost1012=67;G->cost3

18、10=G->cost103=34;G->cost1310=G->cost1013=65;G->cost135=G->cost513=118;if (o) while(h=1)v=v+1;pri();cout<<"火車花費編輯"<<endl;cout<<"請輸入開始城市的代碼"<<endl;cin>>a;cout<<"請輸入結尾城市的代碼"<<endl;cin>>b;cout<<"請輸入你的

19、兩地花費"<<endl;cin>>mv.c_cost;nv.c_cost=a;xv.c_cost=b;cout<<"請選擇"<<endl;cout<<"*"<<endl;cout<<"1：繼續更改城市費用"<<endl;cout<<"0:返回上一級菜單"<<endl;cout<<"*"<<endl;cin>>h;switch(h)

20、case 1: h=1;break;case 0: h=0;break;default:cout<<"選擇出錯"<<endl;f=v+1;while (v-) G->costnv.c_costxv.c_cost=mv.c_cost;v=f;return(G);/構造帶權(時間)圖 返回首地址G：unDiGraph *CreateTimeG(int o)/火車的時間的存貯和編輯功能unDiGraph *G;int i,j;int a=0,b=0,f,h=1;if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph)

21、/為G分配存儲空間。return(NULL);for(i=1;i<c_number+1;i+)for(j=1;j<c_number+1;j+)G->costij=INF;/初始化使G->costij為無窮。G->numVerts=c_number;G->cost16=G->cost61=9;G->cost12=G->cost21=8;G->cost23=G->cost32=5;G->cost34=G->cost43=5;G->cost45=G->cost54=4;G->cost56=G->co

22、st65=9;G->cost57=G->cost75=6;G->cost58=G->cost85=6;G->cost67=G->cost76=6;G->cost79=G->cost97=2;G->cost311=G->cost113=6;G->cost1112=G->cost1211=1;G->cost1210=G->cost1012=6;G->cost310=G->cost103=3;G->cost1310=G->cost1013=6;G->cost135=G->cost5

23、13=11;if (o) while(h=1)z=z+1;pri();cout<<"火車時間編輯"<<endl;cout<<"請輸入開始城市的代碼"<<endl;cin>>a;cout<<"請輸入結尾城市的代碼"<<endl;cin>>b;cout<<"請輸入你的兩地時間"<<endl;cin>>mz.c_time;nz.c_time=a;xz.c_time=b;cout<<

24、;"請選擇"<<endl;cout<<"*"<<endl;cout<<"1：繼續更改城市時間"<<endl;cout<<"0:返回上一級菜單"<<endl;cout<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"選擇出錯"<<

25、;endl;f=z+1;while (z-) G->costnz.c_timexz.c_time=mz.c_time;z=f;return(G);unDiGraph *CreateTimeF(int o)/飛機的時間的存貯和編輯功能unDiGraph *G;int i,j;int a=0,b=0,f,h=1;if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) /為G分配存儲空間。return(NULL);for(i=1;i<c_number+1;i+)for(j=1;j<c_number+1;j+)G->costij=INF;/初始

26、化使G->costij為無窮。G->numVerts=c_number;G->cost16=G->cost61=3;G->cost12=G->cost21=2;G->cost23=G->cost32=1;G->cost34=G->cost43=2;G->cost45=G->cost54=4;G->cost56=G->cost65=3;G->cost57=G->cost75=6;G->cost58=G->cost85=6;G->cost67=G->cost76=6;G->

27、cost79=G->cost97=2;G->cost311=G->cost113=6;G->cost1112=G->cost1211=1;G->cost1210=G->cost1012=2;G->cost310=G->cost103=3;G->cost1310=G->cost1013=6;G->cost135=G->cost513=1;if (o) while(h=1)t=t+1;pri();cout<<"飛機時間編輯"<<endl;cout<<"請輸

28、入開始城市的代碼"<<endl;cin>>a;cout<<"請輸入結尾城市的代碼"<<endl;cin>>b;cout<<"請輸入你的兩地時間"<<endl;cin>>mt.f_time;nt.f_time=a;xt.f_time=b;cout<<"請選擇"<<endl;cout<<"*"<<endl;cout<<"1：繼續更改城市時間&qu

29、ot;<<endl;cout<<"0:返回上一級菜單"<<endl;cout<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"選擇出錯"<<endl;f=t+1;while (t-) G->costnt.f_timext.f_time=mt.f_time;t=f;return(G);unDiGraph *CreateCostF

30、(int o)/飛機花費的存貯和編輯功能unDiGraph *G;int i,j;int a=0,b=0,f,h=1;if(!(G=(unDiGraph *)malloc(sizeof(unDiGraph) /為G分配存儲空間。return(NULL);for(i=1;i<c_number+1;i+)for(j=1;j<c_number+1;j+)G->costij=INF; /初始化使G->costij為無窮。G->numVerts=c_number;G->cost16=G->cost61=960;G->cost12=G->cost21=

31、840;G->cost23=G->cost32=501;G->cost34=G->cost43=530;G->cost45=G->cost54=400;G->cost56=G->cost65=900;G->cost58=G->cost85=670;G->cost57=G->cost75=670;G->cost67=G->cost76=600;G->cost79=G->cost97=200;G->cost311=G->cost113=690;G->cost1112=G->cos

32、t1211=310;G->cost1210=G->cost1012=670;G->cost310=G->cost103=340;G->cost1310=G->cost1013=650;G->cost135=G->cost513=1180;if (o) while(h=1)r=r+1;pri();cout<<"飛機花費編輯"<<endl;cout<<"請輸入開始城市的代碼"<<endl;cin>>a;cout<<"請輸入結尾城市

33、的代碼"<<endl;cin>>b;cout<<"請輸入你的兩地花費"<<endl;cin>>mr.f_cost;nr.f_cost=a;xr.f_cost=b;cout<<"請選擇"<<endl;cout<<"*"<<endl;cout<<"1：繼續更改城市費用"<<endl;cout<<"0:返回上一級菜單"<<endl;cou

34、t<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"選擇出錯"<<endl;f=r+1;while (r-) G->costnr.f_costxr.f_cost=mr.f_cost;r=f;return(G); /Floyed函數 求任意兩點的最短路徑：void Floyed(unDiGraph *D,unDiGraph *M) int i,j,k,n;costAdj A,C;n=

35、c_number; for(i=1;i<=n;i+) for(j=1;j<=n;j+)Aij=D->costij;/初始化矩陣A。Cij=M->costij; Pathij=-1; /初始化矩陣p, 置-1. for(k=1;k<=n;k+) /k為逐步參加的中間結點 for(i=1;i<=n;i+) /i為A中行號for(j=1;j<=n;j+)if(Aik+Akj<Aij)Aij=Aik+Akj;Cij=Cik+Ckj; Pathij=k;/假設i經過k到j比i到j小，那么令Aij=Aik+Akj。 Bij=Aij;Lij=Cij; else

36、Bij=Aij;Lij=Cij;/end-for cout<<"n最短路徑為: "<<endl;/end-Floyed/為了求從i到j的最短路徑，只需要調用如下的過程：void prn_pass(int i,int j) if(Pathij!=-1) prn_pass(i,Pathij);/輸出最短路徑經過的所有點 pr(Pathij,0);/求最少時間路徑。void time()int Bcity,Ecity;/起始成市號碼和終點城市號碼 int l,h=1;do pri();/輸出城市列表及相應代碼。 cout<<"請輸入起

37、始城市和目的城市的代碼，中間以空格隔開，范圍(1- "<<c_number<<")" cin>>Bcity; cin>>Ecity;/輸入起始城市和終點城市的代碼。 if (!(0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity) cout<<"n出錯啦! 輸入城市號碼請在1-"<<c_number&

38、lt;<"之間，且兩城市不能相等!"<<endl; Floyed(CreateTimeG(0),CreateCostG(0);/調用Floyed函數。pr(Bcity,0);/ 顯示起始城市。 prn_pass(Bcity,Ecity);/調用prn_pass函數，顯示最短路徑經過的城市。pr(Ecity,0);/顯示終點城市。if (BBcityEcity>5000|LBcityEcity>10000) cout<<"兩地間還沒有線路通過"<<endl;elsecout<<"火

39、車花的錢是"<<LBcityEcity<<"元"<<endl;cout<<"火車花的時間是"<<BBcityEcity<<"小時"<<endl; printf("nn 1.繼續最少花費查找n 2.返回主菜單n 清選擇."); scanf("%d",&l); /輸入1或2選擇是否繼續。 h=l; while(h=1); printf("n");void f_time()int

40、Bcity,Ecity;/起始成市號碼和終點城市號碼 int l,h=1;do pri();/輸出城市列表及相應代碼。 cout<<"請輸入起始城市和目的城市的代碼，中間以空格隔開，范圍(1- "<<c_number<<")" cin>>Bcity; cin>>Ecity;/輸入起始城市和終點城市的代碼。 if (!(0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1

41、)&&Bcity!=Ecity) cout<<"n出錯啦! "<<endl; Floyed(CreateTimeF(0),CreateCostF(0);/調用Floyed函數。pr(Bcity,0);/ 顯示起始城市。 prn_pass(Bcity,Ecity);/調用prn_pass函數，顯示最短路徑經過的城市。pr(Ecity,0);/顯示終點城市。if (BBcityEcity>5000|LBcityEcity>10000) cout<<"兩地間還沒有線路通過"<<endl

42、;elsecout<<"飛機花的錢是"<<LBcityEcity<<"元"<<endl;cout<<"飛機花的時間是"<<BBcityEcity<<"小時"<<endl; printf("nn 1.繼續最少花費查找n 2.返回主菜單n 清選擇."); scanf("%d",&l); /輸入1或2選擇是否繼續。 h=l; while(h=1); printf("n&

43、quot;);/求最少花費路徑。void money() int Bcity,Ecity;/起始成市號碼和終點城市號碼 char l,h=1;/*unDiGraph *G;*/do pri();/輸出城市列表及相應代碼。cout<<"請輸入起始城市和目的城市的代碼，中間以空格隔開，范圍(1- "<<c_number<<")" cin>>Bcity;cin>>Ecity;/輸入起始城市和終點城市的代碼。if (!(0<Bcity&&Bcity<c_number+1)&a

44、mp;&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity) cout<<"n出錯啦! "<<endl; /輸入出錯 Floyed(CreateCostG(0),CreateTimeG(0);/調用Floyed函數。pr(Bcity,0);/顯示起始城市。prn_pass(Bcity,Ecity);/調用prn_pass函數，顯示最短路徑經過的城市。pr(Ecity,0);/顯示終點城市。if (BBcityEcity>5000|LBcityEcity>1

45、0000) cout<<"兩地間還沒有線路通過"<<endl;elsecout<<"火車花的錢是"<<BBcityEcity<<"元"<<endl;cout<<"火車花的時間"<<LBcityEcity<<"小時"<<endl; printf("nn 1.繼續最少花費查找n 2.返回主菜單n 清選擇."); scanf("%d",&

46、;l); /輸入1或2選擇是否繼續。 h=l; while(h=1); printf("n"); /求飛機的情況void f_money() cout<<"1"<<endl;int Bcity,Ecity;/起始成市號碼和終點城市號碼 char l,h=1;/*unDiGraph *G;*/do cout<<"2"<<endl; pri();/輸出城市列表及相應代碼。cout<<"請輸入起始城市和目的城市的代碼，中間以空格隔開，范圍(1- "<<

47、;c_number<<")" cin>>Bcity;cin>>Ecity;/輸入起始城市和終點城市的代碼。if (!(0<Bcity&&Bcity<c_number+1)&&(0<Ecity&&Ecity<c_number+1)&&Bcity!=Ecity) cout<<"n出錯啦! "<<endl; /輸入出錯 Floyed(CreateCostF(0),CreateTimeF(0);/調用Floyed函數

48、。pr(Bcity,0);/顯示起始城市。prn_pass(Bcity,Ecity);/調用prn_pass函數，顯示最短路徑經過的城市。pr(Ecity,0);/顯示終點城市。if (BBcityEcity>5000|LBcityEcity>10000) cout<<"兩地間還沒有線路通過"<<endl;elsecout<<"飛機花的錢是"<<BBcityEcity<<"元"<<endl;cout<<"飛機花的時間"&

49、lt;<LBcityEcity<<"小時"<<endl; printf("nn 1.繼續最少花費查找n 2.返回主菜單n 清選擇."); scanf("%d",&l); /輸入1或2選擇是否繼續。 h=l; while(h=1); printf("n"); void add_city()/對城市的增加static int i=1;int j;cout<<"請輸入你要增加的城市的個數"<<endl;cin>>j;for (i

50、=1;i<=j;i+)cout<<"請輸入你要增加的城市名"<<endl;pr(i,1);c_number=c_number+1;cout<<"城市增加完畢"<<endl;void chose_money()/花最少錢的算法int h;cout<<"1:火車"<<endl;cout<<"2:飛機"<<endl;cout<<"請選擇："<<endl;cin>>h

51、;if (h=1) money();elsef_money();void chose_time()/花最少時間的算法int h;cout<<"1:火車"<<endl;cout<<"2:飛機"<<endl;cout<<"請選擇："<<endl;cin>>h;if (h=1) time();elsef_time();void edit_line()/增加編輯火車的費用CreateCostG(1);void edit_hour()/增加編輯火車的時間Crea

52、teTimeG(1);void edit_fline()/增加編輯飛機的費用CreateCostF(1);void edit_fhour()/增加編輯飛機的時間CreateTimeF(1);void administrator()/管理員功能int h=1;while (h) cout<<"*"<<endl;cout<<"1:增加城市"<<endl;cout<<"2:添加或編輯火車費用"<<endl;cout<<"3:添加或編輯火車時間"<<endl;cout<<"4:添加或編輯飛機費用"<<endl;cout<<"5:添加或編輯飛機時間"<<endl;cout<<"0:返回主菜單"<<endl;cout<<"*"<<endl;cout<<"請選擇"<<endl;cin>>h;sw