《哈夫曼樹與哈夫曼編碼》由會員分享，可在線閱讀，更多相關《哈夫曼樹與哈夫曼編碼（10頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、
哈夫曼樹與哈夫曼編碼
實驗三 : 哈夫曼樹與哈弗曼編碼 1 、實驗目的 :
(1) 理解哈夫曼樹的含義和性質(zhì)。
(2) 掌握哈夫曼樹的存儲結(jié)構以及描述方法。
(3) 掌握哈夫曼樹的生成方法。
(4) 掌握哈夫曼編碼的一般方法，并理解其在數(shù)據(jù)通訊中的應用。2 、實驗內(nèi)
容 :
哈夫曼樹與哈弗曼編碼、譯碼
a. 問題描述 :
哈夫曼問題的提出可以參考教材 P.145.
利用哈弗曼編碼進行通信可以大大提高通信利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編
2、碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，
在
接收端將傳來的數(shù)據(jù)進行譯碼。
b. 算法提示 :
參見教材 P.147-148 算法 6.12 、6.13 的描述。 3 、實驗要求 :
建立哈夫曼樹，實現(xiàn)編碼，譯碼。
1. 初始化 (Initialization) 。從終端讀入字符集大小 n，以及 n 個字符和 n 個
權值，建 ?
立哈夫曼樹，并將它存于文件 hfmTree 中。
2. 編碼 (Encoding) 。利用已建好的哈夫曼樹 ( 如不在內(nèi)存，則從文件 hfmTree
中讀 ?
3、
入 ) ，對文件 ToBeTran 中的正文進行編碼，然后將結(jié)果存入文件 CodeFile
中。
3. 譯碼 (Decoding ) 。利用已建好的哈夫曼樹將文件 CodeFile 中的代碼進行譯碼，結(jié) ?
果存入文件 TextFile 中。
4. 輸出代碼文件 (Print) 。將文件 CodeFile 以緊湊格式顯示在終端上，每行 50
個代 ?
碼。同時將此字符形式的編碼文件寫入文件 CodePrint 中。
5. 輸出哈夫曼樹 (TreePrinting) 。將已在內(nèi)存中的哈夫曼樹以直觀的方式
4、( 樹
或凹入 ?
表形式 ) 顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件 TreePrint
中。
測試數(shù)據(jù) :
設權值 c= (a, b, c, d , e, f, g, h)
w=(5，29，7，8，14，23，3，11) ，n=8。
按照字符‘ 0’或‘ 1’確定找左孩子或右孩子，則權值對應的編碼為 :
5:0001 ， 29:10 ，7:1110 ，8:1111
14:110 ， 23:01 ，3:0000 ，11:001
4、實驗程序 :
#include
5、>
#include
#include
1
#define N 100
// 赫夫曼樹和赫夫曼編碼的存儲表示
typedef struct{
char ch;
unsigned int weight;
unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char * *HuffmanCode;
int min(HuffmanTree &HT,int i) { //
6、
函數(shù)
void select()
調(diào)用
int j,flag;
int k=65535;
for(j=1;j<=i;j++)
if(HT[j].weight
7、in(HT,i);
}
// 構造赫夫曼樹 HT , 并求出 n 個字符的赫夫曼編碼 HC void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, char *cha,int n)
{
char c;
int f,i,start,m,s1,s2;
HTNode *p;
if(n<=1) return ;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for
8、(p=HT,++p,i=1;i<=n;++i,++p)
{ p->ch=cha[i]; p->weight=w[i]; p->parent=0;
p->lchild=0;
p->rchild=0;
2
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;++i)
{
Select(HT,i-1,s1,s2);
9、HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
} HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd=(char *)malloc(n*sizeof(char)); cd[n-1]=\0;
for(i=1;i<=n;++i){ start=n-1;
for(c=i,f=HT[i].pa
10、rent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild == c) cd[--start]=0;
else cd[--start]=1;
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
printf(" 字符為 %c",HT[i].ch);
printf(" 的編碼是 %s\n ",HC[i]);
}
free(cd);
}
// 赫夫曼譯碼函數(shù)
void D
11、eCoding(HuffmanTree &HT,HuffmanCode &HC,int n)
{
char f[N];
printf(" 請輸入一串字符串 :\n");
getchar();
gets(f);
int i;int m,k=0;
while(f[k]!=\0)
3
for(i=1;i<=n;i++)
{
m=strlen(HC[i]);
if(strncmp(HC[i],f+k,m)==0)
{ k=k+m;
printf
12、(" 輸出 %s的字符是 ",HC[i]);
printf("%c\n",HT[i].ch);
}
}
}
void displayHT(HuffmanTree &HT,int n,int m)
{ int i;
printf(" 打印赫夫曼 HC存儲結(jié)構 \n");
printf(" 編號 字符 權重 雙親 左孩子 右孩子 \n");
for(i=1;i<=n;i++)
printf("%d\t%c\t%d\t%d\t%d\t%d\n",i,HT[i].ch,HT[i].weight,HT[i
13、].pare
nt,HT[i].lchild,HT[i]
.rchild);
for(i=n+1;i<=m;i++)
printf("%d\t
\t%d\t%d\t%d\t%d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].r
child);
}
main()
{
HuffmanTree HT;
HuffmanCode HC;
int n,i;
printf("********* 建赫夫曼樹
14、, 編碼和譯碼程序 *************");
printf("\n 輸入建赫夫曼樹元素的個數(shù) :");
scanf("%d",&n);
int m=2*n-1;
char cha[9];
int w[9];
for(i=1;i<=n;i++)
{
printf(" 第%d個元素 =>字母和權重 :\n",i);
getchar();
scanf("%c %d",&cha[i],&w[i]);
}
HuffmanCoding(HT,HC,w,cha,n); displayH
15、T(HT,n,m); 4
DeCoding(HT,HC,n); return 0;
}
5、輸出結(jié)果 :
6、實驗心得 :
對文件操作不熟悉，不會用，沒有用，赫夫曼樹的打印也沒有做出來，不過通
過本次實驗還
是得到了很多東西～
5
哈夫曼樹與哈夫曼編碼
