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

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

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

3、為無向圖，圖的頂點(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) 用不同的功能模塊對城市信息和交通信息進(jìn)行編輯。添加、修改、刪除功能可用菜單方式或命令提示方式。只要能方便的對城市信息和交通信息進(jìn)行管理即可，但要注意人機(jī)界面，具體實(shí)現(xiàn)由學(xué)生自行設(shè)計(jì)，也可參考有關(guān)程序(屆時(shí)在網(wǎng)上提供)。這些工作有不小的工作量。(5) 最優(yōu)決策功能模塊 讀入城市信息和交通信息，用鄰接表生成含權(quán)網(wǎng)絡(luò)，表頭數(shù)組中的元素存放城市名及對方城市到達(dá)該元素所代表城市的所有信息；表頭數(shù)組中的元素所對應(yīng)

4、的單鏈表存放與該元素所代表的城市有交通聯(lián)系的城市(代碼、里程、列車車次)。 根據(jù)具體最優(yōu)決策的要求，用floyd算法求出出發(fā)城市到其它各城市的最優(yōu)值(最短時(shí)間或最小的費(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ù)：7046513491579138523688125112553北京徐州西安成都鄭州廣州上海四、概要設(shè)計(jì)本程序運(yùn)用了關(guān)于圖這種數(shù)據(jù)結(jié)構(gòu)

5、。它的抽象數(shù)據(jù)類型定義如下：typedef struct unDiGraph int numVerts; /結(jié)點(diǎn) costAdj cost; /鄰接矩陣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)的最短路徑。五、調(diào)用關(guān)系圖unDiGraph（圖）Floyed函數(shù) 求任意兩點(diǎn)的最短路徑CreateTimeG（構(gòu)造帶權(quán)時(shí)間）Cre

6、ateCostG（構(gòu)造帶權(quán) 費(fèi)用）6、 程序代碼#include <windows.h>#include <stdio.h>#include <crtdbg.h>#include <string.h>#include<iostream.h> #include <malloc.h>#define INF 10000 /定義一個(gè)最大數(shù)定為無窮值#define MAX 7static int cnumber=7;static int k=0;static int v=0,z=0;/定義靜態(tài)變量typedef struct zhu

7、/定義結(jié)構(gòu)體zhuint ccost;/定義結(jié)構(gòu)變量int ctime;zhu;zhu m20,x20,n20;/定義數(shù)組為struct zhu 類型數(shù)組，且三個(gè)數(shù)組分別儲(chǔ)存添加后的數(shù)據(jù)，且表示花費(fèi)m，起點(diǎn)n，和終點(diǎn)xtypedef int costAdjMAX+1MAX+1;/定義圖的鄰接矩陣，并從1開始int PathMAX+1MAX+1;/路程矩陣，表示經(jīng)過存放的點(diǎn)ktypedef struct unDiGraphint numV;/結(jié)點(diǎn)costAdj cost;/鄰接矩陣unDiGraph,*UNG;typedef struct ceditchar a10;cedit;cedit ad

8、d10;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)cin>>addi.a;switch (h)case(0) : cout<<""break;case(1) : cout<<"成都 "break;case(2) : cout<<"廣州 " break; case(3) : cout<<"上海 "break; case(4)

9、: 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

