首页 / 操作系统 / Linux / Huffman编码C实现

Huffman编码：根据Huffman树进行编码的，用到的数据结构是二叉树。C++使用优先队列来构建huffman树[哈夫曼树] http://www.linuxidc.com/Linux/2012-01/52790.htmHuffman编码实现（详细实现） http://www.linuxidc.com/Linux/2012-01/51730.htmHuffman编码与解码的实现 http://www.linuxidc.com/Linux/2014-08/105644.htmtypedef int elemtype;
typedef struct
{
  elemtype weight;
  int parent,l_child,r_child;
} binarytree;//2、构建最优二叉树
void CreateHuffman（int leafnum, binarytree *huffmantree）
{
    //leafnum个叶子，决定nodenum个结点数
 int nodenum=2*leafnum-1;
 huffmantree=（binarytree *）malloc（nodenum*sizeof（binarytree））; //0号单元也使用
 
 //leafnum个叶子，决定nodenum个结点数，也决定了（nodenum-1）个bit位编码
 char *huffmancode;
 huffmancode =（char *）malloc（（nodenum-1）*sizeof（char））; //huffmantree的初始化:叶子结点data权值手动输入，非叶子默认值都为0
 cout<<"请输入叶子权值：";
 int i;
 for（i=0;i<nodenum;i++）
 {
  if（i<leafnum）
  {
   cin>>huffmantree[i].weight;
  }
  else
  {
   huffmantree[i].weight=0;
  }
  huffmantree[i].parent=huffmantree[i].l_child=huffmantree[i].r_child=0;
 } int j;
 //j从leafnum开始，指的是包含了新建子树的结点编号
 for（j=leafnum;j<nodenum;j++）
 {
 int w1=32767,w2=0; //存储最小权值；
 int p=0,q=0; //存储最小权值的编号；     int k; 
    for（k=0;k<j;k++）
   {
      if（huffmantree[k].parent==0）  //判断结点是否使用
      {
     if（huffmantree[k].weight<w1）
        {
       w2=w1;
       q=p;
       w1=huffmantree[k].weight;
       p=k;       
         
        }
     else if（huffmantree[k].weight<w2）
     {
       w2=huffmantree[k].weight;
       q=k;
     }
      }
      }
  //p对应左节点，编码为‘0’；q对应左节点，编码为‘1’；
  huffmancode[p]="0";
  huffmancode[q]="1";
 
  huffmantree[j].weight =w1+w2;
  huffmantree[j].l_child=p;
  huffmantree[j].r_child=q;
  huffmantree[p].parent=j;
  huffmantree[q].parent=j; 
 }//3、寻找从子节点到根节点的编码 HuffmanCoding（int n,binarytree *HuffmanTree）
 //针对每一个叶子，从叶子到根方向寻找huffmancode
 //每一个叶子，对应的编码长度codelength
 const int maxsize=10;
 char iscode[maxsize][maxsize];
 int m;
 for（m=0;m<leafnum;m++） //从第一个叶子开始找
 {
      int n=0;
 iscode[m][n]=huffmancode[m]; 
 int parent=huffmantree[m].parent;  
 while（parent ！=0）
  {
    iscode[m][++n]=huffmancode[parent];
    parent=huffmantree[parent].parent;
  }; int x;
 cout<<"第"<<m+1<<"个叶子的HuffmanCode————";
 for（x=0;x<n;x++）
    cout<<iscode[m][x]; 
 cout<<endl;
 }
}void main（）
{
 binarytree *T=0;
 int leafnum;
 printf（"输入叶子数量n= "）;
 cin>>leafnum;
 CreateHuffman（ leafnum, T）;
 while（1）;
}编译结果如下：本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-08/105670.htm