哈夫曼樹實(shí)驗(yàn)報告

1、實(shí)驗(yàn)報告實(shí)驗(yàn)名稱 Huffman編碼 專業(yè)班級 計(jì)科三班 姓名 學(xué)號 指導(dǎo)教師 日期 2014.12.20 一、實(shí)驗(yàn)?zāi)康?熟練掌握二叉樹應(yīng)用（Huffman編碼）的基本算法實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容l 1對輸入的一串電文字符實(shí)現(xiàn)Huffman編碼，再對Huffman編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。實(shí)現(xiàn)功能如下： Huffman樹的建立 Huffman編碼的生成編碼文件的譯碼三、實(shí)驗(yàn)要求l 設(shè)計(jì)思路：數(shù)據(jù)結(jié)構(gòu)：#define n 100/葉子結(jié)點(diǎn)數(shù)#define m 2*n-1/ Huffman樹中結(jié)點(diǎn)總數(shù)typedef struct int weight;/權(quán)值 int lchild , r

2、child , parent; /左右孩子及雙親指針HTNode; /樹中結(jié)點(diǎn)類型typedef HTNode HuffmanTreem+1;/0號單元不用主要實(shí)現(xiàn)函數(shù)：n 統(tǒng)計(jì)字符串中字符的種類以及各類字符的個數(shù)的函數(shù)n 構(gòu)造Huffman樹的函數(shù)n Huffman編碼的函數(shù)n 建立正文的編碼文件的函數(shù)n 代碼文件的譯碼函數(shù)n 主函數(shù)四、實(shí)驗(yàn)概要設(shè)計(jì)1)功能框圖Huffman樹的建立從葉子到根逆向求編碼退出Huffman編碼程序Huffman編碼的生成編碼文件的譯碼五. 使用說明1.運(yùn)行環(huán)境：VC+ 6.0 2.首先選擇主控菜單中的操作，即建表，然后進(jìn)行其它操作六實(shí)驗(yàn)截圖七 實(shí)驗(yàn)體會1、構(gòu)建

3、哈夫曼樹的關(guān)鍵在于找最小樹；在F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且至新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹上根結(jié)點(diǎn)的權(quán)值之和。2、由于學(xué)習(xí)的不足沒有實(shí)現(xiàn)編碼文件的譯碼，今后會加以改進(jìn) (）3、在逆向求編碼的for循環(huán)里犯了一個邏輯錯誤導(dǎo)致求出來的3、4位編碼串行，嘗試了多鐘數(shù)據(jù)輸入才找到原因所在，并加以改正，編寫程序需一步一步的去調(diào)試并找到錯誤所在。附源程序：#include#include#include#includetypedef struct char data; /結(jié)點(diǎn)字符 int weight; /結(jié)點(diǎn)權(quán)值 int parent,lchild,rchild

4、; /父子結(jié)點(diǎn) HTNode,* HuffmanTree;typedef char * *HuffmanCode;void Select(HuffmanTree HT, int m, int& s1, int& s2) int i; s1 = s2 = 1; for(i=1; i=m; i+) if (HTi.parent=0) s1=i; break; for(i=i+1; iHTi.weight) s1=i; for(i=1; i=m; i+) if(HTi.parent=0&i!=s1) s2=i; break; for(i=i+1; i=m; i+) if(HTi.parent=0 &

5、 HTi.weightHTs2.weight & i!=s1) s2=i; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n) /w存放n個字符的權(quán)值，構(gòu)造赫夫曼樹HT，并求出n個字符的赫夫曼樹編碼HCint f; int m,i,s1,s2;int c;HuffmanTree p;char *cd;if (n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;i=n;+i,+p,+w) (*p).weight=*w

6、; (*p).parent=0; (*p).lchild=0; (*p).rchild=0;for( ;i=m;+i,+p) (*p).parent=0;for(i=n+1;i=m;+i) /建立赫夫曼樹 /在HT1.i-1選擇parent為0且weight最小的兩個節(jié)點(diǎn)，其序號分別為s1,s2.Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/*從葉子到根逆向求每個字符的赫夫曼編碼*HC=(HuffmanCode)m

7、alloc(n+1)*sizeof(char*);/分配n個字符編碼的頭指針向量cd=(char*)malloc(n*sizeof(char); /分配求編碼的工作區(qū)間cdn-1=0; /編碼結(jié)束符for(i=1;i=n;+i) /逐個字符求赫夫曼樹編碼 int start; start=n-1; /編碼結(jié)束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) /從葉子到根逆向求編碼if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char); /為第i個字符編碼分配空間strcpy(HCi,&cdstart); /從cd復(fù)制編碼（串）到HCfree(cd); /釋放空間void main()HuffmanTree HT;HuffmanCode HC;int *w,n,i; printf(請輸入權(quán)值的個數(shù)(): );scanf (%d,&n);w=(int *)malloc(n*sizeof(int);print