本文是數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)系列(6)：樹(shù)和2叉樹(shù)中第15課時(shí)哈夫曼樹(shù)的例程。
#include <stdio.h>
#include <string.h>
#define N 50 //葉子結(jié)點(diǎn)數(shù)
#define M 2*N⑴ //樹(shù)中結(jié)點(diǎn)總數(shù)
//哈夫曼樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)類(lèi)型
typedef struct
{
char data; //結(jié)點(diǎn)值
double weight; //權(quán)重
int parent; //雙親結(jié)點(diǎn)
int lchild; //左孩子結(jié)點(diǎn)
int rchild; //右孩子結(jié)點(diǎn)
} HTNode;
//每一個(gè)節(jié)點(diǎn)哈夫曼編碼的結(jié)構(gòu)類(lèi)型
typedef struct
{
char cd[N]; //寄存哈夫曼碼
int start;
} HCode;
//構(gòu)造哈夫曼樹(shù)
void CreateHT(HTNode ht[],int n)
{
int i,k,lnode,rnode;
double min1,min2;
for (i=0; i<2*n-1; i++) //所有結(jié)點(diǎn)的相干域置初值⑴
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n; i<2*n-1; i++) //構(gòu)造哈夫曼樹(shù)
{
min1=min2=32767; //lnode和rnode為最小權(quán)重的兩個(gè)結(jié)點(diǎn)位置
lnode=rnode=-1;
for (k=0; k<=i-1; k++)
if (ht[k].parent==-1) //只在還沒(méi)有構(gòu)造2叉樹(shù)的結(jié)點(diǎn)中查找
{
if (ht[k].weight<min1)
{
min2=min1;
rnode=lnode;
min1=ht[k].weight;
lnode=k;
}
else if (ht[k].weight<min2)
{
min2=ht[k].weight;
rnode=k;
}
}
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;
ht[i].rchild=rnode;
ht[lnode].parent=i;
ht[rnode].parent=i;
}
}
//實(shí)現(xiàn)哈夫曼編碼
void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
int i,f,c;
HCode hc;
for (i=0; i<n; i++) //根據(jù)哈夫曼樹(shù)求哈夫曼編碼
{
hc.start=n;
c=i;
f=ht[i].parent;
while (f!=-1) //循序直到樹(shù)根結(jié)點(diǎn)
{
if (ht[f].lchild==c) //處理左孩子結(jié)點(diǎn)
hc.cd[hc.start--]='0';
else //處理右孩子結(jié)點(diǎn)
hc.cd[hc.start--]='1';
c=f;
f=ht[f].parent;
}
hc.start++; //start指向哈夫曼編碼最開(kāi)始字符
hcd[i]=hc;
}
}
//輸出哈夫曼編碼
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
int i,k;
double sum=0,m=0;
int j;
printf(" 輸出哈夫曼編碼:
"); //輸出哈夫曼編碼
for (i=0; i<n; i++)
{
j=0;
printf(" %c: ",ht[i].data);
for (k=hcd[i].start; k<=n; k++)
{
printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("
");
}
printf("
平均長(zhǎng)度=%g
",1.0*sum/m);
}
int main()
{
int n=8,i; //n表示初始字符串的個(gè)數(shù)
char str[]= {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
double fnum[]= {0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.1};
HTNode ht[M];
HCode hcd[N];
for (i=0; i<n; i++)
{
ht[i].data=str[i];
ht[i].weight=fnum[i];
}
printf("
");
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("
");
return 0;
}版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
