《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)書

1、數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)書肇慶學(xué)院 計算機(jī)學(xué)院/軟件學(xué)院 編前 言數(shù)據(jù)結(jié)構(gòu)是信息與計算科學(xué)專業(yè)中一門重要的專業(yè)基礎(chǔ)課程。當(dāng)用計算機(jī)來解決實際問題時，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對象，通過這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了厚實的知識基礎(chǔ)，同時也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在計算機(jī)應(yīng)用專業(yè)中具有舉足輕重的作用。本書是針對數(shù)據(jù)結(jié)構(gòu)教程的上機(jī)實驗指導(dǎo)書，內(nèi)容包括線性表、棧和隊列、串、數(shù)組和稀疏矩陣、遞歸、樹狀結(jié)構(gòu)、圖、查找、排序等。書后附錄中給出了學(xué)生應(yīng)提交的實驗報告的格式。本上機(jī)實驗指導(dǎo)書旨在通過指導(dǎo)學(xué)生上機(jī)實踐，對常用

2、數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實現(xiàn)方法的理論得到進(jìn)一步的掌握，并對在不同存儲結(jié)構(gòu)上實現(xiàn)不同的運(yùn)算方式和技巧有所體會。本實驗指導(dǎo)書的內(nèi)容都是基于C語言的，因此，要求學(xué)生對C語言要有一定的了解。建議使用Turbo C 2.0或VC+作為實驗平臺。根據(jù)學(xué)生的實際情況，本上機(jī)實驗指導(dǎo)書的內(nèi)容大多數(shù)為基本算法的綜合驗證，也包括部分算法設(shè)計。本上機(jī)實驗指導(dǎo)書共有9個實驗內(nèi)容，每個實驗約為4課時。由于作者對數(shù)據(jù)結(jié)構(gòu)知識所知有限，書中難免存在錯誤，懇請讀者及時加以指正，以便改進(jìn)。如有對于本書的意見和建議，請與編者聯(lián)系，E-mail：。衷心感謝！編 者目錄前 言實驗一 順序表1實驗二 單鏈

3、表3實驗三 棧和隊列5實驗四 串7實驗五 數(shù)組8實驗六 樹和二叉樹10實驗七 圖12實驗八 查找14實驗九 排序16參考資料18附錄1：肇慶學(xué)院計算機(jī)系實驗報告格式19附錄2：上機(jī)實習(xí)注意事項21實驗一 順序表一、預(yù)備知識1. 順序表的存儲結(jié)構(gòu)形式及其描述2. 順序表的建立、查找、插入和刪除操作二、實驗?zāi)康?. 掌握順序表的存儲結(jié)構(gòu)形式及其描述2. 掌握順序表的建立、查找、插入和刪除操作三、實驗內(nèi)容1. 編寫函數(shù)，輸入一組整型元素序列，建立一個順序表。2. 編寫函數(shù)，實現(xiàn)對該順序表的遍歷。3. 編寫函數(shù)，在順序表中進(jìn)行順序查找某一元素，查找成功則返回其存儲位置i，否則返回錯誤信息。4. 編寫函

4、數(shù)，實現(xiàn)在順序表的第i個位置上插入一個元素x的算法。5. 編寫函數(shù)，實現(xiàn)刪除順序表中第i個元素的算法。6. 編寫利用有序表插入算法建立一個有序表的函數(shù)。7. 編寫函數(shù)，利用以上算法，建立兩個非遞減有序表，并把它們合并成一個非遞減有序表。8. 編寫函數(shù)，實現(xiàn)輸入一個元素x，把它插入到有序表中，使順序表依然有序。9. 編寫一個主函數(shù)，在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。四、實驗說明1.順序表的存儲定義#define MAXSIZE 100 /順序表的最大元素個數(shù)typedef int ElemType；/順序表的元素類型typedef struct list ElemType elem

