Question

哈夫曼编码的算法代码

用C或C++语言实现

Answer 1

// 哈夫曼编码(算法)#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码typedef struct
{
unsigned int weight; //用来存放各个结点的权值
unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针
} HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树//选择两个parent为0，且weight最小的结点s1和s2
void Select(HuffmanTree *ht,int n,int *s1,int *s2)
{
int i,min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0)
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s1=min;
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
min=i;
break;
}
}
for(i=1; i<=n; i++)
{
if((*ht)[i].parent==0 && i!=(*s1))
{
if((*ht)[i].weight<(*ht)[min].weight)
min=i;
}
}
*s2=min;
}//构造哈夫曼树ht。w存放已知的n个权值
void CrtHuffmanTree(HuffmanTree *ht,int *w,int n)
{
int m,i,s1,s2;
m=2*n-1;
*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1; i<=n; i++) //1--n号存放叶子结点，初始化
{
(*ht)[i].weight=w[i];
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
}
for(i=n+1; i<=m; i++)
{
(*ht)[i].weight=0;
(*ht)[i].LChild=0;
(*ht)[i].parent=0;
(*ht)[i].RChild=0;
} //非叶子结点初始化
printf("\nHuffmanTree: \n");
for(i=n+1; i<=m; i++) //创建非叶子结点，建哈夫曼树
{
//在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0
//且weight最小的结点，其序号分别赋值给s1、s2
Select(ht,i-1,&s1,&s2);
(*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;
printf("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);
}
printf("\n");
} //哈夫曼树建立完毕//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码
void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)
{
char *cd;
int i,start,p;
unsigned int c;
hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针
cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间
cd[n-1]='\0'; //从右向左逐位存放编码，首先存放编码结束符
for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码
{
start=n-1; //初始化编码起始指针
for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码
if( (*ht)[p].LChild==c)
cd[--start]='0'; //左分支标0
else
cd[--start]='1'; //右分支标1
hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间
strcpy(hc[i],&cd[start]);
}
free(cd);
for(i=1; i<=n; i++)
printf("HuffmanCode of %3d is %s\n",(*ht)[i].weight,hc[i]);
printf("\n");
}void main()
{
HuffmanTree HT;
HuffmanCode HC;
int *w,i,n,wei,m;
printf("\nn = " );
scanf("%d",&n);
w=(int *)malloc((n+1)*sizeof(int));
printf("\ninput the %d element's weight:\n",n);
for(i=1; i<=n; i++)
{
printf("%d: ",i);
fflush(stdin);
scanf("%d",&wei);
w[i]=wei;
}
CrtHuffmanTree(&HT,w,n);
CrtHuffmanCode(&HT,&HC,n);
}

Answer 2

//本程序根据26个英文字母出现的频度，得到了它们的一种哈夫曼编码方案 //by jirgal 2005.4.18 #include<iostream.h> #include<iomanip.h> #define NUM 26 //字母数 #define TNUM 51 // #define LTH 15 //编码最大长度 class Node { public: char data; int weight; int parent; int lchild; int rchild; }; void main() { char ch[NUM]={'a','b','c','d','e','f','g','h','i','j','k','l', 'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};//26个字母 int weit[NUM]={856,139,279,378,1304,289,199,528,627,13,42, 339,249,707,797,199,12,677,607,1045,249,92,149,17,199,8};//出现频率 Node nodes[TNUM]; //用对象数组存储哈夫曼树 int i,j,one,two,a,b; int hc[NUM][LTH]; //用于存储编码 int m,n; //初始化数组 for(i=0;i<NUM;i++) { nodes[i].data=ch[i]; nodes[i].weight=weit[i]; nodes[i].parent=-1; nodes[i].lchild=-1; nodes[i].rchild=-1; } for(i=NUM;i<TNUM;i++) { nodes[i].data='@'; nodes[i].weight=-1; nodes[i].parent=-1; nodes[i].lchild=-1; nodes[i].rchild=-1; } //建立哈夫曼树 for(i=NUM;i<TNUM;i++) { a=b=-1; one=two=10000; //最大权数 for(j=0;j<i;j++) { if(nodes[j].parent==-1) if(nodes[j].weight<=two) one=two; two=nodes[j].weight; a=b; b=j; } else if(nodes[j].weight>two&&nodes[j].weight<=one) { one=nodes[j].weight; a=j; } } }//for语句得到 parent=-1(即尚没有父结点)且weight最小的两个结点 nodes[a].parent=i; nodes[b].parent=i; nodes[i].lchild=a; nodes[i].rchild=b; nodes[i].weight=nodes[a].weight+nodes[b].weight; } //初始化hc for(i=0;i<LTH;i++) { for(j=0;j<NUM;j++) { hc[j][i]=7; } } //编码 for(i=0;i<NUM;i++) { j=LTH-1; for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent) { if(nodes[n].lchild==m) { hc[i][j]=0; } else { hc[i][j]=1; } j--; } } //输出 nodes cout<<"HuffmanTree:"<<endl; cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6) <<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl; for(i=0;i<TNUM;i++) { cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6) <<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl; } //输出编码 cout<<endl<<"Result:"<<endl; cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n"; for(i=0;i<NUM;i++) { cout<<setw(6)<<ch[i]<<setw(8)<<weit[i]; cout<<" "; for(j=0;j<LTH;j++) { if(hc[i][j]!=7) { cout<<hc[i][j]; } } cout<<endl; } cout<<"\nDone.\n"<<endl; }