廈門理工學(xué)院數(shù)據(jù)結(jié)構(gòu)試驗(yàn)6

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)號(hào)姓名ZRZ專業(yè)、班18計(jì)卓1班實(shí)驗(yàn)地點(diǎn)指導(dǎo)教師林仙麗實(shí)驗(yàn)時(shí)間2020.5.12實(shí)驗(yàn)序號(hào)：6實(shí)驗(yàn)項(xiàng)LI名稱：樹(shù)和二義樹(shù)的操作實(shí)驗(yàn)?zāi)康募耙?、進(jìn)一步掌握指針變量、動(dòng)態(tài)變量的含義。2、掌握二叉樹(shù)的結(jié)構(gòu)特征，以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圉。3、掌握用指針類型描述、訪問(wèn)和處理二義樹(shù)的運(yùn)算。4、掌握用二叉樹(shù)前序、中序、后序、層次遍歷的方法。二、實(shí)驗(yàn)設(shè)備（環(huán)境）及要求微型計(jì)算機(jī)；windows操作系統(tǒng)：Microsoft Visual Studio 6.0 集成開(kāi)發(fā)環(huán)境。三、實(shí)驗(yàn)內(nèi)容與步驟1 根據(jù)P129的方法，將a*b-（c+d*e/f）+g）轉(zhuǎn)化為表達(dá)式二叉樹(shù)（繪圖），并寫出表達(dá)

2、式 二叉樹(shù)的前序、中序和后序遍歷順序。先丿丫: -*ab+c*d/efg中序：a*b-c+d*e/f+g后序:ab*cdef/*+g+-2.鏈?zhǔn)奖肀硎竞蛯?shí)現(xiàn)二義樹(shù)如下：#include include #define max 50typedef struct liuyuint data;struct liuyu *lchild, *rchild;/test;liuyu *root, *p, *q Lmaxj;int sum二0;int m=sizeof(test);void insert_data(int x)/*生成二叉排序樹(shù)*/liuyu *p, *q, *s;s=(test*)mallo

