資料結構實驗指導書

修訂日期：2023年5月

修訂單位：電腦科學與技術系

執筆人：魏海平馮錫偉李文超

一、本大綱適用範圍：

電腦科學與技術專業；資訊與計算科學專業；軟體工程專業

二、實驗與實習內容要求

學時數：共32學時

內容包括線性表、串、樹形結構、圖形結構、排序和檢索共六部分。

要求：根據具體題目設計演算法和程式，並在計算機上實現，具體見實驗指導書。

1概述 3

1.1實驗目的 4

1.2 實驗要求 4

1.2.1驗證實驗的一般步驟 4

1.2.2設計實驗和綜合實驗的一般步驟 5

1.3實習報告內容 6

2 實驗指導書 6

2.1驗證性實驗 6

實驗一單鏈表操作驗證 6

實驗二二叉樹操作驗證 14

實驗三雜湊表的建立 16

2.2設計性實驗 18

實驗一統計候選人得票 18

實驗二漢諾塔問題 19

實驗三求無向連通圖的生成樹 20

實驗四順序查詢與折半查詢的效能比較 21

2.3綜合性實驗 22

實驗一約瑟夫環問題 22

實驗二迷宮最短路徑 23

實驗三靜態鍊錶實現對k個共享空間的棧進行操作的演算法 25

實驗四模擬旅館管理系統的乙個功能——床位的分配與** 26

實驗五串編輯 28

實驗六哈夫曼編碼 29

實驗七交通問題系統 30

實驗八醫院選址問題 32

實驗九查詢、排序演算法效率的實驗分析 33

實驗十簡單個人**號碼查詢系統 33

實驗十一各種排序演算法時間效能的比較 35

實驗十二機器排程問題 35

資料結構是一門實踐性很強的課程，只靠讀書和做習題是不能提高實踐能力的，尤其是在資料結構中要解決的問題更接近於實際。資料結構的實驗是對學生的一種全面的綜合訓練，與程式語言課程中的實驗不同，資料結構課程中的實驗多屬創造性的活動，需要學生自己分析問題，設計資料結構和演算法，再上機除錯和測試程式。資料結構實驗是一種自主性很強的學習過程，其教學目的主要有兩個:

(1)深化理解和掌握書本上的理論知識，將書本上的知識變「活」；(2)理論和實踐相結合，使學生學會如何把書本上有關資料結構和演算法的知識用於解決實際問題，培養資料結構的應用能力和軟體工程所需要的實踐能力。

為了達到上述目的，本書安排了如下三類實驗：

(1)驗證實驗：其主要內容是將書上的重要資料結構上機實現，深化理解和掌握理論知識，這部分的實驗不需要學生自己設計，只須將給定的方案實現即可；

(2)設計實驗：其主要內容是針對具體問題，應用某乙個知識點，自己設計方案，並上機實現，目的是培養學生對資料結構的簡單應用能力；

(3)綜合實驗：其主要內容是針對具體問題，應用某幾個知識點，自己設計方案，並上機實現，目的是培養學生對資料結構的綜合應用能力。

在驗證實驗中，由實驗目的、實驗內容、實現提示和實驗程式等4部分組成，其中實驗目的明確了該實驗要學生掌握哪些知識點；實驗內容規定了實驗的具體任務；實現提示給出了資料結構和演算法的設計方法；實驗程式給出了實驗的範例程式，並且在主教材的隨書光碟中有該實驗涉及到的資料結構的全部實現。在驗證實驗中，不要求但鼓勵學生在完成實驗任務的基礎上，對該實驗涉及的資料結構的其他實現方法進行探索。

在設計實驗和綜合實驗中，由問題描述、基本要求、設計思想、思考題等4部分組成，其中問題描述是為學生建立問題的背景環境，指明「問題是什麼」；基本要求是對問題的實現進行基本規範，保證預定的訓練意圖，使某些難點和重點不會被繞過去，而且也便於教學檢查；設計思想給出了設計資料結構和演算法的主要思路；思考題引導學生在做完實驗後進行總結和擴充。

雖然在設計實驗和綜合實驗中都給出了一定的設計方案，但是，學生不應拘泥於這些分析和設計，要盡量發揮想象力和創造力。對於乙個實際問題，每個人可能會有不同的解決辦法，本書給出的範例方案，只是希望把學生的思路引人正軌，提出了思考問題的方法，但是不希望限制學生的思維，鼓勵學生自己設計解決方案。

《資料結構》是一門實踐性很強的軟體基礎課程，為了學好這門課，每個學生必須完成一定數量的上機作業。通過本課程的上機作業，要求在資料結構的選擇和應用、演算法的設計及實現等方面加深對課程基礎內容的理解，同時，在程式設計方法以及上機操作等基本技能和科學作風方面受到比較系統和嚴格的訓練。

