1、數據結構課程設計參考樣例源程序下載題目：全國交通咨詢設計目的通過實習，了解并初步掌握設計、實現較大系統的完整過程，包括系統分析、 編碼設計、系統集成、以及調試分析，熟練掌握數據結構的選擇、設計、實現以及 操作方法，為進一步的應用開發打好基礎。問題描述(1)設計、實現一個全國大城市間的交通咨詢程序，為旅客提供三種最優決策方案: 時間最短(2)費用最小(3 )中轉次數最少。需求分析該程序所做的工作的是模擬全國交通咨詢，為旅客提供三種最優決策的交通咨詢。此程序規定：(1) 在程序中輸入城市名稱時，需輸入10個字母以內的字母串；輸入列車或飛機編號時需輸入一個整型數據； 輸入列車或飛機的費用時需輸入一個

2、實型數據；輸入列車或飛機開始時間和到達時間時均需輸入兩個整型數據(以hh：mm的形式)；在選擇功能時，應輸入與所選功能對應的一個整型數據。(2) 程序的輸出信息主要是：最快需要多少時間才能到達，或最少需要多少旅費才能到達，或最少需要多少次中轉到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。(3) 程序的功能包括：提供對城市信息的編輯，提供列車時刻表和飛機航班表 的編輯，提供三種最優決策：最快到達、最省錢到達、最少中轉次數到達。四概要設計系統用到的抽象數據類型定義：1 ADT Graph數據對象V: 個集合，該集合中的所有元素具有相同的特性 數據關系R： R=VRVR=<x,y

3、>|P(x,y)A(x,y屬于 V)基本操作：(1)in itgraph(&G)；(2)CreateGraph(&G)；(3)En terVertex(&G)；(4)DeleteVertex(&G)；(5)En terpla neArc(&G)；(6)Deletepla nArc(&G)；(7)En tertrai nArc(&G)；(8)DeletetrainArc(&G);ADT Graph2 . ADT LinkQueue數據元素：可以是任意類型的數據，但必須屬于同一個數據對象 關系：隊列中數據元素之間是線性關系。基本

4、操作：(1)Ini tQueue(&Q);(2)IsEmpty(&Q);(3)EnterQueue(&Q,x);(4)DeleteQueue(&Q,&y);ADT Lin kQueue3 . ADT TimeTree數據對象D: 個集合，該集合中的所有元素具有相同的特性數據關系R：若D為空，則為空樹。若 D中僅含有一個數據元素，則R為空集，否則R=H, H為如下二元關系：(1) 在D中存在唯一的稱為根的數據元素root ,它在關系H中沒有前驅(2) 除root以外，D中每個結點在關系H下有且僅有一個前驅。基本操作：(1) CreateTimeTree(p

5、,i,j，&Q,i nfolist arcs);(2) CopyTimeTree(p,q);(3) VisitTimeTree(p);ADT TimeTree系統中子程序及功能要求: 1.Administer(ALGraph *G)2.3.4.5.6.:提供管理員管理城市交通系統的界面，通過該子程 序可調用其他管理交通系統的子程序。:初始化交通系統的子程序in itgraph(ALGraph *G):創建城市文件的子程序:創建航班文件的子程序:創建列車時刻表文件的子程序:提供城市名在城市交通系統中相應的編 號createcityfile() createpla nefile() cre

6、atetra in file() LocateVertex(ALGraph *G,char *v)9. EnterVertex(ALGraph *G):10. DeleteVertex(ALGraph *G)11. flightedit(ALGraph *G):12. EnterplaneArc(ALGraph *G)13. DeleteplaneArc(ALGraph *G)7. CreateGraph(ALGraph *G):創建城市交通系統8. cityedit(ALGraph *G):提供城市編輯功能 提供在城市交通系統中加入城市的功能:提供在城市交通系統中刪除城市的功 能提供航班編輯

