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

1、.實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱Huffman 編碼專業(yè)班級(jí)計(jì)科三班姓名學(xué)號(hào)指導(dǎo)教師日期2014.12.20一、實(shí)驗(yàn)?zāi)康氖炀氄莆斩鏄鋺?yīng)用（Huffman 編碼）的基本算法實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容1對(duì)輸入的一串電文字符實(shí)現(xiàn) Huffman 編碼，再對(duì) Huffman 編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。實(shí)現(xiàn)功能如下：Huffman 樹的建立Huffman 編碼的生成編碼文件的譯碼三、實(shí)驗(yàn)要求設(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 ,rchild ,

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

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

4、de,* 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 & HTi.weightHTs2.weight &

5、i!=s1)s2=i;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n)/w存放 n 個(gè)字符的權(quán)值，構(gòu)造赫夫曼樹HT，并求出n 個(gè)字符的赫夫曼樹編碼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;(*p).parent=0;(*p).lchild=0

6、;(*p).rchild=0;for( ;i=m;+i,+p)(*p).parent=0;for(i=n+1;i=m;+i) /建立赫夫曼樹/在 HT1.i-1選擇 parent為 0 且 weight最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)分別為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;/*從葉子到根逆向求每個(gè)字符的赫夫曼編碼*HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配

7、n 個(gè)字符編碼的頭指針向量cd=(char*)malloc(n*sizeof(char);/分配求編碼的工作區(qū)間cdn-1=0;/編碼結(jié)束符for(i=1;i=n;+i)/逐個(gè)字符求赫夫曼樹編碼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 個(gè)字符編碼分配空間strcpy(HCi,&cdstart);/從 cd 復(fù)制編碼（串）到HCfree(cd);/釋放空間void main()HuffmanTree HT;HuffmanCode HC;int *w,n,i;printf(請(qǐng)輸入權(quán)值的個(gè)數(shù)(): );scanf (%d,&n);w=(int *)malloc(n*sizeof(int);printf(請(qǐng)依次輸入