數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---二叉排序樹實(shí)現(xiàn)集合的運(yùn)算

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p>　　設(shè)計(jì)題目 二叉排序樹實(shí)現(xiàn)集合的運(yùn)算 </p><p>　　班 級(jí) 信息管理1班 </p><p>　　學(xué) 號(hào) &

2、lt;/p><p><b>　　引言</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)是研究與數(shù)據(jù)之間的關(guān)系，我們稱這一關(guān)系為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡稱數(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ù)采用“樹形結(jié)構(gòu)”作為其數(shù)據(jù)結(jié)構(gòu)。而二叉排序樹又是一種特殊的二叉樹。本課程設(shè)中

3、的二叉排序樹是用來實(shí)現(xiàn)集合中的運(yùn)算功能，一共要實(shí)現(xiàn)五項(xiàng)集合的基本的功能。它們分別是集合的元素判定，子集判定，交，并，差運(yùn)算。實(shí)現(xiàn)這五項(xiàng)基本功能的目的是為了鞏固和運(yùn)用理論知識(shí)、鍛煉實(shí)踐能力、構(gòu)件合理知識(shí)結(jié)構(gòu)和提高程序設(shè)計(jì)能力。</p><p><b>　　正文</b></p><p><b>　　1 需求分析</b></p><

4、p>　　1.1課程設(shè)計(jì)題目、任務(wù)及要求</p><p>　?。?） 用二叉排序樹實(shí)現(xiàn)集合的元素判定，子集判定，集合的交，并，差的運(yùn)算； </p><p>　?。?） 集合的元素限整數(shù)；</p><p>　?。?） 程序運(yùn)行時(shí)要先顯示題目，班級(jí)，學(xué)號(hào)，姓名，完成時(shí)間等信息。</p><p>　　1.2 課程設(shè)計(jì)思想</p>

5、<p>　　a.用二叉排序樹建立集合，然后用二叉排序樹的算法實(shí)現(xiàn)集合的元素判定，子集判定，集合的交并差的運(yùn)算；可見，要想完成集合的這些算法，最主要運(yùn)用到了二叉排序樹里面的查找算法，然后將數(shù)組與二叉排序樹結(jié)合起來，來實(shí)現(xiàn)這些算法。</p><p>　　b.查找函數(shù)采用遞歸的方式進(jìn)行查找；</p><p>　　對二叉排序樹進(jìn)行中序遍歷采用遞歸函數(shù)的方式：在根結(jié)點(diǎn)不為空的情況下，先

6、訪問左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹。由于二叉排序樹自身的性質(zhì)，左子樹小于根結(jié)點(diǎn)，而根結(jié)點(diǎn)小于右子樹，所以中序遍歷的結(jié)果是遞增的。</p><p><b>　　2 概要設(shè)計(jì)</b></p><p>　　2.1 對二叉排序樹的理解</p><p>　　二叉排序樹是一種動(dòng)態(tài)數(shù)表。</p><p>　　二叉排序樹的定義：二

7、叉排序樹或者是一棵空樹，或者是一棵具有如下性質(zhì)的二叉樹：</p><p>　　（１）每個(gè)結(jié)點(diǎn)都有一個(gè)作為搜索依據(jù)的關(guān)鍵碼（key），所有結(jié)點(diǎn)的關(guān)鍵碼互不相同；</p><p>　　（２）若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；</p><p>　?。ǎ常┤羲挠易訕浞强眨瑒t右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；</p><p&g

8、t;　　(4) 左、右子樹本身又各是一棵；</p><p>　?。?）左、右子樹本身又各是一棵二叉排序樹。</p><p>　　2.2 建立二叉排序樹（二叉鏈表做存儲(chǔ)結(jié)構(gòu)）</p><p>　　從空的二叉排序樹開始，經(jīng)過一系列的查找插入操作以后，生成一棵二叉排序樹。</p><p>　　根據(jù)二叉排序樹的定義，建立一棵二叉排序樹的過程是按照待