5、MAXSIZE；/靜態(tài)線性表 int length； /順序表的實際長度 SqList；/順序表的類型名五、注意問題1. 插入、刪除時元素的移動原因、方向及先后順序。2. 理解不同的函數(shù)形參與實參的傳遞關(guān)系。六、實驗報告根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗二 單鏈表一、預(yù)備知識1. 動態(tài)鏈表的存儲結(jié)構(gòu)形式及其描述2. 單鏈表的建立、查找、插入和刪除操作二、實驗?zāi)康?. 掌握單鏈表的存儲結(jié)構(gòu)形式及其描述2. 掌握單鏈表的建立、查找、插入和刪除操作三、實驗內(nèi)容1. 編寫函數(shù)，實現(xiàn)隨機(jī)產(chǎn)生或鍵盤輸入一組元素，建立一個帶頭結(jié)點的單鏈表（無序）。2. 編寫函數(shù)，實現(xiàn)遍歷單鏈表。3. 編寫函數(shù)，實現(xiàn)

6、把單向鏈表中元素逆置（不允許申請新的結(jié)點空間）。4. 編寫函數(shù)，建立一個非遞減有序單鏈表。5. 編寫函數(shù)，利用以上算法，建立兩個非遞減有序單鏈表，然后合并成一個非遞減鏈表。6. 編寫函數(shù)，在非遞減有序單鏈表中插入一個元素使鏈表仍然有序。7. 編寫函數(shù)，實現(xiàn)在非遞減有序鏈表中刪除值為x的結(jié)點。8. 編寫一個主函數(shù)，在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。四、實驗說明1. 單鏈表的類型定義#include typedef int ElemType；/單鏈表結(jié)點類型typedef struct LNode ElemType data； struct LNode *next； LNode，*L

7、inkList；2. 為了算法實現(xiàn)簡單，最好采用帶頭結(jié)點的單鏈表。五、注意問題1. 重點理解鏈?zhǔn)酱鎯Φ奶攸c及指針的含義。2. 注意比較順序存儲與鏈?zhǔn)酱鎯Φ母髯蕴攸c。3. 注意比較帶頭結(jié)點、無頭結(jié)點鏈表實現(xiàn)插入、刪除算法時的區(qū)別。4. 單向鏈表的操作是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，一定要注意對這部分的常見算法的理解。六、實驗報告根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗三 棧和隊列一、預(yù)備知識1.棧的順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)的類型定義方法及其基本操作算法2.隊列的順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)的類型定義方法及其基本操作算法二、實驗?zāi)康?.掌握棧、隊列的思想及其存儲實現(xiàn)2.掌握棧、隊列的常見算法的程序?qū)崿F(xiàn)三、實驗內(nèi)容1.

8、編寫函數(shù)，采用鏈?zhǔn)酱鎯崿F(xiàn)棧的初始化、入棧、出棧操作。2.編寫函數(shù)，采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作。3.編寫函數(shù)，采用鏈?zhǔn)酱鎯崿F(xiàn)隊列的初始化、入隊、出隊操作。4.編寫函數(shù)，采用順序存儲實現(xiàn)隊列的初始化、入隊、出隊操作。5.編寫一個主函數(shù)，在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。四、實驗說明1.順序棧的類型定義#define MAX 100 /棧的最大值typedef struct ElemType *base； int top； SqStack； 2.鏈棧的類型定義typedef struct SqNode SElemType data； SqNode *Link； *S

9、qptr；typedef struct Sqptr top；/棧項指針 3.順序隊列的類型定義#define MAX 100 /隊列的最大長度typedef struct ElemType *base； int front，rear； SqQueue； 4.單鏈隊列的類型定義typedef struct QNode QElemType data； struct QNode *next； *QueuePtr；typedef struct QueuePtr frout；/隊頭指針 QueuePtr rear；/隊尾指針 五、注意問題1.重點理解棧、隊列的算法思想，能夠根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)

10、。2.明確棧、隊列均是特殊的線性表。3.棧、隊列的算法是后續(xù)實驗的基礎(chǔ)（廣義表、樹、圖、查找、排序等）。六、實驗報告根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗四 串一、預(yù)備知識1.字符串的基本概念2.字符串的模式匹配算法二、實驗?zāi)康?.理解字符串的模式匹配算法（包括KMP算法）三、實驗內(nèi)容1.編寫函數(shù)，實現(xiàn)字符串的模式匹配算法。四、實驗說明1.從鍵盤輸入主串和子串元素，調(diào)用字符串的模式匹配算法，判斷子串是否在主串中，若在，返回起始位置，否則顯示否定信息。五、注意問題1.明確串也是特殊的線性表，掌握其特殊性所在。六、實驗報告根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗五 數(shù)組一、預(yù)備知識1.稀疏矩