7、功能:提供在城市交通系統中加入航班的功 能:提供在城市交通系統中刪除航班的功能14： trainedit(ALGraph *G):提供列車車次的編輯功能15. EntertrainArc(ALGraph *G):提供在城市交通系統中加入列車車次的功能16. DeletetrainArc(ALGraph *G):提供在城市交通系統中刪除列車車次的功能17. UserDemand(ALGraph G):提供用戶咨詢的界面18. DemandDispose(int n,ALGraph G):通過該子程序調用其他咨詢子程序19. InitQueue(LinkQueue 創建交通圖算法的偽碼描述如下：i

8、nt LocateVertex(ALGaph *G ,char *v)/* 找出城市名在圖中對應結 點位置*/for(k=0;kv 圖 G 中的結點個數 G->vexnum;k+)Q):初始化隊列20. EnterQueue(LinkQueue *Q,int x) :入隊操作21. DeleteQueue(LinkQueue *Q,int *x):出隊操作22. IsEmpty(LinkQueue *Q):隊列判空操作23. TransferDispose(int k,infolist(*arcs)MAX_VERTEX_NUM, (*arcs)MAX_VERTEX_NUM ,ALGrap

9、h G,ALGraph G,i nt v0,i nt v1) :提供最少中轉次數決策的功能24 . MinExpenditure(infolist arcs,float *expenditure,float *route) :提供兩個城市之間最少費用的功能25 . ExpenditureDispose(int k, infolist (*arcs)MAX_VERTEX_NUM,ALGraph G, i nt v0,i nt v1,float *D,i nt *fin al):提供最少費用決策的功能26 . MinTime(infolist arcs,float *time,float *rou

10、te):提供兩個城市之間最短時間的功能27 . TimeTreeDispose(Node *head,infolist(*arcs)MAX_VERTEX_NUM):提供兩個之間相隔一個以上城市的城市間的最短時間的功能28 . CreateTimeTree(TimeTree p,int i,int j,Lin kQueue *Q,i nfolist(*arcs)MAX_VERTEX_NUM):創建時間樹29 . CopyTimeTree(TimeTree p,TimeTree q):復制時間樹30 . VisitTimeTree(TimeTree p):訪問時間樹31 . DestoryTime

11、Tree(TimeTree p) :銷毀時間樹32 . TimeDispose(i nt k,i nfolist (*arcs)MAX_VERTEX_NUM,ALGraphG,i nt v0,i nt v1,float *D,i nt *fin al):提供最少時間決策的功能33 : PrintGraph(ALGraph *G):顯示整個城市交通系統主函數可調用子程序 1,17,33子程序1可調用子程序2, 8,11,14子程序2可調用子程序3, 4,5,7子程序7, 12, 13, 15,16可調用子程序子程序8可調用子程序9, 10子程序11可調用子程序12,13子程序14可調用子程序15

12、,16子程序17可調用子程序18子程序18可調用子程序23,25,32子程序23可調用子程序19,29,21, 22子程序25可調用子程序24子程序32可調用子程序26,27子程序27可調用子程序28,30,31子程序28可調用子程序29* 各程序模塊之間的調用關系(子程序編號見上)6五.詳細設計if（第k個結點中的城市名與傳過來的城市名相同）j=k;/* 記錄位置 */break; 返回 k 的數值；int CreatGraph（ALGraph *G）if（打開城市文件，文件指針返回值為空）輸出錯誤文件信息；程序返回值為 0；while（文件不為空）將文件指針所指的字符串讀到城市名數組cit

13、yi中；i+;關閉文件；j=0;while（j< 城市個數）將 cityi 中的內容復制到圖的結構體的結點數組中 ;圖的結構體其他項負初值 ;j+;G->vexnum=i;打開航班信息文件 "plane.txt"將文件中的內容以塊為單位讀到緩沖區數組 a 中； 關閉文件； a 的計數變量 k=0;弧的計數變量 arc_num=0;while（k< 信息個數 ）調用函數 LocateVertex（G,ak.vt） 得到起始結點的位置i；調用函數 LocateVertex（G,ak.vt） 得到起始結點的位置j；q=G->verticesi.planfi

