PAGE4實驗項目名稱：線性表（實驗一）實驗目的(1)了解線性表的邏輯結構特性是數(shù)據(jù)元素之間存在著線性關系，在計算機中表示這種關系有順序存儲結構和鏈式存儲結構；(2)掌握這兩種存儲結構的描述方法；(3)掌握線性表的基本操作（查找、插入、刪除）；(4)考慮時間和空間復雜度設計算法。2、實驗內(nèi)容（1）創(chuàng)建一個順序表，存放在數(shù)組A[N]中，元素的類型為整型，設計算法調(diào)整A，使其左邊的所有元素小于0，右邊的所有元素大于0（要求算法的時間復雜度和空間復雜度均為O(n)）。建立一個循環(huán)單鏈表，其節(jié)點有l(wèi)eft,data和right三個域，其中data為數(shù)據(jù)域，存放元素的有效信息，right域為指針域，指向后繼節(jié)點，left為指針域，它的值為NULL。編寫一個算法將此表改為循環(huán)雙鏈表。實驗項目名稱：棧（實驗二）、實驗目的(1)理解棧的定義、特點及與線性表的異同；(2)熟悉順序棧的組織方法，棧滿、棧空的判斷條件及其描述；(3)掌握棧的基本操作（進棧、退棧等）。2、實驗內(nèi)容(1)設計一個算法，將一般算術表達式轉化為逆波蘭表達式，并求逆波蘭表達式的值。(2)設計兩個棧S1、S2都采用順序棧方式，并且共享一個存儲區(qū)[0，MaxLen-1]，為了盡量利用空間，減少溢出的可能，可采用棧頂相向、迎面增長的存儲方式，如下圖所示。設計一個有關棧的入棧和出棧算法。實驗項目名稱：隊列（實驗三）、實驗目的(1)理解隊列的定義、特點及與線性表的異同；(2)熟悉隊列的組織方法，隊列滿、隊列空的判斷條件及其描述；(3)掌握隊列的基本操作（入隊、出隊等）。2、實驗內(nèi)容(1)假設以數(shù)組sequ[MaxSise]存放環(huán)形隊列的元素，同時rear和len分別指示環(huán)形隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。設計相應的入隊和出隊算法。(2)某汽車輪渡口，過江渡船每次能載10輛車過江。過江車輛分別為客車類和貨車類，上船有如下規(guī)定：同類車先到先上船，客車先于貨車上渡船，且每上4輛客車，才允許上一輛貨車；若等待客車不足4輛則以貨車代替；若無貨車等待則允許客車都上船。設計一個算法模擬渡口管理。實驗項目名稱：二叉樹（實驗四）1、實驗目的(1)掌握二叉樹的結構特性和二叉鏈表存儲結構；(2)理解二叉樹、完全二叉樹、滿二叉樹的概念和存儲特點；(3)掌握二叉樹遍歷的遞歸和非遞歸方法。2、實驗內(nèi)容（1）假設二叉樹采用鏈接存儲方式存儲，分別編寫一個二叉樹先序遍歷的遞歸算法和非遞歸算法。（2）一棵完全二叉樹以順序方式存儲，設計一個遞歸算法，對該完全二叉樹進行中序遍歷。實驗項目名稱：哈夫曼樹（實驗五）1、實驗目的(1)理解哈夫曼樹的概念、結構特性和哈夫曼編碼原理；(2)掌握構造哈夫曼樹的基本方法；(3)掌握運用哈夫曼樹進行哈夫曼編碼的方法；2、實驗內(nèi)容根據(jù)哈夫曼(Huffman)編碼的原理，編寫一個程序，在用戶輸入節(jié)點權重的基礎上建立它的哈夫曼編碼。實驗項目名稱：圖（實驗六）1、實驗目的(1)理解圖的基本概念、圖的結構特性；(2)掌握鄰接表表示圖的基本方法；(3)掌握連通圖遍歷的基本的方法。2、實驗內(nèi)容(1)用鄰接表存儲一個圖G。分別設計實現(xiàn)下列要求的算法：-求出圖G中每個頂點的出度；-求出圖G中出度最大的一個頂點，輸出該頂點的編號；-計算圖G中出度為0的頂點數(shù)。(2)編寫一個實現(xiàn)連通圖G的深度優(yōu)先遍歷（從頂點V0出發(fā)，以鄰接矩陣為存儲結構）的遞歸和非遞歸函數(shù)，分別用這兩種方法對圖進行深度優(yōu)先遍歷，比較遍歷結果。實驗項目名稱：圖（實驗七）1、實驗目的(1)理解拓撲排序的基本概念和拓撲排序的實用意義；(2)掌握AOV-網(wǎng)解決拓撲排序問題的基本方法。(3)理解最小生成樹的基本概念和實用意義；(4)掌握利用MST性質(zhì)構造最小生成樹的prim算法和Kruskal算法。2、實驗內(nèi)容(1)教學計劃編制問題。按先修課程和后續(xù)課程關系，編制一個簡單的排課計劃程序。(2)在n個城市之間架設n-1條線路，要求建設代價最小。編寫完整算法構造最小生成樹。實驗項目名稱：查找（實驗八）1、實驗目的(1)理解查找表的基本概念，定義、分類和各類的特點；(2)掌握哈希表的構造方法以及解決沖突的方法；(3)掌握哈希存儲和哈希查找的基本思想及有關方法。2、實驗內(nèi)容使用哈希函數(shù)：H（K）=3KMOD11并采用鏈地址法處理沖突。試對關鍵字序列（22，41，53，46，30，13，01，67）構造哈希表，設計構造哈希表的完整算法。實驗項目名稱：排序（實驗九）1、實驗目的(1)理解各類內(nèi)部排序的基本思想；(2)掌握各類內(nèi)部排序的基本方法；(3)了解各類內(nèi)部排序的優(yōu)缺點。2、實驗內(nèi)容(1)編寫一個雙向冒泡排序算法，即在排序過程中以交替的正、反兩個方向進行遍歷。若第一趟把關鍵字最大的記錄放到最末尾，則第二趟把關鍵字最小的記錄放到最前端，如此反復進行之。(2)設計一個進行堆排序的算法。實驗項目名稱：自主設計應用實例（可選）指導思想：訓練學生自主學習、綜合知識和查閱、收集資料的能力。通過自主學習、查閱和收集所需的知識點完成。給學生充分展示才華的舞臺，對學生設計的軟件作品要提供一個自由展示的平臺、互動交流的平臺，可以大大提高學生的學習激情和科學研究的精神，也能顯著提高學習效果。實驗目的及要求：為進一步提高教與學的效果，在各個章節(jié)的基本編程訓練的基礎上，再結合課程重點和難點進行較大軟件編制的選題，并在具體題目上提倡與實際應用相結合并由學生自主選題，教師審核。說明：在線性表、棧、隊列、二叉樹、圖、查找和排序等實驗項目中選擇