11、陣的三元組表壓縮存儲結(jié)構(gòu)2.稀疏矩陣的三元組表表示方法下的相乘算法二、實驗?zāi)康?.掌握稀疏矩陣的三元組表存儲結(jié)構(gòu)的實現(xiàn)2.實現(xiàn)稀疏矩陣的三元組表表示下的相乘算法三、實驗內(nèi)容1.編寫程序，實現(xiàn)利用三元組表進(jìn)行兩個稀疏矩陣相乘的算法。四、實驗說明1.三元組表的類型定義#define MAXSIZE 1000/非零元素個數(shù)的最大值typedef struct int row，col；/非零元素的行下標(biāo)和列下標(biāo) ElemType e；/非零元素的值 Triple；typedef struct Triple dataMAXSIZE+1； /非零元素的三元組表，data0未用 int mu，nu，tu；/

12、矩陣的行數(shù)、列數(shù)和非零元素個數(shù) TSMatrix；五、注意問題1.首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運(yùn)算是否相匹配。可設(shè)矩陣的行數(shù)和列數(shù)均不超過20。2.程序可以對三元組的輸入順序加以限制，例如，按行優(yōu)先，以便提高計算效率。3.在用三元組表示稀疏矩陣時，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可用二維數(shù)組存放。4.三元組表是線性表的一種應(yīng)用，通過它可以更好地理解線性表的存儲結(jié)構(gòu)。同時矩陣又是圖的重要的存儲方式，所以這個實驗對更好地掌握線性表對將來對圖的理解都有極大的幫助。六、實驗報告根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗六 樹和二叉樹一、預(yù)備知識1

13、.二叉樹的二叉鏈表存儲結(jié)構(gòu)2.二叉樹的常見算法二、實驗?zāi)康?.掌握二叉樹的存儲實現(xiàn)2.掌握二叉樹的遍歷思想3.掌握二叉樹的常見算法的程序?qū)崿F(xiàn)三、實驗內(nèi)容1.編寫函數(shù)，輸入字符序列，建立二叉樹的二叉鏈表。2.編寫函數(shù)，實現(xiàn)二叉樹的中序遞歸遍歷算法。(最好也能實現(xiàn)前綴和后綴遍歷算法)3.編寫函數(shù)，實現(xiàn)二叉樹的中序非遞歸遍歷算法。4.編寫函數(shù)，借助隊列實現(xiàn)二叉樹的層次遍歷算法。5.編寫函數(shù)，求二叉樹的高度。6.編寫函數(shù)，求二叉樹的結(jié)點個數(shù)。7.編寫函數(shù)，求二叉樹的葉子個數(shù)。8.編寫函數(shù)，交換二叉樹每個結(jié)點的左子樹和右子樹。9.編寫一個主函數(shù)，在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。四、實驗說

14、明1.二叉鏈表的類型定義#define ElemType char/二叉鏈表結(jié)點類型typedef struct BiTNode ElemType data； struct BiTNode *lchild，*rchild； BiTNode，*BiTree；2.元素類型可以根據(jù)實際情況選取。五、注意問題1.注意理解遞歸算法的執(zhí)行步驟。2.注意字符類型數(shù)據(jù)在輸入時的處理。3.重點理解如何利用棧結(jié)構(gòu)實現(xiàn)非遞歸算法六、實驗報告根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗七 圖一、預(yù)備知識1.圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)2.圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷算法二、實驗?zāi)康?.掌握圖的存儲思想及其存儲

