Huffman编码与解码的实现

Huffman编码相信学过数据结构这么课的都知道，概念也比较好理解，但是一般好理解的算法，在实际实现的过程中总是会遇到各种问题，一方面个人认为是对算法的实现过程不熟，另一方面在实际实现的过程中可以提升自己实现算法的能力，将自己的想法实现后还是比较满足的。下面是本人亲自实现的Huffman编码与解码的C语言实现，主要是记录一下自己当时的想法，供以后备忘吧。C++使用优先队列来构建huffman树[哈夫曼树] http://www.linuxidc.com/Linux/2012-01/52790.htmHuffman编码实现（详细实现） http://www.linuxidc.com/Linux/2012-01/51730.htm

数据结构定义如下：typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, * HuffmanTree;typedef char * * HuffmanCode;建Huffman树的过程是使用顺序结构数组存储树，由于没有度为一的节点，因此总数为2*n - 1个节点，n为叶子节点个数，也是待编码的字符个数。

建树的关键代码如下： //建立Huffman树，初始化1到n号元素的parent都为0，每次从parent为0的元素中
//挑选最小的两个建树之后,将它们的parent都置为对应号码
for（i = n + 1; i <= m; i++）
{
int min1, min2;
int j;
for（j = 1; j <= i - 1; j++）
if（HT[j].parent == 0） {min1 = j; break;}
for（j = 1; j <= i - 1; j++）
{
if（HT[j].parent ！= 0） continue;
if（HT[j].weight < HT[min1].weight）
min1 = j;
}
HT[min1].parent = i;

for（j = 1; j <= i - 1; j++）
if（HT[j].parent == 0） {min2 = j; break;}
for（j = 1; j <= i - 1; j++）
{
if（HT[j].parent ！= 0） continue;
if（HT[j].weight < HT[min2].weight）
min2 = j;
}
HT[min2].parent = i;

HT[i].lchild = min1;
HT[i].rchild = min2;
HT[i].weight = HT[min1].weight + HT[min2].weight;
}编码过程是更加树的结构，对每个非叶子节点的左子树为‘0’，右子树为‘1’。实现如下：//编码
HuffmanCode HC = （HuffmanCode）malloc（n*sizeof（char *））;
char * cd = （char *）malloc（n*sizeof（char））;
cd[n-1] = "";
for（i = 0; i < n; i++）
{
int end = n - 1;
int cur = i + 1;
for （int a = HT[cur].parent; a ！= 0; cur = a, a = HT[a].parent）
{
if （HT[a].lchild == cur） cd[--end] = "0";
else if （HT[a].rchild == cur） cd[--end] = "1";
}
HC[i] = （char*）malloc（（n-end）*sizeof（char））;
strcpy（HC[i], &cd[end]）;
}
free（cd）;全部实现，封装在一个HuffmanEncode函数中。HuffmanCode HuffmanEncode（HuffmanTree & HT, unsigned int * w, int n）
{
int m = 2 * n - 1;
HT = （HuffmanTree）malloc（（m+1）*sizeof（HTNode））; //第一个不用
int i;
for（i = 1; i <= n; i++）
{
HT[i].weight = w[i-1];
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for（i = n + 1;i <= m; i++）
{
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
//建立Huffman树，初始化1到n号元素的parent都为0，每次从parent为0的元素中
//挑选最小的两个建树之后,将它们的parent都置为对应号码
for（i = n + 1; i <= m; i++）
{
int min1, min2;
int j;
for（j = 1; j <= i - 1; j++）
if（HT[j].parent == 0） {min1 = j; break;}
for（j = 1; j <= i - 1; j++）
{
if（HT[j].parent ！= 0） continue;
if（HT[j].weight < HT[min1].weight）
min1 = j;
}
HT[min1].parent = i;

for（j = 1; j <= i - 1; j++）
if（HT[j].parent == 0） {min2 = j; break;}
for（j = 1; j <= i - 1; j++）
{
if（HT[j].parent ！= 0） continue;
if（HT[j].weight < HT[min2].weight）
min2 = j;
}
HT[min2].parent = i;

HT[i].lchild = min1;
HT[i].rchild = min2;
HT[i].weight = HT[min1].weight + HT[min2].weight;
}

//编码
HuffmanCode HC = （HuffmanCode）malloc（n*sizeof（char *））;
char * cd = （char *）malloc（n*sizeof（char））;
cd[n-1] = "";
for（i = 0; i < n; i++）
{
int end = n - 1;
int cur = i + 1;
for （int a = HT[cur].parent; a ！= 0; cur = a, a = HT[a].parent）
{
if （HT[a].lchild == cur） cd[--end] = "0";
else if （HT[a].rchild == cur） cd[--end] = "1";
}
HC[i] = （char*）malloc（（n-end）*sizeof（char））;
strcpy（HC[i], &cd[end]）;
}
free（cd）;
return HC;
}更多详情见请继续阅读下一页的精彩内容： http://www.linuxidc.com/Linux/2014-08/105644p2.htm