數(shù)據(jù)結(jié)構(gòu)試驗指導書

1、計算機專業(yè)實驗教林數(shù)據(jù)結(jié)構(gòu)（C語言描述）實驗鵬辱書田軍峰夏克儉編北京科技大學信息工程學院計算機系、計算機實驗室二OO六年四月前言數(shù)據(jù)結(jié)構(gòu)是信息工程學院計算機科學與技術(shù)系計算機專業(yè)及其他院系 相關(guān)專業(yè)的一門重要專業(yè)基礎(chǔ)課，也是一門本科生必修課。在計算機科學的各領(lǐng) 域中，都會或多或少的用到數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識，學好數(shù)據(jù)結(jié)構(gòu)這門課程，對從 事訃算機技術(shù)及相關(guān)領(lǐng)域的工作人員來說是非常重要，尤其對從事軟件開發(fā)的工 程師來說更為重要。數(shù)據(jù)結(jié)構(gòu)的某些知識和相關(guān)算法比較抽象，理解和熟練掌握有一定的難 度。學習這門課程，實驗是非常重要的環(huán)節(jié)，因為通過實驗?zāi)苡行У睦斫馑鶎W的 數(shù)據(jù)結(jié)構(gòu)的知識點和算法。根據(jù)北京科技大學

2、本科教學訃劃（05版）規(guī)定，數(shù) 據(jù)結(jié)構(gòu)這門課程共有課堂教學42學時，課內(nèi)上機實驗12學時，課外上機28 學時，合計80小時，實驗學時占到總學時的50%,可見實驗課在本門課程中的 重要性。在以前的教學過程中，同學們對實驗重視不夠，尤其沒有很好的理解一 些重要的算法。為了幫助同學們更好的理解數(shù)據(jù)結(jié)構(gòu)的知識要點和算法，根據(jù)數(shù) 據(jù)結(jié)構(gòu)實驗教學大綱，參考多年的教學實驗實踐，收集、整理并編寫了這本實 驗指導書，希望同學們能通過這本書的指導和上機實驗，掌握數(shù)據(jù)結(jié)構(gòu)及其算法。要想學好數(shù)據(jù)結(jié)構(gòu)，C語言及相關(guān)計算機知識的掌握也是必不可少的。特 別是C語言中關(guān)于數(shù)組、結(jié)構(gòu)和指針部分尤其要熟練掌握。本書是按照教學的章

3、節(jié)順序安排每個實驗，每個實驗都有實驗準備、實驗 目的、實驗內(nèi)容、實驗提示等部分組成。本書參考了計算機專業(yè)課數(shù)據(jù)結(jié)構(gòu)任課教師夏克儉老師提供的實驗習 題，并山夏克儉老師審定。在此感謝各位任課老師的辛苦工作和寶貴意見。山于 時間倉促，疏漏與不當之處在所難免，真誠希望得到使用本書的教師和學生的批 評指正。編者 2006年4月2路汲漫其修遠兮汙將上下而求索-百度文庫目錄刖呂2目錄3實驗一順序線性表的基本操作4實驗二單鏈表的基本操作5實驗三棧的順序表示與實現(xiàn)6實驗四棧的鏈式表示和實現(xiàn)6實驗五 隊列的順序表示與實現(xiàn)8實驗六隊列的鏈式表示與實現(xiàn)8實驗七二叉樹的基本操作10實驗八哈夫曼樹的構(gòu)造及編碼實驗10實驗

