手机版
你好,游客 登录 注册
背景:
阅读新闻

Huffman编码与解码的实现

[日期:2014-08-17] 来源:Linux社区  作者:OshynSong [字体: ]

Huffman编码相信学过数据结构这么课的都知道,概念也比较好理解,但是一般好理解的算法,在实际实现的过程中总是会遇到各种问题,一方面个人认为是对算法的实现过程不熟,另一方面在实际实现的过程中可以提升自己实现算法的能力,将自己的想法实现后还是比较满足的。下面是本人亲自实现的Huffman编码与解码的C语言实现,主要是记录一下自己当时的想法,供以后备忘吧。

C++使用优先队列来构建huffman树[哈夫曼树]  http://www.linuxidc.com/Linux/2012-01/52790.htm

Huffman编码实现(详细实现) 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] = '\0';
 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] = '\0';
 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

linux
相关资讯       Huffman  Huffman编码  编码 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款