一个简单的Huffman编码实现

hongchh

问题描述：
有一组字符集{c1, c2, …, cn}，在使用这组字符集的过程中，通过统计发现每个字符都有其相应的出现频率，假设对应的频率为{f1, f2, …, fn}。现在需要对这些字符进行二进制编码，我们希望的编码结果如下：每个字符都有其独一无二的编码；编码长度是变长的，频率大的字符使用更少的二进制位进行编码，频率小的字符则使用比较多的二进制位进行编码，使得最终的平均编码长度达到最短；每个字符的编码都有特定的前缀，一个字符的编码不可能会是另一个字符的前缀，这样我们可以在读取编码时，当读取的二进制位可以对应一个字符时，就读取出该字符。举个例子，假如我们有字符集{‘a’, ‘b’, ‘c’}，字符’a’的编码为001，字符’b’的编码为010，那么此时c的编码不能为00或者01，这样我们才能识别’a’和’c’或者’b’和’c’。
解决方案：
Huffman编码，详细的算法介绍和实现细节请参考下面博客
博客地址： http://blog.csdn.net/hongchh/article/details/52218338

游客，如果您要查看本帖隐藏内容请回复

cosmosh73

看看

薇薇

棒棒的，加油

薇薇

表示实在是该好好学习哈夫曼编码的了

xgeng

谢谢分享

豪情壮志

谢谢楼主~

暴力书生

顶~加油

zndownload

这个有用，数据压缩算法方面

小鸟游家族

看看

lijialijialijia

AA

溯影

学习一下，希望这种技术贴都可以被顶起来！！！

JCSY

what

ALIEN_NoT

zhichi

FFISH

学习

Hariki

看看

云端之梦

#include <stdio.h>
#include <stdlib.h>
typedef char * * Huffmancode;
typedef struct
{
        int parent,lchild,rchild;
        int weight;
}Htnode,*Huffmantree;

int Select(Huffmantree HT,int end,int *s1,int *s2)//end保存数组最后一个
{
        int i=1;
        int min1,min2;
       
        while(HT[i].parent!=0&&i<end)//s1保存较小的
        {       
                i++;
        }
        min1=HT[i].weight;
        *s1=i;
        i++;
        while(HT[i].parent!=0&&i<end)
                i++;
        if(HT[i].weight<min1)
        {
                min2=min1;
                *s2=*s1;
                min1=HT[i].weight;
                *s1=i;
        }
        else
        {
                min2=HT[i].weight;
                *s2=i;
        }
        for(int j=i+1;j<end;j++)
        {
                if(HT[j].parent!=0)
                {
                        continue;
                }
                if(HT[j].weight<min1)
                {
                        min2=min1;
                        *s2=*s1;
                        min1=HT[j].weight;
                        *s1=j;
                }
                if(HT[j].weight>min1&&HT[j].weight<min2)
                {
                        min2=HT[j].weight;
                        *s2=j;
                }
        }
        return 0;
}
int CreatHTfumantree(Huffmantree *HT,Huffmancode &HC,int *w,int n)//n为叶子节点数
{

        if(n<=1)
                return 1;
        int m=2*n-1;//m为总节点数
        *HT=(Huffmantree)malloc((m+1)*sizeof(Htnode));//0号位置不用
        Huffmantree p=*HT;
        for(int i=1;i<=n;i++)
        {
                (p+i)->weight=*(w+i-1);
                (p+i)->parent=0;
                (p+i)->rchild=0;
                (p+i)->lchild=0;
        }
        for( i=n+1;i<=m;i++)
        {
                (p+i)->weight=0;
                (p+i)->lchild=0;
                (p+i)->rchild=0;
                (p+i)->parent=0;
        }
        for( i=n+1;i<=m;i++)
        {
                int s1,s2;
                Select(*HT,i-1,&s1,&s2);
                (*HT)[s1].parent=i;
                (*HT)[s2].parent=i;
                (*HT)[i].lchild=s1;
                (*HT)[i].rchild=s2;
                (*HT)[i].weight=(*HT)[s1].weight+(*HT)[s2].weight;
        }
       
        return 0;
}


int main()
{
        return 0;
}

Tiｚ

谢谢分享