前言：本站為你精心整理了數(shù)據(jù)結(jié)構(gòu)作業(yè)報告范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

編者按：本文主要從大型作業(yè)（課程設(shè)計）題目和內(nèi)容；程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明；算法的設(shè)計思想；平衡二叉樹與未平衡化的二叉樹查找效率比較；時間復(fù)雜度的分析；心得和總結(jié)，對數(shù)據(jù)結(jié)構(gòu)作業(yè)報告進行講述。其中，主要包括：用二叉鏈表作存儲結(jié)構(gòu)、用順序表（一維數(shù)組）作存儲結(jié)構(gòu)、二插鏈表作存儲結(jié)構(gòu)、對于未平衡化的二叉樹、查找函數(shù)最壞的情況是要找的點正好是二叉樹的最深的葉子結(jié)點，此時時間復(fù)雜度＝O（n）、刪除函數(shù)不采用遞歸手法，而是采用重新建立一顆不含要刪結(jié)點的二插排序樹、只有真正理解這樣定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu)的性質(zhì)是非常有用的，它往往是編寫程序的關(guān)鍵，具體材料請詳見：

一、大型作業(yè)（課程設(shè)計）題目和內(nèi)容

1、用二叉鏈表作存儲結(jié)構(gòu)

（1）以回車（‘\n’）為輸入結(jié)束標(biāo)志，輸入數(shù)列L，生成二叉排序樹T；

（2）對二叉排序樹T作中序遍歷,輸出結(jié)果；

（3）計算二叉排序樹T的平均查找長度，輸出結(jié)果；

（4）輸入元素x，查找二叉排序樹T，如果存在含x的結(jié)點，則刪除該結(jié)點，并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無結(jié)點x”；

（5）判斷二叉排序樹T是否為平衡二叉樹，輸出信息“OK!”/“NO!”;

*（6）再用數(shù)列L，生成平衡二叉排序樹BT：當(dāng)插入新元素后，發(fā)現(xiàn)當(dāng)前二叉排序樹BT不是平衡二叉排序樹，則立即將它轉(zhuǎn)換成新的平衡二叉排序樹BT；

*（7）計算平衡二叉排序樹BT的平均查找長度，輸出結(jié)果。

2、用順序表（一維數(shù)組）作存儲結(jié)構(gòu)

（1）以回車（‘\n’）為輸入結(jié)束標(biāo)志，輸入數(shù)列L，生成二叉排序樹T；

（2）對二叉排序樹T作中序遍歷,輸出結(jié)果；

（3）計算二叉排序樹T的平均查找長度，輸出結(jié)果；

（4）輸入元素x，查找二叉排序樹T，如果存在含x的結(jié)點，則刪除該結(jié)點，并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無結(jié)點x”；

（5）判斷二叉排序樹T是否為平衡二叉樹，輸出信息“OK!”/“NO!”。

二、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲結(jié)構(gòu)的說明

程序中的數(shù)據(jù)采用“樹形結(jié)構(gòu)”作為其數(shù)據(jù)結(jié)構(gòu)。具體的，我采用的是“二叉排序樹”。

二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：（1）若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；（2）若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；（3）它的左右子樹也分別為二叉排序樹。

程序中分別采用了“二插鏈表”和“一維數(shù)組”作為其存儲結(jié)構(gòu)。

二插鏈表存儲結(jié)構(gòu)中二插樹的結(jié)點由一個數(shù)據(jù)元素和分別指向其左、右子樹的兩個分支構(gòu)成。如：我的程序中采用的結(jié)構(gòu)是：

typedefstructTnode{

intdata;/*數(shù)據(jù)元素*/

structTnode*lchild,*rchild；/*左右指針*/

}*node,BSTnode;

一維數(shù)組順序表存儲結(jié)構(gòu)是用一組地址連續(xù)的存儲單元依次自上而下、自左而右存儲完全二插樹上的結(jié)點元素，即將完全二叉樹上編號為i的結(jié)點元素存儲在如上定義的一維數(shù)組中下標(biāo)為i-1的分量中。利用順序表作為存儲結(jié)構(gòu)：

typedefstruct{

int*data;/*一維數(shù)組基址*/

intlenth;/*一維數(shù)組的長度*/

}BST;

一維數(shù)組存儲結(jié)構(gòu)中結(jié)點i的父母親為|_i/2_|,左孩子為2i，右孩子為2i+1.

三、算法的設(shè)計思想

a)二插鏈表作存儲結(jié)構(gòu)：

建立二插排序樹采用邊查找邊插入的方式。查找函數(shù)采用遞歸的方式進行查找。如果查找成功則不應(yīng)再插入原樹，否則返回當(dāng)前結(jié)點的上一個結(jié)點。然后利用插入函數(shù)將該元素插入原樹。