3、c(m);s-data=x;s-lchild=NULL;s-rchild=NULL;if(!root)root=s;p=root;while (p)/*如何接入二叉排序樹(shù)的適當(dāng)位置*/q=p;if (p-data=x)printf(，?data already exist! n);return;else if(xdata)p=p-lchild;elsep=p-rchild;if(xdata)q-lchild=s;elseq-rchild=s;void mainO/*先生成二叉排序樹(shù)*/int i, x;i=l ；:root二NULL;/*千萬(wàn)別忘了賦初值給root!*/doprintf (pl

4、ease input data%d： i);i+;scanf (Wd, &x);/*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結(jié)朿*/if (x=-9999) printf C?nNow output data value:n?，);elseinsert_data(x);/*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!二-9999);改寫以上程序，并實(shí)現(xiàn)功能如下：(任選兩題實(shí)現(xiàn))1) .編寫函數(shù)實(shí)現(xiàn)前序、中序和后序遍歷。2) .分別編寫函數(shù)實(shí)現(xiàn)訃算所有結(jié)點(diǎn)及葉子結(jié)點(diǎn)的個(gè)數(shù)。3) .編寫函數(shù)實(shí)現(xiàn)按值查找功能。4) .編寫函數(shù)實(shí)現(xiàn)求二義樹(shù)的高度。圖2：二叉樹(shù)代碼效果圖實(shí)驗(yàn)說(shuō)明： 編寫函數(shù)實(shí)現(xiàn)前序、中序和后

5、序遍歷：這一部分的思路主要就是進(jìn)行一個(gè) 遞歸的操作，我們從根結(jié)點(diǎn)開(kāi)始向下遍歷，根據(jù)前療:、中序、后序的不同特點(diǎn)選 擇性的對(duì)左右子結(jié)點(diǎn)和父結(jié)點(diǎn)的值進(jìn)行輸出，就可以達(dá)到三種不同的遍歷效果。例如先序遍歷，我們就可以先打印當(dāng)前根結(jié)點(diǎn)的值，然后再對(duì)當(dāng)前根結(jié)點(diǎn)的 左子結(jié)點(diǎn)進(jìn)行遞歸，然后再對(duì)右結(jié)點(diǎn)進(jìn)行遞歸，這樣就能實(shí)現(xiàn)打印順序?yàn)楦Y(jié)點(diǎn), 然后左結(jié)點(diǎn)，最后右結(jié)點(diǎn)的操作，另外的中序和后序只需要將三條語(yǔ)句的順序進(jìn) 行交換即可。void DLR(Tree* root):if (root != NULL):；printf(%droot-data);!DLR(root-lchild);:DLR(root-rchild)

6、;:圖3：先序遍歷代碼 分別編寫函數(shù)實(shí)現(xiàn)計(jì)算所有結(jié)點(diǎn)及葉子結(jié)點(diǎn)的個(gè)數(shù)：其實(shí)這一部分與上面 的二義樹(shù)遍歷很相似，遍歷二義樹(shù)的過(guò)程我們完全可以想象為就是對(duì)二義樹(shù)進(jìn)行 一個(gè)結(jié)點(diǎn)的計(jì)數(shù)，而葉子結(jié)點(diǎn)實(shí)際上只需要加入一個(gè)特殊判斷即可，即左右結(jié)點(diǎn) 都為空就可以記為葉子結(jié)點(diǎn)。同樣的，我們可以使用遞歸來(lái)實(shí)現(xiàn)這個(gè)功能是最好 的。Node_count(root-lchild); Node_count(root-rchild); node+;return;圖4：結(jié)點(diǎn)計(jì)算核心代碼 編寫函數(shù)實(shí)現(xiàn)按值查找功能：同樣，查找值的功能只需要對(duì)二義樹(shù)遍歷的 部分就行修改就行，一旦找到對(duì)應(yīng)的值就返回即可。 編寫函數(shù)實(shí)現(xiàn)求二義樹(shù)的高度

7、：這一部分我們可以釆用dfs的思想，只要 從根結(jié)點(diǎn)開(kāi)始不斷的對(duì)左右向下遍歷，最后比較左右的深度大小，取最大值即可if (!root)return 0;return max(get_height(root-lchild) get_height(rootrchild) + 1;圖5：深度il算核心代碼3、用Huffman編碼方法，實(shí)現(xiàn)對(duì)通信字符的編碼和解碼。Ol MKrosoft V6ua! StucloX第1次: 第2次: 第3次: 第4次: 弟5次:6次: 第7次:m）/r. “點(diǎn)X1權(quán)值為1取出的右“點(diǎn)也丈出的WMcl權(quán)值為1如出的右“點(diǎn)也2出的左力點(diǎn)門權(quán)備為1 燦的左廿點(diǎn)x車侑為2 幅I的

8、左卄點(diǎn)權(quán)值為2R出的左1點(diǎn)“權(quán)i為31它創(chuàng)的父 弋值為：2 1它tn的父竹點(diǎn)取值為:2 2它們的父仃點(diǎn)權(quán)值為:3 2它們的父仃點(diǎn)權(quán)値為:4:4它們的父竹點(diǎn)權(quán)備為:7為：岀的右廿點(diǎn)x2 乂值為：岀的右廿點(diǎn)x2權(quán)值為：出的右也點(diǎn)x2灼i為:出的右W點(diǎn)x2 5（他為: 一ll出的右廿點(diǎn)x2權(quán)”i為： . IUII的左廿點(diǎn)玖權(quán)值為5 敢出的右也加2板値為:7它門的父W/AKffi為：212(5(2,3), 7(3(1,2(h 1, 4(2(1 1). 2)i的編碼為:碼加 u的軸碼為】 合的編碼為 J的編碼為9 f JK：00 0110010101011 1100 1101111請(qǐng)購(gòu)入耍解碼的1100

9、1010101101111100110111100011100 1010 1011 01 111 100 1101 111 00 01 Just do it圖6：輸入字符串原碼來(lái)實(shí)現(xiàn)HuffmanTreeSI Microsoft Visual Studio if試占諂綸入些購(gòu)入鄉(xiāng)一. 訥軻入第1個(gè)了符H 諂輸入樂(lè)1個(gè)7捋的權(quán)0. 19 諂輪入第2個(gè)7符1 諂輸入第2個(gè)了符的權(quán)10.21 諂軻入第3個(gè)7符o 諂輸入第3個(gè)7符的權(quán)0.0】 諂輪入第4個(gè)字符 諂輸入第4個(gè)了符的權(quán)（0.01 諂輸入曲5個(gè)了符.諂輸入第5個(gè)7符的權(quán)仇0. 03 請(qǐng)輸入第6個(gè)字符!諂輸入第6個(gè)了符的權(quán)值0. 06 說(shuō)軻入

10、曲7個(gè)了符請(qǐng)輸入笫7個(gè)字符的ttfrto. 16BI輸入弟8個(gè)r;:riff輸入8個(gè)符的權(quán)值016 謚輸入心9個(gè)丫符d諸輸入第9個(gè)丫符的權(quán)值007諸輸入用10個(gè)丫符諸輸入用10個(gè)？ 第1次:.拯的權(quán)frtO. 1取出的A：廿點(diǎn)權(quán)值為001 取;I；的/irUxlKfrt為0 02 阪出的左力點(diǎn)*1權(quán)備為0.05 取出的左節(jié)點(diǎn)xltttfi M 07 JR出的左節(jié)點(diǎn)xlttffiM 11 取岀的左北點(diǎn)xl(fi為016 取出的烷竹點(diǎn)“權(quán)值為0.19 取出的左1*點(diǎn)xlttffi為027一販出的左*Jxl權(quán)值為0.4 I1(0.40.19.0. 21),0.6(0. 27(0.11(0.05(0.

11、02(0.01,0.01),0.03),0.06)0.0 33(0.16.0.17(0.07.0.1)H仙編構(gòu)為I 】的編碼為| o的編碼為】 的編碼Z .的編碼為 !的編碼為、 x的編碼為I 啲編碼為 d的編碼為的編碼為】諂輸入要解碼的字符申 I 001000010101100000100111111101000001010111101000100 100001 01 01 100000 1001 1111 110 100000 101 01 1110 10001 Hello! world.射次:TkOSV00 01 100000 100001 10001 1001101110 1110 1

12、111取出的右“點(diǎn)*2儀值為:取:加2權(quán)值為: 取出的右竹點(diǎn)*2找備為： 取出的右m2權(quán)值為： 取出的右為: 取出的右U點(diǎn)找值為: 恥II的右曲點(diǎn)x2ttffi為： ?。簽椋??。簗步點(diǎn)x2權(quán)值為：06它劄的父廿點(diǎn)權(quán)価為二10.01它們的父點(diǎn)權(quán)値為:0.02 0. 03它們的父“點(diǎn)權(quán)值為:0.05 0. 06佗幻的父廿點(diǎn)權(quán)值為:0.110.1它們的父點(diǎn)權(quán)仮為:0.170.16它幻的父卄點(diǎn)權(quán)值為:0.270.17它們的父“點(diǎn)權(quán)值為:0.33 0.21它Y的父“點(diǎn)嘆值為：0.40. 33它Y】的父廿點(diǎn)乂值為：0.6隸聯(lián)跚牆谿煽鏟倆辟怦弊躊爐點(diǎn)弩.聯(lián)制偶踹亦”.圖7：輸入權(quán)值來(lái)實(shí)現(xiàn)HuffmanTr

13、ee1 DB Mkrsoft Visual Studio fliXUWJfeS一X諂輸人113sada dsd r取III的右紡點(diǎn)工2權(quán)值為】取岀的右節(jié)點(diǎn)*2權(quán)值為,2它們的父節(jié)點(diǎn)權(quán)值為，3 取出的右節(jié)點(diǎn)工2權(quán)值知2它們的父節(jié)點(diǎn)權(quán)值為4 取出的右節(jié)點(diǎn)工2權(quán)值為I 2它們的父廿點(diǎn)權(quán)血為* 4 取川的右肖點(diǎn)冷3它們的父“點(diǎn)權(quán)値為:6 取HI的右百點(diǎn)x2HMi 4它們的父節(jié)點(diǎn)權(quán)値為x 8 取出的右節(jié)點(diǎn)*2權(quán)值為I 8它們的父節(jié)點(diǎn)權(quán)值為* 14第1次:取山的好節(jié)點(diǎn)P權(quán)値為】 第2次:取出的左節(jié)點(diǎn)燈權(quán)垃為1 第3次:取出的左節(jié)Axlttffl為2 第4次:取出的亞節(jié)點(diǎn)xlttffl為2 第5次:取川的左

14、節(jié)點(diǎn)xlttffl為3 第6次:取川的左節(jié)點(diǎn)xlttfft為4 新次:取出的左節(jié)點(diǎn)工】權(quán)值為614(6(3(1,2, 3, 8(4(2,2，4(2,2(1,1”劇齡黙聽(tīng)能2x的編碼為：0009的編碼為* 001 d的編碼為】01 1的編碼加】00 a的編碼為：101的編碼為X 1103的編碼為:1110 g的編碼為:1111 - 110 1110 1111 01 000 3gdr諂輸入耍解碼的7符小I 1101110111101000圖&可以同時(shí)輸入數(shù)字、字符、空格、符號(hào)實(shí)驗(yàn)說(shuō)明： ：首先，要想構(gòu)造出HuffmanTree,我們需要對(duì)輸入的字符權(quán)值進(jìn)行處理, 這里山于主要的輸入方式為輸入字符串

15、，通過(guò)相應(yīng)的函數(shù)來(lái)計(jì)算每個(gè)字符的占比 權(quán)值或者是直接輸入每個(gè)字符的權(quán)值兩種方式，相應(yīng)的處理方式有略微的不同， 但是大體是一致的,我定義了一個(gè)double類型的weight數(shù)組來(lái)存放字符的權(quán)值, 然后再定義了一個(gè)code數(shù)組來(lái)存放侮個(gè)不重復(fù)的字符，這樣就能解決當(dāng)用戶輸 入字符串時(shí)，就算有大量重復(fù)字符也能訃算出正確的權(quán)值，得到完整的權(quán)值后， 我們就可以開(kāi)始構(gòu)建HuffmanTreeo 首先我們根據(jù)code數(shù)組的大小來(lái)建立相應(yīng)數(shù)量的HuffmanTree結(jié)點(diǎn)，同 時(shí)也要對(duì)這些結(jié)點(diǎn)進(jìn)行初始化，然后我們建立一個(gè)HuffmanTree結(jié)點(diǎn)類型的優(yōu)先 隊(duì)列6根據(jù)結(jié)點(diǎn)的權(quán)值從小到大進(jìn)行內(nèi)部排序，這樣就為我們下

16、一步正式構(gòu)建 HuffmanTree做好準(zhǔn)備，我們每次將q中最前面的兩個(gè)元素拿出進(jìn)行合并，這樣 實(shí)現(xiàn)了每次合并結(jié)點(diǎn)都是權(quán)值最小的結(jié)點(diǎn)進(jìn)行合并，然后我們將兩個(gè)結(jié)點(diǎn)合并后 的結(jié)點(diǎn)再次放入q隊(duì)列中，這樣循環(huán)直到q中只剩一下一個(gè)元素根節(jié)點(diǎn)，這樣一 棵HuffmanTree就構(gòu)造完畢了。 HuffmanTree構(gòu)造完畢后，我們可以利用遞歸函數(shù)來(lái)對(duì)HuffmanTree進(jìn)行 遍歷，這樣做的目的是可以將每個(gè)字符的編碼進(jìn)行打印，同時(shí)我們也可以模擬 HuffmanTree樹(shù)將每個(gè)結(jié)點(diǎn)的權(quán)值打印出來(lái)，這樣可以更直觀的看到 HuffmanTree內(nèi)部的構(gòu)建T青況。 解碼的過(guò)程只需要根據(jù)輸入的密文對(duì)HuffmanTr

17、ee樹(shù)進(jìn)行遍歷，從根結(jié)點(diǎn) 和密文的第一位，如果當(dāng)前一位是則當(dāng)前結(jié)點(diǎn)山根結(jié)點(diǎn)變成根結(jié)點(diǎn)的左節(jié) 點(diǎn)，如果當(dāng)前一位是T則當(dāng)前結(jié)點(diǎn)山根結(jié)點(diǎn)變成根結(jié)點(diǎn)的右節(jié)點(diǎn)，就這樣直 到根結(jié)點(diǎn)沒(méi)有左右結(jié)點(diǎn)時(shí)，我們?cè)賹⑦@個(gè)節(jié)點(diǎn)中保存的字符打印出來(lái)，就實(shí)現(xiàn)了 一個(gè)字符的解碼，要繼續(xù)解碼的話只需要X前結(jié)點(diǎn)更新回最原本的根結(jié)點(diǎn)即可。四、分析與討論在這一次的實(shí)驗(yàn)中，我學(xué)到了許多關(guān)于二義樹(shù)的知識(shí)，先是通過(guò)表達(dá)二叉 樹(shù)和二義樹(shù)的一些基本操作了解并明口了二義樹(shù)的原理，也體會(huì)到了二義樹(shù)中遞 歸思想的美妙，然后就是通過(guò)HuffmanTree樹(shù)對(duì)樹(shù)形結(jié)構(gòu)有了更深的體會(huì)，也理 解了 HuffmanTree樹(shù)編碼和解碼的原理，讓我收獲了很多。

18、五、教師評(píng)語(yǔ)成績(jī)簽名:日期:附源程序淸單:2.include include typedef struct Treeint data;struct Tree* lchild, * rchild;Node;Tree* root,字 p, * q;int leaf = 0;int node = 0;int m = sizeof (Node);bool findflag = false;int height = 0;int max(int a, int b)if (a b)return a;elsereturn b;void insert_data(int/*生成二叉排序樹(shù)*/Tree * s;s

