Huffman编码C实现

Huffman编码C实现

Huffman编码：根据Huffman树进行编码的，用到的数据结构是二叉树。

C++使用优先队列来构建huffman树[哈夫曼树]

Huffman编码实现（详细实现）

Huffman编码与解码的实现

typedef 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=\n");
  cin>>leafnum;
  CreateHuffman( leafnum, T);
  while(1);
}

编译结果如下：

本文永久更新链接地址：