資料結構
實驗指導書
資料結構課程組
廣東工業大學計算機學院
2023年4月
第1章概述
1.1 課程、教材和實驗
資料結構是電腦科學的演算法理論基礎和軟體設計的技術基礎，主要研究資訊的邏輯結構及其基本操作在計算機中的表示和實現。資料結構不僅是計算機專業的核心課程，而且已成為其他理工專業的熱門選修課。課程的教學要求之一是訓練學生進行複雜程式設計的技能和培養良好程式設計的習慣, 其重要程度決不亞於知識傳授。
因此，在資料結構的整個教學過程中, 完成習題作業和上機實習是兩個至關重要的環節。
習題的作用在於幫助學生深入理解教材內容, 鞏固基本概念, 達到培養良好程式設計能力和習慣的目的。從認知的程度劃分，資料結構的習題通常可分為三類：基礎知識題、演算法設計題和綜合實習題。
基礎知識題主要是檢查對概念知識的識記和理解，一般可作為學生自測題。演算法設計題的目的是練習對原理方法的簡單應用，多數是要求在某種資料儲存結構上實現某一操作，是資料結構的基礎訓練，構成了課外作業的主體。綜合實習題則訓練對知識的綜合應用和軟體開發能力，主要是針對具體應用問題，選擇、設計、和實現抽象資料型別（adt）的可重用模組，並以此為基礎開發滿足問題要求的小型應用軟體，應將其看作軟體工程的綜合性基礎訓練的重要一環，給予足夠的重視。
本實驗指導書為採用下列教材的資料結構課程而編寫：
[1] 嚴蔚敏，吳偉民. 《資料結構》（c語言版，含光碟）. 清華大學出版社，2002.9
[2] 嚴蔚敏，吳偉民. 《資料結構題集》（c語言版）. 清華大學出版社，1999.2
其中，《資料結構題集》實際上是一本較全面的學習和實驗指導書。本實驗指導書根據教學計畫給予一些補充，與上述兩本教材配合使用。
《資料結構題集》的第一篇為習題篇，含有三百餘道習題，組織成十二章，分別對應教科書中各章內容，並在每章之前給出該章的內容提要和學習要求。這些習題是作者在多年教學過程中所積累資料的基礎上，參考大量國外教材之後精心設計而成的。書中對特別推薦的題目作了標記，並對每道習題的難易程度按五級劃分法給出了難度係數。
第二篇為實習篇，分別以抽象資料型別、線性表、棧和佇列、串、陣列和廣義表、樹和圖以及查詢和排序為核心，設定了七組上機實習題，每組有3至9個題目供學生自由選擇。期望這些實習題能對習題起到良好的擴充作用，使學生受到涉及「從問題到程式」的應用軟體設計的完整過程的綜合訓練，培養合作能力，成為將來進行軟體開發和研究工作的「實踐演習」。
資料結構是實踐性很強的課程，光是「聽」和「讀」是絕對不夠的。在努力提高課堂教學的同時，必須大力加強對作業實踐環節的要求和管理。國內外先進院校一般都要求修讀資料結構的學生每週應不少於4個作業機時，而且有一套嚴格的作業和實習規範和成績評定標準，形成行之有效的教學質量保證體系。
《資料結構題集》強調規範化在演算法設計基本訓練中的重要地位。在習題篇中給出了演算法書寫規範，在實習篇中給出了實習步驟和實習報告的規範。教學經驗表明，嚴格實施這些貌似繁瑣的規範，對於學生基本程式設計素養的培養和軟體工作者工作作風的訓練，將能起到顯著的促進作用。
資料結構及其演算法的教學難點在於它們的抽象性和動態性。雖然在書本教材和課堂授課（板書或投影膠片）中採用圖示可以在一定程度上化抽象為直觀，但很難有效展現資料結構的瞬間動態特性和演算法的作用過程。在隨教科書配發的光碟中，「資料結構的演算法動態模擬輔助教學軟體dsdemo」是為學習並掌握資料結構中各類典型演算法而開發的乙個輔助教學軟體，可對教科書中八十餘個典型演算法進行動態互動式跟蹤演示，在演算法執行過程中實現資料結構和演算法的動態同步視覺化，使學生獲得僅從教材文字說明中無法獲得的直觀知識。
軟體既可用於課堂講解演示，又能供個人課外反覆觀察、體會和理解，對提高教學質量和效率有顯著效果。在習題篇的每一章列舉了與該章相關的演算法清單，並在《資料結構題集》附錄中提供該軟體完整的使用說明。
1.2 實驗安排
根據教學計畫，資料結構課程的實驗和上機由三部分構成：
1． 演算法設計實驗和上機（30機時）
在「資料結構演算法設計作業系統」上機完成40道題，學有餘力的同學還可以選做另外40道題。
2． 抽象資料型別的實現（6學時設計性實驗）
實現乙個抽象資料型別，並對所採用的儲存結構和相關操作的實現進行討論。
3． 課程設計（一周綜合性實驗）
完成《資料結構題集》中的乙個實習題。
第2章演算法設計實驗和上機
2.1 資料結構習題概述
《資料結構題集》把資料結構的習題分為「基礎知識題」和「演算法設計題」兩類。
「基礎知識題」主要供學生進行自測和複習之用，目的是幫助學生深化理解教科書的內容，澄清基本概念、理解和掌握資料結構中分析問題的基本方法和演算法要點，為完成演算法設計題做準備。
「演算法設計題」則側重於基本程式設計技能的訓練，相對於實習題而言，這類程式設計習題屬於偏重於編寫功能單一的「小」程式的基礎訓練，然而，它是進行複雜程式設計的基礎，是本課程習題作業的主體和重點。
各章的題量根據教學內容的多少和重要程度而定，幾乎對教科書的每一小節都安排了對應的習題。但對每個學生來說，不必去解全部習題，而只須根據自己的情況從中選擇若干求解即可。為了表明題目的難易程度，便於學生選擇，在每個題的題號之後注了乙個難度係數，難度級別從①至⑤逐漸加深，其區別大致如下：
難度係數為①和②的習題以基礎知識題為主；難度係數為③的習題以程式設計基礎訓練為主要目的，如強化對「指標」的基本操作的訓練等；習題中也收納了不少難題，其難度係數設為④和⑤，解答這些題可以激起學習潛力較大的學生的興趣，對廣泛開拓思路很有益。但習題的難度係數也只是乙個相對量，學生的水平將隨學習的進展而不斷提高，因此沒有必要去比較不同章節的習題的難度係數，此外，該難度系數值的假設是以學生沒有參照習題的解答或提示為前提的。
「循序漸進」是最基本的學習原則。學習者不應該片面追求難題。對於解難度係數為i的習題不太費力的學生，應試試難度係數為i+1的習題，但不要把太多的時間浪費在難度係數為i+2的習題上。
「少而精」和「舉一反三」是實踐證明行之有效的。解答習題應注重於「精」，而不要求「多」。為此，在一些值得向學生推薦的「好題」題號前加註了標記◆。
把握住這些「關鍵點」，就把握住了資料結構習題、乃至資料結構課程的總脈絡。
2.2 演算法設計的上機作業要求
1．使用anyview c語言和演算法書寫規範寫出書面作業的演算法（函式），作為上機前的準備。
需要強調的是「演算法的可讀性」。演算法是為了讓人來讀的，而不是供機器讀的。初學者總是容易忽視這一點。
演算法的真正意圖主要在於提供一種在程式設計者之間交流解決問題方法的手段。因此，可讀性具有頭等的重要性。不可讀的演算法是沒有用的，由它得到的程式極容易產生很多隱藏很深的錯誤，且難以除錯正確。
一般地說，寧要乙個可讀性好、邏輯清晰簡單、但篇幅較長的演算法，也不要篇幅較小但晦澀難懂的演算法。演算法的正確性力求在設計演算法的過程中得到保證，然而一開始做不到這一點也沒多大關係，可以逐步做到。
演算法設計的正確方法是：首先理解問題，明確給定的條件和要求解決的問題，然後按照自頂向下，逐步求精，分而治之的策略逐一地解決子問題，最後嚴格按照和使用本章後面提供的演算法書寫規範和類c語言完成演算法的最後版本。
按照規範書寫演算法是乙個值得高度重視的問題。在基礎訓練中就貫徹這一規範，不但能夠有助於寫出「好程式」，避免形成一系列難以糾正且遺害無窮的程式設計壞習慣，而且能夠培養軟體工作者應有的嚴謹的科學工作作風。
2．對函式進行靜態檢查修改，形成準備上機的程式文字。
多數初學者在編好程式後處於以下兩種狀態之一：一種是對自己的「精心作品」的正確性確信不疑；另一種是認為上機前的任務已經完成，查糾錯誤是上機的工作。這兩種態度是極為有害的。
事實上，非訓練有素的程式設計者編寫的程式長度超過50行時，極少不含有除語法錯誤以外的錯誤。上機動態除錯決不能代替靜態檢查，否則除錯效率將是極低的。
靜態檢查主要有兩種方法，一是用一組測試資料手工執行程式（通常應先分模組檢查）；二是通過閱讀或給別人講解自己的程式而深入全面地分析理解程式邏輯，在這個過程中再加入一些註解和斷言。如果程式中邏輯概念清楚，後者將比前者有效。
3．在「anyview c資料結構演算法設計作業系統」編輯提交程式，並在系統的自動測試和提示下，除錯程式，直到能通過系統的測試。
「anyview c資料結構演算法設計作業系統」提供了程式視覺化執行和除錯的環境，為進行資料結構教學的師生提供了演算法設計作業程式的視覺化自動測試環境。可在該整合環境編輯c源程式，並對其進行視覺化執行、分析和除錯。通過設定斷點、單步或變換速度的連續執行，可在多個視窗上動態觀察程式執行時的資料變數的物理和邏輯2d或3d檢視，使得程式執行期間本來不可見的程式對資料的處理過程和資料之間的動態抽象關係全部視覺化。
在提交演算法設計作業程式時，系統自動進行視覺化測試，評判作業程式的正確性。通過對比「標準結果檢視」和「作業結果檢視」，作業者可對自己的程式進行直觀的分析和排錯。關於該作業系統的使用，請參閱系統的幫助文件。
在除錯過程中可以不斷借助系統的可視debug的各種功能，提高除錯效率。除錯中遇到的各種異常現象往往是預料不到的，這時不應「苦思冥想」，而應動手確定疑點，通過修改程式來證實它或繞過它。
4．在除錯程式的過程中，做好除錯筆記，記錄心得體會。
除錯正確後，認真整理源程式及其注釋，記錄帶有完整注釋的且格式良好的源程式清單和結果。
一道演算法設計作業文件包括：
（1）上機前編寫並經過靜態檢查的程式文字；
（2）除錯筆記；
（3）最後程式文字，及通過時間。
2.3 演算法設計上機作業
1．作業內容和機時
40道必做題，40道選做題。每年作適當調整更換。
6個課內實驗機時，教師現場指導答疑。
24個課外訓練機時，實驗教師指導答疑。
學生平時可以在網際網路上登入系統，做選做題。
2．演算法設計題目文件
系統為每道演算法設計題提供乙個題目文件，包括以下內容：
（1）題目；
（2）演算法的函式原型；
（3）可用的型別定義和函式原型。
做題前，必須仔細閱讀題目文件，正確理解題目和做題要求。
第3章抽象資料型別的實現
3.1 實驗概要
實驗專案名稱: 抽象資料型別的實現
實驗專案性質: 設計性實驗
所屬課程名稱: 資料結構
實驗計畫學時: 6
資料結構課程設計指導書
2011 8 16 一 課程設計目的 3 二 課程設計步驟 3 三 課程設計報告 4 四 課程設計內容 6 五 提交材料 6 六 考核方式與評分標準 7 七 關於編寫 的說明 7 八 參考文獻 8 附錄1 武漢工業學院課程設計說明書 報告 撰寫規範 9 附錄2 visual c 6.0簡介 11 培...
演算法與資料結構課程設計指導書2019
資料結構與演算法 課程設計指導書 宣城校區資訊工程系 2014年12月 課程設計是對學生的一種全面綜合訓練，是與課堂聽講 自學和練習相輔相成的 必不可少的乙個教學環節。通常，課程設計中的問題比平時的習題複雜的多，也更接近實際。課程設計著眼於原理與應用的結合點，使學生學會如何把書上學到的知識用於解決實...
2019版《資料結構A》課程設計指導書
基本功能 乙個完整的系統應具有以下功能 1.初始化 輸入一串字元 正文 計算不同字元 包括空格 的數目以及每種字元出現的頻率 以該種字元出現的次數作為其出現頻率 根據權值建立哈夫曼樹，輸出每一種字元的哈夫曼編碼。2.編碼 利用求出的哈夫曼編碼，對該正文 字串 進行編碼，並輸出。3.解碼 對於得到的一...