1、數據結構實驗指導書潘向輝/吳學毅編寫印包學院數字媒體技術專業2011年3月實驗說明【實驗環境】操作系統：MicrosoftWindowsXP/2000?編程語言:C語言【實驗要求】實驗前，了解實驗目的？實驗內容及相關的基本理論知識，并按照實驗內容要求設計程序流程，書寫預習報告；本課程實驗均為單人單組，獨立完成；1. 實驗所用計算機固定，以便實現實驗之間的延續性；按要求完成實驗內容，在實驗結束后按照格式和規范撰寫實驗報告？【實驗項目及學時分配】本課程實驗環節共計16學時，實驗項目及學時分配如下序號實驗項目學時實驗類型要求1線性表（順序表及單鏈表）4驗證掌握線性表的基本操作，熟悉指針操作，完成實驗

2、內容要求2棧和隊列2驗證掌握順序棧？順序循環隊列以及鏈式堆棧和隊列基本操作并應用3二叉樹的構建?基本操作和遍歷4設計掌握二叉樹的基本操作，實現二叉樹的三種遍歷？掌握哈夫曼樹的構造以及編碼4圖的建立？基本操作以及遍歷4設計掌握圖的兩種存儲結構，并實現某一存儲結構下圖的操作的實現5排序與查找算法實現2設計掌握幾種排序和查找算法的思想，實現任意排序和查找算法【實驗報告及考核】實驗報告撰寫符合格式及規范要求，詳見實驗報告撰寫格式及規范1. 本課程實驗占課程總成績的15%?實驗（一）線性表一？實驗項目名稱：線性表課時:4學時?實驗要求1、掌握順序表的定義與實現，包括查找？插入？刪除算法的實現,能在實際應

3、,能在實際應2、掌握在各種鏈表結構中實現線性表操作的基本方法用中選用適當的鏈表結構；三？實驗環境Widows操作系統？C語言四？實驗內容（1）順序表建立一如下表所示的學生信息表學號姓名性別年齡20001張三男2020002李四男22使用結構體，下內容：1. 初始化依次輸鍵盤輸入）用順序表完成以線性表為空；入數據元素；（由完成數據元素的插入？刪除操作2. 取第i個數據元素依次顯示當前線性表中的數據元素（2）單鏈表建立一個單鏈表，依次輸入數據元素09?使用結構體，用單鏈表完成以下內容：1. 初始化單鏈表；2.在單鏈表指定位置插入一個數據元素3. 刪除指定位置的一個數據元素；4.取第i個數據元素2.

4、 查找數據元素x是否在單鏈表中；6.銷毀單鏈表；五？思考題：在什么情況下使用順序表比鏈表好？實驗(二)棧和隊列一？實驗項目名稱：棧和隊列課時:2學時二？實驗要求1、掌握棧的順序表示？鏈表表示以及相應操作的實現？特別注意棧空和棧滿的條件；2、掌握隊列的順序表示？鏈表表示以及相應操作的實現？特別是循環隊列中隊頭與隊尾指針的變化情況；三？實驗環境Widows操作系統？VC6.0四？實驗內容分別使用順序循環隊列和堆棧以及鏈式隊列和堆棧編寫程序：判斷一個字符序列是否是回文？回文是指一個字符序列以中間字符為基準，兩邊字符完全相同？如：“ABCDEDCBA?字符串長度小于等于80,用于判斷回文的字符串不包括

5、字符串的結束標記符？基本要求：(1) 字符序列可由用戶從鍵盤隨意輸入；(2) 可以連續測試多個字符序列，由用戶決定退出測試程序；算法思想：判斷回文的算法思想是：把字符串中的字符逐個分別存入隊列和堆棧中，然后逐個出隊列和退棧并比較出隊列的數據元素和退棧的數據元素是否相等，若全部相等則該字符序列為回文，否則就不是回文？基本操作：回文判斷操作主要包括入棧和入隊列？退棧和出隊列操作？在對堆棧以及隊列進行操作之前，必須對隊列以及堆棧進行初始化？若使用鏈式堆棧和鏈式隊列，操作結束后必須銷毀鏈表？五？思考題：1 ?棧有哪些特點及與一般線性表有哪些區別？2 ?隊列有哪些特點及于一般線性表有哪些區別？實驗(三)