驗證實驗安排的內容在書上都能找到具體的實現方法，並且在主教材的隨書光碟中也都有相應的程式實現。這些驗證實驗是學生在學習完一種資料結構後進行的，對於深化理解和掌握相應資料結構具有很重要的意義。

1.預備知識的學習

由於篇幅所限，本書沒有整理驗證實驗所用到的預備知識，但主教材中的相關內容已經敘述得很清楚了，需要學生在實驗前複習實驗所用的預備知識。這需要學生有自主的學習意識和整理知識的能力。

2.上機前的準備

將實現提示中給出的資料型別和演算法轉換為對應的程式，並進行靜態檢查，儘量減少語法錯誤和邏輯錯誤。

很多學生在上機時只帶一本資料結構書或實驗指導書，而書上只有演算法設計而沒有實驗程式，於是就直接在鍵盤上輸入程式，結果不僅程式的輸入速度慢，而且編譯後出現很多錯誤。上機前的充分準備能高效利用機時，在有限的時間內完成更多的實驗內容。

3.上機除錯和測試程式

除錯程式是乙個辛苦但充滿樂趣的過程，也是培養程式設計師素質的乙個重要環節。很多學生都有這樣的經歷：花了好長時間去除錯程式，錯誤卻越改越多。

究其原因，一方面，是對除錯工具不熟悉，出現了錯誤提示卻不知道這種錯誤是如何產生的；另一方面，沒有認識到努力預先避免錯誤的重要性，也就是對程式進行靜態檢查。

對程式進行測試，首先須設計測試資料。在資料結構中測試資料須考慮以下兩種情況。（1）一般情況：

例如迴圈的中間資料、隨機產生的資料等；(2)特殊情況：例如迴圈的邊界條件、資料結構的邊界條件等。

4.實驗報告

在實驗後要總結和整理實驗報告。

設計實驗和綜合實驗的自主性比較強，涉及到的知識點也比較多，可以在課程設計中完成，設計實驗建議由單人完成，綜合實驗建議由多人完成，主要目的是為了培養資料結構的應用能力、軟體工程的規範訓練、團隊精神和良好的科學作風。

1.問題分析

在設計實驗和綜合實驗中的問題描述通常都很簡潔，因此，首先要充分理解問題，明確問題要求做什麼，限制條件是什麼，也就是對所要完成的任務做出明確的描述，例如，輸入資料的型別、值的範圍以及輸人的形式，輸出資料的型別、值的範圍以及輸出的形式，哪些屬於非法輸人，等等。在問題分析時還應該準備好測試資料。

2.概要設計

概要設計是對問題描述中涉及到的資料定義抽象資料型別，設計資料結構，設計演算法的偽**描述。在這個過程中，要綜合考慮系統的功能，使得系統結構清晰、合理、簡單，抽象資料型別盡可能做到資料封閉，基本操作的說明盡可能明確。而不必過早地考慮儲存結構，不必過早地考慮語言的實現細節，不必過早地表述輔助資料結構和區域性變數。

3.詳細設計

在詳細設計階段，要設計具體的儲存結構（即用c++描述抽象資料型別對應的類）以及演算法所需的輔助資料結構，演算法在偽**的基礎上要考慮細節問題並用c++描述。

此外，還要設計一定的使用者介面。資料結構課程實驗的主要目的是為了培養資料結構的應用能力，因此在實驗中不要求圖形介面，只要在螢幕上提示使用者每一步操作的輸入，並將結果物出即可。

4.編碼實現和靜態檢查

將詳細設計階段的結果進一步優化為c++程式，並完成靜態檢查。

很多初學者在編寫程式後都有這樣的心態：確信自己的程式是正確的，認為上機前的任務已經完成，檢查錯誤是計算機的事。這種心態是極為有害的，這樣的上機除錯效率是極低的。

事實上，即使有幾十年經驗的高階軟體工程師，也經常利用靜態檢查來查詢程式中的錯誤。

5.上機除錯和測試程式

掌握除錯工具，設計測試資料，上機除錯和測試程式。除錯正確後，認真整理源程式和注釋，給出帶有完整注釋且格式良好的源程式清單和結果。

6.總結並整理實驗報告

在實驗後要總結和整理課程設計報告。

⒈ 問題描述

包括實驗題目（問題描述）、實驗目的（實驗基本要求）、實驗內容（任務）、條件和約束的描述。

⒉ 設計

⑴ 資料結構設計和核心演算法設計描述；

⑵ 主控及功能模組層次結構；

⑶ 主要功能模組的輸入、處理(演算法框架描述)和輸出；

⑷ 功能模組之間的呼叫與被呼叫關係等。

⒊ 測試

測試範例，測試結果，測試結果的分析與討論，測試過程中遇到的主要問題及所採用的解決措施。

⒋ 使用說明和作業小結

⑴ 使用說明主要描述如何使用你的程式以及使用時的主要事項；

資料結構實驗指導書

資料結構實驗指導書

資料結構實驗指導書

資料結構實驗指導書

相關推薦