4、九二叉排序樹的基本操作11附錄一：數(shù)據(jù)結(jié)構(gòu)實驗教學大綱12附錄二：數(shù)據(jù)結(jié)構(gòu)實驗報告格式133實驗一順序線性表的基本操作【實驗?zāi)康摹?. 熟悉C語言的上機環(huán)境，進一步掌握C語言的結(jié)構(gòu)特點。2. 掌握線性表的順序存儲結(jié)構(gòu)的定義及C語言的實現(xiàn)。3. 掌握順序線性表的建立、插入、刪除、查找等基本操作?！緦嶒瀮?nèi)容】把從鍵盤輸入的n個整數(shù)以順序存儲的方式建立一個線性表，然后輸出該表 及該表的長度；刪除笫m個結(jié)點后重新輸出該表及長度；在表中的第k個結(jié)點 后插入2個結(jié)點后重新輸出該表?！緦嶒灠才拧坑捎谠搶嶒炇菙?shù)據(jù)結(jié)構(gòu)的第一個實驗，建議適當多安排一些時間進行熟悉。 建議課時安排如下：課外6學時，課內(nèi)2學時【實驗

5、提示】1. 采用C語言的數(shù)組類型實現(xiàn)線性表的順序存儲，用C語言的結(jié)構(gòu)體類型 定義順序表結(jié)點：、#define MAXSIZE 10typedef int elemtype; 線性表中存放整形元素typedef struct elemtype vecMAXSIZE;int len; sequenList;2. 為了方便調(diào)試及編程，可以分析題目，將整個實驗分解成若干個小的函 數(shù)，最后由主函數(shù)分別調(diào)用子函數(shù)即可，建議編寫下列子函數(shù)：CreateList/建立順序表函數(shù)Print Li st輸出順序表函數(shù)GetLenList/順序表長度函數(shù)Insert/在順序表中插入結(jié)點函數(shù)Delete/在順序表刪除

6、結(jié)點函數(shù)3. 進行實驗結(jié)果測試時，要注意分別對頭結(jié)點、尾結(jié)點及空表分別進行測 試，另外要對滿表進行測試，看是否有溢出情況發(fā)生。實驗二單鏈表的基本操作【實驗?zāi)康摹縄. 掌握單鏈表的鏈式存儲結(jié)構(gòu)的定義及c語言的實現(xiàn)。3. 掌握單鏈表的建立、插入、刪除、查找、合并等基本操作?！緦嶒瀮?nèi)容】分別把從鍵盤輸入的nl個整數(shù)和n2個整數(shù)以鏈式存儲的方式建立兩個單鏈 表，然后輸出兩表及兩表的長度；刪除第1個鏈中的笫m個結(jié)點后后重新輸出 該表及長度；在第2表中的第k個結(jié)點后插入2個結(jié)點后重新輸出該表；最后將 兩個表合并后重新輸出新表及長度，最后輸出相鄰兩結(jié)點data值之和為最大的 第一結(jié)點?！緦嶒灠才拧拷ㄗh課時安

7、排如下：課外4學時，課內(nèi)2學時【實驗提示】1. 采用C語言的定義表結(jié)點如下：typedef int elemtype;typedef struct elemtype data; /數(shù)據(jù)域struct node *next; 指針域 linkList;2. 為了方便調(diào)試及編程，可以分析題目，將整個實驗分解成若干個小的函 數(shù)，最后由主函數(shù)分別調(diào)用子函數(shù)即可，建議編寫下列子函數(shù)：CreateList/建立表函數(shù)Print Li st/輸出表函數(shù)GetLenList/求表長度函數(shù)Insert插入結(jié)點函數(shù)Delete刪除結(jié)點函數(shù)MergeList合并表函數(shù)Adjmax(L)求值函數(shù)3. 進行實驗結(jié)果測試

8、時，要注意分別對頭結(jié)點、尾結(jié)點及空表分別進行測試。實驗三棧的順序表示與實現(xiàn)【實驗?zāi)康摹空莆諚５捻樞虮硎竞蛯崿F(xiàn)。【實驗內(nèi)容】編寫一個程序?qū)崿F(xiàn)順序棧的各種基本運算，并在此基礎(chǔ)上設(shè)計一個主程序, 完成如下功能：1. 初始化順序棧2. 插入元素3. 刪除棧頂運算4. 取棧頂元素5. 遍歷順序棧6. 置空順序?！緦嶒灠才拧拷ㄗh課時安排如下：課外2學時，課內(nèi)1學時【實驗提示】采用C語言的定義順序棧的存儲結(jié)構(gòu)：typedef struct elemtype stackMAXNUM;int top ; sequenStack;實驗四棧的鏈式表示和實現(xiàn)【實驗?zāi)康摹?掌握棧的鏈式表示和實現(xiàn)?！緦嶒瀮?nèi)容】編寫一個程

