數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)：動態(tài)查找表教材

1、桂林電孑科被火玲編號：139GUILIN UNIVERSITY OF ELECTRONIC TECHNOLOGY數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說明書動態(tài)查找表學(xué) 院：海洋信息工程學(xué)院專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名：學(xué) 號：指導(dǎo)教師：2015年 6月26 日動態(tài)查找表學(xué)生姓名：銀杰指導(dǎo)老師：王曉瑩摘要本課程設(shè)計(jì)說明書系統(tǒng)地闡述了我使用C語言在Code:Blocks軟件編寫的動態(tài)查找表程序的整個(gè)過程，編寫的環(huán)境是win7 64位操作系統(tǒng)。根據(jù)題目要求，編寫動態(tài)查找表使用二叉排序樹，即二叉鏈表作為存儲結(jié)構(gòu)。該程序具有建立數(shù)據(jù)功能、具有數(shù)據(jù)查找功能、具有數(shù)據(jù)插入功能、具有數(shù)據(jù)刪除功能等基本功能操作。關(guān)鍵詞

2、：動態(tài)查找表，Code:Blocks 軟件， win7 64 位操作系統(tǒng)，C#dynamic lookup tableAuthor :yinjieTutor :WangxiaoyingAbstractThis course design specification system to explain the whole process of using C language in Code: Blocks software written in the dynamic look-up table program, the preparation of the environment is wi

3、n7 64 bit operating system. According to the topic request, the preparation of the dynamic look-up table using the two fork sort tree, that is, the two binary list as the storage structure. The program has the function of building data, data searching, data insertion, data deletion and so on.Key wor

4、ds:dynamic lookup table, Code:Blocks software,win7 64 bit operating system， C引言 1查找的基本概念1小結(jié) 1題目 1第1 章程序的構(gòu)圖設(shè)計(jì)21.1 動態(tài)查詢表： 21.2 程序功能流程圖： 2(1)、主函數(shù)模塊 2(2)、二叉排序樹的生成 3(3)、二叉排序樹的查找模塊 4(4)、二叉排序樹的插入模塊 4(5)、二叉排序樹刪除連接模塊 5(6)、二叉排序樹的刪除模塊 5(7)、二叉排序樹的遍歷模塊 6第2 章詳細(xì)設(shè)計(jì)的程序6各函數(shù)模塊 6(1)主函數(shù)模塊 6(2)二叉排序樹的生成模塊 8(3)二叉排序樹的查找模塊 8

5、(4)二叉排序樹的插入模塊 9(5)多態(tài)查找表刪除模塊 10(6)二叉排序樹的中序遍歷模塊 12第3 章 程序測試和運(yùn)行 123.1 程序測試 123.2 程序運(yùn)行 131、主界面 132、建立二叉排序樹模塊界面 133、二叉排序樹查找模塊界面 144、二叉排序樹插入模塊界面 145、二叉排序樹刪除模塊界面 146、退出程序的界面 14總結(jié) 15程序完成情況 15有待改進(jìn)之處 15課程設(shè)計(jì)期間的收獲 15附錄源代碼如下 17桂林電子科技大學(xué)課程設(shè)計(jì)說明書引言查找的基本概念查找又稱為檢索，就是從一個(gè)數(shù)據(jù)元素集合中找出某個(gè)特定的數(shù)據(jù)元素。查找是數(shù) 據(jù)處理中最為常用的一種操作，查找算法的優(yōu)劣對整個(gè)軟

6、件系統(tǒng)的效率影響很大，尤其 當(dāng)所涉及的數(shù)據(jù)量較大時(shí)，更是如此。在一個(gè)數(shù)據(jù)集合中進(jìn)行查找操作可選用的方法與 該數(shù)據(jù)元素集合的存儲結(jié)構(gòu)有很大關(guān)系。查找是根據(jù)某個(gè)給定的值，在數(shù)據(jù)元素構(gòu)成的集合中確定是否在這樣一個(gè)數(shù)據(jù)元素，它的關(guān)鍵字等于給定值的關(guān)鍵字。要進(jìn)行查找，必須明確要查找對象的特征，也就是要查找元素的關(guān)鍵值。如果在數(shù) 據(jù)集合中能找到與給定值相等的關(guān)鍵字， 則該關(guān)鍵字所屬的數(shù)據(jù)元素就是所要查找的數(shù) 據(jù)元素，此時(shí)稱該查找成功；如果查遍了整個(gè)數(shù)據(jù)元素集合也未能找到與給定值相等的 關(guān)鍵字，則稱該查找失敗。小結(jié)當(dāng)然對于這個(gè)說明書，我不可能做得至善至美，但是一些基本的格式內(nèi)容還是符合 要求的。首先，我對查

