哈夫曼樹實(shí)驗(yàn)報(bào)告2011.4.22實(shí)驗(yàn)題目：Huffman編碼和譯碼。實(shí)驗(yàn)?zāi)康模?、練習(xí)樹和哈夫曼樹的有關(guān)操作，和各個(gè)算法程序。2、理解哈夫曼樹的編碼和譯碼實(shí)驗(yàn)內(nèi)容:抽象數(shù)據(jù)類型：ADTHuffmantree{數(shù)據(jù)對(duì)象:D={帶有各自實(shí)數(shù)W(D)的數(shù)據(jù)元素}數(shù)據(jù)關(guān)系：(1)D=NULL則huffmantree不存在//判斷huffman樹是否存在(2)D≠NULLR={H}.H為如下二元關(guān)系：//如果存在，假設(shè)R為其元素名稱，H為里邊所有元素①D中存在唯一根數(shù)據(jù)元素root,這個(gè)元素?zé)o前驅(qū)。//如果只有一個(gè)元素，則為根元素②D-{root}≠NULL.則存在D-{root}={D1，Dr}.且D1∧Dr=NULL//如果除了根元素還有別的元素，那么會(huì)有D1和Dr兩部分，并且兩者的交集為空，也就是兩者是獨(dú)立的。③若D1≠NULL，則D1中存在唯一元素xr,<root,xr>∈H//如果D1部位空集，則會(huì)有一個(gè)元素xr，且存在Dr上關(guān)系Hr∈H,H={<root,x1>,<root,xr>,H1,Hr};④符合①②③的R的組合中，存在一個(gè)組合R’使D中所有結(jié)點(diǎn)到root長(zhǎng)與其權(quán)值W(Di)相乘的和最小，此時(shí)的<D/R>集合稱為huffmantree.基本操作：voidselect(HTNodeHT[],intm,int*s1,int*s2)//比較得到權(quán)最小的兩棵樹。用指針指向所在位置。*voidprint1(char*HC[])//將哈弗曼編碼逐個(gè)打印出來(lái)voidprint2(HTNodeHT[])//將哈夫曼樹前后的結(jié)構(gòu)打印出來(lái)voidCreatHuffmanTree(HTNodeHT[],lettervaluew[])//建立哈夫曼樹voidHuffmanTreeCoding(HTNodeHT[],char*HC[])//從樹根出發(fā)，對(duì)哈夫曼樹做一次先序遍歷，在遍歷過(guò)程中利用一個(gè)字符//的順序棧S記下遍歷路程，向左轉(zhuǎn)時(shí)0入棧，向右轉(zhuǎn)時(shí)1入棧。當(dāng)遍歷到//一個(gè)葉子節(jié)點(diǎn)時(shí)，棧s自棧底至棧頂記錄著樹根到該葉子結(jié)點(diǎn)的路徑上的//0,1序列，即該葉子結(jié)點(diǎn)的哈弗曼編碼。voiddecode(HTNodeHT[],lettervaluew[])//把編碼譯成哈夫曼碼}ADTHuffmantree二、算法描述：建立哈夫曼樹：對(duì)于給定的n個(gè)權(quán)值{W1，W2，…，Wn}，構(gòu)成n棵二叉樹的集合F={T1，T2，…，Tn}，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為Wi的根結(jié)點(diǎn)，其左右子樹均空。在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)的權(quán)值之和。在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入到F中。重復(fù)(2)和(3)，直到F只含一棵樹為止。這棵樹便是帶權(quán)路徑長(zhǎng)度WPL最小的赫夫曼樹。

具體操作：（1）N個(gè)葉子節(jié)點(diǎn)賦節(jié)點(diǎn)值和權(quán)值，并將孩子，雙親的值置0。其余節(jié)點(diǎn)所有值置0。（2）從HT中選擇兩個(gè)權(quán)值最小且尚無(wú)父節(jié)點(diǎn)的節(jié)點(diǎn)構(gòu)建新樹，并完成對(duì)雙親，孩子信息的復(fù)值。（3)循環(huán)N-1次實(shí)現(xiàn)整個(gè)樹的構(gòu)建。求編碼：從左到右掃描HT，若當(dāng)前節(jié)點(diǎn)HT[i]有雙親，則將其雙親入棧，并將HT[i]是其雙親的左孩子或右孩子記錄至flag數(shù)組。這樣繼續(xù)搜尋，一定可以最終找到根節(jié)點(diǎn)，而此時(shí)flag數(shù)組所記錄的信息即為HT[i]所對(duì)應(yīng)的Huffman編碼。由于棧的先進(jìn)后出性質(zhì)，從棧中將其一一取出則正好是其對(duì)應(yīng)的Huffman編碼。每個(gè)HT[i]都可以用上述方法找到其對(duì)應(yīng)的Huffman編碼，故所有節(jié)點(diǎn)都可以用此方法做出。具體操作：（1）從葉子節(jié)點(diǎn)開始按照所儲(chǔ)存的父節(jié)點(diǎn)的信息向上尋找，若該節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子將路徑記為0，是右孩子則將路徑記為1。（2）用臨時(shí)字符數(shù)組cd來(lái)儲(chǔ)存路徑并從從后向前儲(chǔ)存。（3）從1.找到的父節(jié)點(diǎn)開始繼續(xù)向上尋找，直到找到根節(jié)點(diǎn)，即parent為0結(jié)束。（4)將整個(gè)路徑copy到HC中。解碼：具體操作：（1）以字符串的形式輸入編碼存于code中。（2）從根節(jié)點(diǎn)開始按照編碼所給的路徑一次向下尋找，即：code=1，訪問(wèn)右子樹；code=0，訪問(wèn)左孩子。（3）直到找到葉子節(jié)點(diǎn)為止。徑字符寫入譯碼數(shù)組text。（4）此時(shí)，若code=’\0’，則譯碼結(jié)束；否則繼續(xù)從根節(jié)點(diǎn)開始尋找，重復(fù)1-3。（5）打印譯碼。三、程序清單：（略）四、運(yùn)行結(jié)果（截圖）：五、調(diào)試分析和體會(huì)：1.生成Huffman樹時(shí)，我們直接采用數(shù)組來(lái)做而舍棄指針，簡(jiǎn)化了編程復(fù)雜度，由其序列的穩(wěn)定性我們可以正確無(wú)誤地生成所對(duì)應(yīng)的Huffman樹。2．判斷一個(gè)節(jié)點(diǎn)是否被用過(guò)時(shí)我們無(wú)須另開數(shù)組來(lái)表示，而直接利用其是否有雙親