數(shù)據(jù)結構課程設計全國交通咨詢系統(tǒng)

1、太原工業(yè)學院計算機工程系數(shù)據(jù)結構課程設計設計題目：全國交通網(wǎng)絡咨詢系統(tǒng)1班級：計算機科學與技術學號：132054103姓名：陳敏指導教師：劉海靜目錄一、課程設計題目 1二、需求分析 1三、測試數(shù)據(jù) 2四、概要設計2五、調(diào)用關系圖3六、程序代碼 3七、測試結果 14八、心得體會及總結 14數(shù)據(jù)結構課程設計一、課程設計題目全國交通網(wǎng)絡咨詢系統(tǒng)二、需求分析1、實現(xiàn)功能對城市信息（城市名、城市間的里程）進行編輯：具備添加、修改、刪除功能；對城市間的交通工具：火車。對列車時刻表進行編輯：里程、和列車班次的添加、修改、刪除；提供兩種最優(yōu)決策：最快到達或最省錢到達。全程只考慮一種交通工具，可以不考慮回程；咨

2、詢以用戶和計算機對話方式進行，要注意人機交互的屏幕界面。由用戶選擇最優(yōu)決策原則和交通工具，輸入起始站、終點站、出發(fā)時間，輸出信息：最快需要多長時間才能到達及旅費，或者最少需要多少旅費才能到達及時間，并詳細說明依次于何時何地乘坐哪一趟列車何時到達何地。2、設計思路（1）數(shù)據(jù)存儲。城市信息（城市名、代碼）、交通信息（城市間的里程、各航班和列車時刻 ） 存儲于磁盤文件。在實驗中本想用文本儲存數(shù)據(jù)， 但操作不熟悉，而是改用圖的鄰接矩陣 儲 存原始信息，而后用數(shù)組進行添加刪改（2）數(shù)據(jù)的邏輯結構。根據(jù)設計任務的描述，其城市之間的旅游交通問題是典型的圖結構，可看作為無向圖，圖的頂點是城市，邊是城市之間所耗

3、費的時間（要包括中轉站的時間）或旅費。（3）數(shù)據(jù)的存儲結構。采用鄰接表和鄰接矩陣都可作為數(shù)據(jù)的存儲結構，這里建議采用 鄰接矩陣作為數(shù)據(jù)的存儲結構。（4）用不同的功能模塊對城市信息和交通信息進行 編輯。添加、修改、刪除功能可用菜單方式或命令提示方式。只要能方便的對城市信息和交通信息進行管理即可，但要注意人機界面，具體實現(xiàn)由學生自行設計， 也可參考有關程序（屆時在網(wǎng)上提供）。這些工作有不小的工作量。（5）最優(yōu)決策功能模塊 讀入城市信息和交通信息，用鄰接表生成含權網(wǎng)絡，表頭數(shù)組中的元素存放城市名及對方城市到達該元素所代表城市的所有信息；表頭數(shù)組中的元素所對應的單鏈表存放與該元素所代表的城市有交通聯(lián)系

4、的城市 （代碼、里程、列車車次）。 根據(jù)具體最優(yōu)決策的要求，用floyd算法求出出發(fā)城市到其它各城市的最優(yōu)值（最短時間 或最小的費用），搜索過程中所經(jīng)過城市的局部最優(yōu)信息都保存在鄰接表的表頭數(shù)組中。其目的城市所代表的元素中就保存了所需的最優(yōu)決策結果。其相應的初始值可為并在表頭數(shù)組對應的城市元素中保存響應的信息。 主程序可以有系統(tǒng)界面、菜單；也可用命令提示方式；選擇功能模塊執(zhí)行，要求在程序 運行過程中可以反復操作。三、測試數(shù)據(jù):四、概要設計本程序運用了關于圖這種數(shù)據(jù)結構。它的抽象數(shù)據(jù)類型定義如下：typedef struct un DiGraphint num Verts; /纟吉點 costA

5、dj cost; 鄰接矩陣un DiGraph,*UNG;基本操作：un DiGraph* CreateCostG（）操作結果：構造帶權（費用）圖。un DiGraph* CreateTimeG（）操作結果：構造帶權（時間）圖。構造飛機帶權（費用）圖。PathMat *Floyed（u nDiGraph *D）操作結果：Floyed函數(shù) 求任意兩點的最短路徑。五、調(diào)用關系圖un DiGraph （圖）Floyed函數(shù) 求任意兩點的最短路徑CreateCostG（構造帶權 費用）CreateTimeG （構造帶權時間）六、程序代碼#i nclude #i nclude #in clude #in