14、rstarc;m=0;while（q!=NULL）if（弧q中的鄰接頂點與j相等）將數組 ai 中的內容都復制到弧 q 中；m=1;break;q=q->nextarc;if(m=O);開辟一個弧結點；將數組ai中的內容都復制到新的弧結點中；將弧結點連接到適當的位置中去；arc_num+; _k+;G->planarcnum=arc_num;打開列車信息文件"plane.txt"將文件中的內容以塊為單位讀到緩沖區數組a中；關閉文件；a的計數變量k=0;弧的計數變量 arc_num=0;while(kv信息個數)調用函數 LocateVertex(G,ak.vt)

15、得到起始結點的位置 i ； 調用函數 LocateVertex(G,ak.vt)得到起始結點的位置 j ； q=G->verticesi.trainfirstarc;m=0;while(q!=NULL)if(弧q中的鄰接頂點與j相等)將數組ai中的內容都復制到弧q中；m=1;break;q=q->nextarc;if(m=0);開辟一個弧結點；將數組ai中的內容都復制到新的弧結點中；將弧結點連接到適當的位置中去；arc_num+;k+;G->trainarcnum=arc_num;返回；*創建航班算法的偽碼描述如下：creatplanefile()while(flag)/*f

16、lag 為標志位，初值為 1*/提示“輸入航班信息”；輸入航班code;輸入航班的出發城市 vt;輸入航班的到達城市vh;輸入機票價格 money;輸入航班的出發時間 bt;輸入航班的到達時間at;a.count.co=code;/* a為程序頭部定義的結構體*/strcpy（a.count.vt,vt）;strcpy（a.count.vh,vh）;a.count.bt=bt;a.count.at=at;a.count.mo=money;計數值count+1;提示 是否要繼續輸入航班信息：”；scanf（ “ d'，&flag）;if（航班文件不能以讀寫形式打開）提示“無法打開

17、文件”；將計數值count寫入航班車文件；for（i=O;ivcount;i+）if（無法將ai寫入航班文件）提示“文件無法寫入”；關閉航班文件；刪除城市結點算法的偽碼描述如下：DeleteVertex（ALGraph *G）/* G是程序頭部定義的結構體 */提示“輸入刪除城市名”；gets（城 市名：v）;提示“是否確定要刪除（Y/N）“；c=getchar（）;if（c= ' Y' |c= ' y'）n=0;/*0是記數標志，控制循環次數*/while（n圖G表頭接點總個數 &&圖G的存儲城市名與 v不同） /*G表頭結點總個數比實際大1*

18、/記數值n+1;if（n =圖G表頭結點總個數）提示“無法找到此城市“；elsei=LocateVertex（G ,v）;/*利用G函數找到此城市名所處在G中位置*/刪除從此結點出發的所有航班弧；刪除從此結點出發的所有列車弧；for（j=i;jv圖G表頭結點總個數-1 ； j+）將G第j個結點的信息依前移1位；將G第j個結點的信息制空；/*以下是刪除所有指向此結點的航班弧*/for（k=O;kv圖G表頭記點總個數-1 ； k+）p指向圖G中k結點的第一條飛機弧；while （ p ！ =NULL ） if （該弧指向的頂點位置（p-adjvex ）i）將該弧指向頂點位置-1 ；q=p ；p指向

