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

太原工業(yè)學(xué)院計算機工程系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計題目：全國交通網(wǎng)絡(luò)咨詢系統(tǒng)1班 級： 計算機科學(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)功能對城市信息(城市名、城市間的里程)進行編輯：具備添加、修改、刪除功能； 對城市間的交通工具：火車。對列車時刻表進行編輯：里程、和列車班次的添加、修改、刪除； 提供兩種最優(yōu)決策：最快到達或最省錢到達。全程只考慮一種交通工具，可以不考慮回程； 咨詢以用戶和計算機對話方式進行，要注意人機交互的屏幕界面。由用戶選擇最優(yōu)決策原則和交通工具，輸入起始站、終點站、出發(fā)時間，輸出信息：最快需要多長時間才能到達及旅費，或者最少需要多少旅費才能到達及時間，并詳細說明依次于何時何地乘坐哪一趟列車何時到達何地。2、 設(shè)計思路（1) 數(shù)據(jù)存儲。城市信息(城市名、代碼)、交通信息(城市間的里程、各航班和列車時刻)存儲于磁盤文件。在實驗中本想用文本儲存數(shù)據(jù)，但操作不熟悉，而是改用圖的鄰接矩陣儲存原始信息，而后用數(shù)組進行添加刪改(2) 數(shù)據(jù)的邏輯結(jié)構(gòu)。根據(jù)設(shè)計任務(wù)的描述，其城市之間的旅游交通問題是典型的圖結(jié)構(gòu)，可看作為無向圖，圖的頂點是城市，邊是城市之間所耗費的時間（要包括中轉(zhuǎn)站的時間）或旅費。(3) 數(shù)據(jù)的存儲結(jié)構(gòu)。采用鄰接表和鄰接矩陣都可作為數(shù)據(jù)的存儲結(jié)構(gòu)，這里建議采用鄰接矩陣作為數(shù)據(jù)的存儲結(jié)構(gòu)。(4) 用不同的功能模塊對城市信息和交通信息進行編輯。添加、修改、刪除功能可用菜單方式或命令提示方式。只要能方便的對城市信息和交通信息進行管理即可，但要注意人機界面，具體實現(xiàn)由學(xué)生自行設(shè)計，也可參考有關(guān)程序(屆時在網(wǎng)上提供)。這些工作有不小的工作量。(5) 最優(yōu)決策功能模塊 讀入城市信息和交通信息，用鄰接表生成含權(quán)網(wǎng)絡(luò)，表頭數(shù)組中的元素存放城市名及對方城市到達該元素所代表城市的所有信息；表頭數(shù)組中的元素所對應(yīng)的單鏈表存放與該元素所代表的城市有交通聯(lián)系的城市(代碼、里程、列車車次)。 根據(jù)具體最優(yōu)決策的要求，用floyd算法求出出發(fā)城市到其它各城市的最優(yōu)值(最短時間或最小的費用)，搜索過程中所經(jīng)過城市的局部最優(yōu)信息都保存在鄰接表的表頭數(shù)組中。其目的城市所代表的元素中就保存了所需的最優(yōu)決策結(jié)果。其相應(yīng)的初始值可為，并在表頭數(shù)組對應(yīng)的城市元素中保存響應(yīng)的信息。 主程序可以有系統(tǒng)界面、菜單；也可用命令提示方式；選擇功能模塊執(zhí)行，要求在程序運行過程中可以反復(fù)操作。三、測試數(shù)據(jù)：7046513491579138523688125112553北京徐州西安成都鄭州廣州上海四、概要設(shè)計本程序運用了關(guān)于圖這種數(shù)據(jù)結(jié)構(gòu)。它的抽象數(shù)據(jù)類型定義如下：typedef struct unDiGraph int numVerts; /結(jié)點 costAdj cost; /鄰接矩陣unDiGraph,*UNG;基本操作：unDiGraph* CreateCostG()操作結(jié)果：構(gòu)造帶權(quán)(費用)圖。unDiGraph* CreateTimeG()操作結(jié)果：構(gòu)造帶權(quán)（時間）圖。構(gòu)造飛機帶權(quán)(費用)圖。PathMat *Floyed(unDiGraph *D)操作結(jié)果：Floyed函數(shù) 求任意兩點的最短路徑。五、調(diào)用關(guān)系圖unDiGraph（圖）Floyed函數(shù) 求任意兩點的最短路徑CreateTimeG（構(gòu)造帶權(quán)時間）CreateCostG（構(gòu)造帶權(quán) 費用）6、 程序代碼#include #include #include #include #include #include #define INF 10000 /定義一個最大數(shù)定為無窮值#define MAX 7static int cnumber=7;static int k=0;static int v=0,z=0;/定義靜態(tài)變量typedef struct zhu/定義結(jié)構(gòu)體zhuint ccost;/定義結(jié)構(gòu)變量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;/結(jié)點costAdj cost;/鄰接矩陣unDiGraph,*UNG;typedef struct ceditchar 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;case(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)造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 *)malloc(sizeof(unDiGraph) /為G圖分配存儲空間。return(NULL); for(i=1;i=cnumber;i+)for(j=1;jcostij=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=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ù)組中的存放代碼pri();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);/構(gòu)造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;jcostij=INF;/初始化使G-costij為無窮。G-numV=cnumber; 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=z+1;/全局靜態(tài)變量，初始值為0.即1=0+1pri();cout火車時間編輯endl;cout請輸入開始城市的代碼a;cout請輸入結(jié)尾城市的代碼b;cout請輸入你的兩地時間mz.ctime;nz.ctime=a;xz.ctime=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選擇出錯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;jcostij;/初始化矩陣A,C。Cij=M-costij; Pathij=-1; /初始化權(quán)矩陣pfor(k=1;k=n;k+) /k為逐步加入的中間結(jié)點 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個中間點之后，i,j兩點的最佳路徑。Bij=Aij;/構(gòu)造A C 兩個任意節(jié)點上的最優(yōu)路徑所建造的矩陣，并分別賦給B L代表時間與花費Lij=Cij; else Bij=Aij; Lij=Cij; /end for循環(huán) coutn最短路徑為: endl;/end-Floyed/為了求從i到j(luò)的最短路徑，只需要調(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();/輸出城市列表及相應(yīng)代碼。cout請輸入起始城市和目的城市的代碼，中間以空格隔開Bcity;cinEcity;/輸入起始城市和終點城市的代碼。if (!(0Bcity&Bcitycnumber+1)&(0Ecity&Ecitycnumber+1)&Bcity!=Ecity)coutn出錯啦! 輸入城市號碼請在1-7之間，且兩城市代碼不能相等!8000|LBcityEcity8000) cout兩地間還沒有線路通過endl;elsecout火車花的時間是BBcityEcity小時endl; cout 輸入0.返回主菜單 endl; scanf(%d,&l); / h=l; while(h=1); /求最少花費路徑。void money() int Bcity,Ecity;/起始成市號碼和終點城市號碼 char l,h=1;do pri();/輸出城市列表及相應(yīng)代碼。cout請輸入起始城市和目的城市的代碼，中間以空格隔開Bcity;cinEcity;/輸入起始城市和終點城市的代碼。if (!(0Bcity&Bcitycnumber+1)&(0Ecity&Ecitycnumber+1)&Bcity!=Ecity) coutn出錯啦! 輸入城市號碼請在1-7之間，且兩城市代碼不能相等!8000|BBcityEcity8000)cout兩地間還沒有線路通過endl;elsecout火車花的錢是BBcityEcity元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 chose()/選擇最少時間或最小花費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) cout*endl;cout1:增加城市endl;cout2:添加或編輯火車費用endl;cout3:添加或編輯火車時間endl;cout0:返回主菜單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;cou