9、排序序列元素的先后次序，不斷動(dòng)態(tài)生成二叉樹的結(jié)點(diǎn)，逐個(gè)插入到二叉樹中。其過程可以描述為：</p><p>　　BSTree createBST(int *iArr)//建立集合二叉排序樹</p><p><b>　　{ </b></p><p>　　BSTree t=NULL; //根結(jié)點(diǎn)</p><p>　　KeyTy

10、pe key;</p><p><b>　　int i=0;</b></p><p>　　if(!*iArr)</p><p><b>　　{</b></p><p><b>　　cin>>key;</b></p><p>　　while(k

11、ey!=-1 && ++i<MaxElement) //輸入-1或輸入到最大個(gè)數(shù)止</p><p><b>　　{</b></p><p>　　(*iArr)++;iArr[*iArr] = key; //集合元素先在數(shù)組中存放</p><p><b>　　cin>>key;</b><

12、;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(i=1;i<=*iArr;i++) //由數(shù)組形式 生成 二叉排序樹狀集合形式</p><p><b>　　{</b></p><p>　　in

13、sertBST(t,iArr[i]);</p><p><b>　　}</b></p><p><b>　　return t;</b></p><p><b>　　}</b></p><p>　　左、右子樹的插入方式與二叉排序樹的插入方式相同。</p><p

14、>　　不斷調(diào)用上述的插入過程，直到所有待排序序列均排入后，就形成一棵二叉排序樹。</p><p>　　由此可見，建立二叉排序樹就是多次調(diào)用二叉排序樹的插入算法。</p><p>　　2.3二叉排序樹的生成過程</p><p>　　二叉排序樹的生成，采用遞歸方式的邊查找邊插入的方式。如圖：</p><p>　　2.4中序遍歷二叉排序樹(中

15、序輸出集合，按從小到大的順序)</p><p>　　中序遍歷二叉樹算法的框架是：</p><p>　　若二叉樹為空，則空操作；否則</p><p><b>　　中序遍歷左子樹；</b></p><p><b>　　訪問根結(jié)點(diǎn)；</b></p><p><b>　　中

16、序遍歷右子樹。</b></p><p>　　中序遍歷二叉樹也采用遞歸函數(shù)的方式，先訪問左子樹，然后訪問根結(jié)點(diǎn)，最后訪問右子樹，直至所有的結(jié)點(diǎn)都被訪問完畢。</p><p><b>　　代碼如下：</b></p><p>　　void inorder_btree(BSTree root)// 中序遍歷打印二叉排序樹 </p>