19、下一條飛機弧;else if (該弧指向的頂點位置( p->adjvex ) = = i) if (p指向圖G中k結點的第一條飛機弧) m=p ；將圖 G 中 k 結點的第二條飛機弧改為第一弧； p 指向下一條飛機弧；釋放( m)；else將p的下一條弧賦給 q的下一條弧； m=p；p 指向下一條飛機弧； 釋放( q)；elseq=p；p 指向下一條飛機弧；/*以下是刪除所有指向此結點的列車弧 */ for(k=0;k< 圖 G 表頭記點總個數 -1； k+)p指向圖G中k結點的第一條列車弧；while( p！=NULL ) if (該弧指向的頂點位置(p->adjvex )

20、>i)將該弧指向頂點位置 -1；q=p；p 指向下一條列車弧；else if (該弧指向的頂點位置( p->adjvex )=i) if(p 指向圖 G 中 k 結點的第一條列車弧) m=p ；將圖 G 中 k 結點的第二條列車弧改為第一弧； p 指向下一條列車弧；釋放( m)；else 將 p 的下一條弧賦給 q 的下一條弧； m=p；p 指向下一條列車弧； 釋放( q )；elseq=p；p 指向下一條列車弧；圖 G 表頭結點總個數 -1； else return；求城市vO, v1之間的最少費用算法的偽碼描述如下：Expe nditureDispose()for(v=0 ；

21、v<城市個數；v+) 城市v還未求得最少費用；*(D+v)= 城市vO到v的最少費用；將城市v的路徑設置為空；if(最少中轉次數算法的偽碼描述如下：求城市V0到城市v1的最少中轉次數TransferDispose()for(v=0 ； wG.vexnum ； v+)城市v設為未訪問； 城市v的路徑設為空；將城市V0設為已訪問；將城市V0入隊；(D+v)<INFINITY)將城市v0和v加入到城市v的路徑中；城市v0到城市v0的最少費用為0；城市v0設為已求得最少費用；for(i=1； i< 城市個數；v+)m=INFINITY;for(w=0； w<城市個數；w+)if

22、(城市w未求得最少費用)if(*(D+w)<m)v=w;m=*(D+w);if(v 等于 v1)根據城市v的路徑輸出從城市 v0到城市v1所需經過的城市及路線;輸出最少費用*(D+v1)；返回；else將城市v設為已求得最少費用；for(w=0 ； <G.vexnum; w+)if(城市w未求得最少費用并且從城市v到w有路徑)求出從城市v到城市w的最少費用及路線；if(*(D+w)>m+ 城市v到w的最少費用)*(D+w)=m+ 城市v到w的最少費用；將城市w的路徑改成城市v的路徑并在最后加入城市w；輸出沒有列車或飛機從城市 v0到v1 ；while（隊列不空）隊首城市v出隊

23、；w為與城市v相連的第一個城市；while（w 存在）if（城市w未訪問）將城市w設為已訪問； 將城市w的路徑改為城市 v的路徑并在最后加入城市w；if（w 等于 v1）根據城市w的路徑輸出從城市 v0到城市v1所需經過的城市及路線; 返回；將城市w入隊；w等于城市v相連的下一個城市；輸出沒有列車或飛機從城市v0到v1 ； 求城市v0，v1之間的最少時間算法的偽碼描述如下：TimeDispose（） for（v=0 ； v城市個數；v+）城市v還未求得最少時間； *（D+v）=城市v0到v的最少時間； 將城市v的路徑設置為空； if（*（D+v）vlNFINITY）將城市v0和v加入到城市v的

24、路徑中；城市v0到城市v0的最少時間為0； 城市v0設為已求得最少時間； for（i=1 ； i城市個數；v+）m=INFINITY;for（w=0 ； w 城市個數； w+）if（城市w未求得最少時間）if（*（D+w）m）v=w; m=*（D+w）;if（v 等于 v1）根據城市v的路徑輸出從城市 v0到城市v1所需經過的城市及路線; 輸出最少時間v1； 返回；else將城市v設為已求得最少時間；for（w=0 ； vG.vexnum ； w+）if（城市w未求得最少時間并且從城市v到w有路徑）保存城市w原來的路徑； 將城市w的路徑設為城市 v的路徑并在最后加入城市 w； 利用時間樹求出從

25、城市 v0城市w的最少時間及路徑； if（*（D+w）從城市v0到城市 w的最少時間）*(D+w)= 從城市 v0 到城市 w 的最少時間； else將城市 w 的路徑還原；輸出沒有列車或飛機從城市 v0 到 v1；六測試分析按照附錄中的測試數據，得出如下測試、分析結果：1. 操作員管理功能 .1>. 當我們從鍵盤輸入有關圖的頂點及弧的信息后 ,用顯示圖的函數驗證 ,DOS 中顯示的 圖的信息與從鍵盤輸入的信息相同 ,表明交通系統可以從鍵盤正確輸入信息 .2>. 我們事先建立了有關圖的 3 個文本文件 ( 包括 city.txt,plan.txt,train.txt), 在交通系統

