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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上太原工業(yè)學院計算機工程系數(shù)據(jù)結構課程設計設計題目：全國交通網(wǎng)絡咨詢系統(tǒng)1班 級： 計算機科學與技術 學 號： 姓 名： 陳敏 指導教師： 劉海靜 年 月 日目錄一、 課程設計題目1二、 需求分析1三、 測試數(shù)據(jù)2四、 概要設計2五、 調(diào)用關系圖3六、 程序代碼3七、 測試結果14八、 心得體會及總結14專心-專注-專業(yè)數(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、是典型的圖結構，可看作為無向圖，圖的頂點是城市，邊是城市之間所耗費的時間（要包括中轉(zhuǎn)站的時間）或旅費。(3) 數(shù)據(jù)的存儲結構。采用鄰接表和鄰接矩陣都可作為數(shù)據(jù)的存儲結構，這里建議采用鄰接矩陣作為數(shù)據(jù)的存儲結構。(4) 用不同的功能模塊對城市信息和交通信息進行編輯。添加、修改、刪除功能可用菜單方式或命令提示方式。只要能方便的對城市信息和交通信息進行管理即可，但要注意人機界面，具體實現(xiàn)由學生自行設計，也可參考有關程序(屆時在網(wǎng)上提供)。這些工作有不小的工作量。(5) 最優(yōu)決策功能模塊 讀入城市信息和交通信息，用鄰接表生成含權網(wǎng)絡，表頭數(shù)組中的元素存放城市名及對方城市到達該元素所代表城市的所有信息；

4、表頭數(shù)組中的元素所對應的單鏈表存放與該元素所代表的城市有交通聯(lián)系的城市(代碼、里程、列車車次)。 根據(jù)具體最優(yōu)決策的要求，用floyd算法求出出發(fā)城市到其它各城市的最優(yōu)值(最短時間或最小的費用)，搜索過程中所經(jīng)過城市的局部最優(yōu)信息都保存在鄰接表的表頭數(shù)組中。其目的城市所代表的元素中就保存了所需的最優(yōu)決策結果。其相應的初始值可為，并在表頭數(shù)組對應的城市元素中保存響應的信息。 主程序可以有系統(tǒng)界面、菜單；也可用命令提示方式；選擇功能模塊執(zhí)行，要求在程序運行過程中可以反復操作。三、測試數(shù)據(jù)：7046513491579138523688125112553北京徐州西安成都鄭州廣州上海四、概要設計本程序運

5、用了關于圖這種數(shù)據(jù)結構。它的抽象數(shù)據(jù)類型定義如下：typedef struct unDiGraph int numVerts; /結點 costAdj cost; /鄰接矩陣unDiGraph,*UNG;基本操作：unDiGraph* CreateCostG()操作結果：構造帶權(費用)圖。unDiGraph* CreateTimeG()操作結果：構造帶權（時間）圖。構造飛機帶權(費用)圖。PathMat *Floyed(unDiGraph *D)操作結果：Floyed函數(shù) 求任意兩點的最短路徑。五、調(diào)用關系圖unDiGraph（圖）Floyed函數(shù) 求任意兩點的最短路徑CreateTimeG

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

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

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

9、k; 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<<"*"&

10、lt;<endl;for(i=1;i<=cnumber;i+)cout<<i<<"."pr(i,0);cout<<"*"<<endl;/構造CostG圖，表示其費用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 *)mall

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

12、3; 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ù)組中的存放代碼pri();cout<<"火車花費編輯"<<endl;cout<<"請輸入開始城市

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

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

15、(G);/構造TimeG圖，表示其花費時間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;j<=cnumber+1;j+)G->costij=INF;/初始化使G->costij為無窮。G->numV=cnumber;

16、 G->cost16=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=

17、z+1;/全局靜態(tài)變量，初始值為0.即1=0+1pri();cout<<"火車時間編輯"<<endl;cout<<"請輸入開始城市的代碼"<<endl;cin>>a;cout<<"請輸入結尾城市的代碼"<<endl;cin>>b;cout<<"請輸入你的兩地時間"<<endl;cin>>mz.ctime;nz.ctime=a;xz.ctime=b;cout<<"請

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

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

20、A,C。Cij=M->costij; Pathij=-1; /初始化權矩陣pfor(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經(jīng)過k到j比i到j小，則選擇經(jīng)過K個中間點之后，i,j兩點的最佳路徑。Bij=Aij;/構造A C 兩個任意節(jié)點上的最優(yōu)路徑所建造的矩陣，并分別賦給B L代表時間與花費Lij=Cij; else Bij=Aij; Lij=Cij; /end fo

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

22、中間以空格隔開"<<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)

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

24、quot; 輸入0.返回主菜單 "<<endl; scanf("%d",&l); / h=l; while(h=1); /求最少花費路徑。void money() int Bcity,Ecity;/起始成市號碼和終點城市號碼 char l,h=1;do pri();/輸出城市列表及相應代碼。cout<<"請輸入起始城市和目的城市的代碼，中間以空格隔開"<<endl; cin>>Bcity;cin>>Ecity;/輸入起始城市和終點城市的代碼。if (!(0<Bcity&a

25、mp;&Bcity<cnumber+1)&&(0<Ecity&&Ecity<cnumber+1)&&Bcity!=Ecity) cout<<"n出錯啦! 輸入城市號碼請在1-7之間，且兩城市代碼不能相等!"<<endl; /輸入出錯 Floyed(CreateCostG(0),CreateTimeG(0);/調(diào)用Floyed函數(shù)。pr(Bcity,0);/顯示起始城市。prn_pass(Bcity,Ecity);/調(diào)用prn_pass函數(shù)，顯示最短路徑經(jīng)過的城市。pr(Ecit

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

27、ty()/對城市的增加static int i=1;int j;cout<<"請輸入你要增加的城市的個數(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()/選擇最少時間或最小花費int h;cout<<&qu

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

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

30、 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) cout<<endl;cout<<"輸入你希望查詢的種類代碼，你將得到最佳方案!"<<endl;cout<<" *全國交通網(wǎng)絡模擬系統(tǒng)*"<<endl;cout<<&qu