實驗課程編號：07zb101109 實驗室名稱：多**技術實驗室
系（院）：數計學院實驗室地點：n5-402
實驗課學時：36
實驗類別：專業課適用專業：電腦科學與技術
是否獨立設課：是
執筆人：李文新審批人：
一、實驗課程教學目的和要求
《資料結構與演算法》是一門實踐性很強的課程，光靠讀書和做習題是不能提高實踐能力的。
《資料結構與演算法》的實驗與程式語言課程中的實驗不同，後者更多的強調語言方面的功能實現，而前者更接近實際，需要同學們自己分析問題，設計模型和演算法，再上機除錯完成。
《資料結構與演算法》的實驗的目的主要有兩個：
1）深化理解書本上的理論知識，將書本的知識變「活」（為已掌握，為已活用）；
2）理論和實踐相結合，學會將相關的資料結構和演算法應用於解決實際問題，培養資料結構的應用能力和軟體工程所需要的實踐能力。
《資料結構與演算法》的實驗型別
1）驗證性實驗—主要是驗證教材中已有的資料結構和演算法。
2）設計性實驗—針對具體問題，應用某乙個知識點，自己設計資料結構和演算法，培養對資料結構的簡單運用能力。
3）綜合性實驗—針對具體問題，應用某幾個知識點，自己設計資料結構和演算法，培養對資料結構的綜合運用能力。
《資料結構與演算法》的實驗安排
《資料結構與演算法》實驗的一般步驟
1）需求分析：要對簡單的問題描述進行詳細的分析，充分理解問題，明確問題要求做什麼，有什麼資料，邊界條件……。
2）概要設計：針對問題描述中涉及到資料定義抽象資料型別，設計資料結構和演算法模型。本部分不必考慮實現的細節。
3）詳細設計：設計具體的儲存結構（用c++實現抽象資料型別對應的類）。此外，還要設計物件間的呼叫關係及輸入輸出。
4）上機除錯（執行**，修正語法及邏輯錯誤）
5）結果與總結
《資料結構與演算法》的實驗要求：
1）完成實驗預習；
2）完成並上交實驗報告；
3）完成電子設計文件
預習/實驗報告的格式要求：
1）實驗名稱
2）實驗目的
3）實驗內容及要求
4）概要設計：adt
5）詳細設計：c++類或c函式
6）除錯分析：
7）結果與總結
實驗一: 結構體的運用
一、實驗目的：
1）結合c++的輸入輸出流複習c語言的知識；
3）掌握結構體的運用方法。
二、實驗內容及要求：
乙個班有n個學生，每個學生有學號（no）、姓名（name）、年齡（age）、成績（score）。定義結構體來描述學生資訊。並定義n個學生的結構體陣列。
要求：設計乙個函式，輸入n個學生的資料；提示性輸入。
設計乙個函式，輸出n個學生的資料；輸出整齊，控制域寬。
設計主函式，呼叫輸入輸出函式。
分別定義結構體陣列為全域性變數和區域性變數兩種情形進行除錯和執行程式。
結構體與指標的運用
一、實驗目的：
1）結合c++的輸入輸出流及動態分配/撤消運算子複習c語言的知識；
3）掌握結構體與指標的運用。
二、實驗內容及要求：
建立乙個動態鍊錶，鍊錶的結點結構：
data next
其中：data為整數型別，next為指標型別
鏈表示例：
其中：head為指向該鍊錶的頭指標。
要求：定義乙個結構體：描述結點資訊；
設計乙個函式，動態建立該鍊錶；
設計乙個函式，輸出該鍊錶的資料；
設計主函式，呼叫建立鍊錶和輸出鍊錶資料的函式。
分別定義head為全域性變數和區域性變數兩種情形進行除錯和執行程式。當head為區域性變數時應將建立鍊錶函式的引數設為引用引數。
實驗二: 順序表的保序插入操作
一、實驗目的：
1）掌握線性表的順序儲存結構與演算法實現；
3）掌握順序表的邏輯插入方法。
二、實驗內容及要求：
設計：主函式、構建n個整數的順序表函式、保序插入函式、輸出函式。
提示：主函式中呼叫構建n個整數的順序表函式並呼叫輸出函式；
呼叫保序插入函式實現插入操作並呼叫輸出函式輸出。
實驗三: 單鏈表的保序插入操作
一、實驗目的：
1）掌握線性表的鏈結儲存結構與演算法實現；
2）掌握線性表的邏輯插入操作方法。
二、實驗內容及要求：
設計：主函式、構建乙個帶頭結點的單鏈表a（值為整數並有序）的函式、保序插入函式、輸出函式。
提示：主函式中呼叫構建單鏈表a函式並呼叫輸出函式；
呼叫保序插入函式實現插入操作並呼叫輸出函式輸出。
結點結構： struct node
int data;
node *next;
};實驗四: 迴圈單鏈表的插入和刪除
一、實驗目的：
1）進一步掌握線性表的鏈結儲存結構；
2）掌握迴圈單鏈表及其基本操作的實現。
二、實驗內容及要求：
1）用頭插法（或尾插法）建立帶頭結點的迴圈單鏈表；
2）在採用尾指標（rear）表示的迴圈單鏈表中，查詢元素為x的結點，如果有則刪除該結點；如果沒有則插入到迴圈單鏈表的尾部。
操作介面 ：t linklistldi(t x)
實驗五: 棧與隊的操作
一、實驗目的：
1）掌握棧和隊的順序與鏈結儲存結構；
2）掌握棧和隊的操作特性；
3) 掌握順序棧和鏈佇列的基本操作的實現方法。
二、實驗內容及要求：
1）分別建立乙個空的順序棧和空的鏈佇列；
2）對已建立的順序棧和鏈佇列實現插入、刪除、取棧頂元素、取隊頭元素及輸出等基本操作。
實驗六：棧與隊的的應用（括號匹配問題）
一、實驗目的：
1）掌握棧和佇列的儲存結構；
2）掌握棧和佇列的操作特性；
3）掌握棧和佇列基本操作的實現。
二、實驗內容及要求：
括號匹配問題
在算述表示式中，可能出現巢狀的大、中、小括號，設計乙個演算法，可以判斷給定的表示式串中的括號是否是匹配的。
要求：首先，分別先定義乙個棧和乙個隊；其次，將表示式串中的各種括號字元依次入隊（其它字元不予考慮）；最後利用棧來判斷隊中的括號是否是匹配的。
無論是什麼括號，最後出現的左括號，必須與其後最先出現的右括號匹配，這符合棧的後進先出的特點，故我們可以用棧和進行匹配性判斷。
根據要求，串(括號) 隊棧
操作介面：bool match(char *s)
主要操作：
隊，棧初始化
括號字元入隊
出隊為左括號：進棧
出隊為右括號：彈棧
匹配？實驗七：對稱矩陣的壓縮儲存
一、實驗目的：
1）掌握對稱矩陣的壓縮儲存方法；
2）掌握對稱矩陣的壓縮儲存的定址方法。
二、實驗內容：
1) 建立乙個n×n的對稱矩陣；
2) 將對稱矩陣用一維陣列儲存
三、實現提示：
首先建立乙個n×n的對稱矩陣a並初始化矩陣的元素。對稱矩陣只須儲存下三角部分，即將乙個n×n的對稱矩陣用乙個大小為n×(n+1)/2的一維陣列sa來儲存，則對稱矩陣中的元素aij(i≥j)在sa中的下標k與i、j的關係為k=i×(i+1)/2+j，元素aij(i實驗八：壓縮矩陣的應用（稀疏矩陣的轉置）
一、問題描述：
採用三元組順序表儲存稀疏矩陣並實現轉置。
二、基本要求：
1) 設計儲存結構實現稀疏矩陣的壓縮儲存；
2) 設計演算法實現稀疏矩陣的轉置；
3) 分析演算法的時間複雜度和空間複雜度。
三、設計思想：
將稀疏矩陣的非零元素對應的三元組（行號、列號、非零元素值）所構成的集合，按行優先的順序排列成乙個線性表(三元組順序表),對該線性表採用順序儲存結構，同時儲存該稀疏矩陣的行數、列數和非零元素的個數。
將稀疏矩陣a轉置為矩陣b的基本思想是：在a的三元組順序表中依次找第0列、第1列……最後一列的三元組，並將找到的每個三元組的行、列交換後順序儲存到b的三元組順序表中。即轉置演算法：
搜尋取，順序存
實驗九：二叉樹的操作
一、實驗目的：
1）掌握二叉樹的二叉鍊錶儲存結構；
2）掌握二叉樹的建立方法；
3）掌握二叉樹的遍歷操作的演算法實現。
二、實驗內容及要求：
1) 利用擴充套件二叉樹的先序遍歷序列
建立乙個含有n個結點的二叉樹，採用二叉鍊錶儲存；
2) 進行各種遍歷（先序，中序，後序，層序）該二叉樹；
3) 遍歷演算法分別用遞迴和非遞迴演算法。
實驗十：二叉樹的應用
求二叉樹葉子結點個數和深度
一、問題描述：
已知一棵二叉樹，求該二叉樹中的葉子結點的個數和深度。
二、基本要求：
1) 採用二叉鍊錶儲存結構；
2) 設計演算法求二叉樹中的葉子結點的個數和二叉樹t的深度。
三、設計思想：
在實驗九（二叉樹的操作）的基礎上設計演算法求二叉樹中的葉子結點個數和二叉樹t的深度。
分別用遞迴和非遞迴演算法。
實驗十一：二叉樹的應用（哈夫曼編碼）
一、問題描述：
設某編碼系統共有n個字元，使用頻率分別為（w1,w2,…,wn）。設計乙個不等長的編碼方案，使用該編碼系統的空間效率最好。
二、基本要求：
1) 設計資料結構；
2) 設計編碼演算法；
3）分析演算法的時間複雜度和空間複雜度。
三、設計思想：
利用huffman編碼樹求得最佳的編碼方案。
根據哈夫曼演算法，建立哈夫曼樹時，可以將哈夫曼樹定義為乙個結構型的一維陣列huffman，儲存哈夫曼樹中各結點的資訊，每個結點包括權值、左孩子、右孩子和雙親。由於哈夫曼樹中共有2n－1個結點。並且進行n－1次合併操作，所以該陣列的長度為2n－1。
在哈夫曼樹中，設左分支為0，右分支為1，從根結點出發，遍歷整棵哈夫曼樹，求得各個葉子結點所表示字元的哈夫曼樹編碼。
實驗十二：圖的操作
一、實驗目的：
1）掌握圖的儲存結構；
2）掌握構造鄰接矩陣的方法；
3）掌握圖的遍歷演算法的演算法實現。
二、實驗內容及要求：
按給定的任一連通無向圖構造鄰接矩陣，再進行深度優先遍歷和廣度優先遍歷。
《資料結構與演算法》實驗指導書
鬱松軟體學院 資料結構 是計算機 資訊管理和電子商務專業一門重要的專業技術基礎課程，是計算機 資訊管理和電子商務專業的一門關鍵性課程。本課程較系統地介紹了軟體設計中常用的資料結構以及相應的儲存結構和實現演算法，介紹了常用的多種查詢和排序技術，並做了一些效能分析和比較，內容非常豐富。本課程的學習將為後...
《資料結構 演算法與應用》實驗指導書
山東大學軟體學院 一 實驗要求 1 採用良好的程式設計風格 關鍵操作要有注釋。2 程式能夠執行，顯示執行結果。二 開發工具 microsoft visual c eclipse ide for c 三 實驗時間 地點 一 實驗目的 1 熟悉開發工具的使用。2 掌握遞迴的實現思想。二 實驗內容 1 輸...
實驗指導書 2019級計科 《資料結構》
實驗指導書 學科 電腦科學與技術 課程名稱 資料結構 適用專業 電腦科學與技術專業 資訊科技學院 實驗一認識資料結構和演算法 一 實驗目的 1 了解資料結構中問題求解的基本步驟 2 學會簡單的用順序儲存結構存放資料結構的c 寫法 二 實驗學時 2學時三 實驗內容 開發乙個查詢 資料結構 課程成績的程...