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

1、數(shù)據(jù)結(jié)構(gòu)課設(shè)課程名稱數(shù)據(jù)結(jié)構(gòu)課設(shè)題目名稱全國交通系統(tǒng)學(xué)生學(xué)院計算機專業(yè)班級學(xué)號學(xué)生姓名指導(dǎo)教師蔣2016年11月28日一.需求分析1）程序任務(wù)要求問題描述出于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。基本要求提供對城市信息進行編輯（如：添加或刪除）的功能。城市之間有兩種交通工具：火車和飛機。提供對列車時刻表和飛機航班進行編輯（增設(shè)或刪除）的功能。提供兩種最優(yōu)決策：最快到達或最省錢到達。全程只考慮一種交通工具。旅途中

2、耗費的總時間應(yīng)該包括中轉(zhuǎn)站的等候時間。咨詢以用戶和計算機的對話方式進行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具，輸出信息為：最快需要多長時間才能到達或者最少需要多少旅費才能到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。選做內(nèi)容增加旅途中轉(zhuǎn)次數(shù)最少的最優(yōu)決策。二.設(shè)計概要1）數(shù)據(jù)類型的定義本程序運用了關(guān)于圖這種數(shù)據(jù)結(jié)構(gòu)。ADTGraph數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集數(shù)據(jù)關(guān)系R：R=VRVR=|v,wCV且P（v,w）,表示從v至Iw的弧。謂詞P(v,w)定義了弧v,w的意義或信息基本操作P:CreateGraph(&G,YVR);初始條件：V是圖

