1、數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書潘向輝/吳學(xué)毅編寫印包學(xué)院數(shù)字媒體技術(shù)專業(yè)2011年3月實驗說明【實驗環(huán)境】操作系統(tǒng)：Microsoft Windows XP/2000?編程語言:C語言【實驗要求】1. 實驗前，了解實驗?zāi)康模繉嶒瀮?nèi)容及相關(guān)的基本理論知識，并按照實驗內(nèi)容要求設(shè)計程序流程 ，書寫預(yù)習(xí)報告；2. 本課程實驗均為單人單組，獨立完成；3. 實驗所用計算機固定，以便實現(xiàn)實驗之間的延續(xù)性；4. 按要求完成實驗內(nèi)容，在實驗結(jié)束后按照格式和規(guī)范撰寫實驗報告？【實驗項目及學(xué)時分配】本課程實驗環(huán)節(jié)共計16學(xué)時，實驗項目及學(xué)時分配如下序號實驗項目學(xué)時實驗類型要求1線性表（順序表 及單鏈表）4驗證掌握線性表的基本操

2、作，熟悉指針 操作，完成實驗內(nèi)容要求2棧和隊列2驗證掌握順序棧？順序循環(huán)隊列以及鏈?zhǔn)蕉褩：完犃谢静僮鞑?yīng)用3二叉樹的構(gòu)建?基本操作和遍歷4設(shè)計掌握二叉樹的基本操作，實現(xiàn)二叉樹的三種遍歷？掌握哈夫曼樹的構(gòu)造以及編碼4圖的建立？基本操作以及遍歷4設(shè)計掌握圖的兩種存儲結(jié)構(gòu)，并實現(xiàn)某一存儲結(jié)構(gòu)下圖的操作的實現(xiàn)5排序與查找算法實現(xiàn)2設(shè)計掌握幾種排序和查找算法的思想，實現(xiàn)任意排序和查找算法【實驗報告及考核】1. 實驗報告撰寫符合格式及規(guī)范要求，詳見實驗報告撰寫格式及規(guī)范2. 本課程實驗占課程總成績的15%?實驗（一）線性表一 ？實驗項目名稱：線性表課時:4學(xué)時?實驗要求1、掌握順序表的定義與實現(xiàn)，包括查

3、找？插入？刪除算法的實現(xiàn),能在實際應(yīng)2、掌握在各種鏈表結(jié)構(gòu)中實現(xiàn)線性表操作的基本方法 用中選用適當(dāng)?shù)逆湵斫Y(jié)構(gòu)；三？實驗環(huán)境Widows操作系統(tǒng)？C語言四？實驗內(nèi)容（1） 順序表建立一如下表所示的學(xué)生信息表學(xué)號姓名性別年齡20001張三男2020002李四男22使用結(jié)構(gòu)體， 下內(nèi)容：1. 初始化2. 依次輸 鍵盤輸入）用順序表完成以線性表為空； 入數(shù)據(jù)元素；（由3. 完成數(shù)據(jù)元素的插入？刪除操作4. 取第i個數(shù)據(jù)元素5. 依次顯示當(dāng)前線性表中的數(shù)據(jù)元素（2）單鏈表建立一個單鏈表，依次輸入數(shù)據(jù)元素09?使用結(jié)構(gòu)體，用單鏈表完成以下內(nèi)容：1. 初始化單鏈表；2.在單鏈表指定位置插入一個數(shù)據(jù)元素3.

4、刪除指定位置的一個數(shù)據(jù)元素；4.取第i個數(shù)據(jù)元素5. 查找數(shù)據(jù)元素 x是否在單鏈表中；6.銷毀單鏈表； 五？思考題：在什么情況下使用順序表比鏈表好？實驗(二)棧和隊列一 ？實驗項目名稱：棧和隊列課時:2學(xué)時二？實驗要求1、 掌握棧的順序表示？鏈表表示以及相應(yīng)操作的實現(xiàn)？特別注意棧空和棧滿的條件；2、 掌握隊列的順序表示？鏈表表示以及相應(yīng)操作的實現(xiàn)？特別是循環(huán)隊列中隊頭與隊尾指針的變化情況；三？實驗環(huán)境Widows操作系統(tǒng)？VC6.0四？實驗內(nèi)容分別使用順序循環(huán)隊列和堆棧以及鏈?zhǔn)疥犃泻投褩＞帉懗绦颍号袛嘁粋€字符序列是否是回文？回文是指一個字符序列以中間字符為基準(zhǔn)，兩邊字符完全相同 ？如：“ABC

