你好,游客 登录 注册 搜索
背景:
阅读新闻

C实现哈夫曼树和哈夫曼编码

[日期:2013-12-16] 来源:Linux社区  作者:hjgblog [字体: ]

C实现哈夫曼树和哈夫曼编码

typedef struct HaffTree{
  int parent,lchild,rchild;
  int data;
  int weight;
}HaffTree,*Htree;

typedef char* *Ch;

//得到每个叶子结点的haffman编码值
void get_haff_code(Htree T,Ch *ch,int n){
      int c,f;
      char * chpoint=(char*)malloc(n*sizeof(char));  //分配一串字符空间
      chpoint[start]='/0';                          //最后一个字符设置为空格,便于在控制台输出更清晰。
      for(int i=1;i<=n;i++){                        //从第一个叶子结点开始循环读取haff编码
        int start=n-1;                                 
        for(c=1,f=T[c].parent;f!=0;c=f;f=T[f].parent)  //
        {    if(T[f].lchild==c)
                chpoint[--start]='0';                  //若为左孩子则设置为0
            else
                chpoint[--start]='1';                  //否则设置为1
      }       
      ch[i]=(char*)malloc((n-start)sizeof(char));    //分配得到的编码的长度的字符空间。
      strcopy(ch[i],&chpoint[start]);                //复制。
      }
      free(chpoint);                                  //最后释放空间。
}
 
 
 //创建一个Haffmantree,传递的参数为:T 树的首地址,s1为左孩子的序号,s2为右孩子序号,n为叶子结点数
void create_haff_tree(Htree T,int n,int &s1,int&s2){
    for(int i=n+1;i<2*n-1;i++){
        select_max_node(T,i-1,&s1,&s2);
        T[s1].parent=i;
        T[s2].parent=i;
        T[i].lchild=s1;
        T[i].rchild=s2;
        T[i].weight=T[s1].weight+T[s2].weight;       
    }
}

Ch* init_tree(Htree T,Data *v,int n)
{
      Ch *ch;
      int m= 2*n-1;
      T=(Htree)malloc((m+1)*sizeof(HaffTree));//分配m+1个结点的HaffTree,从1开始计数
      ch=(Ch)malloc((m+1)sizeof(Ch));        //分配m+1个字符串指针数组,每个指针值指向一串字符编码
     
    //***************初始化叶子结点值
      for(int i=1;i<=m;i++)
      {
          T[i]->parent=0;
          T[i]->lchild=0;
          T[i]->rchild=0;
          T[i]->data=v.data;
          T[i]->weight=v.weight;
      }
      //*****************初始化父节点的值
      for(int i=n+1;i<=2*n-1;i++)
      {
            T[i].parent=0;
            T[i].lchild=0;
            T[i].rchild=0;
            T[i].weight=0;
      }
      return ch;
}

相关阅读

C++实现哈夫曼编码完整代码 http://www.linuxidc.com/Linux/2012-12/76849.htm

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

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

       

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