動(dòng)態(tài)查找表(二叉排序樹(shù))

1、北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) 動(dòng)態(tài)查找表 摘 要 數(shù)據(jù)結(jié)構(gòu)是研究與數(shù)據(jù)之間的關(guān)系我們稱這一關(guān)系為數(shù)據(jù)的邏輯結(jié)構(gòu)簡(jiǎn)稱數(shù)據(jù)結(jié)構(gòu)。當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)確定以后數(shù)據(jù)在物理空間中的存儲(chǔ)方式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。相同的邏輯結(jié)構(gòu)可以具有不同的存儲(chǔ)結(jié)構(gòu)因而有不同的算法。 本次課程設(shè)計(jì)程序中的數(shù)據(jù)采用“樹(shù)形結(jié)構(gòu)”作為其數(shù)據(jù)結(jié)構(gòu)。具體采用的是“二叉排序樹(shù)”并且使用“二叉鏈表”來(lái)作為其存儲(chǔ)結(jié)構(gòu)。本課程設(shè)計(jì)實(shí)現(xiàn)了二叉排序樹(shù)的創(chuàng)建、中序遍歷、插入、查找和刪除二叉排序樹(shù)中某個(gè)結(jié)點(diǎn)。 本課程主要實(shí)現(xiàn)動(dòng)態(tài)查找表的功能通過(guò)“二叉排序樹(shù)”的算法和“二叉鏈表”的存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。本課程設(shè)計(jì)說(shuō)明書重點(diǎn)介紹了系統(tǒng)的設(shè)計(jì)思路、總體設(shè)計(jì)

2、、各個(gè)功能模塊的設(shè)計(jì)與實(shí)現(xiàn)方法。 關(guān)鍵詞數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言 二叉排序樹(shù) 動(dòng)態(tài) 二叉鏈表1北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) 2目 錄 摘 要. 1 1 ABSTRACT. 323 抽象數(shù)據(jù)類型動(dòng)態(tài)查找表定義 . 4 43 系統(tǒng)總體分析. 53.1系統(tǒng)模塊劃分 . 5 3.2 二叉樹(shù)的生成過(guò)程 . 5 3.3 主要功能模塊設(shè)計(jì) . 5 3.4 系統(tǒng)詳細(xì)設(shè)計(jì) . 7 3.4.1 主函數(shù)菜單模塊 . 7 3.4.2 查找模塊 . 10 3.4.3 刪除模塊 . 11 3.4.4 插入模塊 . 13 3.4.5 中序輸出模塊 . 15 參考文獻(xiàn). 17 心 得 體 會(huì). 18 教 師 評(píng) 語(yǔ). 19

3、 附 錄. 202北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) 1 Abstract(摘要)Data structure is the relationship between research and data, we call this relationship as a logical data structure, referred to as data structures. When the data logical structure is determined, the data stored in the physical space, is known as the data s

4、torage structure. The same logical structure can have different storage structure, which has a different algorithm. The curriculum design, program data is "tree" as its data structure. Specific uses "binary sort tree" and use "binary list" as its storage structure. The

5、course is designed to achieve a binary sort tree creation, in-order traversal, insert, find and delete a binary sort tree nodes. This course is mainly the function of dynamic look-up table, through the "binary search tree" algorithm and "binary list" of storage structures. This c

6、ourse is designed to highlight the system design concept, overall design, each functional module design and implementation. Keywords: C Language Data Structure Dynamic Binary Search Tree, Binary List 3北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) 2 抽象數(shù)據(jù)類型動(dòng)態(tài)查找表定義 ADT DynamicSearchTable 數(shù)據(jù)對(duì)象DD是具有相同特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素含有類型相同可唯一標(biāo)識(shí)數(shù)

7、據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系R:數(shù)據(jù)元素同屬一個(gè)集合。 基本操作P InitDSTable(&DT); 操作結(jié)果構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT。 DestroyDSTable&DT; 初始條件動(dòng)態(tài)查找表DT存在。 操作結(jié)果銷毀動(dòng)態(tài)查找表DT。 SearchDSTableDTkey; 初始條件動(dòng)態(tài)查找表DT存在key為和關(guān)鍵字類型相同的給定值。 操作結(jié)果若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素則函數(shù)值為該元素的值或在表中的位置否則為“空” 。 InsertDSTable&DTe; 初始條件動(dòng)態(tài)查找表DT存在e為待插入的數(shù)據(jù)元素。 操作結(jié)果若DT中不存在其關(guān)鍵字等于e的數(shù)據(jù)元素則