3、的頂點集，VR是圖中弧的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖GoLocateVet(G,u);初始條件：圖G存在，u和G中頂點有相同的特征。操作結(jié)果：若G中存在頂點u,則返回該頂點在圖中的位置，否則返回其他信息。InsertVex(&G,v);初始條件：圖G存在，v和圖中頂點有相同特征。操作結(jié)果：在圖G中添加新頂點VoDeleteVex(&G,v);初始條件：圖G存在，v是G中某個頂點。操作結(jié)果：刪除G中頂點v及相關(guān)弧。InsertArc(&G,v,w);初始條件：圖G存在，v和w是G中兩個頂點。操作結(jié)果：在G中增添弧v,w,若G是無向的則還增加對稱弧w,w。DeleteArc(&G,v,w

4、);初始條件：圖G存在，v和w是G中兩個頂點。操作結(jié)果：在G中刪除弧v,w,若G是無向的，則還刪除對稱弧w,v。ADTGraph其他的抽象數(shù)據(jù)類型定義如下：typedefstructintnumber;floatexpenditure;intbegintime2;intarrivetime2;Vehide;/飛機或列車運行信息typedefstruct(VehidestataMAX_ROUTE_NUM;intlast;/航班次或列車次infolist;/弧的權(quán)的信息(車次或航班信息)typedefstructArcNode(intadjvex;structArcNode*nextarc;inf

5、olistinfo;ArcNode;/鄰接表節(jié)點，存入弧(交通路線)的信息typedefstructVNode(charcityname10;ArcNode*planefirstarc,*trainfirstarc;VNode,AdjListMAX_VERTEX_NUM;/頂點數(shù)組元素typedefstruct(AdjListvertices;intvexnum,planearcnum,trainarcnum;ALGraph;/圖結(jié)構(gòu)typedefstructNode(intadjvex;introute;structNode*next;Node;/輔助節(jié)點的存儲結(jié)構(gòu)typedefstruct

6、QNode(intadjvex;structQNode*next;QNode;/隊列節(jié)點，節(jié)點元素為int型typedefstruct(QNode*front;QNode*rear;LinkQueue;/隊列結(jié)構(gòu)typedefstructTimeNode(intadjvex;introute;intbegintime2;intarrivetime2;structTimeNode*childMAX_ROUTE_NUM;TimeNode,*TimeTree;求最短時間輔助樹structarc(intco;/列車或飛機編號charvt10;/起始城市charvh10;至I達城市intbt2;/起始時

7、間intat2;到達時間floatmo;/費用aMAX_ARC_SIZE;/存放邊信息2)操作函數(shù)voidAdminister(ALGraph*G);/*管理員操作*/voidcityedit(ALGraph*G);/*編輯城市節(jié)點*/voidCopyTimeTree(TimeTreep,TimeTreeq);/電制輔助樹*/voidcreatecityfile();/*創(chuàng)建城市文檔*/voidCreateGraph(ALGraph*G);/*創(chuàng)建圖*/voidcreateplanefile();/*創(chuàng)建航線文檔*/voidCreateTimeTree(TimeTreep,inti,intj,

8、LinkQueue*Q,infolist(*arcs)MAX_VERTEX_NUM);voidcreatetrainfile();/*創(chuàng)建列車路線文檔*/intDeleteplaneArc(ALGraph*G);voidDeleteQueue(LinkQueue*Q,int*x);intDeletetrainArc(ALGraph*G);voidDeleteVertex(ALGraph*G);voidDemandDispose(intn,ALGraphG);/*處理用戶請求*/voidDestoryTimeTree(TimeTreep);voidEnterplaneArc(ALGraph*G)

9、;voidEnterQueue(LinkQueue*Q,intx);voidEntertrainArc(ALGraph*G);voidEnterVertex(ALGraph*G);voidExpenditureDispose(intk,infolist(*arcs)MAX_VERTEX_NUM,ALGraphG,intv0,intvl,float*M,int*final);/*求取費用最少路線*/voidflightedit(ALGraph*G);voidinitgraph(ALGraph*G);/*初始化交通系統(tǒng)*/voidInitQueue(LinkQueue*Q);intIsEmpty(

10、LinkQueue*Q);intLocateVertex(ALGraph*G,char*v);voidMinExpenditure(infolistarcs,float*expenditure,int*route);voidMinTime(infolistarcs,int*time,int*route);voidPrintGraph(ALGraph*G);intsave(ALGraph*G);voidTimeDispose(intk,infolist(*arcs)MAX_VERTEX_NUM,ALGraphG,intv0,intv1,int(*T)2,int*final);/*求取用時最少的路

11、線*/voidTimeTreeDispose(Node*head,infolist(*arcs)MAX_VERTEX_NUM);一一voidtrainedit(ALGraph*G);voidTransferDispose(intk,infolist(*arcs)MAX_VERTEX_NUM,ALGraphG,intv0,intv1);/*求取中轉(zhuǎn)最少路線*/voidUserDemand(ALGraphG);voidVisitTimeTree(TimeTreep);voidLogIn(ALGraph*G);/*登錄管理員界面*/3)主程序的流程以及各程序模塊之間的調(diào)用關(guān)系初始化交通索文登統(tǒng)irn

12、tgr&thz一一一骰且城市鞘帽添加rityedit卜.一除系統(tǒng)管理Adniinister航班墉帽添加Hishtedit除,車次編相添加iranitdit刪除品少費用ExpeiiditueDiipose弱少時向TirneDispose聶少中轉(zhuǎn)次敷IransterDispose卮示飛機航班顯不列車車次三.詳細設(shè)計1)偽碼算法intmain()(界面初始化；輸入操作命令；While(“命令”！=“退出”)(接受命令(用戶輸入要實現(xiàn)功能)；進入各個處理命令函數(shù)；)voidTransferDispose(intk,infolist(*arcs)MAX_VERTEX_NUM,ALGraphG,intv0

13、,intv1)/求中轉(zhuǎn)站最少路徑該函數(shù)要用到存儲路徑的鏈?zhǔn)焦?jié)點數(shù)組*p和輔助隊列；V0入隊While(隊列不為空)If(v0的下一個連接頂點w未被訪問)將v0,w按順序存到鏈?zhǔn)綌?shù)組元素pw中If(w=v1)輸出路徑信息WA隊)下一個連接頂點(t=t-nextarc;)不存在v0到v1的路線)voidExpenditureDispose(intk,infolist(*arcs)MAX_VERTEX_NUM,ALGraphG,intv0,intv1,float*M,int*final)/求費用最少的路線該函數(shù)要用到存儲路徑的鏈?zhǔn)焦?jié)點數(shù)組*p和floatM,MV表示從起始城市V0到V的最少費用，標(biāo)志