26、 程序中 ,選擇從文本文件輸入圖的信息后,用顯示操作驗證 , 表明文本文件的內容可以正確調入圖的結構體中 ,說明交通系統可以從文本文件中讀取信息.3>. 當從鍵盤或文本文件初始化交通圖后,測試增加或刪除城市結點 ,增加或刪除航班或列車弧 ,以上各功能都正確 .2. 交通咨詢功能 .1>. 火車情況 .1.1>.最少費用 .a. 兩地間無中轉且有多輛火車 .北京 鄭州輸出結果為 :旅行路線是 :乘坐 NO.27 列車車次在 13： 15 從 Beijing 到 zhengzhou. 最少旅行費用是 78 元 .而若選擇 NO.41 則花費為 80 元 .結果正確 .b. 兩地之

27、間無中轉達且只有一輛火車 .西安 武漢輸出結果為 :旅行路線是 :乘坐NO.218列車車次在 1: 34從xi ' a到 wuhan.最少旅行費用是178.00元.結果正確 .c. 兩地之間有中轉 .昆明 北京輸出結果為 :旅行路線是 :乘坐 NO.323 列車車次在 16.： 31 從 kunming 到 Guangzhou.乘坐 NO.59 列車車次在 3： 39 從 Guangzhou 到 shanghai.乘坐 NO.41 列車車次在 0： 35 從 shanghai 到 zhengzhou.乘坐 NO.27 列車車次在 13： 42 從 zhengzhou 到 Beijing

28、. 最少旅行費用是 462 元 .而若選擇 昆明 - 武漢 - 蘭州 - 北京 則花費為 506 元 .若選擇 昆明 - 武漢 - 西安- 鄭州 - 北京 則花費為 472元.結果正確 .1.2> 最短時間 .a. 兩地間無中轉且有多輛火車 .北京 鄭州輸出結果為 : 旅行路線是 : 乘坐 NO.41 列車車次在 13： 15 從 Beijing 到 zhengzhou. 最少旅行時間是 7： 57.結果正確 .b.兩地之間無中轉達且只有一輛火車.烏魯木齊 蘭州輸出結果為 :旅行路線是 :乘坐 No.371 列車車次在 0：35 從 wulumuqi 到 lanzhou. 最少旅行時間是

29、 10： 48.結果正確 .c. 兩地之間有中轉 .廣州 蘭州輸出結果為 : 旅行路線是 :乘坐NO.59列車車次在 3: 39從guangzhou到shanghai. 乘坐 NO.41 列車車次在 0： 35 從 shanghai 到 zhengzhou. 乘坐NO.41列車車次在 9.40從zhengzhou到Beijing. 乘坐 NO.134 列車車次在 19.24 從 Beijing 到 lanzhou. 最少旅行時間是 54: 49.結果正確 .1.3>. 最短周轉次數 .a. 兩地可直達且有中轉 .昆明 - 廣州 輸出結果為 : 旅行路線是 :乘坐 NO.323 列車車次在

30、 16: 31 從 kunming 到 guangzhou. 最少旅行中轉次數是 0次 .而若選擇 昆明 - 武漢 - 長沙 - 蘭州 則 結果為 3. 結果正確 .b. 兩地間有多條中轉路徑.昆明 - 上海 輸出結果為 : 旅行路線是 :乘坐 NO.323 列車車次在 16: 31 從 kunming 到 guangzhou. 乘坐 NO.59 列車車次在 3: 39 從 guangzhou 到 shanghai. 最少旅行總轉次數是 1 次 .而若選擇 昆明 - 武漢 - 西安 - 鄭州 - 上海 則 結果為 4. 結果正確 .2.飛機情況 .2.1>. 兩地無直達 .蘭州 - 武漢

