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

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

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

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

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

5、dj cost; 鄰接矩陣un DiGraph,*UNG;基本操作：un DiGraph* CreateCostG（）操作結(jié)果：構(gòu)造帶權(quán)（費(fèi)用）圖。un DiGraph* CreateTimeG（）操作結(jié)果：構(gòu)造帶權(quán)（時間）圖。構(gòu)造飛機(jī)帶權(quán)（費(fèi)用）圖。PathMat *Floyed（u nDiGraph *D）操作結(jié)果：Floyed函數(shù) 求任意兩點(diǎn)的最短路徑。五、調(diào)用關(guān)系圖un DiGraph （圖）Floyed函數(shù) 求任意兩點(diǎn)的最短路徑CreateCostG（構(gòu)造帶權(quán) 費(fèi)用）CreateTimeG （構(gòu)造帶權(quán)時間）六、程序代碼#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定義結(jié)構(gòu)體 zhuin t ccost;/定義結(jié)構(gòu)變量int ctime;zhu;zhu m20,x20,n20;定義數(shù)組為struct zhu類型數(shù)組，且三個數(shù)組分別儲存添加后的數(shù)據(jù)，且表示花費(fèi) m起點(diǎn)n，和終點(diǎn)xtypedef in t costAdjMAX+1MAX+1; 定義圖的鄰接矩陣

7、，并從 1開始int PathMAX+1MAX+1;/路程矩陣，表示經(jīng)過存放的點(diǎn)ktypedef struct un DiGraphint numV;/ 結(jié)點(diǎn)costAdj cost;/ 鄰接矩陣u nDiGraph,*UNG;14typedef struct cedit char a10; cedit; cedit add10;costAdj B,L;/ 功能一 輸出相應(yīng)的城市信息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;/ 構(gòu)造 Cost

9、G 圖，表示其費(fèi)用unDiGraph *CreateCostG(int o)/火車的花費(fèi)的存貯和編輯功能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 表示編輯的火車花費(fèi)的組數(shù)， 三個編輯數(shù)組中的存放代碼p

11、ri();cout 火車花費(fèi)編輯 endl;cout 請輸入開始城市的代碼 a;cout 請輸入目的城市的代碼 b;cout 請輸入你的兩地花費(fèi) mv.ccost;nv.ccost=a;xv.ccost=b;cout 請選擇 endl; cout*endl;cout1 ：繼續(xù)更改城市費(fèi)用 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);/構(gòu)造TimeG圖，表

12、示其花費(fèi)時間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 請輸入結(jié)尾城市的代碼 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ù) 求任意兩點(diǎn)的最短路徑： void Floyed(unDiGraph *D,unDiGraph *M)/圖 D McostAdjint i,j,k,n;/i,j 為循環(huán)變量 ,

15、k 表中間節(jié)點(diǎn)的變量 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; / 初始化權(quán)矩陣 p for(k=1;k=n;k+) /k 為逐步加入的中間結(jié)點(diǎn)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(luò)比i到j(luò)小，則選擇經(jīng)過 K個中間點(diǎn)之后， i,j 兩

16、點(diǎn)的最佳路徑。Bij=Aij;/構(gòu)造 A C 兩個任意節(jié)點(diǎn)上的最優(yōu)路徑所建造的矩陣，并分別賦給 B L 代表時間與花費(fèi)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)過的所有點(diǎn)個數(shù) kpr(Pathij,0);/ 求最少時間路徑。void time()int Bcity,Ecity;/ 起始成市號碼和終點(diǎn)城市號

17、碼int l,h=1;/ 定義變量 l hdo pri();/ 輸出城市列表及相應(yīng)代碼。cout 請輸入起始城市和目的城市的代碼，中間以空格隔開 Bcity;cinEcity;/ 輸入起始城市和終點(diǎn)城市的代碼。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);/ 求最少花費(fèi)路徑。void money()int Bcity,Ecity;/ 起始成市號碼和終點(diǎn)城市號碼char l,h=1;do pri();/ 輸出城市列表及相應(yīng)代碼。cout 請輸入起始城市和目的城市的代碼，中間以空格隔開 Bcity;cinEcity;/ 輸入起始城市和終點(diǎn)城市的代碼。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()/ 選擇最少時間或最小花費(fèi)int h;cout1: 最小花費(fèi) endl;cout2: 最小時間 endl; cout 請選擇： h;if (h=1) money();elsetime();void edit_line()/ 增加編輯火車的費(fèi)用CreateCostG(1);void edit_hour()/ 增加編輯火車的時間CreateTimeG(1);void administrator()/ 管理員功能int h=1;while (h) *endl;cout1: 增加城市 endl;cout2: 添加或編輯火車費(fèi)用 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) 絡(luò) 模 擬 系 統(tǒng)*、endl;cout*endl;cout*endl;cout*endl;cout*endl;cout*endl;cout主菜單1. 查 看 城 市2. 選 擇 最 短 時 間 路 線3. 選擇最 節(jié)約費(fèi)用路線4. 管 理 員 程 序0.