5、DEDCBA ?字符串長度小于等于 80,用 于判斷回文的字符串不包括字符串的結(jié)束標(biāo)記符？基本要求：(1) 字符序列可由用戶從鍵盤隨意輸入；(2) 可以連續(xù)測試多個字符序列，由用戶決定退出測試程序；算法思想：判斷回文的算法思想是：把字符串中的字符逐個分別存入隊列和 堆棧中，然后逐個出隊列和退棧并比較出隊列的數(shù)據(jù)元素和退棧的 數(shù)據(jù)元素是否相等，若全部相等則該字符序列為回文，否則就不是回文？基本操作：回文判斷操作主要包括入棧和入隊列？退棧和出隊列操作 ？在對堆棧以及隊列進行操作之前 ，必須對隊列以及堆棧進行初始化？若使用鏈?zhǔn)蕉褩：玩準(zhǔn)疥犃校僮鹘Y(jié)束后必須銷毀鏈表 ？五？思考題：1 ?棧有哪些特點及

6、與一般線性表有哪些區(qū)別？2 ?隊列有哪些特點及于一般線性表有哪些區(qū)別？實驗(三)二叉樹的構(gòu)建？基本操作和遍歷一 ?實驗項目名稱：二叉樹的構(gòu)建？基本操作和遍歷課時:4學(xué)時二?實驗要求1?熟練掌握二叉樹的結(jié)構(gòu)特性，熟悉二叉樹的各種存儲結(jié)構(gòu)的特點及適用范 圍；2?熟練掌握二叉樹的遍歷方法及遍歷算法；3?掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權(quán)路徑長度的計算？三？實驗環(huán)境Widows操作系統(tǒng)？VC6.0四？實驗內(nèi)容(1)二叉樹建立如下圖所示的二叉樹：要求:1?建立帶頭結(jié)點的二叉樹，將?依次將二叉樹的所有?用戶可由鍵盤輸入數(shù)?打印二叉樹；?對二叉樹實現(xiàn)前入乞樹初始化為空;7上圖所示的二叉樹；現(xiàn)對二叉樹各

7、結(jié)點的插入 ？刪除等操作;?中序？后序遍歷；算法思想：建立一棵只有頭結(jié)點的二叉樹，并通過調(diào)用插入左子樹和插入右子樹操作 依次將上圖中的結(jié)點插入二叉樹中，利用二叉樹的特殊中序遍歷方法將該樹以凹 入表示法打印顯示？最后,調(diào)用二叉樹的前序？中序？后序遍歷函數(shù)對二叉樹進行 遍歷,并顯示遍歷結(jié)果？ ？哈夫曼樹設(shè)計各設(shè)有字符集A?B?C?D,各字符在電文中出現(xiàn)的次數(shù)集為1,3,5,7, 字符的哈夫曼編碼？要求：1?構(gòu)造字符集的哈夫曼樹,其結(jié)點數(shù)據(jù)結(jié)構(gòu)如下：weightflagpare ntleftChildrightChild哈夫構(gòu)造哈夫曼編碼，輸出權(quán)值及其對應(yīng)的編碼？算法思想：首先，由給定的n個權(quán)值構(gòu)造

