數(shù)據(jù)結(jié)構實驗指導書

1、數(shù)據(jù)結(jié)構實驗指導書（C語言版）2017年9月 TOC o 1-5 h z HYPERLINK l bookmark6 o Current Document 1、順序表的實現(xiàn)1 HYPERLINK l bookmark29 o Current Document 2、鏈棧的實現(xiàn)3 HYPERLINK l bookmark51 o Current Document 3、前序遍歷二叉樹5 HYPERLINK l bookmark70 o Current Document 4、圖的深度優(yōu)先遍歷算法7 HYPERLINK l bookmark87 o Current Document 5、散列查找91、順

2、序表的實現(xiàn)實驗目的掌握線性表的順序存儲結(jié)構；驗證順序表及其基本操作的實現(xiàn)；理解算法與程序的關系，能夠?qū)㈨樞虮硭惴ㄞD(zhuǎn)換為對應的程序。實驗容建立含有若干個元素的順序表；對已建立的順序表實現(xiàn)插入、刪除、查找等基本操作。實現(xiàn)提示定義順序表的數(shù)據(jù)類型 順序表結(jié)構體SeqList，在SeqList基礎上實現(xiàn)題目要求的 插入、刪除、查找等基本操作，為便于查看操作結(jié)果，設計一個輸出函數(shù)依次輸出順序表的 元素。簡單起見，本實驗假定線性表的數(shù)據(jù)元素為int型，要求學生：（1）將實驗程序調(diào)試通過后，用模板類改寫；（2）加入求線性表的長度等基本操作；（3）重新給定測試數(shù)據(jù)，驗證拋出異常機制。實驗程序在編程環(huán)境下新建一

3、個工程“順序表驗證實驗”，并新建相應文件，文件包括順序表結(jié) 構體SeqList的定義，例程序如下：#define MaxSize 100/*假設順序表最多存放100個元素*/typedef int DataType;/*定義線性表的數(shù)據(jù)類型，假設為int型*/typedef structDataType dataMaxSize;/*存放數(shù)據(jù)元素的數(shù)組*/int length;/*線性表的長度*/ SeqList;文件包括建立順序表、遍歷順序表、按值查找、插入操作、刪除操作成員函數(shù)的定義， 例程序如下：int CreatList（SeqList *L, DataType a , int n）if

4、 （n MaxSize） printf（順序表的空間不夠，無法建立順序表n）; return 0;for （int i = 0; i datai = ai;L-length = n;return 1;void PrintList(SeqList *L)for (int i = 0； i length； i+)printf(%d , L-datai);/*輸出線性表的元素值，假設為int型*/int Locate(SeqList *L, DataType x)for (int i = 0; i length; i+)if (L-datai = x) return i+1;/*返回序號*/retu

5、rn 0;/*退出循環(huán)，說明查找失敗*/int Insert(SeqList *L, int i, DataType x)if (L-length = MaxSize) printf(上溢錯誤，插入失敗n); return 0;if (i L-length + 1) printf (位置錯誤，插入失敗n); return 0;for (int j = L-length; j = i; j-)/*j 表示元素序號*/L-dataj = L-dataj - 1;L-datai - 1 = x;L-length+;return 1;int Delete(SeqList *L, int i, Data

6、Type *ptr)if (L-length = 0) printf(下溢錯誤，刪除失敗n); return 0;if (i L-length) printf(位置錯誤，刪除失敗n); return 0;*ptr = L-datai - 1;/*取出位置 i 的元素*/for (int j = i; j length; j+)/* j表示元素所在數(shù)組下標*/L-dataj - 1 = L-dataj;L-length-;return 1;在定義了順序表的存儲結(jié)構SeqList并實現(xiàn)了基本操作后，程序中就可以使用SeqList 類型來定義變量，可以調(diào)用實現(xiàn)基本操作的函數(shù)來完成相應的功能。例程序如

7、下：#include #include /*將順序表的存儲結(jié)構定義和各個函數(shù)定義放到這里*/int main()int r5 = 1, 2, 3, 4, 5, i, x；SeqList L；/*定義變量L為順序表類型*/Creat(&L, r, 5);/*建立具有5個元素的順序表*/printf(當前線性表的數(shù)據(jù)為：)；PrintList(&L);/*輸出當前線性表 1 2 3 4 5*/Insert(&L, 2, 8)；/*在第2個位置插入值為8的元素*/printf(執(zhí)行插入操作后數(shù)據(jù)為：)；PrintList(&L)；/*輸出插入后的線性表1 8 2 3 4 5*/printf(當前線性