15、實現(xiàn)2.掌握圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)3.掌握圖的常見應(yīng)用算法的思想及其程序?qū)崿F(xiàn)三、實驗內(nèi)容1.編寫函數(shù)，采用鄰接矩陣表示法，構(gòu)造一個無向網(wǎng)。2.編寫函數(shù)，實現(xiàn)從鍵盤輸入數(shù)據(jù)，建立一個有向圖的鄰接表。3.編寫函數(shù)，輸出該鄰接表。4.編寫函數(shù)，采用鄰接表存儲實現(xiàn)無向圖的深度優(yōu)先非遞歸遍歷。5.編寫函數(shù)，采用鄰接表存儲實現(xiàn)無向圖的廣度優(yōu)先遍歷。6.編寫一個主函數(shù)，在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。四、實驗說明1. 鄰接表的類型定義#define MAX_VERTEX_NUM 10 /頂點最大個數(shù)typedef struct ArcNode int adjvex； st

16、ruct ArcNode *nextarc； int weight； /邊的權(quán) ArcNode； /表結(jié)點#define VertexType int /頂點元素類型typedef struct VNode int degree，indegree；/頂點的度，入度 VertexType data； ArcNode *firstarc； VNode/*頭結(jié)點*/，AdjListMAX_VERTEX_NUM；typedef struct AdjList vertices； int vexnum，arcnum；/頂點的實際數(shù)，邊的實際數(shù) ALGraph；2.上述類型定義可以根據(jù)實際情況適當(dāng)調(diào)整。五、

17、注意問題1.注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。六、實驗報告根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗八 查找一、預(yù)備知識1.查找的不同方法，圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu)2.二叉排序樹的構(gòu)造和查找方法二、實驗?zāi)康?.掌握各種不同查找算法的思想及高級語言程序?qū)崿F(xiàn)2.掌握二叉排序樹的查找、插入、刪除算法的思想及程序?qū)崿F(xiàn)三、實驗內(nèi)容1.編寫函數(shù)，建立有序表，采用折半查找實現(xiàn)某一已知的關(guān)鍵字的查找。(采用順序表存儲結(jié)構(gòu))2.編寫函數(shù)，隨機(jī)產(chǎn)生一組關(guān)鍵字，利用二叉排序樹的插入算法建立二叉排序樹。3.編寫函數(shù)，在以上二叉排序樹中刪除某一指定關(guān)鍵字元素。4.編寫一個主函數(shù)，在主函數(shù)中設(shè)計一個簡單的菜單，分

18、別調(diào)試上述算法。四、實驗說明1.二叉排序樹的類型定義 /二叉排序樹的存儲結(jié)構(gòu)采用二叉鏈表作為存儲結(jié)構(gòu)#define ElemType char/二叉鏈表結(jié)點類型typedef struct BiTNode ElemType data； struct BiTNode *lchild，*rchild； BiTNode，*BiTree；2.各種關(guān)鍵字?jǐn)?shù)據(jù)輸入可利用隨機(jī)函數(shù)自動產(chǎn)生，以便節(jié)省上機(jī)時間。五、注意問題1.注意理解折半查找的適用條件（思考：鏈表能否實現(xiàn)折半查找？）。2.注意建立二叉排序樹相同元素的處理。3.注意理解靜態(tài)查找、動態(tài)查找概念。4.比較各種查找算法的各自特點，能夠根據(jù)實際情況選擇合

19、適的查找方法。六、實驗報告根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗九 排序一、預(yù)備知識1.排序算法(插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等)的思想、特點及其適用條件二、實驗?zāi)康?.掌握常見的排序算法(插入排序、交換排序、選擇排序、歸并排序、基數(shù)排序等)的思想、特點及其適用條件2.熟練掌握常見的排序算法的程序?qū)崿F(xiàn)三、實驗內(nèi)容輸入一組關(guān)鍵字序列，分別實現(xiàn)下列排序算法:1.編寫函數(shù)，實現(xiàn)簡單選擇排序、直接插入排序和冒泡排序算法。2.編寫函數(shù)，實現(xiàn)希爾排序算法。3.編寫函數(shù)，實現(xiàn)快速排序算法。4.編寫函數(shù)，實現(xiàn)堆排序算法。5.編寫函數(shù)，實現(xiàn)折半插入排序算法。6.編寫一個主函數(shù)，在主函數(shù)中