8、插入e到DT。 DeleteDSTable&DTkey; 初始條件動(dòng)態(tài)查找表DT存在key為和關(guān)鍵字類型相同的給定值。 操作結(jié)果若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素則刪除之。 InOrderTraverse(DT); 初始條件動(dòng)態(tài)查找表DT存在。 操作結(jié)果按中序的次序輸出DT中的每個(gè)結(jié)點(diǎn)數(shù)據(jù)值。 ADT DynamisSearchTable 4北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) 5 3 系統(tǒng)總體分析 3.1系統(tǒng)模塊劃分 二叉排序樹(shù)是一種動(dòng)態(tài)樹(shù)表。 二叉排序樹(shù)的定義二叉排序樹(shù)或者是一棵空樹(shù) 或者是一棵具有如下性質(zhì)的二叉樹(shù) 若它的左子樹(shù)非空則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值 若

9、它的右子樹(shù)非空則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值 左、右子樹(shù)本身又各是一棵二叉排序樹(shù)。 3.2 二叉樹(shù)的生成過(guò)程 二叉排序樹(shù)的生成采用遞歸方式的邊查找邊插入的方式。如圖 3.3 主要功能模塊設(shè)計(jì) 程序主要設(shè)計(jì)了五個(gè)功能首先是創(chuàng)建二叉排序樹(shù)完成后出現(xiàn)任務(wù)菜單菜單中設(shè)計(jì)了六個(gè)模塊查找刪除插入中序輸出清屏和退出。5北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) 創(chuàng)建二叉排序樹(shù)N查找數(shù)據(jù)Switch(1) Y N刪除數(shù)據(jù)Switch(2) Y NSwitch(3)插入數(shù)據(jù) Y N中序輸出Switch(4) YSwitch(5) N清屏 Y NSwitch(6)退出 Y N輸出錯(cuò)誤default Y N圖2

10、.3 主函數(shù)流程圖北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) 3.4 系統(tǒng)詳細(xì)設(shè)計(jì) 3.4.1 主函數(shù)菜單模塊 該模塊功能主要是給用戶提供清晰的可操作界面易于人機(jī)操作并能很好的調(diào)用其他各模塊使程序更加優(yōu)化絲路更加清晰結(jié)構(gòu)更加明了提高了程序的實(shí)用性。其代碼如下 #include "BinaryTree.h" void main() BiTree T = NULL; int arr100; int n, i, k; int data; InitBiTree(T); printf("請(qǐng)輸入結(jié)點(diǎn)數(shù)"); scanf("%d", &n);

11、printf("請(qǐng)輸入數(shù)據(jù)"); for(i = 0; i < n; i+) /輸入要排序的數(shù)據(jù) scanf("%d", &arri); for(i = 0; i < n; i+) /構(gòu)造二叉排序樹(shù) InsertBiTree(T,arri); printf("按中序輸出"); InOrderTraverse(T); /調(diào)用中序輸出函數(shù)將二叉排序樹(shù)按中序輸出 printf("n"); Z: /語(yǔ)句塊供用戶選擇操作7北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) printf("tt-n"

12、;); printf("tt| 功能菜單 |n"); printf("tt-n"); printf("tt| 1.查找數(shù)據(jù) |n"); printf("tt-n"); printf("tt| 2.刪除數(shù)據(jù) |n"); printf("tt-n"); printf("tt| 3.插入數(shù)據(jù) |n"); printf("tt-n"); printf("tt| 4.輸出有序序列 |n"); printf("tt-n

13、"); printf("tt| 5.清屏 |n"); printf("tt-n"); printf("tt| 6.退出 |n"); printf("tt-nn"); X: /該語(yǔ)句塊用于循環(huán)選擇 printf("請(qǐng)輸入選擇功能的序號(hào)"); V: /該語(yǔ)句塊用于輸入序號(hào)錯(cuò)誤時(shí)重新輸入 scanf("%d", &k); /end V switch(k) case 1: printf("請(qǐng)輸入要查找的數(shù)據(jù)"); scanf("%d&q

14、uot;, &data); if(InsertBiTree(T, data) printf("不存在數(shù)據(jù)元素%dn", data); else8北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) printf("存在數(shù)據(jù)元素%dn", data); break; case 2: printf("請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)"); scanf("%d", &data); if(!DeleteBiTree(T, data) printf("不存在要輸出的數(shù)據(jù)%dn", data); else printf

15、("刪除操作成功n"); break; case 3: printf("請(qǐng)輸入要插入的數(shù)據(jù)"); scanf("%d", &data); if(!InsertBiTree(T, data) printf("要插入的數(shù)據(jù)%d已存在插入失敗n", data); else printf("插入操作成功n"); break; case 4: printf("有序序列為"); InOrderTraverse(T); printf("n"); break; c

16、ase 5: system("cls"); 9北京理工大學(xué)珠海學(xué)院計(jì)算機(jī)學(xué)院課程設(shè)計(jì) 10 goto Z; break; case 6: DestroyBiTree(T); exit(0); default: printf("輸入字符錯(cuò)誤請(qǐng)重新輸入:"); goto V; /end switch printf("nn"); /end X goto X; /end Z 圖2.4.13.4.2 查找模塊 該模塊是給用戶提供查找功能。其查找過(guò)程是若二叉排序樹(shù)為空則查找失敗結(jié)束查找返回信息 NULL否則將要查找的值與二叉排序樹(shù)根結(jié)點(diǎn)的值進(jìn)行比

17、較若相等則查找成功結(jié)束查找返回被查找到結(jié)點(diǎn)的地址若不等則根據(jù)要查找的值與根結(jié)值的大小關(guān)系決定時(shí)到根結(jié)點(diǎn)的左子樹(shù)還是右子樹(shù)中繼續(xù)查找查找過(guò)程同上直到查找成功或者查找失敗為止。其代碼如下: Status SearchBiTree(BiTree T, Elem key, BiTree f, BiTree &p) /在根指針T所指二叉排序樹(shù)中遞歸地查找某關(guān)鍵字等于key的數(shù)據(jù)元素 /若查找成功則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)并返回TRUE否則指針p /指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)并返回FALSE指針f指向T的雙親其初始調(diào)用值為NULL if(!T) p = f; return FALSE; /查

