資料結構課程設計報告

交通諮詢系統設計

不用輸入程式語句，也不用那個截圖……不用太著急，報告周五之前給我就行了……列印和壓縮包都要哈！對了，這段文字記得刪掉啊嘿嘿~

題目名稱交通諮詢系統設計

院（系）管理學院

課程名稱資料結構課程設計

班級資訊 10-2

學生姓名呂德麗

指導教師李長雲

目錄一、需求分析及選題要求 3

1、問題描述 3

2、設計要求 3

3、實現提示 3

二、演算法設計 4

1．主程式流程圖： 4

2．建立圖演算法流程圖： 5

3.主選單操作演算法流程圖： 5

三、演算法設計關鍵意圖 6

四、拓展功能 6

1. 圖的結構建立 6

2.迪傑斯特拉演算法的改進 6

3.關於最快到達及時間的處理： 7

五、程式設計體會 7

題目名稱：交通諮詢模擬系統

處於不同目的的旅客對交通工具有不同的要求。編制乙個各個城市間的交通諮詢程式，為旅客提供兩種或三種最優決策的交通諮詢。

1)提供對城市資訊進行編輯（如：新增或刪除）的功能。

2)提供對列車時刻表進行編輯（增設或刪除）的功能。

3) 提供兩種最優決策：最快到達和最省錢到達。

4)旅途中耗費的總時間應該包括中轉站的等候時間。

5)諮詢以使用者和計算機的對話方式進行。由使用者輸入起始站、終點站、最優決策原則。輸出資訊：

最快需要多長時間才能到達或者最少需要多少旅費才能到達，並詳細說明於何時乘坐哪一趟列車到何地。

1) 對全國城市交通圖和列車時刻表進行編輯，應該提供檔案形式輸入和鍵盤輸入兩種方式。列車時刻表則需根據交通圖給出各個路段的詳細資訊。

2) 以鄰接表作交通圖的儲存結構，表示邊的結構內除含有鄰接點的資訊外，還應包括路程中耗費的時間和花費以及出發和到達的時間等多種屬性。

3）增加旅途中轉次數最少的最優決策。

1.問題分析和任務定義：根據設計題目的要求，充分地分析和理解問題，明確問題要求做什麼？（而不是怎麼做？）限制條件是什麼？

2.邏輯設計：對問題描述中涉及的操作物件定義相應的資料型別，並按照以資料結構為中心的原則劃分模組，定義主程式模組和各抽象資料型別。

邏輯設計的結果應寫出每個抽象資料型別的定義(包括資料結構的描述和每個基本操作的功能說明)，各個主要模組的演算法，並畫出模組之間的呼叫關係圖。

3.詳細設計：定義相應的儲存結構並寫出各函式的偽碼演算法。

在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易於除錯，抽象資料型別的實現盡可能做到資料封裝，基本操作的規格說明盡可能明確具體。詳細設計的結果是對資料結構和基本操作做出進一步的求精，寫出資料儲存結構的型別定義，寫出函式形式的演算法框架。

4.程式編碼：把詳細設計的結果進一步求精為程式語言程式。同時加入一些註解和斷言，使程式中邏輯概念清楚。

5.程式除錯：採用自底向上，分模組進行，即先除錯低層函式。

能夠熟練掌握除錯工具的各種功能，設計測試資料確定疑點，通過修改程式來證實它或繞過它。除錯正確後，認真整理源程式及其注釋，形成格式和風格良好的源程式清單和結果。

6.結果分析：程式執行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。演算法的時間、空間複雜性分析。

此次課程設計是對全國城市交通圖列車時刻表及飛機航班表的編輯。此次課設是利用vc工具在dos環境下實現全國交通的諮詢與管理。通過此次程式可以對全國城市之間火車與飛機進行兩方面的諮詢，即最少的時間與最少的費用的諮詢，從而方便旅客的出行。

通過此次課程設計，我要學會怎樣用在vc dos環境下程式設計，而且要通過此次課程設計加深對資料結構的理解，在設計中用鄰接表作交通圖的儲存結構，表示邊的結點中除含有鄰接點的資訊外，還包括交通工具、路程中消耗的時間和花費以及出發和到達的時間等屬性。圖中頂點城市的資訊，包括城市名稱、城市編號和依附該頂點的邊的指標。

在程式中，利用迪傑斯特拉演算法求花錢最少和花時間最少的交通方式。

採取鄰接表結構，為了便於刪除，加入flag域標誌是否是圖中頂點

迪傑斯特拉演算法是針對，兩點之間值存在一條邊，在本題中兩點之間存在不只一條邊，在設定dijkst初值的時候就不再是簡單的賦值，而是首先比較，改變dist的值，使用void copypath (pathtype &pa, int v, int w)後不是使用void insertpath (pathtype &pa, int v, int w);而是為得到dist初值和路徑初值專門設定的基本操作：

setpath(pathtype &pa, int v, int w, edgetype t)

其作用是設定第一條路徑使其是兩點之間最短路徑

程式與迪傑斯特拉主題演算法的區別主要在以下程式部份

p=g.adjlist[st].firstedge;

while(p) //初始化dist陣列檢測依附於起始點的每一邊

p=q;

}對於最快到達問題，理解到所謂最快到達一定是相對乙個擬出發時間而言的，只有有了擬出發時間才能夠求算。否則（如果是求取路上最短時間）要進行窮舉將所有路線的總時間進行比較，求取最小的才可以。求取最快到達時，應該讓使用者輸入擬出發時間，程式所做的是相對這個時間得到最快由a到b的路徑。

同樣對於乙個中間站，我們可以認為上一趟車的到達時間就是此時使用者的擬出發時間，在由此去尋求最快到達的，這樣又可以用迪傑斯特拉演算法，只是需要權值的計算不再是單純的乙個量的比較，而是下一站到站時間跟此時的擬出發時間之差，其餘演算法與計算最省錢路徑沒有區別。

通過此次課程設計大大加深了我對資料結構這門課程的理解，而且尤其對圖這章的理解，可以說有乙個大的進步。學習能力也大大提高。當然通過此次課設也為我以後的道路奠定了一定的基礎，認識到了基礎的重要。

當然此次課設中遇到的困難是再所難免的，因為我面對的課設是圖的內容，是乙個相對較難的內容，而且最短路徑的演算法也發了不少時間才有所深刻理解。但功夫不負有心人，只要肯努力，任何困難相信我們都可以克服與攻堅。

資料結構課程設計報告

資料結構課程設計報告

《資料結構》課程設計報告

資料結構課程設計報告

相關推薦