6、clude #i nclude#i nclude #defi ne INF 10000 /定義一個最大數(shù)定為無窮值#defi ne MAX 7static int cnu mber=7;static int k=0;static in t v=0,z=0;定義靜態(tài)變量typedef struct zhu定義結構體 zhuin t ccost;/定義結構變量int ctime;zhu;zhu m20,x20,n20;定義數(shù)組為struct zhu類型數(shù)組，且三個數(shù)組分別儲存添加后的數(shù)據(jù)，且表示花費 m起點n，和終點xtypedef in t costAdjMAX+1MAX+1; 定義圖的鄰接矩陣

7、，并從 1開始int PathMAX+1MAX+1;/路程矩陣，表示經(jīng)過存放的點ktypedef struct un DiGraphint numV;/ 結點costAdj cost;/ 鄰接矩陣u nDiGraph,*UNG;14typedef struct cedit char a10; cedit; cedit add10;costAdj B,L;/ 功能一 輸出相應的城市信息int pr(int i,int j)/pr 函數(shù)表輸出功能int h=0;if (j=0)h=i;else if (j=1)cinaddi.a;switch (h)case(0) : cout;break;cas

8、e(1) : cout 成都 ;break;case(2) : cout 廣州 ;break;case(3) : cout上海 break;case(4) : cout徐州 break;case(5) : cout鄭州 break;case(6) : cout西安 break;case(7) : cout北京 break;return 1;void pri() 聲明pri函數(shù)，即利用pr函數(shù)輸出代碼為i 的城市信息int i;cout 城市以及其代碼 endl;cout*、endl;for(i=1;i=cnumber;i+)couti.;pr(i,0);cout*、endl;/ 構造 Cost

9、G 圖，表示其費用unDiGraph *CreateCostG(int o)/火車的花費的存貯和編輯功能unDiGraph *G;int i;int j;/ 定義的 i,j 做循環(huán)變量int a=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;jcostij=INF;/ 初始化矩陣 cost 每一項，使其無窮大G-nu

10、mV=cnumber;G-cost16=G-cost61=90;G-cost12=G-cost21=84;G-cost23=G-cost32=51;G-cost25=G-cost52=67;G-cost34=G-cost43=53;G-cost45=G-cost54=40;G-cost47=G-cost74=88;G-cost56=G-cost65=90;G-cost57=G-cost75=67;G-cost67=G-cost76=60;if (o)while(h=1)/h 初始值為 1v=v+1;/V 為全局靜態(tài)變量，初始值為 0 ,v 表示編輯的火車花費的組數(shù)， 三個編輯數(shù)組中的存放代碼p

11、ri();cout 火車花費編輯 endl;cout 請輸入開始城市的代碼 a;cout 請輸入目的城市的代碼 b;cout 請輸入你的兩地花費 mv.ccost;nv.ccost=a;xv.ccost=b;cout 請選擇 endl; cout*endl;cout1 ：繼續(xù)更改城市費用 endl;cout0: 返回上一級菜單 endl;cout* h; switch(h) case 1: h=1; break;case 0:h=0; break;default:cout 選擇出錯 costnv.ccostxv.ccost=mv.ccost;v=f; return(G);/構造TimeG圖，表

12、示其花費時間unDiGraph *CreateTimeG(int o)/ 火車的時間的存貯和編輯功能 unDiGraph *G; int i,j;/ 循環(huán)變量 int a=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;jcostij=INF;/ 初始化使 G-costij 為無窮。 G-numV=cnumber;G-cost16=G-cost61=9; G-cost12=G-cost21=8

13、;G-cost23=G-cost32=5;G-cost25=G-cost52=3;G-cost34=G-cost43=5;G-cost45=G-cost54=4;G-cost47=G-cost75=6;G-cost56=G-cost65=9;G-cost57=G-cost75=6;G-cost67=G-cost76=6;if (o)while(h=1) z=z+1;/ 全局靜態(tài)變量，初始值為 0. 即 1=0+1 pri();cout 火車時間編輯 endl; cout 請輸入開始城市的代碼 a;cout 請輸入結尾城市的代碼 b;cout 請輸入你的兩地時間 mz.ctime; nz.cti