8、有2n-1個結(jié)點的哈夫曼樹？在哈夫曼樹中，其葉 結(jié)點的權(quán)值為相應(yīng)的給定權(quán)值，非葉結(jié)點的權(quán)值為其孩子結(jié)點的權(quán)值之和？哈夫曼樹構(gòu)造過程如下：1. 根據(jù)給定的n個權(quán)值w 1 ,w2,wn,構(gòu)成的n棵二叉樹的森林F =T1,T2,斤,其中每棵二叉樹Ti中只有一個權(quán)值為wj的結(jié)點，其左 ?右子樹均為空；2. 在F中選取根結(jié)點的權(quán)值最小和次小的兩棵樹作為左？右子樹構(gòu)造一棵 新的二叉樹,且置新二叉樹的根結(jié)點的權(quán)值為其左？右子樹上根結(jié)點的權(quán)值 之和；3. 在F中刪除這兩棵二叉樹,并將新二叉樹加入到F中；4. 重復(fù)2和3,直到F中只含一棵樹為止？這棵樹就是哈夫曼樹?其次,對n個結(jié)點的哈夫曼樹進行不等長編碼？保證

9、任何一個字符的哈夫曼編碼 不為另一字符的哈夫曼編碼的前綴？五？思考題：已知一棵二叉樹的層序序列是ABCDEFGH中序序列是DBGEHJACI試畫出 此二叉樹?實驗（四）圖的建立？基本操作以及遍歷一 ?實驗項目名稱:圖的建立？基本操作以及遍歷課時:4學(xué)時二?實驗要求1?熟練掌握圖的結(jié)構(gòu)特性，熟悉圖的各種存儲結(jié)構(gòu)的特點及適用范圍；2?熟練掌握幾種常見圖的遍歷方法及遍歷算法；三？實驗環(huán)境Widows 操作系統(tǒng)？VC6.0四？實驗內(nèi)容選用任一種圖的存儲結(jié)構(gòu)，建立如下圖所示的帶權(quán)有向圖：要求:1 ?建立邊的條數(shù)為零的圖2 ? 依次將圖的邊以及相應(yīng)的權(quán)值插入,建立如上圖所示的圖，并將結(jié)點集合和權(quán)值集合輸出

10、；3 ?對所建立的圖進行深度優(yōu)先搜索或廣度優(yōu)先搜索，輸出圖的遍歷序列； 算法思想：首先,選定所使用的圖的存儲結(jié)構(gòu)（鄰接矩陣存儲或鄰接表存儲），建立圖的結(jié)構(gòu)體定 義?根據(jù)所選用的結(jié)構(gòu)建立邊條數(shù)為零的圖，依次插入圖的結(jié)點和圖的各有向邊以及權(quán) 值weight再次將圖的結(jié)點集合以及權(quán)值集合輸出，以驗證所建立圖的正確性最后調(diào)用 圖的遍歷函數(shù)，實現(xiàn)圖的深度優(yōu)先遍歷或廣度優(yōu)先遍歷，并輸出遍歷序列？ 五？思考題：1 ?采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的哪種遍歷？2?采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的哪種遍歷？實驗（五）排序與查找算法實現(xiàn)一?實驗項目名稱:排序與查找算法實現(xiàn)課時：

11、2學(xué)時二?實驗要求1 ?熟練掌握幾種常見的排序方法及優(yōu)缺點；2?熟練掌握幾種常見的查找方法及其性能的評價；3?上機完成常見排序與查找功能的程序？三？實驗環(huán)境Widows操作系統(tǒng)？VC6.0四？實驗內(nèi)容編寫程序?qū)崿F(xiàn)任一排序和查找功能？要求：1、數(shù)據(jù)元素個數(shù)n可由用戶隨意確定且有0<*80;2、可連續(xù)測試多組數(shù)據(jù)元素；3、數(shù)據(jù)元素由鍵盤輸入；4、 將輸入的數(shù)據(jù)元素進行排序后，實現(xiàn)任意查找功能；若查找成功，則 返回數(shù)據(jù)元素在數(shù)組中的下標(biāo)和數(shù)據(jù)元素本身，若查找不成功，則輸 出查找失敗信息；5、最后，將經(jīng)過排序的數(shù)據(jù)元素輸出用以驗證？ 五？思考題：在待排序的兀素序列基本有序的前提下，哪種排序方法效率最高？附錄A西安理工大學(xué)實驗報告課程實驗名稱第頁共頁系另U實 驗日期年月日專業(yè)班級組別實驗報告日期年月日姓 名號實驗報告內(nèi)容驗證性