7、找表進(jìn)行一個(gè)簡要的概述。 然后，我就查找表進(jìn)行了詳細(xì)的分析, 這是設(shè)計(jì)中很重要的一步。接下來，我把查找表中所有的設(shè)計(jì)簡明清晰地展現(xiàn)出來，并 把我在設(shè)計(jì)中遇到的問題和分析解決問題的辦法做了分析。最后，在結(jié)論中，我對自己 的課程設(shè)計(jì)做了總體的評價(jià)同時(shí)簡述了我在這次課程設(shè)計(jì)中的收獲和經(jīng)驗(yàn)。題目選題十二：動態(tài)查找表【問題描述】利用二叉排序樹完成動態(tài)查找表的建立、指定關(guān)鍵字的查找、插入與刪除指定關(guān)鍵字結(jié)點(diǎn)?！救蝿?wù)要求】算法輸入：指定一組數(shù)據(jù)。算法輸出：顯示二叉排序樹的中序遍歷結(jié)果、查找成功與否的信息、插入和刪除后 的中序遍歷結(jié)果（排序結(jié)果）。算法要點(diǎn)：二叉排序樹建立方法、動態(tài)查找方法 ，對樹進(jìn)行中序遍歷

8、?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。第1章程序的構(gòu)圖設(shè)計(jì)a）所示：當(dāng)插入11的時(shí)1.1 動態(tài)查詢表:依照輸入的一組數(shù)據(jù)56,80,65,20所得的二叉排序樹如下（候就如（b）所示1.2 程序功能流程圖:（1）、主函數(shù)模塊(2)、二叉排序樹的生成-k打印輸心動態(tài)表 的6個(gè)功能選擇欄do循環(huán)I輸入連擇號h結(jié)束開始輸入數(shù)據(jù)個(gè)數(shù)X(3)、二叉排序樹的查找模塊(4)、二叉排序樹的插入模塊調(diào)用卡詢函數(shù) Search。否 * 被插入結(jié)點(diǎn)*s 為新的根結(jié)點(diǎn)J1是v.插入的節(jié)點(diǎn)<?>根結(jié)點(diǎn)A<_>被插結(jié)點(diǎn)*s被插結(jié)點(diǎn)*s.為左孩子為石孩子j1插入成功*(結(jié)束二查詢成功(5)、二叉

9、排序樹刪除連接模塊是一向右走到盡頭While循環(huán)*重接它的 左右子樹(6)、二叉排序樹的刪除模塊輸入要刪除 的的數(shù)據(jù)調(diào)用刪除的連接函數(shù)Delete()找到關(guān)鍵 字并刪除(7)、二叉排序樹的遍歷模塊開始一二叉樹根是一.查為空.第2章詳細(xì)設(shè)計(jì)的程序各函數(shù)模塊(1)主函數(shù)模塊：用主函數(shù)main()來實(shí)現(xiàn)。主要是通過設(shè)計(jì)一個(gè)do()函數(shù)并讓主函數(shù)調(diào)用它來顯示主菜單, 讓用戶選擇操作。在do()函數(shù)中，我應(yīng)用了 switch-case語句來進(jìn)行選擇，是個(gè)比較簡單實(shí)現(xiàn)的模塊。最后若選擇“ 5”退出循環(huán)。否則繼續(xù)循環(huán)。主要代碼如下:int main()bitree T=NULL,p;ElemType e;i

10、nt n;int h;char c;doprintf("*n");printf("*n");printf("*動態(tài)查找表*n");printf("*1.建立二叉排序樹*n");printf("*2.二叉排序樹查找元素*n");printf("*3.二叉排序樹插入元素*n");printf("*4.二叉排序樹刪除元素*n");printf("*5.退出*n");printf("*n");printf("*n&

11、quot;);printf("請輸入你的選擇：n");scanf("%d",&h);switch(h)case 1:Init(T);printf("中序遍歷二叉排序樹:");Zhongxu(T);printf("n");break;case 2:printf("請輸入要查找的數(shù)據(jù)：n");scanf("%d",&n);e.key=n;if(Search(T,e,NULL,p)printf("數(shù)據(jù)已經(jīng)存在！n");else printf(&q

12、uot;數(shù)據(jù)不存在！n"); break;case 3:printf(”請輸入要插入的數(shù)據(jù)：n");scanf("%d",&n);e.key=n;if(Search(T,e,NULL,p)printf("已經(jīng)存在!n");elseInsert(T, e); printf("成 功插入!n");printf("中序遍歷二叉排 序4i : ");Zhongxu(T);printf("n");break;case 4:printf("請輸入要刪除的數(shù)據(jù)：n&quo

13、t;);scanf("%d",&n);e.key=n;if(Search(T,e,NULL,p) Deletebit(T,n); printf("已經(jīng)成功刪除!n");printf("中序遍歷二叉排序樹：");Zhongxu(T);printf("n"); else printf("數(shù)據(jù)不存在!n");break;case 5:printf("退出! n");break;default:printf("選擇錯誤，重新開始!n"); while(h!

14、=5);(2)二叉排序樹的生成模塊：二叉排序樹的生成，是從空的二叉排序樹開始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，就調(diào)用一次插入 算法將它插到當(dāng)前已經(jīng)生成的二叉排序樹中。主要代碼如下：void Init(bitree &T)構(gòu)造一個(gè)動態(tài)查找表Tint x;int i;int n;ElemType e;printf("請輸入結(jié)點(diǎn)個(gè)數(shù)：");scanf("%d",&x);for(i=1;i<=x;i+)print/第 個(gè)結(jié)點(diǎn)數(shù)據(jù)值 二i);scanf("%d",&n);e.key=n;Insert(T,e);printf(&

15、quot;二叉排序樹已經(jīng)建立!n");(3)二叉排序樹的查找模塊：二叉排序樹的查找方法如下。當(dāng)二叉排序樹為空時(shí)，查找失敗。當(dāng)二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字等于key時(shí)，查找成功。當(dāng)二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字大于key時(shí)，從根結(jié)點(diǎn)的左子樹中以同樣方法進(jìn)行查找。當(dāng)二叉樹根結(jié)點(diǎn)的關(guān)鍵字小于key時(shí)，從根結(jié)點(diǎn)的右子樹以同樣方法進(jìn)行查找。顯然，該過程是一個(gè)遞歸過程，下面給出這一算法的實(shí)現(xiàn)。主要代碼：bitree Search(bitree T,ElemType e,bitree f,bitree &p)施二叉排序樹中查找數(shù)據(jù)if(!T)p=f；return NULL;查找不成功else if(

16、T->data.key=e.key)p=T;return T; /查找成功else if(T->data.key>e.key)return Search(T->lchild,e,T,p);else return Search(T->rchild,e,T,p);/在二叉排序樹中查找數(shù)據(jù)(4)二叉排序樹的插入模塊：若要將一個(gè)關(guān)鍵字值為key的結(jié)點(diǎn)t插到二叉排序樹中，只需要使該結(jié)點(diǎn)插入后，二叉 排序樹中的元素依然按照原來的規(guī)律排列即可。二叉排序樹的插入方法如下。若二叉排序樹是空樹，則key稱為二叉排序樹的根。若二叉排序樹為非空，則將key與二叉排序樹的根結(jié)點(diǎn)進(jìn)行比較：如

17、果 key的值等于根 結(jié)點(diǎn)的值，則停止插入；如果key的值小于根結(jié)點(diǎn)的值，則將key插到左子樹；如果key 的值大于根結(jié)點(diǎn)的值，則將key插到右子樹中。主要代碼如下：void Insert(bitree &T,ElemType e)/4二叉排序樹中插入數(shù)據(jù)bitree p,s;if (!Search(T,e,NULL,p)/ 查找不成功s=(bitree)malloc(sizeof(bitnode);s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;/被插入結(jié)點(diǎn)*s為新的根結(jié)點(diǎn)else if(e.key<p->dat

18、a.key)p->lchild=s;/被插結(jié)點(diǎn)*s為左孩子elsep->rchild=s;/被插結(jié)點(diǎn)*s為右孩子(5)多態(tài)查找表刪除模塊：從二叉排序樹中刪除一個(gè)結(jié)點(diǎn)，不能簡單地把以該結(jié)點(diǎn)為根的子樹都刪除，只能刪除掉 該結(jié)點(diǎn)，并且還應(yīng)該保證刪除后所得到的二叉樹依然滿足二叉樹的性質(zhì)不變。也就是說，在二叉排序樹中刪除一個(gè)結(jié)點(diǎn)相當(dāng)于刪除有序序列中的一個(gè)結(jié)點(diǎn)。假設(shè)要刪除的結(jié)點(diǎn)為P,其雙親結(jié)點(diǎn)為F,同時(shí)假設(shè)結(jié)點(diǎn)P是結(jié)點(diǎn)F的左孩子(右孩子 的情況類似)。刪除操作首先要確定被刪結(jié)點(diǎn) P是否在二叉排序樹中。若不在，則不做 任何操作；若在，分為以下三種情況討論。若P為葉子結(jié)點(diǎn)，可直接將其刪除。若結(jié)點(diǎn)P

19、只有左子樹，或只有右子樹，則可將P的左子樹或右子樹直接改為其雙親結(jié)點(diǎn)F的左子樹或右子樹。若P既有左子樹，又有右子樹此時(shí)有兩種處理方法。方法1:首先找到結(jié)點(diǎn)P在中序序列中的直接前驅(qū)結(jié)點(diǎn) S,然后用結(jié)點(diǎn)P的左子樹改為 F的左子樹，而將P的右子樹改為S的右子樹。方法2:首先找到結(jié)點(diǎn)P在中序序列中的直接前驅(qū)結(jié)點(diǎn)s,然后用結(jié)點(diǎn)s的值替代結(jié)點(diǎn)p 的值，再將結(jié)點(diǎn)s刪除，原結(jié)點(diǎn)s的左子樹改為s的雙親結(jié)點(diǎn)q的右子樹。主要代碼如下：void Delete(bitree &p)/從二叉排序樹中刪除結(jié)點(diǎn)p,并重接它的左或右子樹bitree q,s;if(!p->rchild)/右子樹空，只需重接它的左子

20、樹q=p;p=p->lchild;free(q);q=NULL;else if(!p->lchild)左子樹空，只需重接它的右子樹q=p;p=p->rchild;free(q);q=NULL;else/左右子樹均不空q=p;s=p->lchild;while(s->rchild)/向右走到盡頭q=s;s=s->rchild;p->data=s->data;/等被刪結(jié)點(diǎn)的前驅(qū)s的內(nèi)容直接替代該結(jié)點(diǎn)的內(nèi)容 if(q!=p)/若被刪除結(jié)點(diǎn)的左子樹的右子樹不為空q->rchild=s->lchild;/重接*q 的右子樹elseq->l

21、child=s->lchild;/ 重接*q 的左子樹free(s);s=NULL;刪除結(jié)點(diǎn)void Deletebit(bitree &T,int n)刪除二叉排序樹中的數(shù)據(jù) if(!T)return;/不存在關(guān)鍵字等于n的數(shù)據(jù)元素elseif(T->data.key=n)return(Delete(T);/找到關(guān)鍵字等于n的數(shù)據(jù)元素并刪除它else if(T->data.key>n)Deletebit(T->lchild,n); 繼續(xù)在左子樹中刪除else Deletebit(T->rchild,n);/繼續(xù)在右子樹中刪除(6)二叉排序樹的中序遍

22、歷模塊：中序遍歷二叉樹定義：若二叉樹根為空，則返回；否則，中序遍歷左子樹；訪問根結(jié)點(diǎn);中序遍歷右子樹。主要代碼如下：void Zhongxu(bitree T)/中序遍歷if(T!=NULL)Zhongxu (T->lchild);printf("%d ”,T->data.key);Zhongxu (T->rchild);第3章程序測試和運(yùn)行3.1程序測試程序測試是程序質(zhì)量保證的主要活動之一，在程序編寫的過程中，在各個(gè)階段都有 可能存在錯誤和缺陷。通過測試是可以發(fā)現(xiàn)程序設(shè)計(jì)中存在的種種問題，并可以及時(shí)改 正。避免在程序運(yùn)行時(shí)才出現(xiàn)不必要的錯誤。測試是質(zhì)量保證一個(gè)臨界

23、和決定懲罰，它 提供對程序說明、設(shè)計(jì)和編碼的最終評審。是發(fā)現(xiàn)程序缺陷和錯誤的有力手段。根據(jù)系統(tǒng)設(shè)計(jì)目標(biāo)和功能，對系統(tǒng)進(jìn)行測試。1、功能性(1)程序?qū)崿F(xiàn)的主要功能，包括查詢，插入，刪除等。(2)題目要求的輸入輸出字段，以及題目要求的輸入限制。2、可靠性程序正確實(shí)現(xiàn)了對動態(tài)查找表的查詢、插入、刪除等各種功能。3、易用性現(xiàn)有程序?qū)崿F(xiàn)了如下易用性：(1)查詢，插入，刪除，操作相關(guān)提示信息的一致性，可理解性(2)輸入限制的正確性(3)輸入限制提示信息的正確性，可理解性，一致性(4)界面排版簡潔完整3.2程序運(yùn)行1、主界面：n【m5與算法的球性徵計(jì)黃拂a物與幅現(xiàn)津唐設(shè)計(jì)1臼血元元元 翳入除 寸 h -IC

24、jlE!;! 婚立曼叉出 天建二二二退*請輸入你的選擇:2、建立二叉排序樹模塊界面 ：睛輸入你的選擇;3、二叉排序樹查找模塊界面 ：請輸入你的選擇;3輸入要查找的數(shù)據(jù)：20數(shù)據(jù)已經(jīng)存在？4、二叉排序樹插入模塊界面：KM* 箕*MififiMKHMntMHHHIfJitKItJCIfJtJCXKJOtJtMiMi* * itiMKKMXMltHMIflltKhtJC請輸入你的選擇：;青輸入要插入的數(shù)據(jù)：11樂功插入？巾序遛歷二叉排序樹：11 20 56 65 865、二叉排序樹刪除模塊界面 ：請輸入禰的選擇：褊人要刪除的數(shù)據(jù)：20整座功刪除一巾序通歷二叉排序樹：11 56 65 806、退出程序

25、的界面，青輸入你的選擇;，擇錯誤，重新開始，元元元 ©除找一查叉,-4下* *七' 土方- TT叉叉叉+. 建二二二退1.請輸入你的選擇士退出！Process iretm*ned 團(tuán) <0x0> execution t. ime : 7.297 s Pi*£s：s： amy ksy t口 心tmtiriuE.程序完成情況在編寫程序?qū)懻n程設(shè)計(jì)的時(shí)間里，雖然歷經(jīng)重重困難和挫折，但是在我自己的努力 和老師的幫助下終于完成了動態(tài)查找表的設(shè)計(jì)。盡管該程序在功能和性能上可能還有一 些缺陷，但是我已經(jīng)完成了課程設(shè)計(jì)的任務(wù)和目標(biāo)，達(dá)到了題目基本要求，成功完成了 算法與數(shù)

26、據(jù)結(jié)構(gòu)課程設(shè)計(jì)。有待改進(jìn)之處有待改進(jìn)：1、我在編寫程序的時(shí)候，用的是C+略式去保存編譯的，用了 C語言來編寫，但是 有一些C+勺形式，當(dāng)我用C來新建保存的時(shí)候卻出現(xiàn)問題。所以程序我是用 C+球新 建保存的。2、流程圖畫的不是很規(guī)范表準(zhǔn)，在一些邏輯表達(dá)上不夠簡潔清晰。課程設(shè)計(jì)期間的收獲在完成此次的課程設(shè)計(jì)的過程中，我跨越了傳統(tǒng)方式下的教與學(xué)的體制束縛， 通過自己的思考和設(shè)計(jì)，培養(yǎng)了自學(xué)能力和動手能力。并且由原先的被動的接受知識轉(zhuǎn) 換為主動的尋求知識，這可以說是學(xué)習(xí)方法上的一個(gè)很大的突破。在以往的傳統(tǒng)的學(xué)習(xí) 模式下，我們可能會記住很多的書本知識，但是通過課程設(shè)計(jì)，我們學(xué)會了如何將學(xué)到 的知識轉(zhuǎn)化為

27、自己的東西，學(xué)會了怎么更好的處理知識和實(shí)踐相結(jié)合的問題。通過這次課程設(shè)計(jì)，我認(rèn)識到數(shù)據(jù)結(jié)構(gòu)與算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)課程，是我們學(xué) 習(xí)的核心課程。我對數(shù)據(jù)結(jié)構(gòu)和算法又有了新的認(rèn)識。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算 機(jī)軟件，而且和計(jì)算機(jī)硬件的研究也有著密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)， 都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信息檢索時(shí)也必須考慮如何組織數(shù) 據(jù)，以便使查找和存取數(shù)據(jù)元素更為方便?？梢哉J(rèn)為數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件 和計(jì)算機(jī)軟件三者之間的一個(gè)核心內(nèi)容， 是從事計(jì)算機(jī)科學(xué)研究及其應(yīng)用的人必須掌握 的重要內(nèi)容。這次的課程設(shè)計(jì)有效的培養(yǎng)了我們獨(dú)立思考的能力，提高了我們的動手操作水平。 在具體設(shè)計(jì)中，我們鞏固了上學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)與算法的理論知識，進(jìn)一步提高了自 己的編程能力。這也是課程設(shè)計(jì)的目的所在。通過編程實(shí)踐，不僅開發(fā)了自己的邏輯思 維能力，培養(yǎng)了分析問題、解決問題的能力，更充分鍛煉了我們的編程能力。在這次課程設(shè)計(jì)中我