對二叉樹進行中序遍歷采用遞歸函數(shù)的方式。在根結(jié)點不為空的情況下，先訪問左子樹，再訪問根結(jié)點，最后訪問右子樹。

計算二插排序樹的平均查找長度時，仍采用類似中序遍歷的遞歸方式，用s記錄總查找長度，j記錄每個結(jié)點的查找長度，s置初值為0，采用累加的方式最終得到總查找長度s。平均查找長度就等于s/i(i為樹中結(jié)點的總個數(shù))。

刪除結(jié)點函數(shù)，采用邊查找邊刪除的方式。如果沒有查找到，則不對樹做任何的修改；如果查找到結(jié)點，則分四種情況分別進行討論：1、該結(jié)點左右子樹均為空；2、該結(jié)點僅左子樹為空；3、該結(jié)點僅右子樹為空；4、該結(jié)點左右子樹均不為空。

判斷二插排序樹是否為平衡二叉樹的函數(shù)，也是采用遞歸函數(shù)的方式，分別判定以樹中每個結(jié)點為根結(jié)點的子樹是否為平衡二叉樹。只要有一個子樹不為平衡二叉樹，則該樹便不是平衡二叉樹。

b)一維數(shù)組作存儲結(jié)構(gòu)：

建立二插排序樹，首先用一個一維數(shù)組記錄下讀入的數(shù)據(jù)，然后再用邊查找邊插入的方式將數(shù)據(jù)一一對應(yīng)放在完全二叉樹相應(yīng)的位置，為空的樹結(jié)點用“0”補齊。

中序遍歷二叉樹也采用遞歸函數(shù)的方式，先訪問左子樹2i,然后訪問根結(jié)點i,最后訪問右子樹2i+1.先向左走到底再層層返回，直至所有的結(jié)點都被訪問完畢。

計算二插排序樹的平均查找長度時，采用類似中序遍歷的遞歸方式，用s記錄總查找長度，j記錄每個結(jié)點的查找長度，s置初值為0，采用累加的方式最終得到總查找長度s。平均查找長度就等于s/i(i為樹中結(jié)點的總個數(shù))。

刪除二插排序樹中某個結(jié)點，采用邊查找邊插入的方式，類似重新建立一個一維數(shù)組作為存儲新樹的空間。將原數(shù)組中的數(shù)據(jù)一個一個的插入樹中，若遇到需要刪除的結(jié)點則不執(zhí)行插入操作。

判斷二插排序樹是否為平衡二叉樹的函數(shù)，也是采用遞歸函數(shù)的方式，分別判定以樹中每個結(jié)點為根結(jié)點的子樹是否為平衡二叉樹。只要有一個子樹不為平衡二叉樹，則該樹便不是平衡二叉樹。

四、平衡二叉樹與未平衡化的二叉樹查找效率比較

(1)對于未平衡化的二叉樹：

當(dāng)先后插入的關(guān)鍵字有序時，構(gòu)成的二插排序樹蛻變?yōu)閱沃?。樹的深度為n,其平均查找長度為（n+1）/2.這是最差的情況。這種情況下比較關(guān)鍵字的最大次數(shù)為n次。

(2)最好的情況是：

建成的樹是一棵平衡二叉樹。在這種情況下，二插排序樹的平均查找長度和log2(n)成正比。比較關(guān)鍵字的最大次數(shù)為：0.5logψ（5）＋logψ(n+1)-2次（其中ψ＝（1＋根號5）/2）。

(3)那么，平均情況下分析：

假設(shè)在含有n(n>=1)個關(guān)鍵字的序列中，i個關(guān)鍵字小于第一個關(guān)鍵字，n-i-1個關(guān)鍵字大于第一個關(guān)鍵字，則由此構(gòu)造而得的二插排序樹在n個記錄的查找概率相等的情況下，其平均查找長度為

：P(n,i)=[1+i*(P(i)+1)+(n-i-1)(P(n-i-1)+1)]/n

其中P(i)為含有i個結(jié)點的二插排序樹的平均查找長度，則P(i)+1為查找左子樹中每個關(guān)鍵字時所用比較次數(shù)的平均值，P（n-i-1）+1為查找右子樹中每個關(guān)鍵字時所用比較次數(shù)的平均值。又假設(shè)表中n個關(guān)鍵字的排列是“隨機”的，即任一個關(guān)鍵字在序列中將是第1個，或第2個，…，或第n個的概率相同，則可對上式從i等于0至n-1取平均值。最終會推導(dǎo)出：

當(dāng)n>=2時，P（n）<=2（1＋1/n）ln(n)

由此可見，在隨機的情況下，二插排序樹的平均查找長度和log（n）是等數(shù)量級的。

五、時間復(fù)雜度的分析

說明：對時間復(fù)雜度的分析，均指在最壞情況下的時間復(fù)雜度。

二插鏈表存儲結(jié)構(gòu)中：