10、;for(i=1;i<=cnumber;i+)cout<<i<<"."pr(i,0);cout<<"*"<<endl;/構(gòu)造CostG圖，表示其費(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臨時(shí)表示開始城市代碼以及目的城市代碼 if(!(G=(unDiGraph *)malloc(sizeof(u

11、nDiGraph) /為G圖分配存儲(chǔ)空間。return(NULL); for(i=1;i<=cnumber;i+)for(j=1;j<=cnumber;j+)G->costij=INF;/初始化矩陣cost每一項(xiàng)，使其無窮大 G->numV=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->co

12、st45=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ù)，三個(gè)編輯數(shù)組中的存放代碼pri();cout<<"火車花費(fèi)編輯"<<endl;cout<<"請輸入開始城市的代碼"&l

13、t;<endl;cin>>a;cout<<"請輸入目的城市的代碼"<<endl;cin>>b;cout<<"請輸入你的兩地花費(fèi)"<<endl;cin>>mv.ccost;nv.ccost=a;xv.ccost=b;cout<<"請選擇"<<endl;cout<<"*"<<endl;cout<<"1：繼續(xù)更改城市費(fèi)用"<<endl;cou

14、t<<"0:返回上一級菜單"<<endl;cout<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"選擇出錯(cuò)"<<endl; f=v+1;/初始定義變量f為1,全局變量v為0，即1=0+1 while (v+) /v+代表的意思G->costnv.ccostxv.ccost=mv.ccost; v=f; return(G);/構(gòu)造Time

15、G圖，表示其花費(fèi)時(shí)間unDiGraph *CreateTimeG(int o)/火車的時(shí)間的存貯和編輯功能unDiGraph *G;int i,j;/循環(huán)變量int a=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->costij=INF;/初始化使G->costij為無窮。G->numV=cnumber; G->cost

16、16=G->cost61=9;G->cost12=G->cost21=8;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)變量

17、，初始值為0.即1=0+1pri();cout<<"火車時(shí)間編輯"<<endl;cout<<"請輸入開始城市的代碼"<<endl;cin>>a;cout<<"請輸入結(jié)尾城市的代碼"<<endl;cin>>b;cout<<"請輸入你的兩地時(shí)間"<<endl;cin>>mz.ctime;nz.ctime=a;xz.ctime=b;cout<<"請選擇"<

18、;<endl;cout<<"*"<<endl;cout<<"1：繼續(xù)更改城市時(shí)間"<<endl;cout<<"0:返回上一級菜單"<<endl;cout<<"*"<<endl;cin>>h;switch(h) case 1: h=1;break;case 0: h=0;break;default:cout<<"選擇出錯(cuò)"<<endl; f=z+1;/全局靜態(tài)變

19、量z,初始值為0while (z+) G->costnz.ctimexz.ctime=mz.ctime; z=f; return(G); /Floyed函數(shù) 求任意兩點(diǎn)的最短路徑：void Floyed(unDiGraph *D,unDiGraph *M)/圖D M int i,j,k,n;/i,j為循環(huán)變量,k表中間節(jié)點(diǎn)的變量costAdj A,C;/A C為圖，臨時(shí)表示兩種最佳路線組成的矩陣，定義costAdj B Ln=cnumber; for(i=1;i<=n;i+) for(j=1;j<=n;j+)Aij=D->costij;/初始化矩陣A,C。Cij=M-&

20、gt;costij; Pathij=-1; /初始化權(quán)矩陣pfor(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+Akj<Aij)Aij=Aik+Akj;Cij=Cik+Ckj;Pathij=k;/若i經(jīng)過k到j(luò)比i到j(luò)小，則選擇經(jīng)過K個(gè)中間點(diǎn)之后，i,j兩點(diǎn)的最佳路徑。Bij=Aij;/構(gòu)造A C 兩個(gè)任意節(jié)點(diǎn)上的最優(yōu)路徑所建造的矩陣，并分別賦給B L代表時(shí)間與花費(fèi)Lij=Cij; else Bij=Aij; Lij=Cij; /end for循環(huán) cout<

21、;<"n最短路徑為: "<<endl;/end-Floyed/為了求從i到j(luò)的最短路徑，只需要調(diào)用如下的過程：void prn_pass(int i,int j) if(Pathij!=-1) prn_pass(i,Pathij);/輸出最短路徑經(jīng)過的所有點(diǎn)個(gè)數(shù)k pr(Pathij,0);/求最少時(shí)間路徑。void time()int Bcity,Ecity;/起始成市號碼和終點(diǎn)城市號碼int l,h=1;/定義變量l hdo pri();/輸出城市列表及相應(yīng)代碼。cout<<"請輸入起始城市和目的城市的代碼，中間以空格隔開&quo

22、t;<<endl; cin>>Bcity;cin>>Ecity;/輸入起始城市和終點(diǎn)城市的代碼。if (!(0<Bcity&&Bcity<cnumber+1)&&(0<Ecity&&Ecity<cnumber+1)&&Bcity!=Ecity)cout<<"n出錯(cuò)啦! 輸入城市號碼請?jiān)?-7之間，且兩城市代碼不能相等!"<<endl; Floyed(CreateTimeG(0),CreateCostG(0);/調(diào)用Floyed函

23、數(shù)。pr(Bcity,0);/ 顯示起始城市。 prn_pass(Bcity,Ecity);/調(diào)用prn_pass函數(shù)，顯示最短路徑經(jīng)過的城市。 pr(Ecity,0);/顯示終點(diǎn)城市。 if (BBcityEcity>8000|LBcityEcity>8000) cout<<"兩地間還沒有線路通過"<<endl;elsecout<<"火車花的時(shí)間是"<<BBcityEcity<<"小時(shí)"<<endl; cout<<" 輸入0.返

24、回主菜單 "<<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<<"請輸入起始城市和目的城市的代碼，中間以空格隔開"<<endl; cin>>Bcity;cin>>Ecity;/輸入起始城市和終點(diǎn)城市的代碼。if (!(0<Bcity&&Bci

25、ty<cnumber+1)&&(0<Ecity&&Ecity<cnumber+1)&&Bcity!=Ecity) cout<<"n出錯(cuò)啦! 輸入城市號碼請?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)過的城市。pr(Ecity,0);/顯示終點(diǎn)城

26、市。if (LBcityEcity>8000|BBcityEcity>8000)cout<<"兩地間還沒有線路通過"<<endl;elsecout<<"火車花的錢是"<<BBcityEcity<<"元"<<endl; cout<<" 輸入0.返回主菜單"<<endl; scanf("%d",&l); / h=l; while(h=1); void add_city()/對城市的增加

27、static int i=1;int j;cout<<"請輸入你要增加的城市的個(gè)數(shù)"<<endl;cin>>j;for (i=1;i<=j;i+)cout<<"請輸入你要增加的城市名"<<endl;pr(i,1);/將添加的內(nèi)容放置于add數(shù)組中，并以i為代碼cnumber=cnumber+1;cout<<"城市增加完畢"<<endl;void chose()/選擇最少時(shí)間或最小花費(fèi)int h;cout<<"1:最小花費(fèi)&q

28、uot;<<endl;cout<<"2:最小時(shí)間"<<endl;cout<<"請選擇："<<endl;cin>>h;if (h=1) money();elsetime();void edit_line()/增加編輯火車的費(fèi)用CreateCostG(1);void edit_hour()/增加編輯火車的時(shí)間CreateTimeG(1);void administrator()/管理員功能int h=1;while (h) cout<<"*"<<

29、;endl;cout<<"1:增加城市"<<endl;cout<<"2:添加或編輯火車費(fèi)用"<<endl;cout<<"3:添加或編輯火車時(shí)間"<<endl;cout<<"0:返回主菜單"<<endl;cout<<"*"<<endl;cout<<"請選擇"<<endl;cin>>h;switch(h) case 1 :ad

30、d_city();break;case 2:edit_line();break;case 3:edit_hour();break;case 0:h=0;break;default:cout<<"選擇出錯(cuò)！"<<endl;/主函數(shù)void main() char n;int x;while(x!=0) cout<<endl;cout<<"輸入你希望查詢的種類代碼，你將得到最佳方案!"<<endl;cout<<" *全國交通網(wǎng)絡(luò)模擬系統(tǒng)*"<<endl;cout<<&quo