6、二叉樹的構建？基本操作和遍歷一?實驗項目名稱：二叉樹的構建？基本操作和遍歷課時:4學時二?實驗要求1?熟練掌握二叉樹的結構特性，熟悉二叉樹的各種存儲結構的特點及適用范圍；2?熟練掌握二叉樹的遍歷方法及遍歷算法；3?掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權路徑長度的計算？三？實驗環境Widows操作系統？VC6.0四？實驗內容(1)二叉樹建立如下圖所示的二叉樹：要求:1?建立帶頭結點的二叉樹，將?依次將二叉樹的所有?用戶可由鍵盤輸入數?打印二叉樹；?對二叉樹實現前入乞樹初始化為空;7上圖所示的二叉樹；現對二叉樹各結點的插入？刪除等操作;?中序？后序遍歷；算法思想：建立一棵只有頭結點的二叉樹，并通

7、過調用插入左子樹和插入右子樹操作依次將上圖中的結點插入二叉樹中，利用二叉樹的特殊中序遍歷方法將該樹以凹入表示法打印顯示？最后,調用二叉樹的前序？中序？后序遍歷函數對二叉樹進行遍歷,并顯示遍歷結果？哈夫曼樹設計各設有字符集A?B?C?D,各字符在電文中出現的次數集為1,3,5,7,字符的哈夫曼編碼？要求：1?構造字符集的哈夫曼樹,其結點數據結構如下：weightflagparentleftChildrightChild哈夫構造哈夫曼編碼，輸出權值及其對應的編碼？算法思想：首先，由給定的n個權值構造有2n-1個結點的哈夫曼樹？在哈夫曼樹中，其葉結點的權值為相應的給定權值，非葉結點的權值為其孩子結點

8、的權值之和？哈夫曼樹構造過程如下：1. 根據給定的n個權值w1,w2,wn,構成的n棵二叉樹的森林F=T1,T2,斤,其中每棵二叉樹Ti中只有一個權值為wj的結點，其左?右子樹均為空；2. 在F中選取根結點的權值最小和次小的兩棵樹作為左？右子樹構造一棵新的二叉樹,且置新二叉樹的根結點的權值為其左？右子樹上根結點的權值之和；3. 在F中刪除這兩棵二叉樹,并將新二叉樹加入到F中；4. 重復2和3,直到F中只含一棵樹為止？這棵樹就是哈夫曼樹?其次,對n個結點的哈夫曼樹進行不等長編碼？保證任何一個字符的哈夫曼編碼不為另一字符的哈夫曼編碼的前綴？五？思考題：已知一棵二叉樹的層序序列是ABCDEFGH中序

9、序列是DBGEHJACI試畫出此二叉樹?實驗（四）圖的建立？基本操作以及遍歷一?實驗項目名稱:圖的建立？基本操作以及遍歷課時:4學時二?實驗要求1?熟練掌握圖的結構特性，熟悉圖的各種存儲結構的特點及適用范圍；2?熟練掌握幾種常見圖的遍歷方法及遍歷算法；三？實驗環境Widows操作系統？VC6.0四？實驗內容選用任一種圖的存儲結構，建立如下圖所示的帶權有向圖：要求:1?建立邊的條數為零的圖2 ?依次將圖的邊以及相應的權值插入,建立如上圖所示的圖，并將結點集合和權值集合輸出；3 ?對所建立的圖進行深度優先搜索或廣度優先搜索，輸出圖的遍歷序列；算法思想：首先,選定所使用的圖的存儲結構（鄰接矩陣存儲或

10、鄰接表存儲），建立圖的結構體定義?根據所選用的結構建立邊條數為零的圖，依次插入圖的結點和圖的各有向邊以及權值weight再次將圖的結點集合以及權值集合輸出，以驗證所建立圖的正確性最后調用圖的遍歷函數，實現圖的深度優先遍歷或廣度優先遍歷，并輸出遍歷序列？五？思考題：1?采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的哪種遍歷？2?采用鄰接表存儲的圖的廣度優先遍歷算法類似于二叉樹的哪種遍歷？實驗（五）排序與查找算法實現一?實驗項目名稱:排序與查找算法實現課時：2學時二?實驗要求1?熟練掌握幾種常見的排序方法及優缺點；2?熟練掌握幾種常見的查找方法及其性能的評價；3?上機完成常見排序與查找功能的程序？三？實驗環境Widows操作系統？VC6.0四？實驗內容編寫程序實現任一排序和查找功能？要求：1、數據元素個數n可由用戶隨意確定且有0<*80;2、可連續測試多組數據元素；3、數據元素由鍵盤輸入；4、將輸入的數據元素進行排序后，實現任意查找功能；若查找成功，則返回數據元素在數組中的下標和數據元素本身，若查找不成功，則輸出查找失敗信息；5、最后，將經過排序的數據元素輸出用以驗證？五？思考題：在待排序的兀素序列基本有序的前提下，哪種排序方法效率最高？附錄A西安理工大學實驗報告課程實驗名稱第頁共頁系另U實驗日期年月日專業班級組別實驗報告日期年月日姓名號實驗報告內容驗證性實驗一