（1）查找函數(shù)最壞的情況是要找的點正好是二叉樹的最深的葉子結(jié)點，此時時間復(fù)雜度＝O（n）。

（2）插入函數(shù)最壞的情況是要插入的點正是二叉樹的最深的那一支的葉子結(jié)點，此時時間復(fù)雜度＝

O（n）。

（3）中序遍歷函數(shù)，求平均查找長度的函數(shù)，刪除函數(shù)以及判斷二插排序樹是否為平衡二叉樹的函數(shù)，其時間復(fù)雜度均與以上情況類似，等于O（n）。

一維數(shù)組順序表存儲結(jié)構(gòu)中：

（1）插入函數(shù)最壞的情況是要插入的點正是二叉樹的最深的那一支的葉子結(jié)點，此時時間復(fù)雜度＝O（n）。

（2）創(chuàng)建函數(shù)最壞的情況就是調(diào)用插入函數(shù)時插入函數(shù)遇到最壞的情況。因此，創(chuàng)建函數(shù)的時間復(fù)雜度也等于O（n）。

（3）中序遍歷函數(shù)，求平均查找長度的函數(shù)，查找函數(shù)，以及判斷二插排序樹是否為平衡二叉樹的函數(shù)，其時間復(fù)雜度均與以上情況類似，等于O（n）。

（4）刪除函數(shù)不采用遞歸手法，而是采用重新建立一顆不含要刪結(jié)點的二插排序樹。其時間復(fù)雜度＝O（n）。

六、心得和總結(jié)

這次暑假的課程設(shè)計作業(yè)我選擇做數(shù)據(jù)結(jié)構(gòu)是出于我對用高級語言編程的極大興趣。通過這次實驗我也著實又感受了一次編程的樂趣，從中也學(xué)到了不少知識。

雖然都說“程序＝數(shù)據(jù)結(jié)構(gòu)＋算法”，但我在學(xué)習(xí)運用數(shù)據(jù)結(jié)構(gòu)編程之前，并沒能深刻體會到這一點，直到這次課設(shè)實踐。

我感受最深的一點是：以前用C編程，只是注重如何編寫函數(shù)能夠完成所需要的功能，似乎沒有明確的戰(zhàn)術(shù)，只是憑單純的意識和簡單的語句來堆砌出一段程序。感覺有點像張飛打仗，有勇無謀，只要能完成任務(wù)就行。但現(xiàn)在編程感覺完全不同了。在編寫一個程序之前，自己能夠綜合考慮各種因素，首先選取自己需要的數(shù)據(jù)結(jié)構(gòu)，是樹還是圖或是別的什么？然后選定一種或幾種存儲結(jié)構(gòu)來具體的決定后面的函數(shù)的主要風(fēng)格。最后在編寫每一個函數(shù)之前，可以仔細斟酌比對，挑選出最適合當(dāng)前狀況的算法。這樣，即使在完整的程序還沒有寫出來之前，自己心中已經(jīng)有了明確的原圖了。這樣無形中就提高了自己編寫的程序的質(zhì)量。

另外，我還體會到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性。只有真正理解這樣定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu)的性質(zhì)是非常有用的，它往往是編寫程序的關(guān)鍵。

我以前對遞歸算法一直很害怕，總是看不明白究竟這遞歸是怎么進行的。在這次實驗中我終于克服了這一障礙，一次次單步執(zhí)行書中遞歸函數(shù)的例子，并一遍遍在心中自己默默的走，終于弄明白了，真的是功夫不負有心人啊！同時我還根據(jù)自己的理解寫出了類似的遞歸函數(shù)實現(xiàn)了新的功能，真是受益良多?。?/p>

在這次實驗中，我對參數(shù)的調(diào)用也進行了很多種嘗試，已經(jīng)能夠相對準(zhǔn)確的選擇合適的參數(shù)形式來實現(xiàn)函數(shù)之間的數(shù)據(jù)傳輸交互了。

這次實驗中我也出現(xiàn)過一些比較嚴(yán)重的錯誤。在用一維數(shù)組順序表結(jié)構(gòu)編寫程序時我錯誤的運用靜態(tài)鏈表來實現(xiàn)函數(shù)功能。這是我對基本概念理解的模糊不清造成的。我原以為只要采用一維數(shù)組作為存儲結(jié)構(gòu)它就一定也是順序表結(jié)構(gòu)，而實質(zhì)上這根本是兩個不相干的概念。后來在同學(xué)的指點下我意識到自己的錯誤。不過收獲也很不少。至少我又練習(xí)了運用靜態(tài)鏈表來實現(xiàn)同樣的功能，同時我也發(fā)現(xiàn)兩者在很多函數(shù)上是互通的，只需稍作修改即可移植。

總之，我會繼續(xù)我的興趣編寫程序的，相信在越來越多的嘗試之后，自己會不斷進步不斷提高的。