9、序?qū)崿F(xiàn)鏈棧的下列各種基本運算:1. 初始化鏈棧2. 鏈棧置空3. 入棧4. 出棧5. 取棧頂元素6. 遍歷鏈棧并在此基礎(chǔ)上編寫實現(xiàn)算術(shù)表達式求值程序(棧的運用)：設(shè)操作數(shù)：0, 1, 2,，8, 9 (可擴充)；運算符：+，*,/,(,),#(#號為結(jié)束)。輸入中綴表達式，如：5+(42)*3#,將其轉(zhuǎn)換成后綴表達式：5423*+#, 然后計算，本例結(jié)果為11。程序結(jié)構(gòu)：類型說明；Clearstack(S)、Emptystack(S)、Push(S)、Pop(S)； 中綴到后綴轉(zhuǎn)換的函數(shù)：Mid-post(En, Bn)； 后綴表達式求值的函數(shù)：Postcount(Bn)； main ()變量

10、說明；輸入中綴表達式，存入En； 調(diào)用 Mid-post(E, B)； 調(diào)用 Postcount(B)； 打印表達式結(jié)果；Y 繼續(xù)？! N停止【實驗安排】建議課時安排如下：課外2學時，課內(nèi)1學時【實驗提示】采用C語言的定義鏈棧的存儲結(jié)構(gòu):typedef int elemtype;typedef struct elemtype data;Stacknode *next; stacknode;實驗五隊列的順序表示與實現(xiàn)【實驗?zāi)康摹空莆贞犃械捻樞虮硎竞蛯崿F(xiàn)?！緦嶒瀮?nèi)容】編寫一個程序?qū)崿F(xiàn)順序隊列的各種基本運算，并在此基礎(chǔ)上設(shè)計一個主程 序，完成如下功能：1. 初始化隊列2. 建立順序隊列3. 入隊4.

11、 出隊5. 判斷隊列是否為空6. 取隊列頭元素7. 遍歷隊列【實驗安排】建議課時安排如下：課外2學時，課內(nèi)1學時【實驗提示】1. 采用C語言的定義順序隊列的存儲結(jié)構(gòu)：typedef struct elemtype suqueueMAXNUM;int front ;int rear; sequenStack;2. 注意：當頭尾指針相等時，隊列為空；在非空隊列里，隊頭指針始終指 向隊頭元素，隊尾指針指向隊列的下一元素位置。實驗六隊列的鏈式表示與實現(xiàn)【實驗LJ的】掌握隊列的鏈式表示和實現(xiàn)?！緦嶒瀮?nèi)容】編寫一個程序?qū)崿F(xiàn)鏈隊的各種基本運算：1. 初始化隊列2. 建立鏈隊列3. 入隊4. 出隊5. 判斷隊

12、列是否為空6. 取隊列頭元素7. 遍歷鏈隊列最后編寫一個主程序，實現(xiàn)如下的圖的過程:【實驗安排】建議課時安排如下：課外2學時，課內(nèi)1學時【實驗提示】1. 采用C語言的定義順序隊列的存儲結(jié)構(gòu): typedef struct Qnode elemtype type data;Stiuct Qnode *next;JQnodetype;132. 為了方便實現(xiàn)，可以使用頭結(jié)點。實驗七【實驗?zāi)康摹?. 掌握二叉樹的鏈式存儲結(jié)構(gòu)及實現(xiàn)方法。2. 掌握二叉樹的遍歷方法。3. 掌握二叉樹中插入結(jié)點、刪除結(jié)點的方法。4. 掌握二叉樹的結(jié)點個數(shù)、葉子結(jié)點個數(shù)和樹的深度的汁算方法?！緦嶒瀮?nèi)容】用鍵盤輸入一字符串，按