14、me=a; xz.ctime=b;cout 請選擇 endl;*/*endl;cout1 ：繼續(xù)更改城市時間 endl; cout0: 返回上一級菜單 endl; cout* h; switch(h) case 1: h=1; break;case 0:h=0; break;default: cout 選擇出錯 costnz.ctimexz.ctime=mz.ctime;z=f; return(G);/Floyed 函數(shù) 求任意兩點的最短路徑： void Floyed(unDiGraph *D,unDiGraph *M)/圖 D McostAdjint i,j,k,n;/i,j 為循環(huán)變量 ,

15、k 表中間節(jié)點的變量 costAdj A,C;/A C 為圖，臨時表示兩種最佳路線組成的矩陣，定義 B Ln=cnumber; for(i=1;i=n;i+)for(j=1;jcostij;/ 初始化矩陣 A,C。 Cij=M-costij;Pathij=-1; / 初始化權矩陣 p for(k=1;k=n;k+) /k 為逐步加入的中間結點for(i=1;i=n;i+) /i 代表矩陣 A 中行號 for(j=1;j=n;j+) if(Aik+AkjAij) Aij=Aik+Akj; Cij=Cik+Ckj;Pathij=k;若i經(jīng)過k到j比i到j小，則選擇經(jīng)過 K個中間點之后， i,j 兩

16、點的最佳路徑。Bij=Aij;/構造 A C 兩個任意節(jié)點上的最優(yōu)路徑所建造的矩陣，并分別賦給 B L 代表時間與花費Lij=Cij;elseBij=Aij; Lij=Cij;/end for 循環(huán)coutn 最短路徑為 : endl;/end-Floyed/ 為了求從 i 到 j 的最短路徑，只需要調(diào)用如下的過程： void prn_pass(int i,int j)if(Pathij!=-1)prn_pass(i,Pathij);/輸出最短路徑經(jīng)過的所有點個數(shù) kpr(Pathij,0);/ 求最少時間路徑。void time()int Bcity,Ecity;/ 起始成市號碼和終點城市號

17、碼int l,h=1;/ 定義變量 l hdo pri();/ 輸出城市列表及相應代碼。cout 請輸入起始城市和目的城市的代碼，中間以空格隔開 Bcity;cinEcity;/ 輸入起始城市和終點城市的代碼。if (!(0Bcity&Bcitycnumber+1)&(0Ecity&Ecitycnumber+1)&Bcity!=Eci ty)coutn 出錯啦! 輸入城市號碼請在 1-7 之間，且兩城市代碼不能 相等!8000|LBcityEcity8000)cout 兩地間還沒有線路通過 endl;elsecout 火車花的時間是 BBcityEcity小時 endl;cout 輸入 0.

18、返回主菜單 endl;scanf(%d,&l); /h=l; while(h=1);/ 求最少花費路徑。void money()int Bcity,Ecity;/ 起始成市號碼和終點城市號碼char l,h=1;do pri();/ 輸出城市列表及相應代碼。cout 請輸入起始城市和目的城市的代碼，中間以空格隔開 Bcity;cinEcity;/ 輸入起始城市和終點城市的代碼。if (!(0Bcity&Bcitycnumber+1)&(0Ecity&Ecitycnumber+1)&Bcity!=Eci ty)coutn 出錯啦 ! 輸入城市號碼請在 1-7 之間，且兩城市代碼不能 相等!800

19、0|BBcityEcity8000)cout 兩地間還沒有線路通過 endl;elsecout火車花的錢是BBcityEcityvv元endl;cout 輸入 0. 返回主菜單 endl;scanf(%d,&l); /h=l; while(h=1);void add_city()/ 對城市的增加static int i=1;int j;cout 請輸入你要增加的城市的個數(shù) j;for (i=1;i=j;i+)cout 請輸入你要增加的城市名 endl;pr(i,1);將添加的內(nèi)容放置于add數(shù)組中，并以i為代碼cnumber=cnumber+1;cout 城市增加完畢 endl;void ch

20、ose()/ 選擇最少時間或最小花費int h;cout1: 最小花費 endl;cout2: 最小時間 endl; cout 請選擇： h;if (h=1) money();elsetime();void edit_line()/ 增加編輯火車的費用CreateCostG(1);void edit_hour()/ 增加編輯火車的時間CreateTimeG(1);void administrator()/ 管理員功能int h=1;while (h) *endl;cout1: 增加城市 endl;cout2: 添加或編輯火車費用 endl;cout3: 添加或編輯火車時間 endl;cout0

21、: 返回主菜單 endl;cout*endl;cout 請選擇 h;switch(h) case 1 :add_city();break;case 2: edit_line();break;case 3:edit_hour();break;case 0:h=0;break; default:cout 選擇出錯！ endl;/ 主函數(shù) void main() char n; int x; while(x!=0) coutendl;cout 輸入你希望查詢的種類代碼，你將得到最佳方案 !endl;cout * 全 國 交 通 網(wǎng) 絡 模 擬 系 統(tǒng)*、endl;cout*endl;cout*endl;cout*endl;cout*endl;cout*endl;cout主菜單1. 查 看 城 市2. 選 擇 最 短 時 間 路 線3. 選擇最 節(jié)約費用路線4. 管 理 員 程 序0.