20、設(shè)計一個簡單的菜單，分別調(diào)試上述算法。四、實驗說明1.排序序列的類型定義#define MAXSIZE 100 /*參加排序元素的最大個數(shù)*/typedef struct list int key； RedType；typedef struct RedType rMAXSIZE+1； int length； /*參加排序元素的實際個數(shù)*/ SqList；五、注意問題1.注意理解各種算法的思想、了解算法的適用情況及時間復(fù)雜度，能夠根據(jù)實際情況選擇合適的排序方法。六、實驗報告根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。參考資料數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴(yán)蔚敏、吳偉民 著(編)，清華大學(xué)出版社，1999數(shù)據(jù)結(jié)

21、構(gòu)習(xí)題集（C語言版），嚴(yán)蔚敏、吳偉民 著(編)，清華大學(xué)出版社，1999數(shù)據(jù)結(jié)構(gòu)與算法，許卓群、楊冬青、唐世渭、張銘 著(編)，高等教育出版社，2004數(shù)據(jù)結(jié)構(gòu)-C語言描述，耿國華 著(編)，高等教育出版社，2005數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計C+語言描述（影印版），Robert L.Kurse，Alexandeer J.Ryba 著(編)，高等教育出版社，2001附錄1：肇慶學(xué)院計算機(jī)學(xué)院/軟件學(xué)院實驗報告格式肇慶學(xué)院 計算機(jī)學(xué)院/軟件學(xué)院實 驗 報 告專業(yè)_班級_姓名_學(xué)號_課程名稱_學(xué)年20 -20 學(xué)期 1 / 2 課程類別 專業(yè)必修 限選 任選 實踐l 實驗內(nèi)容： 實驗時間：2010年 月 日

22、l 實驗?zāi)康募耙螅簂 實驗內(nèi)容、方法與步驟：（使用附頁填寫并附在本頁后）l 實驗結(jié)果：l 小結(jié)：分?jǐn)?shù)： 批閱老師： 2010年 月 日第 頁 / 共 頁肇慶學(xué)院 計算機(jī)學(xué)院/軟件學(xué)院實驗報告（附頁）分?jǐn)?shù)： 批閱老師： 2010年 月 日第 頁 / 共 頁附錄2：上機(jī)實習(xí)注意事項一、關(guān)于上機(jī)實習(xí)的建議上機(jī)實習(xí)應(yīng)該按照一定的步驟和規(guī)范進(jìn)行，從以往的教學(xué)實習(xí)的經(jīng)驗來看，在初學(xué)階段執(zhí)行嚴(yán)格的實習(xí)步驟規(guī)范(包括上機(jī)操作規(guī)范)，會大大提高上機(jī)時間的利用率，有助于養(yǎng)成良好的程序編制風(fēng)格，培養(yǎng)嚴(yán)謹(jǐn)、科學(xué)、高效的工作方式。在以往的教學(xué)實踐中，經(jīng)常有學(xué)生不屑于按實習(xí)步驟規(guī)范去做，甚至對于實習(xí)步驟的要求和建議看都不看一遍，這是極其害的。實習(xí)步驟規(guī)范不但可以培養(yǎng)科學(xué)化的工作作風(fēng)，而且還能有效地避免錯誤。二、上機(jī)實驗的步驟和規(guī)范1.問題分析和任務(wù)的定義充分地分析和理解問題本身，明確問題要求做什么，限制做什么（本步驟強(qiáng)調(diào)做什么，而不是怎么做）。對問題的描述應(yīng)避開算法和所涉及的數(shù)據(jù)類型，而是對所要完成的任務(wù)做出明確的回答。如輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式；輸出數(shù)據(jù)的類型、值得范圍及輸出的形式；還應(yīng)該為調(diào)試程序準(zhǔn)備好測試數(shù)據(jù)，包括合法的輸入數(shù)據(jù)和非法形式的輸入數(shù)據(jù)。2.數(shù)據(jù)類型定義和系統(tǒng)設(shè)計本設(shè)計步驟可分邏輯設(shè)計和詳細(xì)設(shè)計兩步實現(xiàn)。邏輯設(shè)計指的是，為問題的描述中涉及的操