13、照滿二義樹的特點生成一顆二義樹，并將該二義樹 分別用先序、中序和后序的方法遍歷并輸出遍歷結(jié)果，然后輸出該樹的深度?！緦嶒灠才拧拷ㄗh課時安排如下：課外2學時，課內(nèi)1學時【實驗提示】1. 采用C語言的定義樹的存儲結(jié)構(gòu)：typedef struct btnode char data;struct btnode *lchild, *rchild bitree;2. 可以考慮釆用遞歸的方法先創(chuàng)建根結(jié)點，然后分別創(chuàng)建左右子樹。在創(chuàng) 建二叉樹的過程中，要注意結(jié)點數(shù)是根據(jù)輸入的字符確定的。實驗八哈夫曼樹的構(gòu)造及編碼實驗【實驗?zāi)康摹空莆展蚵鼧涞臉?gòu)造方法及其編碼方法?！緦嶒瀮?nèi)容】設(shè)電文字符集D及各字符出現(xiàn)的概率

14、F如下：D=a, b, c, d, e, f, g, h）（字符數(shù) n=8）F=5, 29, 7, 8, 14, 23, 3, 11）（%）編寫完成下列功能的程序： 構(gòu)造關(guān)于F的Huffman樹； 求出并打印D總各字符的Huffman編碼?！緦嶒灠才拧拷ㄗh課時安排如下：課外2學時，課內(nèi)1學時【實驗提示】在哈夫曼樹編碼時，一般令左分支為0,右分支為1,然后對哈夫曼樹進行遍 歷，輸出哈夫曼編碼。實驗九二叉排序樹的基本操作【實驗?zāi)康摹?掌握二義排序樹的構(gòu)造方法?！緦嶒瀮?nèi)容】設(shè)英文句子：“everyone round you can hear you when you speak.”，試編寫完 成下面

15、任務(wù)的程序。（1）依次讀入句中各單詞，構(gòu)造一棵二義排序樹；（2）按LDR遍歷此二叉排序樹。LDR： can everyone hear round speak when you （有序）【實驗安排】建議課時安排如下：課外2學時，課內(nèi)1學時【實驗提示】若遍歷二義排序樹的結(jié)果序列無序，則說明構(gòu)樹時發(fā)生錯誤。附錄一：數(shù)據(jù)結(jié)構(gòu)實驗教學大綱課程名稱：數(shù)據(jù)結(jié)構(gòu)課程總學時：54課程編號：050414上機學時：12面向?qū)I(yè)對象：計算機系本科生實驗類別：專業(yè)課實驗實驗地點：計算機實驗室實驗教學的目的數(shù)據(jù)結(jié)構(gòu)是計算機軟件的專業(yè)基礎(chǔ)課，與之配套的上機實驗是體現(xiàn)理論聯(lián) 系實際的重要環(huán)節(jié)。通過本實驗課，學生可以將課堂、書本上所學到的軟件理論、 技術(shù)與方法運用到實驗任務(wù)的題目中。其目的之一是為后繼課程（如“操作系統(tǒng)”、 “編譯系統(tǒng)”、“數(shù)據(jù)庫原理”等）的學習打下良好的基礎(chǔ)；其二是提高學生獨立 承擔編程任務(wù)的能力與水平。實驗教學的基本要求了解各種類型的“數(shù)據(jù)元素”、“數(shù)據(jù)結(jié)構(gòu)”的描述及存儲方法；將一些重要的算 法轉(zhuǎn)換成c語言程療;實現(xiàn)。要求將布置的程序題調(diào)試成功、在計算機上正確運 行。鼓勵學生編程獨創(chuàng)性的發(fā)揮。實驗教材數(shù)據(jù)結(jié)構(gòu)+算法（國防工業(yè)出版社）