18、找不成功 else if(key = T->data) p = T; return TRUE; /查找成功 else if(key < T->data) /在左子樹(shù)中繼續(xù)查找 return (SearchBiTree(T->left, key, T, p); else /在右子樹(shù)中繼續(xù)查找 return (SearchBiTree(T->right, key, T, p); 圖2.4.23.4.3 刪除模塊 刪除結(jié)點(diǎn)函數(shù)采用邊查找邊刪除的方式。如果沒(méi)有查找到則不對(duì)樹(shù)做任何的修改；如果查找到結(jié)點(diǎn)則分四種情況分別進(jìn)行討論 A該結(jié)點(diǎn)左右子樹(shù)均為空可以直接進(jìn)行刪除 B該結(jié)

19、點(diǎn)僅左子樹(shù)為空右子樹(shù)不為空用右子樹(shù)的根結(jié)點(diǎn)取代被刪除結(jié)點(diǎn)的位置 C該結(jié)點(diǎn)僅右子樹(shù)為空左子樹(shù)不為空 D該結(jié)點(diǎn)左右子樹(shù)均不為空找到被刪除結(jié)點(diǎn)左子樹(shù)中最大的結(jié)點(diǎn)并用該結(jié)點(diǎn)取代被刪除節(jié)點(diǎn)的位置。其代碼如下 Status Delete(BiTree &p) /從二叉排序樹(shù)中刪除結(jié)點(diǎn)p并重接它的左或右子樹(shù) BiTree q, s; /q = (BiTree)malloc(sizeof(BiTree); /s = (BiTree)malloc(sizeof(BiTree); if(!p->right) /右子樹(shù)為空則重接它的左子樹(shù) q = p; p = p->left; q->le

20、ft = NULL; / free(q); 有錯(cuò)誤 else if(!p->left) /只需重接它的右子樹(shù) q = p; p = p->right; q->right = NULL; / free(q); /有錯(cuò)誤 else /左右子樹(shù)都不空 q = p; s = p->left; while(s->right) q = s; s = s->right; /轉(zhuǎn)右然后向右走到盡頭找到被刪點(diǎn)的“前驅(qū)” p->data = s->data; /s指向被刪結(jié)點(diǎn)的“前驅(qū)” s->data = NULL; if(q != p) q->right

21、 = s->left; /重接*q的右子樹(shù) else q->left = s->left; /重接*q的左子樹(shù)任何的修改如果查找到結(jié)點(diǎn)則分四種情況分別進(jìn)行討論 A該結(jié)點(diǎn)左右子樹(shù)均為空可以直接進(jìn)行刪除 B該結(jié)點(diǎn)僅左子樹(shù)為空右子樹(shù)不為空用右子樹(shù)的根結(jié)點(diǎn)取代被刪除結(jié)點(diǎn)的位置 C該結(jié)點(diǎn)僅右子樹(shù)為空左子樹(shù)不為空 D該結(jié)點(diǎn)左右子樹(shù)均不為空找到被刪除結(jié)點(diǎn)左子樹(shù)中最大的結(jié)點(diǎn)并用該結(jié)點(diǎn)取代被刪除節(jié)點(diǎn)的位置。其代碼如下 Status Delete(BiTree &p) /從二叉排序樹(shù)中刪除結(jié)點(diǎn)p并重接它的左或右子樹(shù) BiTree q, s; /q = (BiTree)malloc(siz

22、eof(BiTree); /s = (BiTree)malloc(sizeof(BiTree); if(!p->right) /右子樹(shù)為空則重接它的左子樹(shù) q = p; p = p->left; q->left = NULL; / free(q); 有錯(cuò)誤 else if(!p->left) /只需重接它的右子樹(shù) q = p; p = p->right; q->right = NULL; / free(q); /有錯(cuò)誤 else /左右子樹(shù)都不空 q = p; s = p->left; while(s->right) q = s; s = s-&

23、gt;right; /轉(zhuǎn)右然后向右走到盡頭找到被刪點(diǎn)的“前驅(qū)” p->data = s->data; /s指向被刪結(jié)點(diǎn)的“前驅(qū)” s->data = NULL; if(q != p) q->right = s->left; /重接*q的右子樹(shù) else q->left = s->left; /重接*q的左子樹(shù)/ free(s); 有錯(cuò)誤 return TRUE; Status DeleteBiTree(BiTree &T, Elem key) /若二叉排序樹(shù)T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí) /則刪除該數(shù)據(jù)元素結(jié)點(diǎn)并返回TRUE否則返回FAL

24、SE if(!T) return FALSE; /不存在關(guān)鍵字等于key的數(shù)據(jù)元素 else if(key = T->data) return Delete(T); /找到關(guān)鍵字等于key的數(shù)據(jù)元素 else if(key <= T->data) /從左子樹(shù)繼續(xù)查找等于key的數(shù)據(jù)元素 return DeleteBiTree(T->left, key); else /從右子樹(shù)繼續(xù)查找等于key的數(shù)據(jù)元素 return DeleteBiTree(T->right,key); 圖2.4.33.4.4 插入模塊 在二叉排序樹(shù)種插入新結(jié)點(diǎn)要保證插入后的二叉樹(shù)仍符合二叉排序

25、樹(shù)的定義。插入過(guò)程若二叉排序樹(shù)為空則待插入結(jié)點(diǎn)*p作為根結(jié)點(diǎn)插入到空樹(shù)中當(dāng)非空時(shí)將待插結(jié)點(diǎn)關(guān)鍵字p->item和樹(shù)根關(guān)鍵字t->item進(jìn)行比較若p->item=t->item則無(wú)須插入若p->item<t->item則插入到根的左子樹(shù)中若p->item>t->item則插入到根的右子樹(shù)中。而子樹(shù)種的插入過(guò)程和在樹(shù)中的插入過(guò)程相同如此進(jìn)行下去直到把結(jié)點(diǎn)*p作為一個(gè)新的樹(shù)葉插入到二叉排序樹(shù)中或者直到發(fā)現(xiàn)數(shù)已有相同關(guān)鍵字的結(jié)點(diǎn)為止。其代碼如下 Status InsertBiTree(BiTree &T, Elem key) /當(dāng)二

26、叉排序樹(shù)T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)插入key并返回TRUE /否則返回FALSE BiTree s = NULL; BiTree p = NULL; if(!SearchBiTree(T, key, NULL, p) s = (BiTree)malloc(sizeof(BiTree); if(!s) /內(nèi)存分配失敗時(shí)給出提示然后退出操作 printf("內(nèi)存空間分配失敗n"); exit(OVERFLOW); s->data = key; s->left = s->right = NULL; if(!p) T = s; else if(key

27、< p->data) p->left = s; else p->right = s; return TRUE; else return FALSE; 圖2.4.4 3.4.5 中序輸出模塊 遍歷Traversal是指沿著某條搜索路線依次對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問(wèn)。訪問(wèn)結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問(wèn)題。二叉樹(shù)共有三個(gè)部分組成即根結(jié)點(diǎn)根結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)的右子樹(shù)。限定以從左至右方式共有三種遍歷方式即前序遍歷中序遍歷后序遍歷。中序遍歷的原則若被遍歷的二叉樹(shù)為非空則依次執(zhí)行如下操作 A以中序遍歷方式遍歷左子樹(shù) B訪問(wèn)根結(jié)點(diǎn) C以中序遍歷方式遍歷右子樹(shù)。其代碼如下 Status InsertBiTree(BiTree &T, Elem key) /當(dāng)二叉排序樹(shù)T中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)插入key并返回TRUE /否則返回FALSE BiTree s = NULL;