19、= (Node*)malloc(m);p = (Node*)malloc(m):q = (Node*)malloc(m):sdata = x;s-lchild = NULL;s-rchild = NULL;if (!root)root = s;return;p = root;while (p)/*如何接入二叉排序樹(shù)的適當(dāng)位豆*/q = p;if (p-data = x)printf Cdata already exist! n):return;else if (x data)p = p-lchild;elsep = p*rchild;sdata = x;if (x data)q-lchild

20、= s;elseqrchild = s;void DLR(Tree* root)if (root != NULL)printf(%d 、 rootdata):DLR(rootlchiId);DLR (roofrchi Id);void LDR(Tree* root)if (root != NULL)LDR(rootlchiId);printf(%d 、 rootdata):LDR(rootrchiId);void LRD(Tree* root)if (root != NULL)LRD(root-lchiId);LRD(rootrchiId); printf(%d 、 rootdata):voi

21、d Xode_count(Tree* root)if (!root)return;if (!rootlchild & !root*rchild) node+;return;elseNodecount(rootlchild);Node_count(rootrchild); node+;return;void LeafNode_count(Tree* root)if (!root)return;if (!root-lchild & !rootrchild) leaf+;return;elseLeafNode_count(rootlchild);LeafNode_count(rootrchild);

22、return;int findvalue(int value,Tree* root)if (root != NULL)if (roofdata = value)findflag = true; return 0;elsefind_va1ue(va1ue, rootlchild); find_value(value, root-rchild);intget_height(Tree* root)if (!root)return 0;returnmax(get_height(root-lchild), get_height(rootrchiId) + 1;intmainO/*先生成二叉排序樹(shù)*/in

23、t i,i = 1；rootroot(Node*)malloc(m);NULL;/*千萬(wàn)別忘了賦初值給wot!*/printf (please input data%d: i):i卄;scanf_s(%d &x);if (x = -9999) printf CnNow output data value：n): /*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結(jié)束*/elseinsert_data(X) ;/*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/ while (x != -9999);printfC先序遍歷為：“)；DLR(root);printf Cn r);printfC中序遍歷為:)；LDR(root);

24、printf Cn *);printfC后序遍歷為:LRD(root);printf Cn *);Nodecount(root);LeafNodecount(root);printfC這個(gè)二叉樹(shù)中的結(jié)點(diǎn)為：%d葉子結(jié)點(diǎn)為:%dn, node, leaf); int value;printf(諳輸入要查找的值：)；scanf_s C%d, &value);find_value(value, root);if (!findflag)printf (，z%d值在二叉樹(shù)中找不到rT, value);elseprintf (%d值在二叉樹(shù)中能找到n, value);findflag = false;pr

25、intf(請(qǐng)輸入要查找的值：)；scanf_s C%d, &value);find_value(value, root);if (!findflag)printf (%d值在二叉樹(shù)中找不到n value);elseprintf C%d值在二叉樹(shù)中能找到n, value);findflag = false;printfC 二叉樹(shù)髙度為：get_height (root):3.Sinclude i?include#include#includeJJinclude#includeSineludeSincludeSineludeusing namespace std;vector code;doubl

26、e weight256:int n;typedef struct HuffTreestring code:char symbol;double weight:HuffTree* lchild;HuffTree* rchild; Node, *odeptr;struct cmpbool operator()(Nodeptr & a, Nodeptr & b)return a-weight bweight;priority_queueNodeptrr vector, cmpq;void codework()cout ”歡迎使用霍夫曼樹(shù)” endl;cout 請(qǐng)選抒輸入字符串原碼或者輸入權(quán)值：” e

27、ndl;cout1 輸入原碼2輸入權(quán)值 endl;int x;cin x;char ch=getchar();systemCcls);switch (x)case 1:string s:cout 請(qǐng)輸入原碼：；getline(cin, s):for (int i = 0; i num;for (int i = 0; i y;if (count (code begin0, codeend(), x) = 0) code push_back(x);weightx= y;break;void PrintHuffmanTree(Nodeptr root)cout root-weight:if (roo

28、t-lchild != NULL | root-rchild != NULL)coutPrintHuffmanTree(rootlchild);cout,;PrintHuffmanTree(rootrchild);cout;Nodeptr CreatHuffmanTree 0codework ();n = code sizeO ;for (int i = 0; i symbol = code .i;CurNodeweight = weight.code .iCurNode-lchild = NULL;CurNode-rchild = NULL;q push (CurNode);for (int

29、 i = 1; i weight 取 出的右節(jié)點(diǎn)x2權(quán)值為： (double)x2-weight 它們的父節(jié)點(diǎn)權(quán)值為：weight + x2weight) endl;/zrz 2020.5. 20Nodeptr NewNode = new Node;NewNode*symbol = 0;NewNode*weight = xlweight + x2weight;NewNodelchild = xl;NewNode*rchild = x2;q push(NewNode);PrintHuffmanTree (q topO);cout endl:return q topO ;void Coding(Nodeptr