數(shù)據(jù)結構課程設計：動態(tài)查找表教材

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

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小結 1題目 1第1 章程序的構圖設計21.1 動態(tài)查詢表： 21.2 程序功能流程圖： 2(1)、主函數(shù)模塊 2(2)、二叉排序樹的生成 3(3)、二叉排序樹的查找模塊 4(4)、二叉排序樹的插入模塊 4(5)、二叉排序樹刪除連接模塊 5(6)、二叉排序樹的刪除模塊 5(7)、二叉排序樹的遍歷模塊 6第2 章詳細設計的程序6各函數(shù)模塊 6(1)主函數(shù)模塊 6(2)二叉排序樹的生成模塊 8(3)二叉排序樹的查找模塊 8

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

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

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

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

9、排序樹刪除連接模塊是一向右走到盡頭While循環(huán)*重接它的 左右子樹(6)、二叉排序樹的刪除模塊輸入要刪除 的的數(shù)據(jù)調(diào)用刪除的連接函數(shù)Delete()找到關鍵 字并刪除(7)、二叉排序樹的遍歷模塊開始一二叉樹根是一.查為空.第2章詳細設計的程序各函數(shù)模塊(1)主函數(shù)模塊：用主函數(shù)main()來實現(xiàn)。主要是通過設計一個do()函數(shù)并讓主函數(shù)調(diào)用它來顯示主菜單, 讓用戶選擇操作。在do()函數(shù)中，我應用了 switch-case語句來進行選擇，是個比較簡單實現(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)二叉排序樹的生成模塊：二叉排序樹的生成，是從空的二叉排序樹開始，每輸入一個結點數(shù)據(jù)，就調(diào)用一次插入 算法將它插到當前已經(jīng)生成的二叉排序樹中。主要代碼如下：void Init(bitree &T)構造一個動態(tài)查找表Tint x;int i;int n;ElemType e;printf("請輸入結點個數(shù)：");scanf("%d",&x);for(i=1;i<=x;i+)print/第 個結點數(shù)據(jù)值 二i);scanf("%d",&n);e.key=n;Insert(T,e);printf(&

15、quot;二叉排序樹已經(jīng)建立!n");(3)二叉排序樹的查找模塊：二叉排序樹的查找方法如下。當二叉排序樹為空時，查找失敗。當二叉排序樹根結點的關鍵字等于key時，查找成功。當二叉排序樹根結點的關鍵字大于key時，從根結點的左子樹中以同樣方法進行查找。當二叉樹根結點的關鍵字小于key時，從根結點的右子樹以同樣方法進行查找。顯然，該過程是一個遞歸過程，下面給出這一算法的實現(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)二叉排序樹的插入模塊：若要將一個關鍵字值為key的結點t插到二叉排序樹中，只需要使該結點插入后，二叉 排序樹中的元素依然按照原來的規(guī)律排列即可。二叉排序樹的插入方法如下。若二叉排序樹是空樹，則key稱為二叉排序樹的根。若二叉排序樹為非空，則將key與二叉排序樹的根結點進行比較：如

17、果 key的值等于根 結點的值，則停止插入；如果key的值小于根結點的值，則將key插到左子樹；如果key 的值大于根結點的值，則將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;/被插入結點*s為新的根結點else if(e.key<p->dat

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

19、只有左子樹，或只有右子樹，則可將P的左子樹或右子樹直接改為其雙親結點F的左子樹或右子樹。若P既有左子樹，又有右子樹此時有兩種處理方法。方法1:首先找到結點P在中序序列中的直接前驅結點 S,然后用結點P的左子樹改為 F的左子樹，而將P的右子樹改為S的右子樹。方法2:首先找到結點P在中序序列中的直接前驅結點s,然后用結點s的值替代結點p 的值，再將結點s刪除，原結點s的左子樹改為s的雙親結點q的右子樹。主要代碼如下：void Delete(bitree &p)/從二叉排序樹中刪除結點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;/等被刪結點的前驅s的內(nèi)容直接替代該結點的內(nèi)容 if(q!=p)/若被刪除結點的左子樹的右子樹不為空q->rchild=s->lchild;/重接*q 的右子樹elseq->l

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

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

23、和決定懲罰，它 提供對程序說明、設計和編碼的最終評審。是發(fā)現(xiàn)程序缺陷和錯誤的有力手段。根據(jù)系統(tǒng)設計目標和功能，對系統(tǒng)進行測試。1、功能性(1)程序實現(xiàn)的主要功能，包括查詢，插入，刪除等。(2)題目要求的輸入輸出字段，以及題目要求的輸入限制。2、可靠性程序正確實現(xiàn)了對動態(tài)查找表的查詢、插入、刪除等各種功能。3、易用性現(xiàn)有程序實現(xiàn)了如下易用性：(1)查詢，插入，刪除，操作相關提示信息的一致性，可理解性(2)輸入限制的正確性(3)輸入限制提示信息的正確性，可理解性，一致性(4)界面排版簡潔完整3.2程序運行1、主界面：n【m5與算法的球性徵計黃拂a物與幅現(xiàn)津唐設計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 團 <0x0> execution t. ime : 7.297 s Pi*£s：s： amy ksy t口 心tmtiriuE.程序完成情況在編寫程序寫課程設計的時間里，雖然歷經(jīng)重重困難和挫折，但是在我自己的努力 和老師的幫助下終于完成了動態(tài)查找表的設計。盡管該程序在功能和性能上可能還有一 些缺陷，但是我已經(jīng)完成了課程設計的任務和目標，達到了題目基本要求，成功完成了 算法與數(shù)

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

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