《數(shù)據(jù)結(jié)構(gòu)》課程實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告4 實(shí)驗(yàn)一基于二叉鏈表的二叉樹的實(shí)現(xiàn)4.1 問題描述基于二叉鏈表和隊(duì)列及其堆棧存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)二叉鏈表的二叉樹的對(duì)數(shù)據(jù)進(jìn)行各種必要的操作。4.2 系統(tǒng)設(shè)計(jì)1.2.1提供20個(gè)功能，分別是：1.2.2二叉鏈表的結(jié)構(gòu)試一堆棧和隊(duì)列的形式進(jìn)行儲(chǔ)存的分別是：1.2.3在程序中所定義的數(shù)據(jù)結(jié)構(gòu)有： 2.3 系統(tǒng)實(shí)現(xiàn)1.3.1 inittree功能初始二叉鏈表，傳入的是頭結(jié)點(diǎn)地址。申請(qǐng)一個(gè)存儲(chǔ)空間，并用頭結(jié)點(diǎn)中的首結(jié)點(diǎn)指針指向該空間首地址，相應(yīng)的時(shí)間復(fù)雜度為1。具體實(shí)現(xiàn)如下： 1.3.2 destroytree功能銷毀頭結(jié)點(diǎn)中首結(jié)點(diǎn)址針指向的線性存儲(chǔ)空間，傳入的是頭結(jié)點(diǎn)地址。具體實(shí)現(xiàn)如下

2、： 1.3.3 createbitree功能與destroybitree類似但是又有不同，clearbitree并不銷毀物理空間，而是修改邏輯關(guān)系值： 1.3.4 clearbitree功能與destroybitree類似但是又有不同，clearbitree并不銷毀物理空間，而是修改邏輯關(guān)系值 1.3.5 bitreeempty功能判空功能，判斷表是否為空表。時(shí)間復(fù)雜度為1，因?yàn)橹恍枧袛嘁淮尉涂梢灾朗欠駷榭?。?shí)現(xiàn)如下：1.3.6 bitreedepth功能求二叉鏈表深度的功能，由于創(chuàng)建過程中已經(jīng)把表長信息包含在頭結(jié)點(diǎn)中，所以直接調(diào)用并顯示即可 1.3.7 root(bitree t)功能 獲

3、取二叉鏈表的根節(jié)點(diǎn)的元素，通過遍歷二叉鏈表中的元素，來逐個(gè)判斷，時(shí)間復(fù)雜度為（n）。1.3.8 value(bitree t,telemtype e)功能求指定元素的前一個(gè)元素的內(nèi)容，傳入頭結(jié)點(diǎn)值、包含指定元素信息的一個(gè)臨時(shí)表結(jié)點(diǎn)值、存儲(chǔ)前一個(gè)元素的表結(jié)點(diǎn)地址。主要思路是遞歸算法。時(shí)間復(fù)雜度為o(n)。具體實(shí)現(xiàn)如下： 1.3.9 assign功能求指定元素的后一個(gè)元素的內(nèi)容，傳入頭結(jié)點(diǎn)值、包含指定元素信息的一個(gè)臨時(shí)表結(jié)點(diǎn)值、存儲(chǔ)前一個(gè)元素的表結(jié)點(diǎn)地址。找到后，把新的數(shù)據(jù)值賦給所找到的節(jié)點(diǎn)。時(shí)間復(fù)雜度為o(n)。具體實(shí)現(xiàn)如下： 1.3.10 parent功能找雙親節(jié)點(diǎn)，找到后輸出1.3.11 leftchild功能 查找左孩子，利用遞歸的算法，與遍歷的時(shí)間復(fù)雜度為相同o(n) 1.3.12rightchild功能查找右孩子，利用遞歸的算法，與遍歷的時(shí)間復(fù)雜度為相同o(n)