31、輸出結果為 : 不存在飛機航班從 lanzhou 到 wuhan.2.2>.兩地無直達 .拉薩 - 昆明a.最少費用：輸出結果為 :乘坐 NO.173 飛機航班在 10： 20 從 lasa 到 kunming.最少旅行費用是 830 元. 結果正確 .b.最短時間： 輸出結果為 ： 乘坐 NO.173 飛機航班在 10： 20 從 lasa 到 kunming. 最少旅行時間是 1： 25.結果正確 .c最短中轉次數.輸出結果為 ：乘坐 NO.173 飛機航班在 10： 20 從 lasa 到 kunming. 最少旅行中轉次數是 0 次.結果正確 .2.3>兩地可中轉 .廣州

32、北京a.最少費用： 輸出結果為 ：乘坐 NO.2323 飛機航班在 10：15 從 Guangzhou 到 xi 'an.乘坐NO.210飛機航班在12: 35從xi ' a到beijing. 最少旅行費用是 2250 元 .結果正確 .b. 最短時間 ：輸出結果為 ：an.乘坐 NO.2323 飛機航班在 10: 15 從 Guangzhou 到 xi ' 乘坐NO.210飛機航班在12： 35從xi ' a到beijing. 最少旅行時間是 4: 00.結果正確 .c最短中轉次數.輸出結果為 ：乘坐 NO.2323 飛機航班在 10： 15 從 Guangz

33、hou 到 xi ' an. 乘坐NO.210飛機航班在12: 35從xi ' a到beijing.最少旅行中轉次數是 1 次. 結果正確 .3. 打印打印結果正確 ;4. 退出能正確退出七使用說明1 運行程序，首先出現主界面。主界面包括四個選項：選項一：管理員管理界面，選擇該項可進行城市交通系統的管理，具體使用說明見說明2;選項二：用戶咨詢界面，選擇該項可進行最少費用、最少時間、最少中轉次數的決策咨詢，具體 使用見說明7;選項三：顯示城市交通系統程序，選擇該項可顯示城市交通系統 的所有信息，包括城市、航班和列車車次；選項四：退出程序，選擇該項將退出 程序。2 管理員管理界面包

34、括 5個選項：選項一：初始化城市交通系統界面，可進行城市交通系統的初始化，具體使用見說明3;選項二：城市編輯界面，可進行城市的增加和刪除，具體使用見說明4;選項三：航班編輯界面，可進行航班的增加和刪除，具體使用見說明5;選項四：列車車次編輯界面，可進行列車車次的增加和刪除，具體使用見說明 6;選項五：返回上一級菜單，可返回主界面。3 .初始化城市交通系統界面包括兩個選項：選項一：通過鍵盤初始化城市交通系統，選擇該項后程序將給出輸入說明，按輸入說明用戶需逐 步輸入城市、航班、列車車次的信息來對城市交通系統初始化。在輸入航班和 列車信息時需注意兩點：a.所輸入的航班和列車的發車時間均在同一天。b.

35、若發車時間小于到達時間，則說明列車在同一天到達，若發車時間大于到達時間， 則說明列車在次日達到。飛機航班也是如此；選項二：通過文檔初始化城市交 通系統，選擇該項可用文檔進行初始化，但文檔必須存在于程序的同一目錄下， 且必須包含 CITY, PLANE TRAIN三個文本文檔，否則程序將提示出錯。4 城市編輯界面包括兩個選項：選項一：增加城市，可在城市交通系統中加入新的城市，若用戶輸入的是已有的城市名，程序將提示出錯；選項二：刪除城市，可 在城市交通系統中刪除城市，用戶必須輸入一個已有的城市名，否則程序提示出 錯。5 航班編輯界面包括兩個選項：選項一：增加航班，可在兩個城市之間新增航班，選擇該項后用戶需輸入新增航班的編號，起始城市，到達城市及費用、時間等信息；選項二，刪除航班，可刪除兩個城