大連民族學院
資訊與通訊工程學院
2013 年10 月10 日
基本要求
1. 學生必須按時到實驗室做實驗，不得遲到早退，未經老師批准不得中途離開。凡遲到者，應給予批評並作適當扣分。
實驗課遲到20分鐘以上及無故缺席者視為曠課，曠課者不予補做實驗，本次實驗以零分計。學生因病或特殊情況不能按時到實驗室做實驗時，應辦理正常請假手續。請病假必須有醫生簽字的病假條，請事假必須有班主任簽字的事假條。
不符合請假手續的，以曠課論處。請假的學生由指導教師安排補做實驗。對於未做實驗數達三分之一以上（含三分之一）的學生，實驗課程按0分計。
2. 學生在每次實驗課之前，應仔細閱讀實驗教材，查閱相關的資料，寫出預習報告。預習報告的具體內容包括：
實驗內容、實驗目的、實驗原理圖、實驗步驟、實驗資料記錄**等。實驗課前由任課教師檢查預習報告，未寫預習報告者不予做實驗。
3. 做實驗前，了解裝置的原理和正確使用方法。在沒有弄懂儀器裝置的使用方法前，不得貿然使用，否則因使用不當造成儀器裝置損壞的，根據大連民族學院《儀器裝置損壞丟失處理暫行辦法》規定進行處理。
實驗室內裝置在實驗過程中不准任意搬動和調換，非本次實驗所用儀器裝置，未經指導教師允許不得動用。
4. 要求每位學生在實驗過程中，要具有嚴謹的學習態度、認真、踏實、一絲不苟的科學作風。實驗過程中學生按照預習的內容進行實驗，且重視實驗的除錯過程，學會如何根據實驗現象判斷問題所在。
堅持每次實驗都要親自動手，不可「坐車」，每個實驗每個學生都要獨立完成，不允許抄襲，無特殊原因，中途不得退出實驗，否則本次實驗無效。
5. 實驗中若接線、改接、拆線都必須在切斷電源的情況下進行，線路連線完畢再送電。實驗中，特別是裝置剛投入執行時，要隨時注意儀器裝置的運**況，如發現有過熱、異味、冒煙、火花等，應立即斷電，並請指導老師檢查、處理。
6. 實驗過程中，如出現事故，就馬上拉開電源開關，然後找指導教師和實驗技術人員，如實反映事故情況，並分析原因和處理事故。如有損壞儀表和裝置時，應馬上提出，按有關規定處理。
7. 每次實驗結束，指導教師要對實驗資料和結果進行檢查，並簽字，在教師確認正確無誤後，學生方可拆線。整理好實驗台和周圍衛生，填寫實驗登記簿後方可離開。
8. 每次實驗後學生必須寫出符合要求的實驗報告，缺交者本次實驗以零分計。
實驗報告要求字跡工整、原始資料齊全、圖表清晰、程式正確。實驗報告必須附有指導教師簽字的原始資料表或預習報告，否則該實驗報告無效。為滿足上述要求的按其程度扣除一定分值。
9. 實驗總評成績評定：每次實驗後，教師根據學生的出勤、實驗過程操作技能、實驗原始記錄、實驗結果、實驗報告等情況綜合按5分制評分。實驗課考核不合格的學生按規定應重修該課程。
緒論5實驗一：線性表的結構定義及基本操作6
實驗二：棧和佇列的結構定義及基本操作21
實驗三：二叉樹的結構定義及基本操作33
實驗四：圖的結構定義及基本操作40
0 緒論
本書是以《資料結構與演算法》課程教學大綱和實驗教學大綱為指導，分別從實驗的六個方面（實驗目的、實驗內容、實驗指導、參考程式、實驗步驟以及思考題）來組織內容。其中實驗目的強調了每個實驗要掌握的內容和要達到的層次;實驗內容是對基本實驗和擴充套件實驗的問題進行描述，並且對實現要求進行了規劃;實驗指導對整個實驗的結構進行了組織和指導;而參考程式則列出了實驗要求中，特別是一些重要演算法的參考描述;實驗步驟則是指導學生進行實驗的具體操作;思考題則是布置給學生對同類實驗的一種思考和提示。
在參考程式中，主要實現了資料結構定義，基本操作和演算法的驗證。其中：在所有實驗中我們建議採用visual c++作為實驗的開發環境,也可以用bc++,tc++環境以及c#,j**a等其他語言。
如果用c環境，那麼後面的參考程式中，凡是涉及到「引用」內容的，均要改為「指標」。用vc++作為實驗開發環境，首先建立win32 console application 工程,其目的是在windows 圖形環境中模擬dos 字元方式。由於工程是以一組相關的檔案組織的，將嚴格地按照檔案內容的不同功能進行細緻的劃分，為了便於大家認真理解本指導書的內容，特對各
類檔案的名稱作了如下的規定：
檔名的標識基本以每個實驗的內容作為依據，如順序表的儲存結構定義檔案為這些程式檔案主要包含了如下4 類：
（1） 是幾乎所有實驗中都涉及到的，包含了一些常量定義，系統函式原型宣告和型別（status）重定義,結果狀態**等。在本文中的內容對某乙個實驗可能沒有完全用到，但對本課程的其他實驗可能有用;
（2） 資料結構定義：以____ 為檔名;
（3） 基本操作和演算法：以____ 為檔名;
（4） 呼叫基本操作的主程式：以_____ 為檔名。
實驗一：線性表的結構定義及基本操作（必做，2學時）
一、實驗目的：
. 掌握線性表的邏輯特徵
. 掌握線性表順序儲存結構的特點，熟練掌握順序表的基本運算
. 熟練掌握線性表的鏈式儲存結構定義及基本操作
. 加深對順序儲存資料結構的理解和鏈式儲存資料結構的理解，逐步培養解決實際問題的程式設計能力
二、實驗內容：
（一）基本實驗內容（順序表）：
建立順序表，完成順序表的基本操作：初始化、插入、刪除、銷毀、置空表、求表長、查詢元素、判線性表是否為空;
1．問題描述：利用順序表,設計一組輸入資料（假定為一組整數），能夠對順序表進行如下操作：
. 建立乙個新的順序表，實現動態空間分配的初始化;
. 根據順序表結點的位置插入乙個新結點(位置插入)，也可以根據給定的值進行插入(值插入)，形成有序順序表;
. 根據順序表結點的位置刪除乙個結點(位置刪除);
. 徹底銷毀順序線性表，**所分配的空間;
. 對順序線性表的所有元素刪除，置為空表;
. 返回順序線性表資料元素個數;
. 按序號查詢，根據順序表的特點，可以隨機訪問，直接可以定位於第i 個結點，查詢該元素的值，對查詢結果進行返回;
. 按值查詢，根據給定資料元素的值，只能順序比較，查詢該元素的位置，對查詢結果進行返回;
. 判斷順序表中是否為空表，對判斷結果進行返回;
. 編寫主程式，實現對各不同的演算法呼叫。
2．實現要求：
對順序表的各項操作一定要編寫成為c（c++）語言函式，組合成模組化的形式，每個演算法的實現要從時間複雜度和空間複雜度上進行評價;
. 「初始化演算法」的操作結果：構造乙個空的順序線性表。對順序表的空間進行動態管理，實現動態分配、**和增加儲存空間;
. 「位置插入演算法」 的初始條件：順序線性表l 已存在，給定的元素位置為i，且1≤i≤listlength(l)+1 ;
操作結果：在l 中第i 個位置之前插入新的資料元素e，l 的長度加1;
. 「位置刪除演算法」的初始條件：順序線性表l 已存在，1≤i≤listlength(l) ;
操作結果：刪除l 的第i 個資料元素，並用e 返回其值，l 的長度減1 ;
. 「銷毀演算法」初始條件：順序線性表l 已存在;
操作結果：銷毀順序線性表l;
. 「置空表演算法」初始條件：順序線性表l 已存在;
操作結果：將l 重置為空表;
. 「求表長演算法」初始條件：順序線性表l 已存在;
操作結果：返回l 中資料元素個數;
. 「按序號查詢演算法」初始條件：順序線性表l 已存在，元素位置為i，且1≤i≤listlength(l)
操作結果：返回l 中第i 個資料元素的值;
. 「按值查詢演算法」初始條件：順序線性表l 已存在，元素值為e;
操作結果：返回l 中資料元素值為e 的元素位置;
. 「判表空演算法」初始條件：順序線性表l 已存在;
操作結果：若l 為空表，則返回true，否則返回false;
分析: 修改輸入資料，預期輸出並驗證輸出的結果，加深對有關演算法的理解。
(二）基本實驗內容（鍊錶）：
建立單鏈表，完成鍊錶（帶表頭結點）的基本操作：建立鍊錶、插入、刪除和輸出操作。
1． 問題描述：
利用線性表的鏈式儲存結構,設計一組輸入資料（假定為一組整數），能夠對單鏈表進行如下操作：
. 初始化乙個帶表頭結點的空鍊錶;
. 建立乙個單鏈表是從無到有地建立起乙個鍊錶，即乙個乙個地輸入各結點資料，並建立起前後相互鏈結的關係。
. 插入結點根據給定位置進行插入（位置插入）。
. 刪除結點根據給定位置進行刪除（位置刪除）。
. 輸出單鏈表的內容是將鍊錶中各結點的資料依次顯示，直到鍊錶尾結點。
. 編寫主程式，實現對各不同的演算法呼叫。
其它的操作演算法描述略。
2．實現要求：
對鍊錶的各項操作一定要編寫成為c（c++）語言函式，組合成模組化的形式，還要針對每個演算法的
實現從時間複雜度和空間複雜度上進行評價。
. 「初始化演算法」的操作結果：構造乙個空的線性表l，產生頭結點,並使l 指向此頭結點;
. 「建立鍊錶演算法」 初始條件：空鏈存在;
操作結果：選擇逆位序或正位序的方法，建立乙個單鏈表，並且返回完成的結果;
. 「鍊錶（位置）插入演算法」初始條件：已知單鏈表l 存在;
操作結果：在帶頭結點的單鏈線性表l 中第i 個位置之前插入元素e;
. 「鍊錶（位置）刪除演算法」初始條件：已知單鏈表l 存在;
操作結果：在帶頭結點的單鏈線性表l 中，刪除第i 個元素,並由e 返回其值;
. 「輸出演算法」初始條件：鍊錶l 已存在;
操作結果：依次輸出鍊錶的各個結點的值;
三、實驗指導
乙個簡單程式通常主要由三部分構成：
1、常量定義（#define），型別重定義(typedef)及函式原型(#include)宣告;還有針對每一種資料結構的型別定義，由於本實驗是要求實現對線性表的順序儲存和鏈式儲存兩種儲存結構的定義，因此不同的物理儲存結構的定義和其基本操作最好是以獨立的檔案存在，因此本實驗將順序表和煉表可分解為兩個不同的實驗部分。
《資料結構與演算法》實驗指導書
鬱松軟體學院 資料結構 是計算機 資訊管理和電子商務專業一門重要的專業技術基礎課程，是計算機 資訊管理和電子商務專業的一門關鍵性課程。本課程較系統地介紹了軟體設計中常用的資料結構以及相應的儲存結構和實現演算法，介紹了常用的多種查詢和排序技術，並做了一些效能分析和比較，內容非常豐富。本課程的學習將為後...
《資料結構 演算法與應用》實驗指導書
山東大學軟體學院 一 實驗要求 1 採用良好的程式設計風格 關鍵操作要有注釋。2 程式能夠執行，顯示執行結果。二 開發工具 microsoft visual c eclipse ide for c 三 實驗時間 地點 一 實驗目的 1 熟悉開發工具的使用。2 掌握遞迴的實現思想。二 實驗內容 1 輸...
資料結構與演算法大平台實驗指導書
上海交通大學電院資料結構大平台課程組 目錄1.關於實習步驟的要求和建議 2.上機實習 實習一線性結構 實習二樹和二叉樹 實習三查詢 實習四圖 實習五排序 3.實習報告樣例 1 關於實習步驟的要求和建議 從以往的教學事先實習的經驗來看，在初學階段執行嚴格的實習步驟規範 包括上機操作規範 機時利用率會大...