Huffman编码源代码

构建Huffman树：

1.将给定的n个权值看作n棵只有结点无左右孩子的二叉树，组合成一个集合HT。

2.从集合HT中选出2棵权值最小的二叉树，组成一棵新的二叉树，其权值为这两棵二叉树的权值之和。

3.将步骤2中选出的二叉树从集合HT中删去，同时将步骤2中新的二叉树加入到集合HT中。

4.重复步骤2和步骤3，直到集合HT中只含有一棵树，这棵树就是Huffman树。

伪代码：

typedefstruct//定义结构体

{

intweight;//保存权值

intparent, lchild, rchild;//保存父节点、左右孩子的节点值

}HuffmanNode, *HuffmanTree;

typedefchar**HuffmanCode;//用来存储哈夫曼编码

procHuffmanCoding(HuffmanTree &HT,int*w,intn)//编码函数定义

if(n <= 1)then Error();

m := 2 * n - 1;//n nodes create huffman tree need 2n-1 nodes

HT:= (HuffmanNode*)malloc((m +1) *sizeof(HuffmanNode));//HT存放Huffman tree的所有节点，申请m+1个位置

memset(HT, 0, (m + 1)*sizeof(HuffmanNode));//对所有节点初始化为0

//setthe n nodes

fori from 1 to n

HT[i].weight := *w++;//初始化各节点的权值

//createHuffman tree

fori from n + 1 to m//从HT的第n+1个位置开始

select(HT, i - 1, s1,s2);//选择剩余节点中权值较小的s1和s2

HT[s1].parent := i;//s1,s2的父节点都是当前结点

HT[s2].parent := i;

HT[i].lchild := s1;

HT[i].rchild := s2;

HT[i].weight :=HT[s1].weight + HT[s2].weight;

end{for}

HC := (HuffmanCode)malloc((n + 1) *sizeof(char*));

char*cd = (char*)malloc(n *sizeof(char));//申请n个位置，最后一位存放结束符

cd[n - 1] ='\0';

fori from 1 to n

start = n - 1;

for(c= i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)

if(HT[f].lchild == c)

cd[--start] ='0';//cd从后往前依次存放

else

cd[--start] ='1';

end{for}

HC[i] = (char*)malloc((n - start) *sizeof(char));

strcpy(HC[i],&cd[start]);

end{for}

end{proc}

---

源码：

#include

#include

#include

usingnamespacestd;

/*哈夫曼树的存储结构，它是二叉树*/

typedefstruct

{

intweight;//保存权值

intparent, lchild, rchild;//保存父节点、左右孩子的节点值

}HuffmanNode, *HuffmanTree;

typedefchar**HuffmanCode;//用来存储哈夫曼编码

voidHuffmanCoding(HuffmanTree &HT,int*w,intn);//Huffman编码函数

voidselect(HuffmanTree HT,intn,int&s1,int&s2);//选择书中节点值较小的两个节点

voidError(char*message);//显示错误信息

intmain(intargc,char* argv[])

{

inti,n;

int*w;

HuffmanCode HC;

HuffmanTree HT;

cout<<"Enter the size of the code:";

cin>>n;

w=(int*)malloc(n*sizeof(int));

cout<<"Enter the weight of the code:";

for(i=0;i

cin>>w[i];

cout<<"The Huffmancode is:"<

HuffmanCoding(HT, w, n);

system("pause");

}

voidHuffmanCoding(HuffmanTree &HT,int*w,intn)

{

if(n <= 1)

Error("code is small");

intm = 2 * n - 1;//n nodes create huffman tree need2n-1 nodes

HT = (HuffmanNode*)malloc((m +1) *sizeof(HuffmanNode));//Huffman tree的所有节点

ints1, s2;//record the two mini weights nodes

memset(HT, 0, (m + 1)*sizeof(HuffmanNode));//对所有节点初始化为0

//setthe n nodes

for(inti = 1; i <= n; i++)

{

HT[i].weight = *w++;//初始化各节点权值

}

//创建Huffmantree

for(inti = n + 1; i <= m; ++i)

{

//选择剩余节点中权值较小的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;

}

HuffmanCode HC;

intstart, c, f;

HC = (HuffmanCode)malloc((n + 1)*sizeof(char*));

char*cd = (char*)malloc(n *sizeof(char));

cd[n - 1] ='\0';

for(inti = 1; i <= n; ++i)

{

start = n - 1;

for(c= i, f = HT[i].parent; 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]);

}

for(inti = 1; i <= n; i++)

{

cout<

}

free(cd);

free(HC);

free(HT);

}

voidError(char*message)

{

fprintf(stderr,"Error: %s(5s will exit)",message);

cout<<"\n";

Sleep(5000);

exit(1);

}

voidselect(HuffmanTree HT,intn,int&s1,int&s2)

{

s1 = 1;

s2 = 1;

intmin= 99999;

inti;

//选择未被使用的第一个节点，

for(i = 1; i <= n; ++i)

{

if(HT[i].parent == 0)

{

min = HT[i].weight;

break;

}

}

//findthe mini s1

for(intp =1; p <= n; ++p)

{

if(0== HT[p].parent && min >= HT[p].weight)

{

s1 = p;

min = HT[p].weight;

}

}

//findthe s2

min = 99999;

for(intq =1; q <= n; ++q)

{

if(0== HT[q].parent && min >= HT[q].weight )

{

if(q == s1)

continue;

s2 = q;

min = HT[q].weight;

}

}

}

运行结果示例：