8、表的長度為：dn, Length(&L)；/*輸出線性表的長度6*/printf(請輸入查找的元素值：)；scanf(%d, &x)；i = Locate(&L, x)；if (0 = i) printf(查找失敗n)；else printf(元素d 的位置為：dn, x, i)；printf(請輸入查找第幾個元素值：，&i)；scanf(%d, &i)；if (Get(&L, i, &x) = 1) printf(第d 個元素值是%dn, i, x)；else printf(線性表中沒有第%d個元素n, i)；printf(請輸入要刪除第幾個元素：”)；scanf(%d, &i)；if (D

9、elete(&L, i, &x) = 1) /*刪除第 i 個元素*/printf(刪除第d個元素是%d，刪除后數(shù)據(jù)為：,i, x)；PrintList(&L)；/*輸出刪除后的線性表*/else printf(刪除操作失敗n)；return 0；2、鏈棧的實現(xiàn)實驗目的掌握棧的存儲結(jié)構；驗證鏈棧及其基本操作的實現(xiàn)； 驗證棧的操作特性。實驗容建立一個空棧；對已建立的棧進行插入、刪除、取棧頂元素等基本操作。實現(xiàn)提示定義鏈棧中的結(jié)點結(jié)構(鏈棧中結(jié)點結(jié)構基于單鏈表相同)，定義鏈棧的數(shù)據(jù)類型一一 鏈棧結(jié)構體，包括入棧、出棧、取棧頂元素等基本操作。本節(jié)的實驗采臆板實現(xiàn)，要求學生:假設棧元素為字符型，修改主

10、函數(shù)；重新設計測試數(shù)據(jù)，考查棧的上溢、下溢等情況，修改主函數(shù)。實驗程序在編程環(huán)境下新建一個工程“鏈棧驗證實驗”，并新建相應文件，文件包括鏈棧結(jié)構體 的定義，例程序如下：typedef int DataType;/*棧元素的數(shù)據(jù)類型，假設為int型*/typedef struct NodeDataType data;struct Node *next;/*存放棧元素的數(shù)據(jù)域*/*存放下一個結(jié)點的地址*/ Node;Node *top;/*棧頂指針*/文件包括鏈棧初始化、入棧、出棧、獲取棧頂元素、判空操作成員函數(shù)的定義，例程序如下：void InitStack(Node *top)top = NU

