五邑大學計算機學院
資料結構實驗指導手冊
2023年3月
目錄實驗一線性表 1
1．實驗目的 1
2．實驗內容 1
3．解題思路 1
實驗二棧 4
1．實驗目的 4
2．實驗內容 4
3．解題思路 4
實驗三佇列 8
1．實驗目的 8
2．實驗內容 8
3．解題思路 8
實驗四二叉樹 12
1．實驗目的 12
2．實驗內容 12
3．解題思路 12
實驗五哈夫曼樹 18
1．實驗目的 18
2．實驗內容 18
3．解題思路 18
實驗六圖的基本儲存 21
1．實驗目的 21
2．實驗內容 21
3．解題思路 21
實驗七圖的應用 26
1．實驗目的 26
2．實驗內容 26
3．解題思路 26
實驗八查詢 30
1．實驗目的 30
2．實驗內容 30
3．解題思路 30
實驗九排序 32
1．實驗目的 32
2．實驗內容 32
3．解題思路 32
說明 36
附錄實驗報告模板 37
（1） 了解線性表的邏輯結構特性是資料元素之間存在著線性關係，在計算機中表示這種關係有順序儲存結構和鏈式儲存結構；
（2）掌握這兩種儲存結構的描述方法；
（3） 掌握線性表的基本操作（查詢、插入、刪除）；
（4）考慮時間和空間複雜度設計演算法。
（1）建立乙個順序表，存放在陣列a[n]中，元素的型別為整型，設計演算法調整a，使其左邊的所有元素小於0，右邊的所有元素大於0（要求演算法的時間複雜度和空間複雜度均為o(n)）。
（2）建立乙個迴圈單鏈表，其節點有prior，data和next三個域，其中data為資料域，存放元素的有效資訊，next域為指標域，指向後繼節點，prior為指標域，它的值為null。編寫乙個演算法將此表改為迴圈雙鏈表。
（1）如圖1-1所示，設立兩個工作指標i和j，i由陣列的左端向右移動，查詢大於等於0的數，j由陣列的右端向左端移動，查詢小於0的數，然後交換，如圖1-2所示，直到i>=j，調整結束。
圖1-1
圖1-2
演算法描述（c語言）如下：
（2）如圖1-3所示，已建有乙個單迴圈鍊錶（帶頭結點），first指向頭結點。設立兩個工作指標p和q，分別指向頭結點和第1個結點；執行q->prior=p;，建立第1個結點的前驅指標，如圖1-4所示；同步移動工作指標p和q分別指向下乙個結點，如圖1-5所示，建立q指向結點的前驅，直到q==first為止，再將頭結點的前驅設為最後乙個結點，如圖1-6所示。
圖1-3
圖1-4
圖1-5
圖1-6
演算法描述（c語言）如下：
（1）理解棧的定義、特點及與線性表的異同；
（2）熟悉順序棧的組織方法，棧滿、棧空的判斷條件及其描述；
（3）掌握棧的基本操作（進棧、退棧等）。
（1）設計乙個演算法，將一般算術表示式轉化為逆波蘭表示式，並求逆波蘭表示式的值。
（2）設計兩個棧s1、s2都採用順序棧方式，並且共享乙個儲存區[0，maxlen-1]，為了盡量利用空間，減少溢位的可能，可採用棧頂相向、迎面增長的儲存方式，如圖2-1所示。設計乙個有關棧的入棧和出棧演算法。
圖2-1
（1）一般算術表達（中綴表達），如#3*(4+2)/2-5#，#為表示式界定符，逆波蘭表示式（字尾表示式），如前述表達的字尾表示式為：3 4 2 + * 2 / 5 -。設中綴表示式的運算子有+、-、*、/、#五種，運算子的優先級別從高到低為有括號先算括號內，再算括號外的，多層括號由內向外進行。
中綴表示式轉換為字尾表示式需要用到乙個臨時棧optr暫存運算子。
轉換演算法描述（偽**）如下：
字尾表示式求值，由於字尾表達中所有的計算按運算子出現的順序從左向右進行，不用再考慮運算子的優先順序。設定乙個臨時堆疊opnd暫存計算過程的中間結果。
字尾表示式計算演算法描述（偽**）如下：
（2）兩棧共享儲存空間，需要解決的關鍵問題在於如何判斷棧滿和棧空，由於兩棧共享儲存空間，入棧和出棧的時候還需要區分是哪個棧。設lstop是左棧（陣列下標為0的一端為棧底）棧頂指標，rstop為右棧（陣列下標為maxlen-1的一端為棧底）棧頂指標，顯然，當兩個棧都為空時，lstop==-1，rstop==maxlen，如圖2-2所示；當棧滿時，rstop和lstop存在以下關係：rstop==lstop+1，如圖2-3所示。
圖2-2
圖2-3
入棧演算法描述（c語言）如下：
出棧演算法描述（c語言）如下：
（1）理解佇列的定義、特點及與線性表的異同；
（2）熟悉佇列的組織方法，佇列滿、佇列空的判斷條件及其描述；
資料結構實驗指導書2019版
資料結構與演算法實驗 指導書電腦科學與資訊工程學院 資料結構與演算法課程組編寫 1.實驗目的要求 本次實驗的目的掌握順序表的儲存結構形式及其描述和基本運算的實現 掌握動態鍊錶結構及相關演算法設計 實驗要求 輸入和驗證程式例題。正確除錯程式，記錄程式執行結果。完成實驗報告。2.實驗主要內容 2.1 實...
資料結構實驗指導
第2版 程紹輝宋欣李佳音編著 2012 05 實驗目的 1 掌握線性表的邏輯結構定義 2 掌握線性表的兩種儲存結構 順序和鏈式 3 掌握順序表和煉表的定義及基本操作 實驗內容 1 生成26個字母的線性表，並實現對特定字母的插入和刪除的程式。源程式如下 include include typedef ...
2019版《資料結構A》課程實驗指導書
data structure course design 課程編號 06311360學時 15 學分 1 先修課程 程式設計基礎 物件導向程式設計 適用專業 電腦科學與技術 網路工程 軟體工程 一 實驗目的 資料結構a 課程是電腦科學與技術及其相關專業的一門重要的專業基礎課。在課堂教學中，比較全面 ...