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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

typedefstructTnode{

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

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

}*node,BSTnode;

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

typedefstruct{

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

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

}BST;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)對(duì)于未平衡化的二叉樹(shù)：

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

(2)最好的情況是：

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

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

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

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

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

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

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

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

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

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

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

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

O（n）。

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

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

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

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

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

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

六、心得和總結(jié)

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

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

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

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

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

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

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

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