14、數(shù)組final,finali=1表示V0到i已求得用費最少的路線，再通過i求其他最短路線，直到求到目的城市V1,這類似普利姆算法。首先是初始化M,final,p，先求得v0到各個節(jié)點的直接最少費用(若存在)，for(w=0;wG.vexnum;w+)查找M數(shù)組未被訪問的元素中值最少的元素vIf(v=v0)通過存儲路徑的鏈?zhǔn)焦?jié)點數(shù)組*p輸出完整路線Elsev存在，將v置已訪問狀態(tài)，更新M數(shù)組，若v0到w的費用通過前驅(qū)v會比原來少，就更新，更新輔助鏈?zhǔn)酱鎯?shù)組P,將w的前驅(qū)節(jié)點v加入到pw中不存在v0到v1的路線voidTimeDispose(intk,infolist(*arcs)MAX_VER

15、TEX_NUM,ALGraphG,intv0,intv1,int(*T)2,int*final)/求用時最少的路線該函數(shù)要用到存儲路徑的鏈?zhǔn)焦?jié)點數(shù)組*p和T,TV表示從起始城市V0到V的最少用時，標(biāo)志數(shù)組final,finali=1表示V0到i已求得用時最少的路線，再通過i求其他用時最短路線，直到求到目的城市V1,這類似普利姆算法。首先是初始化M,final,p,先求得v0到各個節(jié)點的直接最少用時(若存在)，for(w=0;wtfMinixpendruneTirY*eDiSfseUsiTMinil:UfltinlDLjposcHitUuejtrnLeiQjujeI】rh/wPiirUGidpI

16、EntcrQucueDelleteCJueueTimeTreeDisposeCreateTinieTreeCopyTimeTreeVisitTimeTreeDestory11meTree四.調(diào)試分析1）調(diào)試過程中遇到的問題的解決的以及對設(shè)計與實現(xiàn)的回顧討論和分析a.文件操作中遇到讀入錯誤或找不到文件；解決：通過參考譚浩強編著的C程序設(shè)計中的文件操作，文件寫入和讀取的格式和相關(guān)文件路徑的設(shè)置，最終解決問題b.獲取鍵盤輸入報錯解決：通過調(diào)試發(fā)現(xiàn)是因為粗心大意在用scanf函數(shù)是少打取地址符&c.形參使用不當(dāng)解決：查看教科書和上午查找相關(guān)的用法說明，最終解決問題2）算法的時空分析基本操作時空問問復(fù)復(fù)

17、雜雜度度voidLogIn(ALGraph*G)O(O(1)1)voidAdminister(ALGraph*G)O(O(1)1)voidcityedit(ALGraph*G)O(O(n)n)voidCopyTimeTree(TimeTreep,TimeTreeq)O(O(n)1)voidcreatecityfile()O(O(n)n)voidCreateGraph(ALGraph*G)O(O(n)n)voidcreateplanefile()O(O(1)1)voidCreateTimeTree(TimeTreep,inti,intj,LinkQueue*Q,infolist(*arcs)MA

18、X_VERTEX_NUM)O(n)O(n)voidcreatetrainfile()O(1)O(1)intDeleteplaneArc(ALGraph*G)O(n)O(n)voidDeleteQueue(LinkQueue*Q,int*x)O(1)O(1)intDeletetrainArc(ALGraph*G)O(n)O(n)voidDeleteVertex(ALGraph*G)O(n)O(n)voidDemandDispose(intn,ALGraphG)O(1)O(1)voidDestoryTimeTree(TimeTreep)O(n)O(1)voidEnterplaneArc(ALGra

19、ph*G)O(n)O(n)voidEnterQueue(LinkQueue*Q,intx)O(1)O(1)voidEntertrainArc(ALGraph*G)O(1)O(1)voidEnterVertex(ALGraph*G)O(n)O(n)voidExpenditureDispose(intk,infolist(*arcs)MAX_VERTEX_NUM,ALGraphG,intv0,intv1,float*M,int*final)O(n)O(1)voidflightedit(ALGraph*G)O(O(1)1)voidinitgraph(ALGraph*G)O(1)O(n)voidIni

20、tQueue(LinkQueue*Q)O(1)O(1)intIsEmpty(LinkQueue*Q)O(1)O(1)intLocateVertex(ALGraph*G,char*v)O(n)O(1)voidMinExpenditure(infolistarcs,float*expenditure,int*route)O(n)O(n)voidMinTime(infolistarcs,int*time,int*route)O(n)O(n)voidPrintGraph(ALGraph*G)O(1)O(n)intsave(ALGraph*G)O(1)O(1)voidTimeDispose(intk,i

21、nfolist(*arcs)MAX_VERTEX_NUM,ALGraphG,intv0,intv1,int(*T)2,int*final)O(n)O(n)voidTimeTreeDispose(Node*head,infolist(*arcs)MAX_VERTEX_NUM)O(n)O(n)voidtrainedit(ALGraph*G)O(1)O(1)voidTransferDispose(intk,infolist(*arcs)MAX_VERTEX_NUM,ALGraphG,intv0,intv1)O(n)O(n)voidUserDemand(ALGraphG)O(1)O(1)voidVis

22、itTimeTree(TimeTreep)0(n)O(n)3）經(jīng)驗和體會這次編程我很深的體會就是要有耐心，編寫程序本身是一件對大多數(shù)人來說很枯燥的事情，想想完成程序后的成就感對我來說是個不錯的方法。再有一點就是要細心，程序這種東西很矯情，融不舍得一點的差錯，也許錯一個小小的字母就會上我們的程序崩盤，所以我們要做到細心細心再細心，因為編譯軟件再厲害，還有他們找不到的錯誤。還有通過本次課程設(shè)計，我學(xué)到了一種程序設(shè)計方法，就是結(jié)構(gòu)化程序設(shè)計方法，在程序設(shè)計過程中，我嘗試按如下方法進行結(jié)構(gòu)化程序設(shè)計：（1）自頂向下；（2）逐步細化；（3）模塊化設(shè)計（4）結(jié)構(gòu)化編碼。這種設(shè)計方法的過程是將問題求解由抽象

23、逐步具體化的過程，而且，用這種方法便于驗證算法的正確性。五.用戶使用說明1）打開并運行程序，按任意鍵進入操作主界面，按提示進行相關(guān)操作；2）按“1”進入管理員登錄界面，登錄成功后可進入交通系統(tǒng)操作界面，按“2”進入用戶咨詢界面，按“3”顯示交通系統(tǒng)，按“4”則退出。3）進入管理員界面可鍵入“1”初始化交通系統(tǒng)，并選擇文檔初始化方式（如果是第一次使用該系統(tǒng)建議使用文檔初始化交通系統(tǒng)，免得自己進行繁冗的初始化操作）。4）進入用戶咨詢界面，可根據(jù)用戶需要進行相關(guān)的選擇，或是選擇“1”（最少旅行費用）；或是選擇“2”（最少旅行時間），又或者是選擇“3”（最少旅行中轉(zhuǎn)次數(shù)）等。5）進入顯示交通系統(tǒng)界面，

24、根據(jù)用戶選擇則可顯示城市、飛機航班、列車車次等信息?；蛘叻祷厣弦患壊藛?。六.測試結(jié)果開始界面效據(jù)靖枸深設(shè)由全國交通咨詢系統(tǒng)測試是用加zjszE軌件2母邱偉錚3115005282妗片片匕燈匕時燈時廿湍曲湍4#計附工亦彳。在工：注意；打開程序后需先通過管理員切始化交通系城！管理員名；root密碼：1234請不要泄露出去哦，一般人我都不告訴他的。請按任何健以維續(xù)，功能界面清選持桂手功能：匕口泣其其久久久底式二二，工“箕口久酎其以其電臺1=管理員管理*?*2=用戶咨用*/總*3=顯示交通系統(tǒng)*e附4=退由*怩呼即附片冷讖椰卿崢口情鈍匕能恥黜附艇畫生請輸入便的詵界：登錄界面|管理員名！root密碼工12

25、3密碼錯誤！請重新輸入！1234.管理項目界面請選界管理項目：黑即廣佇府，解建館3建館仆二建跳0:跳0二陽配。鄧屯*1:初始化交通系統(tǒng)*R*2=城市編輯+4fl*3=飛機就邪爆輯*用邪t4=列車車次編輯*電*+5=返向+*&明強。七日尚解。里日佇解時e娜讓安跑心翻!配賽邸?拆j請輸入您的選樣；請選擇初始化方式：注意：第一次初始化最好用文檔的方長（比較方便）【雕顏鮑朋命魂前魂顫蝕魄豳鮑鮑郵辨能的鯉6*1二文檔率*國+*2-鍵盤*0配函似過箕，毓覦鮑能鮑牌6例奧的幽做幼解前選擇？.請選擇城市編輯項目：1二增加城市2二刪除城市選擇?1請輸入新坦城市的名稱：南京確認?（/VM請選押飛機航班堀輯項目:1二新增航班2=刪除航班選擇？1請輸入新增飛機航班的信息：飛機航班編號：7超始好市：劃頭目的城市：廣州航班費用：456起飛時間:12:00到達時間: