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

2、locks軟件，win764位操作系統(tǒng)，C#dynamiclookuptableAuthor:yinjieTutor:WangxiaoyingAbstractThiscoursedesignspecificationsystemtoexplainthewholeprocessofusingClanguageinCode:Blockssoftwarewritteninthedynamiclook-uptableprogram,thepreparationoftheenvironmentiswin764bitoperatingsystem.Accordingtothetopicrequest,th

3、epreparationofthedynamiclook-uptableusingthetwoforksorttree,thatis,thetwobinarylistasthestoragestructure.Theprogramhasthefunctionofbuildingdata,datasearching,datainsertion,datadeletionandsoon.Keywords：dynamiclookuptable,Code:Blockssoftware,win764bitoperatingsystemC引言1查找的基本概念1小結(jié)1題目1第1章程序的構(gòu)圖設(shè)計(jì)21.1 動(dòng)態(tài)查

4、詢表：21.2 程序功能流程圖：2、主函數(shù)模塊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(4)二叉排序樹的插入模塊9(5)多態(tài)查找表刪除模塊10(6)二叉排序樹的中序遍歷模塊12第3章程序測(cè)試和運(yùn)行123.1 程序測(cè)試123.2 程序運(yùn)行131、主界面132、建立二叉排序樹模塊界面133、二叉排序樹查找模塊界面144、二叉排序樹插入模塊界面145、二叉排序樹

5、刪除模塊界面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)劣對(duì)整個(gè)軟件系統(tǒng)的效率影響很大，尤其當(dāng)所涉及的數(shù)據(jù)量較大時(shí)，更是如此。在一個(gè)數(shù)據(jù)集合中進(jìn)行查找操作可選用的方法與該數(shù)據(jù)元素集合的存儲(chǔ)結(jié)構(gòu)有很大關(guān)系。查找是根據(jù)某個(gè)給定的值，在數(shù)據(jù)元素構(gòu)成的集合中確定是否在這樣一個(gè)數(shù)據(jù)元素，它的關(guān)鍵字等于給定值的關(guān)鍵字。要進(jìn)行查找，必須明確要查找對(duì)象的特征，也就是要查找元素的關(guān)鍵值。如果在

6、數(shù)據(jù)集合中能找到與給定值相等的關(guān)鍵字，則該關(guān)鍵字所屬的數(shù)據(jù)元素就是所要查找的數(shù)據(jù)元素，此時(shí)稱該查找成功；如果查遍了整個(gè)數(shù)據(jù)元素集合也未能找到與給定值相等的關(guān)鍵字，則稱該查找失敗。小結(jié)當(dāng)然對(duì)于這個(gè)說明書，我不可能做得至善至美，但是一些基本的格式內(nèi)容還是符合要求的。首先，我對(duì)查找表進(jìn)行一個(gè)簡(jiǎn)要的概述。然后，我就查找表進(jìn)行了詳細(xì)的分析,這是設(shè)計(jì)中很重要的一步。接下來，我把查找表中所有的設(shè)計(jì)簡(jiǎn)明清晰地展現(xiàn)出來，并把我在設(shè)計(jì)中遇到的問題和分析解決問題的辦法做了分析。最后，在結(jié)論中，我對(duì)自己的課程設(shè)計(jì)做了總體的評(píng)價(jià)同時(shí)簡(jiǎn)述了我在這次課程設(shè)計(jì)中的收獲和經(jīng)驗(yàn)。題目選題十二：動(dòng)態(tài)查找表【問題描述】利用二叉排序樹

7、完成動(dòng)態(tài)查找表的建立、指定關(guān)鍵字的查找、插入與刪除指定關(guān)鍵字結(jié)點(diǎn)。【任務(wù)要求】算法輸入：指定一組數(shù)據(jù)。桂林電子科技大學(xué)課程設(shè)計(jì)說明書算法輸出：顯示二叉排序樹的中序遍歷結(jié)果、查找成功與否的信息、插入和刪除后的中序遍歷結(jié)果（排序結(jié)果）。算法要點(diǎn)：二叉排序樹建立方法、動(dòng)態(tài)查找方法，對(duì)樹進(jìn)行中序遍歷。【測(cè)試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。第1章程序的構(gòu)圖設(shè)計(jì)1.1 動(dòng)態(tài)查詢表:a）所示：當(dāng)插入11的時(shí)依照輸入的一組數(shù)據(jù)56,80,65,20所得的二叉排序樹如下（候就如（b）所示1.2 程序功能流程圖:（1）、主函數(shù)模塊桂林電子科技大學(xué)課程設(shè)計(jì)說明書-k打印輸心動(dòng)態(tài)表的6個(gè)功能選擇欄do循環(huán)I輸入連

8、擇號(hào)h結(jié)束(2)、二叉排序樹的生成開始輸入數(shù)據(jù)個(gè)數(shù)X桂林電子科技大學(xué)課程設(shè)計(jì)說明書(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é)束二查詢成功桂林電子科技大學(xué)課程設(shè)計(jì)說明書(5)、二叉排序樹刪除連接模塊是一向右走到盡頭While循環(huán)*重接它的左右子樹(6)、二叉排序樹的刪除模塊輸入要?jiǎng)h除的的數(shù)據(jù)調(diào)用刪除的連接函數(shù)Delete()找到關(guān)鍵字并刪除桂林電子科技大學(xué)課程設(shè)計(jì)說明書(7)、二叉排序樹的遍歷模塊開始是第2章詳細(xì)設(shè)計(jì)的程序各函數(shù)模塊(1)

9、主函數(shù)模塊：用主函數(shù)main()來實(shí)現(xiàn)。主要是通過設(shè)計(jì)一個(gè)do()函數(shù)并讓主函數(shù)調(diào)用它來顯示主菜單,讓用戶選擇操作。在do()函數(shù)中，我應(yīng)用了sw計(jì)ch-case語(yǔ)句來進(jìn)行選擇，是個(gè)比較簡(jiǎn)單實(shí)現(xiàn)的模塊。最后若選擇“5”退出循環(huán)。否則繼續(xù)循環(huán)。主要代碼如下:intmain()bitreeT=NULL,p;ElemTypee;intn;inth;charc;doprintf(*n);桂林電子科技大學(xué)課程設(shè)計(jì)說明書printf(*n);printf(*動(dòng)態(tài)查找表*n);printf(*1.建立二叉排序樹*n);printf(*2.二叉排序樹查找元素*n);printf(*3.二叉排序樹插入元素*n)

10、;printf(*4.二叉排序樹刪除元素*n);printf(*5.退出*n);printf(*n);printf(*n);printf(請(qǐng)輸入你的選擇：n);scanf(%d,&h);switch(h)(case1:Init(T);printf(中序遍歷二叉排序樹：);Zhongxu(T);printf(n);break;case2:printf(請(qǐng)輸入要查找的數(shù)據(jù)：n);scanf(%d,&n);e.key=n;if(Search(T,e,NULL,p)printf(數(shù)據(jù)已經(jīng)存在！n);elseprintf(數(shù)據(jù)不存在！n);break;case3:printf(”請(qǐng)輸入要插入的數(shù)據(jù):n)

11、;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;case4:printf(請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù):n);scanf(%d,&n);e.key=n;if(Search(T,e,NULL,p)Deletebit(T,n);printf(已經(jīng)成功刪除!n);printf(中序遍歷二叉排序桂林電子科技大學(xué)課程設(shè)計(jì)說明書樹：);Zhongxu(T);printf(n);elseprint

12、f(數(shù)據(jù)不存在!n);break;case5:printf(退出!n);break;default:printf(選擇錯(cuò)誤，重新開始!n);while(h!=5);(2)二叉排序樹的生成模塊：二叉排序樹的生成，是從空的二叉排序樹開始，每輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)，就調(diào)用一次插入算法將它插到當(dāng)前已經(jīng)生成的二叉排序樹中。主要代碼如下：voidInit(bitree&T)構(gòu)造一個(gè)動(dòng)態(tài)查找表Tintx;inti;intn;ElemTypee;printf(請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)：);scanf(%d,&x);for(i=1;idata.key=e.key)(p=T;returnT;/查找成功elseif(T-data.

13、keye.key)returnSearch(T-lchild,e,T,p);elsereturnSearch(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)行比較：如果key的值等于根結(jié)點(diǎn)的值，則停止插入；如果key的值小于根結(jié)點(diǎn)的值，則將key插到左子樹；如果key的值大于根結(jié)點(diǎn)的值，則將key插到右子樹中。主要

14、代碼如下：voidInsert(bitree&T,ElemTypee)/4二叉排序樹中插入數(shù)據(jù)桂林電子科技大學(xué)課程設(shè)計(jì)說明書(bitreep,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)elseif(e.keydata.key)p-lchild=s;/被插結(jié)點(diǎn)*s為左孩子elsep-rchild=s;/被插結(jié)點(diǎn)*s為右孩子(5)多態(tài)查找表刪除模塊：從二叉排序樹中刪除一個(gè)結(jié)點(diǎn)，不能簡(jiǎn)單地把以該結(jié)點(diǎn)為根的

15、子樹都刪除，只能刪除掉該結(jié)點(diǎn)，并且還應(yīng)該保證刪除后所得到的二叉樹依然滿足二叉樹的性質(zhì)不變。也就是說，在二叉排序樹中刪除一個(gè)結(jié)點(diǎn)相當(dāng)于刪除有序序列中的一個(gè)結(jié)點(diǎn)。假設(shè)要?jiǎng)h除的結(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只有左子樹，或只有右子樹，則可將P的左子樹或右子樹直接改為其雙親結(jié)點(diǎn)F的左子樹或右子樹。若P既有左子樹，又有右子樹此時(shí)有兩種處理方法。方法1:首先找到結(jié)點(diǎn)P在中序序列中的直接前驅(qū)結(jié)點(diǎn)S,然后用結(jié)點(diǎn)P的左子樹改為F

16、的左子樹，而將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的右子樹。主要代碼如下：桂林電子科技大學(xué)課程設(shè)計(jì)說明書voidDelete(bitree&p)/從二叉排序樹中刪除結(jié)點(diǎn)p,并重接它的左或右子樹(bitreeq,s;if(!p-rchild)/右子樹空，只需重接它的左子樹(q=p;p=p-lchild;free(q);q=NULL;elseif(!p-lchild)/左子樹空，只需重接它的右子樹(q=p;p=p-rchild;free(q);q=NULL;else/左右子樹

17、均不空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-lchild=s-lchild;/重接*q的左子樹free(s);s=NULL;刪除結(jié)點(diǎn)voidDeletebit(bitree&T,intn)刪除二叉排序樹中的數(shù)據(jù)if(!T)return;/不存在關(guān)鍵字等于n的數(shù)據(jù)元素桂林電子科技大學(xué)課程設(shè)計(jì)說明書elseif(T-data.key=n)ret

18、urn(Delete(T);找到關(guān)鍵字等于n的數(shù)據(jù)元素并刪除它elseif(T-data.keyn)Deletebit(T-lchild,n);繼續(xù)在左子樹中刪除elseDeletebit(T-rchild,n);/繼續(xù)在右子樹中刪除(6)二叉排序樹的中序遍歷模塊：中序遍歷二叉樹定義：若二叉樹根為空，則返回；否則，中序遍歷左子樹；訪問根結(jié)點(diǎn);中序遍歷右子樹。主要代碼如下：voidZhongxu(bitreeT)/中序遍歷if(T!=NULL)Zhongxu(T-lchild);printf(%d,T-data.key);Zhongxu(T-rchild);第3章程序測(cè)試和運(yùn)行3.1程序測(cè)試程序

19、測(cè)試是程序質(zhì)量保證的主要活動(dòng)之一，在程序編寫的過程中，在各個(gè)階段都有可能存在錯(cuò)誤和缺陷。通過測(cè)試是可以發(fā)現(xiàn)程序設(shè)計(jì)中存在的種種問題，并可以及時(shí)改正。避免在程序運(yùn)行時(shí)才出現(xiàn)不必要的錯(cuò)誤。測(cè)試是質(zhì)量保證一個(gè)臨界和決定懲罰，它提供對(duì)程序說明、設(shè)計(jì)和編碼的最終評(píng)審。是發(fā)現(xiàn)程序缺陷和錯(cuò)誤的有力手段。根據(jù)系統(tǒng)設(shè)計(jì)目標(biāo)和功能，對(duì)系統(tǒng)進(jìn)行測(cè)試。桂林電子科技大學(xué)課程設(shè)計(jì)說明書1、功能性(1)程序?qū)崿F(xiàn)的主要功能，包括查詢，插入，刪除等。(2)題目要求的輸入輸出字段，以及題目要求的輸入限制。2、可靠性程序正確實(shí)現(xiàn)了對(duì)動(dòng)態(tài)查找表的查詢、插入、刪除等各種功能。3、易用性現(xiàn)有程序?qū)崿F(xiàn)了如下易用性：(1)查詢，插入，刪除，

20、操作相關(guān)提示信息的一致性，可理解性(2)輸入限制的正確性(3)輸入限制提示信息的正確性，可理解性，一致性(4)界面排版簡(jiǎn)潔完整3.2程序運(yùn)行1、主界面：一|二*n【:ums構(gòu)與算法的涕程役計(jì)構(gòu)與苒法的裸槿蝴iwxr蟄/HKKWW帛*SS元元元翳入除寸h-ICjlE!;!婚立曼叉出天建二二二退請(qǐng)輸入你的選擇2、建立二叉排序樹模塊界面：睛輸入你的選擇;桂林電子科技大學(xué)課程設(shè)計(jì)說明書3、二叉排序樹查找模塊界面：請(qǐng)輸入你的選擇;3輸入要查找的數(shù)據(jù)：20數(shù)據(jù)已經(jīng)存在？4、二叉排序樹插入模塊界面：KM*箕*MififiMKHMntMHHHIfJitKItJCIfJtJCXKJOtJtMiMi*itiMKK

21、MXMltHMIflltKhtJC請(qǐng)輸入你的選擇：;青輸入要插入的數(shù)據(jù)：11樂功插入？巾序遛歷二叉排序樹：11205665865、二叉排序樹刪除模塊界面：請(qǐng)輸入禰的選擇：褊人要?jiǎng)h除的數(shù)據(jù)：20整座功刪除一巾序通歷二叉排序樹：115665806、退出程序的界面桂林電子科技大學(xué)課程設(shè)計(jì)說明書，青輸入你的選擇;，擇錯(cuò)誤，重新開始，元元元除找一查叉,-4下*七土方-TT叉叉叉+.建二二二退1.請(qǐng)輸入你的選擇士退出！Processiretm*ned團(tuán)executiont.ime:7.297sPi*s：s：amyksyt口心tmtiriuE.程序完成情況在編寫程序?qū)懻n程設(shè)計(jì)的時(shí)間里，雖然歷經(jīng)重重困難和挫折

22、，但是在我自己的努力和老師的幫助下終于完成了動(dòng)態(tài)查找表的設(shè)計(jì)。盡管該程序在功能和性能上可能還有一些缺陷，但是我已經(jīng)完成了課程設(shè)計(jì)的任務(wù)和目標(biāo)，達(dá)到了題目基本要求，成功完成了算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)。有待改進(jìn)之處有待改進(jìn)：1、我在編寫程序的時(shí)候，用的是C+略式去保存編譯的，用了C語(yǔ)言來編寫，但是有一些C+勺形式，當(dāng)我用C來新建保存的時(shí)候卻出現(xiàn)問題。所以程序我是用C+球新建保存的。2、流程圖畫的不是很規(guī)范表準(zhǔn)，在一些邏輯表達(dá)上不夠簡(jiǎn)潔清晰。課程設(shè)計(jì)期間的收獲在完成此次的課程設(shè)計(jì)的過程中，我跨越了傳統(tǒng)方式下的教與學(xué)的體制束縛，桂林電子科技大學(xué)課程設(shè)計(jì)說明書通過自己的思考和設(shè)計(jì)，培養(yǎng)了自學(xué)能力和動(dòng)手能力

23、。并且由原先的被動(dòng)的接受知識(shí)轉(zhuǎn)換為主動(dòng)的尋求知識(shí)，這可以說是學(xué)習(xí)方法上的一個(gè)很大的突破。在以往的傳統(tǒng)的學(xué)習(xí)模式下，我們可能會(huì)記住很多的書本知識(shí)，但是通過課程設(shè)計(jì)，我們學(xué)會(huì)了如何將學(xué)到的知識(shí)轉(zhuǎn)化為自己的東西，學(xué)會(huì)了怎么更好的處理知識(shí)和實(shí)踐相結(jié)合的問題。通過這次課程設(shè)計(jì)，我認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)與算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)課程，是我們學(xué)習(xí)的核心課程。我對(duì)數(shù)據(jù)結(jié)構(gòu)和算法又有了新的認(rèn)識(shí)。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計(jì)算機(jī)軟件，而且和計(jì)算機(jī)硬件的研究也有著密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲(chǔ)器中的分配問題。在研究信息檢索時(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ú)立思考的能力，提高了我們的動(dòng)手操作水平。在具體設(shè)計(jì)中，我們鞏固了上學(xué)期所學(xué)的數(shù)據(jù)結(jié)構(gòu)與算法的理論知識(shí)，進(jìn)一步提高了自己的編程能力。這也是課程設(shè)計(jì)的目的所在。通過編程實(shí)踐，不僅開發(fā)了自己的邏輯思維能力，培養(yǎng)了分析問題、解決問題的能力，更充分鍛煉了我們的編程能力。在這次課程設(shè)計(jì)中我也知道了的編程能力不強(qiáng)，有很多程序與算法是借鑒別人的，我想只要我有自己寫程序，