數據結構作業報告
前言：本站為你精心整理了數據結構作業報告范文，希望能為你的創作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。
編者按：本文主要從大型作業（課程設計）題目和內容；程序中所采用的數據結構及存儲結構的說明；算法的設計思想；平衡二叉樹與未平衡化的二叉樹查找效率比較；時間復雜度的分析；心得和總結，對數據結構作業報告進行講述。其中，主要包括：用二叉鏈表作存儲結構、用順序表（一維數組）作存儲結構、二插鏈表作存儲結構、對于未平衡化的二叉樹、查找函數最壞的情況是要找的點正好是二叉樹的最深的葉子結點，此時時間復雜度＝O（n）、刪除函數不采用遞歸手法，而是采用重新建立一顆不含要刪結點的二插排序樹、只有真正理解這樣定義數據類型的好處，才能用好這樣一種數據結構。了解典型數據結構的性質是非常有用的，它往往是編寫程序的關鍵，具體材料請詳見：
一、大型作業（課程設計）題目和內容
1、用二叉鏈表作存儲結構
（1）以回車（‘\n’）為輸入結束標志，輸入數列L，生成二叉排序樹T；
（2）對二叉排序樹T作中序遍歷,輸出結果；
（3）計算二叉排序樹T的平均查找長度，輸出結果；
（4）輸入元素x，查找二叉排序樹T，如果存在含x的結點，則刪除該結點，并作中序遍歷(執行操作2)；否則輸出信息“無結點x”；
（5）判斷二叉排序樹T是否為平衡二叉樹，輸出信息“OK!”/“NO!”;
*（6）再用數列L，生成平衡二叉排序樹BT：當插入新元素后，發現當前二叉排序樹BT不是平衡二叉排序樹，則立即將它轉換成新的平衡二叉排序樹BT；
*（7）計算平衡二叉排序樹BT的平均查找長度，輸出結果。
2、用順序表（一維數組）作存儲結構
（1）以回車（‘\n’）為輸入結束標志，輸入數列L，生成二叉排序樹T；
（2）對二叉排序樹T作中序遍歷,輸出結果；
（3）計算二叉排序樹T的平均查找長度，輸出結果；
（4）輸入元素x，查找二叉排序樹T，如果存在含x的結點，則刪除該結點，并作中序遍歷(執行操作2)；否則輸出信息“無結點x”；
（5）判斷二叉排序樹T是否為平衡二叉樹，輸出信息“OK!”/“NO!”。
二、程序中所采用的數據結構及存儲結構的說明
程序中的數據采用“樹形結構”作為其數據結構。具體的，我采用的是“二叉排序樹”。
二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：（1）若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；（2）若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；（3）它的左右子樹也分別為二叉排序樹。
程序中分別采用了“二插鏈表”和“一維數組”作為其存儲結構。
二插鏈表存儲結構中二插樹的結點由一個數據元素和分別指向其左、右子樹的兩個分支構成。如：我的程序中采用的結構是：
typedefstructTnode{
intdata;/*數據元素*/
structTnode*lchild,*rchild；/*左右指針*/
}*node,BSTnode;
一維數組順序表存儲結構是用一組地址連續的存儲單元依次自上而下、自左而右存儲完全二插樹上的結點元素，即將完全二叉樹上編號為i的結點元素存儲在如上定義的一維數組中下標為i-1的分量中。利用順序表作為存儲結構：
typedefstruct{
int*data;/*一維數組基址*/
intlenth;/*一維數組的長度*/
}BST;
一維數組存儲結構中結點i的父母親為|_i/2_|,左孩子為2i，右孩子為2i+1.
三、算法的設計思想
a)二插鏈表作存儲結構：
建立二插排序樹采用邊查找邊插入的方式。查找函數采用遞歸的方式進行查找。如果查找成功則不應再插入原樹，否則返回當前結點的上一個結點。然后利用插入函數將該元素插入原樹。
對二叉樹進行中序遍歷采用遞歸函數的方式。在根結點不為空的情況下，先訪問左子樹，再訪問根結點，最后訪問右子樹。
計算二插排序樹的平均查找長度時，仍采用類似中序遍歷的遞歸方式，用s記錄總查找長度，j記錄每個結點的查找長度，s置初值為0，采用累加的方式最終得到總查找長度s。平均查找長度就等于s/i(i為樹中結點的總個數)。
刪除結點函數，采用邊查找邊刪除的方式。如果沒有查找到，則不對樹做任何的修改；如果查找到結點，則分四種情況分別進行討論：1、該結點左右子樹均為空；2、該結點僅左子樹為空；3、該結點僅右子樹為空；4、該結點左右子樹均不為空。
判斷二插排序樹是否為平衡二叉樹的函數，也是采用遞歸函數的方式，分別判定以樹中每個結點為根結點的子樹是否為平衡二叉樹。只要有一個子樹不為平衡二叉樹，則該樹便不是平衡二叉樹。
b)一維數組作存儲結構：
建立二插排序樹，首先用一個一維數組記錄下讀入的數據，然后再用邊查找邊插入的方式將數據一一對應放在完全二叉樹相應的位置，為空的樹結點用“0”補齊。
中序遍歷二叉樹也采用遞歸函數的方式，先訪問左子樹2i,然后訪問根結點i,最后訪問右子樹2i+1.先向左走到底再層層返回，直至所有的結點都被訪問完畢。
計算二插排序樹的平均查找長度時，采用類似中序遍歷的遞歸方式，用s記錄總查找長度，j記錄每個結點的查找長度，s置初值為0，采用累加的方式最終得到總查找長度s。平均查找長度就等于s/i(i為樹中結點的總個數)。
刪除二插排序樹中某個結點，采用邊查找邊插入的方式，類似重新建立一個一維數組作為存儲新樹的空間。將原數組中的數據一個一個的插入樹中，若遇到需要刪除的結點則不執行插入操作。
判斷二插排序樹是否為平衡二叉樹的函數，也是采用遞歸函數的方式，分別判定以樹中每個結點為根結點的子樹是否為平衡二叉樹。只要有一個子樹不為平衡二叉樹，則該樹便不是平衡二叉樹。
四、平衡二叉樹與未平衡化的二叉樹查找效率比較
(1)對于未平衡化的二叉樹：
當先后插入的關鍵字有序時，構成的二插排序樹蛻變為單支樹。樹的深度為n,其平均查找長度為（n+1）/2.這是最差的情況。這種情況下比較關鍵字的最大次數為n次。
(2)最好的情況是：
建成的樹是一棵平衡二叉樹。在這種情況下，二插排序樹的平均查找長度和log2(n)成正比。比較關鍵字的最大次數為：0.5logψ（5）＋logψ(n+1)-2次（其中ψ＝（1＋根號5）/2）。
(3)那么，平均情況下分析：
假設在含有n(n>=1)個關鍵字的序列中，i個關鍵字小于第一個關鍵字，n-i-1個關鍵字大于第一個關鍵字，則由此構造而得的二插排序樹在n個記錄的查找概率相等的情況下，其平均查找長度為
：P(n,i)=[1+i*(P(i)+1)+(n-i-1)(P(n-i-1)+1)]/n
其中P(i)為含有i個結點的二插排序樹的平均查找長度，則P(i)+1為查找左子樹中每個關鍵字時所用比較次數的平均值，P（n-i-1）+1為查找右子樹中每個關鍵字時所用比較次數的平均值。又假設表中n個關鍵字的排列是“隨機”的，即任一個關鍵字在序列中將是第1個，或第2個，…，或第n個的概率相同，則可對上式從i等于0至n-1取平均值。最終會推導出：
當n>=2時，P（n）<=2（1＋1/n）ln(n)
由此可見，在隨機的情況下，二插排序樹的平均查找長度和log（n）是等數量級的。
五、時間復雜度的分析
說明：對時間復雜度的分析，均指在最壞情況下的時間復雜度。
二插鏈表存儲結構中：
（1）查找函數最壞的情況是要找的點正好是二叉樹的最深的葉子結點，此時時間復雜度＝O（n）。
（2）插入函數最壞的情況是要插入的點正是二叉樹的最深的那一支的葉子結點，此時時間復雜度＝
O（n）。
（3）中序遍歷函數，求平均查找長度的函數，刪除函數以及判斷二插排序樹是否為平衡二叉樹的函數，其時間復雜度均與以上情況類似，等于O（n）。
一維數組順序表存儲結構中：
（1）插入函數最壞的情況是要插入的點正是二叉樹的最深的那一支的葉子結點，此時時間復雜度＝O（n）。
（2）創建函數最壞的情況就是調用插入函數時插入函數遇到最壞的情況。因此，創建函數的時間復雜度也等于O（n）。
（3）中序遍歷函數，求平均查找長度的函數，查找函數，以及判斷二插排序樹是否為平衡二叉樹的函數，其時間復雜度均與以上情況類似，等于O（n）。
（4）刪除函數不采用遞歸手法，而是采用重新建立一顆不含要刪結點的二插排序樹。其時間復雜度＝O（n）。
六、心得和總結
這次暑假的課程設計作業我選擇做數據結構是出于我對用高級語言編程的極大興趣。通過這次實驗我也著實又感受了一次編程的樂趣，從中也學到了不少知識。
雖然都說“程序＝數據結構＋算法”，但我在學習運用數據結構編程之前，并沒能深刻體會到這一點，直到這次課設實踐。
我感受最深的一點是：以前用C編程，只是注重如何編寫函數能夠完成所需要的功能，似乎沒有明確的戰術，只是憑單純的意識和簡單的語句來堆砌出一段程序。感覺有點像張飛打仗，有勇無謀，只要能完成任務就行。但現在編程感覺完全不同了。在編寫一個程序之前，自己能夠綜合考慮各種因素，首先選取自己需要的數據結構，是樹還是圖或是別的什么？然后選定一種或幾種存儲結構來具體的決定后面的函數的主要風格。最后在編寫每一個函數之前，可以仔細斟酌比對，挑選出最適合當前狀況的算法。這樣，即使在完整的程序還沒有寫出來之前，自己心中已經有了明確的原圖了。這樣無形中就提高了自己編寫的程序的質量。
另外，我還體會到深刻理解數據結構的重要性。只有真正理解這樣定義數據類型的好處，才能用好這樣一種數據結構。了解典型數據結構的性質是非常有用的，它往往是編寫程序的關鍵。
我以前對遞歸算法一直很害怕，總是看不明白究竟這遞歸是怎么進行的。在這次實驗中我終于克服了這一障礙，一次次單步執行書中遞歸函數的例子，并一遍遍在心中自己默默的走，終于弄明白了，真的是功夫不負有心人啊！同時我還根據自己的理解寫出了類似的遞歸函數實現了新的功能，真是受益良多啊！
在這次實驗中，我對參數的調用也進行了很多種嘗試，已經能夠相對準確的選擇合適的參數形式來實現函數之間的數據傳輸交互了。
這次實驗中我也出現過一些比較嚴重的錯誤。在用一維數組順序表結構編寫程序時我錯誤的運用靜態鏈表來實現函數功能。這是我對基本概念理解的模糊不清造成的。我原以為只要采用一維數組作為存儲結構它就一定也是順序表結構，而實質上這根本是兩個不相干的概念。后來在同學的指點下我意識到自己的錯誤。不過收獲也很不少。至少我又練習了運用靜態鏈表來實現同樣的功能，同時我也發現兩者在很多函數上是互通的，只需稍作修改即可移植。
總之，我會繼續我的興趣編寫程序的，相信在越來越多的嘗試之后，自己會不斷進步不斷提高的。
