排序二叉樹的應(yīng)用數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告.doc

前言 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)之間關(guān)系的一門科學(xué)，我們稱這一關(guān)系為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡稱數(shù)據(jù)結(jié)構(gòu)。當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)確定以后，數(shù)據(jù)在物理空間中的存儲方式，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。同一邏輯結(jié)構(gòu)可以具有不同的存儲結(jié)構(gòu)，因而有不同的算法。本次課程設(shè)計，程序中的數(shù)據(jù)采用“二叉樹結(jié)構(gòu)”。具體采用的是“二叉排序樹”，并且使用“一維數(shù)組”作為其存儲結(jié)構(gòu)。一維數(shù)組順序表存儲結(jié)構(gòu)是用一組地址連續(xù)的存儲單元依次自左而右、自上而下存儲二叉排序樹的結(jié)點元素；本課程設(shè)計實現(xiàn)了二叉排序樹的創(chuàng)建、查找、插入、刪除，中序遍歷輸出等基本操作，完美地實現(xiàn)了二叉排序樹的大部分功能。 二叉樹是樹形結(jié)構(gòu)的一個重要抽象數(shù)據(jù)類型。許多實際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹的形式，即使是一般的樹也能簡單地轉(zhuǎn)換為二叉樹，而且二叉樹的存儲結(jié)構(gòu)及其算法都較為簡單，因此二叉樹顯得特別重要。排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。排序時計算機程序設(shè)計中的一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個按關(guān)鍵字有序的序列。排序在我們?nèi)粘Ｉ钪须S處可見，經(jīng)常會用到，因此，學(xué)習(xí)和研究各種排序方法是計算機工作者的重要課題之一。二叉樹是另一種樹型結(jié)構(gòu)，它的特點是每個結(jié)點至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。順應(yīng)二叉樹的這個特點來進行對二叉樹的排序操作，這個問題也就思路清晰，設(shè)計起來沒那么困難了。二叉樹有5種基本形態(tài)，二叉樹可以是空集；根可以有空的左子樹或右子樹；或者左、右子樹皆為空。即空二叉樹，只有一個結(jié)點的二叉樹，右子樹為空的二叉樹，左子樹為空的二叉樹，左右子樹均非空的二叉樹。這些形態(tài)在后面的設(shè)計程序中均可以實現(xiàn).正文1.1課程設(shè)計的教學(xué)目的及任務(wù)(1) 使學(xué)生進一步理解和掌握所學(xué)的各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作實現(xiàn)算法，以及它們在程序中的使用方法。(2) 使學(xué)生初步掌握軟件開發(fā)過程的問題分析、設(shè)計、編碼、測試等基本方法和基本技能。(3) 使學(xué)生掌握使用各種計算機資料和有關(guān)參考資料，提高學(xué)生進行程序設(shè)計的基本能力。1.2課程設(shè)計的主要內(nèi)容(1) 問題分析和任務(wù)定義。根據(jù)題目的要求，充分地分析和理解問題，明確問題要求做什么？限制條件是什么？(2) 邏輯設(shè)計。對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明）。(3) 物理設(shè)計。定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽代碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架。(4)程序編碼。把詳細設(shè)計的結(jié)果進一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚(5) 程序調(diào)試與測試。利用VC+6.0調(diào)試程序，能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調(diào)試正確后，認真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。(6) 結(jié)果分析。程序運行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析。 (7) 撰寫課程設(shè)計報告2.1 課程設(shè)計的要求1、 根據(jù)所學(xué)知識并自主查找相關(guān)資料； 2、進行算法設(shè)計與分析； 3、算法實現(xiàn)，測試并檢驗運行結(jié)果是否符合要求；4、書寫課程設(shè)計說明書2.2問題描述排序在我們?nèi)粘Ｉ钪须S處可見，經(jīng)常會用到，因此，學(xué)習(xí)和研究各種排序方法是計算機工作者的重要課題之一。二叉排序樹是一種簡單的樹的排序方法，排序原理簡單易懂，具有較高的易學(xué)性與理解性。2.3數(shù)據(jù)結(jié)構(gòu)分析 2.3.1抽象數(shù)據(jù)類型定義（ADT） 抽象數(shù)據(jù)類型的描述包括給出抽象數(shù)據(jù)類型的名稱、數(shù)據(jù)的集合、數(shù)據(jù)之間的關(guān)系和操作的集合等方面的描述。抽象數(shù)據(jù)類型的設(shè)計者根據(jù)這些描述給出操作的具體實現(xiàn)，抽象數(shù)據(jù)類型的使用者依據(jù)這些描述使用抽象數(shù)據(jù)類型作用：抽象數(shù)據(jù)類型可以使我們更容易描述現(xiàn)實世界。例：用線性表描述學(xué)生成績表，用樹或圖描述遺傳關(guān)系。 定義：一個數(shù)學(xué)模型以及定義在該模型上的一組操作。 關(guān)鍵：使用它的人可以只關(guān)心它的邏輯特征，不需要了解它的存儲方式。定義它的人同樣不必要關(guān)心它如何存儲。2.3.2抽象數(shù)據(jù)類型結(jié)構(gòu)抽象數(shù)據(jù)類型可用三元組表示 （D,S,P）其中，D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是D的基礎(chǔ)操作集。用以下格式定義抽象數(shù)據(jù)類型：ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系： 基礎(chǔ)操作：ADT 抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為基本操作名 初始條件： 操作結(jié)果：基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除提供輸入值外，還將返回輸入結(jié)果?！俺跏紬l件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯信息。“操作結(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化情況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。2.4二叉排序樹設(shè)計分析2.4.1二叉樹的全面定義 二叉樹是n（n=0）個結(jié)點的有限集合，它或為空樹（n=0），或由一個根結(jié)點和兩棵分別稱為根的左子樹和右子樹的互不相交的二叉樹組成。二叉樹是一個遞歸定義。一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。對滿二叉樹的結(jié)點進行連續(xù)編號，一開始就規(guī)定編號從根結(jié)點起，自上而下，自左而右。2.4.2二叉樹的存儲結(jié)構(gòu)1） 順序存儲結(jié)構(gòu)：二叉樹可以采用順序存貯結(jié)構(gòu)，即用一維數(shù)組來存放二叉樹的數(shù)據(jù)元素。它是按照滿二叉樹的結(jié)點層次編號層次來依次存放二叉樹中的數(shù)據(jù)元素。2）鏈?zhǔn)酱鎯Y(jié)構(gòu)：設(shè)計不同的結(jié)點結(jié)構(gòu)可構(gòu)成不同形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。在本程序中，采用順序存儲結(jié)構(gòu)，對二叉樹進行插人、刪除、查找、遍歷等操作。2.4.3二叉樹的建立已知一棵二叉樹，共有n個結(jié)點，建立的方法如下：1） 照完全二叉樹的編號方法，對該二叉樹進行編號。2） 次輸入一個結(jié)點的值x和該結(jié)點的編號k，動態(tài)申請一塊空間來存放該結(jié)點，空間的地址為p。3） 把p值賦給adrk中。4） 如果k=1，轉(zhuǎn)到5；否則，把p的值填入其父結(jié)點的指針域中。p的父結(jié)點地址為adrk/2，若k為偶數(shù)，則做adrk/2-lc=p；若為奇數(shù)，則做adrk/2-rc=p。5） 重復(fù)24，直到全部頂點數(shù)據(jù)輸入完為止。6） 遍歷二叉樹，即如何按某條搜索路徑尋訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。一棵非空二叉樹是由根結(jié)點（D）、左子樹（L）和右子樹（R）三個基本部分組成。要遍歷這三個基本部分，可以有六種可能的順序。若限定先左后右，則只有三種情況：先序遍歷（DLR）、中序遍歷（LDR）、后序遍歷（LRD）。在本程序中，遍歷二叉樹函數(shù)的核心是以一個簡單的case語句來實現(xiàn)的。7)二叉樹的插入操作：這個操作首先生成一個新的結(jié)點結(jié)構(gòu)，把數(shù)據(jù)存入新結(jié)點，然后搜索二叉樹尋找插入結(jié)點的位置，再把新結(jié)點連接到二叉樹。把這個操作定義為一個函數(shù)，其函數(shù)名為instree。8) 二叉樹中元素的查找：在許多情況下，我們需要在一棵已知的二叉樹中查找某個元素，以確定樹中是否存在這個元素。這種查找與鏈表數(shù)據(jù)結(jié)構(gòu)中查找成員的情況極類似。查找函數(shù)名字定義為membertree。9) 從二叉樹中刪除一個成員：進行成員刪除操作時，首先必須用遞歸函數(shù)遍歷這棵樹，找到這個元素。當(dāng)找到這個元素之后，還要考慮以下四種不同的情況：刪除一個終端結(jié)點；刪除只有一個左孩子的結(jié)點；刪除只有一個右孩子的結(jié)點；刪除帶有兩個孩子的結(jié)點。刪除函數(shù)名字定義為deltree。2.4.4二叉排序樹的查找步驟：若根結(jié)點的關(guān)鍵字值等于查找的關(guān)鍵字，成功。 否則，若小于根結(jié)點的關(guān)鍵字值，遞歸查左子樹。 若大于根結(jié)點的關(guān)鍵字值，遞歸查右子樹。 若子樹為空，查找不成功。 平均情況分析（在成功查找兩種的情況下） 在一般情況下，設(shè) P（n，i）且它的左子樹的結(jié)點個數(shù)為 i 時的平均查找長度。如圖的結(jié)點個數(shù)為 n = 6 且 i = 3; 則 P（n,i）= P（6, 3） = 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 / 6 = 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 / 6 注意：這里 P(3)、P(2) 是具有 3 個結(jié)點、2 個結(jié)點的二叉分類樹的平均查找長度。 在一般情況，P（i）為具有 i 個結(jié)點二叉分類樹的平均查找長度。 P(3) = （1+2+2）/ 3 = 5/3 P(2) = （1+2）/ 2 = 3/2 P（n,i）= 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) / n n -1 P（n）= P（n,i）/ n = 2(1+I/n)lnn i=0 因為 2(1+I/n)lnn1.38logn 故P(n)=O(logn)2.5設(shè)計思路2.5.1二叉排序樹的操作實現(xiàn)目的主函數(shù)main() ：由簡單的if語句外加自定義函數(shù)，支持程序選擇，當(dāng)運行時，可以執(zhí)行有關(guān)二叉樹的操作：建立二叉排序樹，如插入一個元素、刪除一個元素、查找一個元素、等。此次設(shè)計僅此設(shè)立簡單的幾種操作，主要是讓大家認識和真正理解二叉排序樹。2.5.2二叉排序樹的分塊流程圖2.5.3簡單舉例分析例如：給定一組序列8，,1,6,78,5,96,56,7利用二叉排序樹的特點構(gòu)造一個二叉排序樹。具體做法如下（全例流程圖解）： （a） （b） （c） （d） （e）先序：（先根遍歷）中序：（中根遍歷）后序：（后根遍歷）以上（a）（e）過程就是二叉排序樹的構(gòu)建與排序的過程，簡單說，就是在一組數(shù)中，取一個元素為根節(jié)點，以所選根節(jié)點為準(zhǔn)，比根節(jié)點大的為左子樹，比根節(jié)點小的做為右子樹，另外，左右子樹又可以做為根節(jié)點，同樣原理對二叉樹進行排序，直到左右子樹后再無其他可以排序的元素為止。在進行遍歷操作的時候，除根節(jié)點便利是順序變化，其余的都是先左子樹，后右子樹的順序。2.5.4主要的樹函數(shù)的說明及關(guān)鍵代碼分析部分1）void prttree(treeptr tnode,int t)；/打印樹。該函數(shù)在屏幕上打印出存放在樹中的元素，如果是空樹，則無輸出。參數(shù)：tnode-指向根結(jié)點的指針； If Else 語句 While 語句 結(jié)構(gòu)體定義類型（struct） Break 語句 t-打印方式：0：先序 1：中序 2：后序（用遞歸算法遍歷二叉樹）。 #include ： 庫函數(shù)的頭文件，stdlib.h里面定義了五種類型、一些宏和通用工具函數(shù)。類型例如size_t、wchar_t、div_t、ldiv_t和lldiv_t；宏例如EXIT_FAILURE、EXIT_SUCCESS、RAND_MAX和MB_CUR_MAX等等；常用的函數(shù)如malloc()、calloc()、realloc()、free()、system()、atoi()、atol()、rand()、 srand()、exit()等等。 struct btree *left; struct btree *right; BTR,*PBTR;這就利用了struct結(jié)構(gòu)類型定義建立的二叉排序樹。第一塊：函數(shù)功能：實現(xiàn)非遞歸建立二叉樹 函數(shù)原型：void creat_btree(int *a,int size) 函數(shù)參數(shù)：int *a :保存二叉樹節(jié)點的數(shù)組首地址 int size:節(jié)點數(shù)目函數(shù)返回值：void 優(yōu)點：建立的二叉樹按中序遍歷后：是從小到大有序的可以是一種排序算法 第二塊：函數(shù)功能：實現(xiàn)遞歸前序遍歷二叉樹 函數(shù)原型：void preorder(PBTR head) 函數(shù)參數(shù)：PBTR :保存二叉樹根節(jié)點 函數(shù)返回值：void 第三塊：函數(shù)功能：實現(xiàn)遞歸中序遍歷二叉樹 函數(shù)原型：void midorder(PBTR head) 函數(shù)參數(shù)：PBTR :保存二叉樹根節(jié)點 函數(shù)返回值：void 第四塊：函數(shù)功能：遞歸求二叉樹的深度 函數(shù)原型：int btreedepth(PBTR head) 函數(shù)參數(shù)：PBTR :保存二叉樹根節(jié)點 函數(shù)返回值：int :二叉樹的深度 第五塊：程序測試部分2.6整體算法流程圖解：開始建一個二叉排序樹輸入選擇的操作（x1，x2，x3，x4）nX4|n0否n=0n=1n=2n=3n=4否或或或是是是是創(chuàng)建二叉排序樹 遍歷結(jié)點 插入結(jié)點求二叉排序樹深度結(jié)束2.7算法的的測試分析與實現(xiàn)：2.7.1 測試結(jié)果分析及截圖編好的C語言程序要經(jīng)過編譯（輸入）、編譯和連接后才能形成可執(zhí)行的程序運用VC+6.0軟件 測試程序結(jié)果（1） 經(jīng)輸入調(diào)試后：（2） 當(dāng)程序段是任意輸入的時候，運行結(jié)果：（3） 源程序段經(jīng)調(diào)試后有以下結(jié)果：對于原程序段，輸入一組數(shù)，則對應(yīng)的二叉排序樹的先序、中序、后序以及該二叉排序樹的深度。當(dāng)查看并調(diào)試程序段發(fā)現(xiàn)沒有錯誤時，就可以運行了，通過測試程序我們可以得到本次課程設(shè)計的預(yù)期結(jié)果。2.7.2二叉排序樹的算法復(fù)雜度：平衡二叉排序樹的時間復(fù)雜度為 O（logn），一般的在排序操作中，快排 ： 是 O(nlog n)的 堆排：速度不穩(wěn)定 ，但 100W時 ，效率比快排高很多！ 二叉排序樹在特定的情況下才使用，效率也很高 ，不過 ，程序復(fù)雜度比堆排、快排也高很多。2.7.3 二叉排序樹的優(yōu)缺點分析：優(yōu)點：插入，刪除操作的時間復(fù)雜度都是O(log(n)級的，即經(jīng)過O(log(n)時間搜索到了需插入和刪除的節(jié)點的位置，后經(jīng)過O(1)級的時間就可以直接插入和刪除，比有序順序表的插入和刪除O(n)(查找O(log(n)，移動節(jié)點O(n)快，而和無序順序表插入O(1)，刪除O(n)比，因為是有序的，所以查找的速度要快很多。缺點：二叉排序樹的構(gòu)造不止和最終節(jié)點的順序有關(guān)，還和節(jié)點插入和刪除的順序有關(guān)，在某些特殊的情況下，樹的高度可以等于節(jié)點的數(shù)量，于是查找的時間復(fù)雜度就退化成了O(n)了,相當(dāng)也無序順序表的查找小結(jié)課本剛結(jié)束，我就開始了數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計。通過課程設(shè)計我進一步掌握了許多課本知識，同時還了解了許多課外的有關(guān)數(shù)據(jù)結(jié)構(gòu)的知識，這對于我來說是受益匪淺的。在此次課程設(shè)計中，我不但運用了數(shù)據(jù)結(jié)構(gòu)的知識，還利用了所學(xué)的c語言和C+中各方面的知識。這對于我來說是一個突破。從中我也學(xué)習(xí)到了許多知識，它有助于增強我的自信心，幫助我提高編寫程序的能力，也使我懂得：光靠課堂和書本是難以真正掌握數(shù)據(jù)結(jié)構(gòu)的。衡量學(xué)習(xí)好壞的標(biāo)準(zhǔn)不是“懂不懂”，而是“敢不敢在知識的道路上邁出你的第一步”。所以，還是馬克思說的那句話“理論與實踐結(jié)合”，是我們能夠更好掌握知識的最直接的手段。在這兩周的課程設(shè)計時光里，對于我的第一次課程設(shè)計，我還是感覺有些摸不著頭腦，剛開始著手的時候遇到了不少理論與實際上的難題，我照著老師給的模板一點一點寫，很慢，最后通過查資料，與同學(xué)交流，終于寫好了，但是不對，還是有很多地方要改就這樣一步一步做出來了，但是我從未因困難而退縮。沒有辛苦的歷程就無法感受甜美的收獲，以上是我兩周構(gòu)想的二叉排序樹的設(shè)計思路以及通過查閱書本，閱覽資料得出的程序段，這個程序設(shè)計是學(xué)者正確掌握并快速學(xué)習(xí)二叉排序樹的很好利器。通過學(xué)習(xí)，我們可以知道什么事二叉樹，什么是二叉排序樹，二叉排序樹的算法思想，如何使用并正確使用二叉排序樹。學(xué)會構(gòu)建二叉排序樹，學(xué)會最簡單且實用的操作（如：二叉排序樹的建立，遍歷）并進一步具備更深一層次的插入，刪除等操作以此來認識二叉排序樹，認識數(shù)據(jù)結(jié)構(gòu)這門課程。當(dāng)然主要關(guān)鍵還是要學(xué)會一門思想，學(xué)會另外一種考慮問題的方法，進一步鞏固語言和編程方面的應(yīng)用技能。參考文獻1嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu).北京:清華大學(xué)出版社,2007.42Decoder編著.C/C+程序設(shè)計.北京：中國鐵道出版社，20023 H.M.Deitel，Paul James Deitel著.薛萬鵬譯.C/C+程序設(shè)計大全.北京：機械工業(yè)出版社.19974Michael J.Young著.Mastering Visual C+6.0 Sybex Inc.19995楊進才，沈顯君，劉蓉編.C/C+語言程序設(shè)計教程.清華大學(xué)出版社，20066 劉振安，劉燕君，孫忱C/C+語言課程設(shè)計.機械工業(yè)出版社，20077Al Strevens,Clayton Walnum著.林麗閩等譯.標(biāo)準(zhǔn)C/C+寶典.北京：電子工業(yè)出版社.20018Brian Overland著.董梁等譯.C/C+語言命令譯解（第二版）.北京：機械工業(yè)出版社，20029 李廉治,姜文清,郭福順.數(shù)據(jù)結(jié)構(gòu)M.大連.大連理工大學(xué)出版社,1989年.10 許卓群,張乃孝,楊冬青,唐世渭.數(shù)據(jù)結(jié)構(gòu)M.北京.高等教育出版社,1988年.11 陳文博,嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)M.北京.機械工業(yè)出版社,1990,87-100.12 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)M.第二版.北京.清華大學(xué)出版社,1992.附錄二叉排序樹的應(yīng)用源代碼：#include #include typedef struct btreeint data;struct btree *left;struct btree *right; BTR,*PBTR;typedef struct BTRStPBTR ptree;struct BTRSt *link;Stack,*PStack; PBTR Bitree=NULL;void creat_btree(int *a,int size)int i;PBTR pre,pre2; for(i=0;idata=ai; Bitree-left=NULL; Bitree-right=NULL; continue; else pre = Bitree; while(1) if(aipre-data) if(pre-right=NULL) pre2=(PBTR)malloc(sizeof(BTR); if(pre2=N