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

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