在编程序的时候 不同的构造方法得到的编码可能不同 树的形态也可能有差异（两个最小值左右孩子选一种） 但是最小WPL一定是相同的 编码的结果都应该是前缀码
直接用出现的概率就可以
因为在编程序时一般采用权值和概率是正相关 权值大的出现的概率高 路径就短 编码就短
#include <stdio.h>
#include <stdlib.h>
#define LEN
sizeof(struct HTNode)
#define STACK_INIT_SIZE 10
#define ADD 10
#define F f//输入和输出的格式
typedef float *Welem;//
typedef float Telew;//权重类型表示
typedef struct HTNode
{
Telew weight;
int parent, lchild, rchild;
}HTNode;
typedef struct
{
HTNode *data;
int n;// the numbers of you need change
}HuffmanTree;
//////////////////////////////////////////////////////////////////
typedef struct
{
char *top;
char *base;
int stacksize;
}SqStack;
void Init_Stack(SqStack &s)
{
s.base = (char *) malloc ( STACK_INIT_SIZE*sizeof(char));
s.top = s.base;
s.stacksize = STACK_INIT_SIZE;
}
void Pop( SqStack &s )
{
if(s.base!=s.top)
printf("%c",*--s.top);
}
void Push( SqStack &s, char temp )
{
if(s.top - s.base >= s.stacksize)
{
s.base = (char *) realloc (s.base,(s.stacksize+ADD)*sizeof(char));
s.top = s.stacksize + s.base;
s.stacksize += ADD;
}
*s.top++ = temp;
}
////////////////////////////////////////////////////////////////////////
//获取有多少个字符需要编码
void Get_N( HuffmanTree &HT )
{
printf("Input the numbers of you need change:");
scanf("%d", &HT.n);
}
//获取每一个字符的权重
void Get_Weight( HuffmanTree HT, Welem &w )
{
w = (Telew *) malloc( HT.n*sizeof(Telew));
int i;
for( i=0; i<HT.n; ++i )
scanf("%F", w+i);
}
//选择权重最小的节点
void Select( HuffmanTree &HT, int i, int &temp)
{
int m = 2*HT.n - 1;
int j = 1;
while( j<=m )
{
if( HT.data[j].parent==0 && HT.data[j].weight!=0 )
{
temp = j;
break;
}
++j;
}
while( j<=m )
{
if( HT.data[j].parent==0 && HT.data[j].weight!=0 )
if(HT.data[temp].weight>HT.data[j].weight)
{
temp = temp + j;
j = temp - j;
temp = temp - j;
}
++j;
}
HT.data[temp].parent = i;
}
//进行编码工作
void HuffmanCoding( HuffmanTree &HT, Welem w)
{
if( HT.n<=1 )
return ;
int m = 2*HT.n-1;
int i = 0, temp1, temp2;
SqStack s;
Init_Stack(s);
HT.data = ( HTNode * ) malloc ((m+1)*LEN);//第零号单元不用
HTNode *p = HT.data+1;
for( i=1; i<=HT.n; ++i, ++w, ++p)
{
p->weight =
*w;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for(; i<=m; ++i, ++p)
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for(i=HT.n+1; i<=m; ++i)
{//temp 是最小权重的下标
Select( HT, i, temp1 );
Select( HT, i, temp2 );
HT.data[i].lchild = temp1;
HT.data[i].rchild = temp2;
HT.data[i].weight = HT.data[temp1].weight + HT.data[temp2].weight;
}
int c, f;
for(i=1; i<=HT.n; ++i)
{
c=i;
f=HT.data[i].parent;
printf("%F\t", HT.data[i].weight);
for( ; f!=0; c=f, f=HT.data[f].parent )
if( HT.data[f].lchild==c )
Push(s, '0');
else
Push(s, '1');
while(s.base!=s.top)
Pop(s);
printf("\n");
}
}
int main()
{
HuffmanTree HT;
Welem w;
Get_N( HT );
Get_Weight( HT, w );
printf("\n");
HuffmanCoding( HT, w);
return 0;
}
2010-05-20 19:23