11、LL;void Push(Node *top, DataType x)Node *s s-data s-next(Node *)malloc(sizeof(Node);/*申請一個結(jié)點s*/x;top; top = s;/*將結(jié)點s插在棧頂*/int Pop(Node *top, DataType *ptr)Node *p = top;if (top = NULL) printf(下溢錯誤，刪除失敗n); return 0; *ptr = top-data;/*存儲棧頂元素*/top = top-next;/*將棧頂結(jié)點摘鏈*/free(p); return 1;int GetTop(Node

12、 *top, DataType *ptr) if (top = NULL) printf(下溢錯誤，取棧頂失敗n)； return 0； *ptr = top-data; return 1;int Empty(Node *top)if (top = NULL) return 1;/*?？談t返回 1*/else return 0;在定義了鏈棧的存儲結(jié)構并實現(xiàn)了基本操作后，可以調(diào)用實現(xiàn)基本操作的函數(shù)來完成相 應的功能。例程序如下：#include #include #include /*將單鏈表的結(jié)點結(jié)構定義和鏈棧的各個函數(shù)定義放到這里*/int main()DataType x;Node *to

13、p = NULL;/*定義鏈棧的棧頂指針并初始化*/InitStack(top);/*初始化鏈棧*/printf(對15和10執(zhí)行入棧操作，)；Push(top, 15);Push(top, 10);if (GetTop(top, &x) = 1)printf(當前棧頂元素為：dn, x);/*輸出當前棧頂元素10*/if (Pop(top, &x) = 1)printf(執(zhí)行一次出棧操作，刪除元素：%dn ”, x);/*輸出出棧元素10*/if (GetTop(top, &x) = 1)printf(當前棧頂元素為：dn”，x);/*輸出當前棧頂元素15*/printf(”請輸入待插入元素

14、：”)；scanf(”d”， &x);Push(&S, x);if (Empty(top) = 1)printf(棧為空n”)；elseprintf(棧非空n”)；/*棧有2個元素，輸出棧非空*/DestroyStack(top)；return 0;3、前序遍歷二叉樹實驗目的掌握二叉樹的邏輯結(jié)構；掌握二叉樹的二叉鏈表存儲結(jié)構；驗證二叉樹的二叉鏈表存儲及遍歷操作。實驗容建立一棵含有n個結(jié)點的二叉樹，采用二叉鏈表存儲；輸出前序遍歷該二叉樹的遍歷結(jié)果。實現(xiàn)提示定義二叉樹的數(shù)據(jù)類型一一二叉樹結(jié)點結(jié)構體BiNode，在BiNode基礎上實現(xiàn)題目要求 的建立二叉鏈表、前序遍歷等基本操作。建立二叉鏈表可以采

15、用擴展二叉樹的一個遍歷序列， 例如前序序列，將擴展二叉樹的前序序列由鍵盤輸入，建立該二叉樹的二叉鏈表存儲。簡單起見，本實驗假定二叉樹的數(shù)據(jù)元素為char型，要求學生：將實驗程序調(diào)試通過后，用模板類改寫；加入層序遍歷二叉樹等基本操作。實驗程序在編程環(huán)境下新建一個工程“二叉鏈表驗證實驗”，并新建相應文件，文件包括二叉樹 結(jié)構體的定義，例程序如下：typedef char DataType;typedef struct BiNodeDataType data;struct BiNode *lchild, *rchild; BiNode;BiNode *root;文件包括建立二叉鏈表、前序遍歷操作成員

16、函數(shù)的定義，例程序如下：BiNode * CreatBiTree(BiNode *root)char ch;cin ch;/*輸入結(jié)點的數(shù)據(jù)信息*if (ch = # ) root = NULL;/*遞歸結(jié)束，建立一棵空樹*/else root = (BiNode *)malloc(sizeof(BiNode);/*生成新結(jié)點*/root-data = ch;/*新結(jié)點的數(shù)據(jù)域為ch*/root-lchild = Creat(root-lchild);/*遞歸建立左子樹*/root-rchild = Creat(root-rchild);/*遞歸建立右子樹*/return root;void

17、PreOrder(BiNode *root)if (root = NULL) return； else printf(%c , root-data);PreOrder(root-lchild);PreOrder(root-rchild);/*遞歸調(diào)用的結(jié)束條件*/*訪問根結(jié)點的數(shù)據(jù)域，為char型*/*前序遞歸遍歷root的左子樹*/*前序遞歸遍歷root的右子樹*/在定義了二叉樹的存儲結(jié)構并實現(xiàn)了基本操作后，可以調(diào)用實現(xiàn)基本操作的函數(shù)來完成 相應的功能。例程序如下：#include #include #include /*將二叉鏈表的結(jié)點結(jié)構定義和各個函數(shù)定義放到這里*/int main()

18、BiNode *root = NULL;/*定義二叉樹的根指針變量*/root = CreatBiTree(root);/*建立一棵二叉樹*/printf(該二叉樹的根結(jié)點是：cn, root-data);printf(n該二叉樹的前序遍歷序列是：);PreOrder(root);return 0;4、圖的深度優(yōu)先遍歷算法實驗目的掌握圖的邏輯結(jié)構；掌握圖的鄰接矩陣存儲結(jié)構；驗證圖的鄰接矩陣存儲及其深度優(yōu)先遍歷操作的實現(xiàn)。實驗容 建立無向圖的鄰接矩陣存儲； 對建立的無向圖，進行深度優(yōu)先遍歷實現(xiàn)提示定義鄰接矩陣存儲的無向圖結(jié)構體MGraph，在其基礎上實現(xiàn)題目要求的圖建立、深度 優(yōu)先遍歷等基本操作

19、。實驗程序在編程環(huán)境下新建一個工程“圖的深度優(yōu)先遍歷驗證實驗”，并新建相應文件，文件包 括圖的鄰接矩陣結(jié)構體MGraph的定義，例程序如下:#define MaxSize 10typedef char DataType;typedef structDataType vertexMaxSize;int edgeMaxSizeMaxSize;int vertexNum, edgeNum; MGraph;/*假設圖中最多頂點個數(shù)*/*圖中頂點的數(shù)據(jù)類型，假設為char型*/*定義鄰接矩陣存儲結(jié)構*/*存放頂點的一維數(shù)組*/*存放邊的二維數(shù)組*/*圖的頂點數(shù)和邊數(shù)*/文件包括建立圖、圖的深度優(yōu)先遍歷操

20、作成員函數(shù)的定義，例程序如下:int n, int e)/*存儲頂點信息*/*初始化鄰接矩陣*/*依次輸入每一條邊*/*輸入邊依附的頂點編號*/*置有邊標志*/void CreatGraph(MGraph *G, DataType a, int i, j, k;G-vertexNum = n; G-edgeNum = e;for (i = 0; i vertexNum; i+) G-vertexi = ai;for (i = 0; i vertexNum; i+)for (j = 0; j vertexNum; j+) G-edgeij = 0;for (k = 0; k edgeNum; k

21、+)scanf(%d%d, &i, &j);G-edgeij = 1; G-edgeji = 1;void DFraverse(MGraph *G, int v) /*全局數(shù)組變量 visitedn已初始化為 0*/printf(%c , G-vertexv); visitedv = 1;for (int j = 0; j vertexNum; j+)if (G-edgevj = 1 & visitedj = 0) DFSTraverse(G, j);在定義了圖的鄰接矩陣存儲結(jié)構并實現(xiàn)了基本操作后，可以調(diào)用實現(xiàn)基本操作的函數(shù)來 完成相應的功能。例程序如下：#include #include int visitedMaxSize = 0；/*全局數(shù)組變量 visited 初始化*/*把鄰接矩陣的存儲結(jié)構定義和各個函數(shù)定義放到這里*/int main()int i；char ch =A,B,C,D,E；MGraph MG；CreatGraph(&M