17、;<p><b>　　{</b></p><p>　　BSTree p=root;</p><p>　　if(p!=NULL){</p><p>　　inorder_btree(p->left );</p><p>　　cout<<" "<<p->k

18、ey<<" ";</p><p>　　inorder_btree(p->right );</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　?。?詳細(xì)設(shè)計(jì)和實(shí)現(xiàn)</b></p&g

19、t;<p>　　3.1主要功能模塊設(shè)計(jì)</p><p><b>　　1.元素判定：</b></p><p>　　用查找的方法實(shí)現(xiàn)元素判定；</p><p>　　BSTree searchBST(BSTree t,KeyType key) </p><p><b>　　{ </b><

20、;/p><p>　　if(!t || key==t->key) return t; </p><p>　　if(key<t->key)</p><p>　　return searchBST(t->left,key);</p><p><b>　　else</b></p><p>

21、;　　return searchBST(t->right,key);</p><p><b>　　}</b></p><p>　　改為返回指針，未找到時(shí)返回空指針 找到時(shí)返回所在位置，先判是不是空指針，非空了再判是不是相等了。</p><p><b>　　2.子集判定：</b></p><p>

22、;　　不懂怎么一個(gè)一個(gè)的來訪問樹結(jié)點(diǎn)，只好使個(gè)偷懶的方法啦，轉(zhuǎn)成數(shù)組，再遍歷數(shù)組，老師，別介意哦；</p><p>　　只要在另一個(gè)集合中找到有沒有與這個(gè)集合相等的元素就ok了。函數(shù)如下：</p><p>　　int beyong(BSTree m,BSTree n) </p><p><b>　　{</b></p><p&

23、gt;　　int i,Array[MaxElement]={0}</p><p>　　inorder_btree2Arr(n,Array);</p><p>　　for(i=1;i<=*Array;i++)</p><p>　　if(!searchBST(m,Array[i])) return 0;</p><p><b>　

24、　return 1;</b></p><p><b>　　}</b></p><p>　　3.求并集：A+B=C</p><p>　　中序遍歷兩個(gè)集合，先把A集合賦給C，然后把集合B的元素插入到C中就行了。</p><p>　　void combineTree(BSTree A,BSTree B,BSTree

25、 &C)</p><p><b>　　{</b></p><p>　　int i,Array[MaxElement]={0};</p><p>　　inorder_btree2Arr(A,Array);</p><p>　　C = createBST(Array);</p><p>　　A

26、rray[0]=0;</p><p>　　inorder_btree2Arr(B,Array);</p><p>　　for(i=1; i<=*Array; i++) insertBST(C,Array[i]);</p><p><b>　　}</b></p><p>　　4.交集：A∩B=C</p>

27、<p>　　用查找的方法在B中查找A中的每一個(gè)元素，把查找到得元素構(gòu)成一個(gè)新的新的集合C。</p><p>　　void joinTree(BSTree A,BSTree B,BSTree &C) </p><p><b>　　{</b></p><p>　　int i,Array[MaxElement]={0},Array

28、1[MaxElement]={0};</p><p>　　inorder_btree2Arr(B,Array);</p><p>　　for(i=1;i<=*Array;i++)</p><p>　　if(searchBST(A,Array[i])){Array1[0]++; Array1[Array1[0]] = Array[i];}//求相交的所有元素&l

29、t;/p><p>　　if(Array1[0]) C = createBST(Array1); //結(jié)果不空時(shí) 再組一個(gè)集合</p><p>　　else C=NULL;</p><p><b>　　}</b></p><p>　　5.求差集：A-B=C</p><p>　　中序遍歷A中的元素，在B中

30、查找到這些元素，求出所有不屬于B中的元素，在創(chuàng)建一顆二叉排序樹集合C，把這些有元素放入到C中即可。</p><p>　　void differencedTree(BSTree A,BSTree B,BSTree &C) </p><p><b>　　{</b></p><p>　　int i,Array[MaxElement]={0},

31、Array1[MaxElement]={0};</p><p>　　inorder_btree2Arr(A,Array);</p><p>　　for(i=1;i<=*Array;i++)</p><p>　　if(!searchBST(B,Array[i])){Array1[0]++; Array1[Array1[0]] = Array[i];}</p

32、><p>　　if(Array1[0]) C = createBST(Array1); //結(jié)果不空時(shí) 再組一個(gè)集合</p><p>　　else C=NULL;</p><p><b>　　}</b></p><p><b>　　3.2主程序設(shè)計(jì)</b></p><p>　　根

33、據(jù)題目要求，先輸出題目，班級(jí)，姓名，日期等等；</p><p>　　然后實(shí)現(xiàn)題目的所要的一系列函數(shù)，調(diào)用著希望函數(shù)，實(shí)現(xiàn)所要求的集合的功能；</p><p>　　寫了一個(gè)while循環(huán)，能夠使程序反復(fù)執(zhí)行下去。</p><p><b>　　4 程序調(diào)試及操作</b></p><p>　　經(jīng)過幾天的反復(fù)調(diào)試和修改后，程序得

34、以正常的運(yùn)行，并實(shí)現(xiàn)所要求的函數(shù)的功能。</p><p><b>　　程序運(yùn)行結(jié)果如下：</b></p><p>　　姓名，題目等的顯示:</p><p>　　集合的輸入與中序遍歷輸出： </p><p><b>　　元素判定：</b></p><p>　　子集判定，交，并差

35、的運(yùn)算：</p><p><b>　　三．體會(huì)與總結(jié)</b></p><p>　　這次課程設(shè)計(jì)使我對數(shù)據(jù)結(jié)構(gòu)認(rèn)識(shí)深刻了許多，其中最深刻的是我理解了二叉排序樹的含義和操作，同時(shí)也加深了對二叉樹的理解。本課程設(shè)計(jì)運(yùn)用了二叉排序樹的創(chuàng)建、中序遍歷、查找的功能。在進(jìn)行搜索時(shí)，可以采用更好的搜索結(jié)構(gòu)即動(dòng)態(tài)搜索結(jié)構(gòu)。在此次課設(shè)中，我遇到最大的一個(gè)問題是如何創(chuàng)建二叉排序樹（還要結(jié)合

36、不能提的要求來建立）以及怎樣把集合與二叉排序樹里聯(lián)系起來實(shí)現(xiàn)集合的一系列運(yùn)算。通過查找資料，請教同學(xué)和老師，終于把它解決了。通過這一周課設(shè)，我已經(jīng)學(xué)會(huì)用順序表和二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)對二叉排序樹的創(chuàng)建、中序遍歷、查找、刪除等操作。</p><p>　　但我同時(shí)也發(fā)現(xiàn)了自己許多不足之處。在這次可設(shè)中我同時(shí)用到了c語言和c++，雖說有點(diǎn)不倫不類，但這更鞏固了自己的C和C++的知識(shí)，呵呵，其實(shí)我知道這樣不好，算是對自己的

37、鼓勵(lì)吧。</p><p>　　首先，對數(shù)據(jù)結(jié)構(gòu)的掌握不夠，雖然完成了課設(shè)，但是只用到了基本的結(jié)點(diǎn)及操作，在數(shù)據(jù)結(jié)構(gòu)的選擇上避重就輕，覆蓋面較小，不能很好的體現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)的掌握度，同時(shí)也缺少了適當(dāng)?shù)腻憻挘谶@方面還需要去提高。</p><p>　　其次，在程序整體的設(shè)計(jì)上還不夠完整，各模塊可以適當(dāng)增加內(nèi)容，界面還可以更加人性化，這樣整個(gè)程序才具有更強(qiáng)的美觀性與實(shí)用性。</p>

38、<p>　　總而言之，這次課程設(shè)計(jì)給了我很大啟發(fā)，我明白了，不管遇到什么困難，只</p><p>　　抓住根源，不氣餒，從不同方面，不同角度去攻破它，終究會(huì)成功，生活也是如此</p><p>　　總而言之，這次課程設(shè)計(jì)給了我很大啟發(fā)，我明白了，不管遇到什么問題，只要抓住根源，不氣餒，從不同方面去攻破它，終究會(huì)成功，生活也是如此，風(fēng)雨之后總會(huì)見彩虹！</p><

39、;p><b>　　四．參考文獻(xiàn)</b></p><p>　　1.曲朝陽等.數(shù)據(jù)結(jié)構(gòu).中國電力出版社,2007</p><p>　　2.唐發(fā)根.數(shù)據(jù)結(jié)構(gòu)教程（第二版）.北京航空航天大學(xué)出版社,2004</p><p>　　3.潭浩強(qiáng).程序設(shè)計(jì).北京：清華大學(xué)出版社，2000</p><p>　　4.嚴(yán)蔚敏，吳偉民.數(shù)

40、據(jù)結(jié)構(gòu).北京：清華大學(xué)出版,2001</p><p>　　5.殷人昆.數(shù)據(jù)結(jié)構(gòu).北京：清華大學(xué)出版社，2004</p><p>　　6.王曉東.數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)．電子工業(yè)出版社 2002</p><p>　　7.陳慧南．?dāng)?shù)據(jù)結(jié)構(gòu)與算法 C++ 語言描述．高等教育出版社 2005</p><p>　　8.竇延平等.數(shù)據(jù)結(jié)構(gòu)與算法 C++．上海