哈夫曼树查找算法与编码(C语言实现代码)

2022年7月17日16:30:10数据结构与算法评论218 views字数 1547阅读模式

1.哈夫曼树的查找算法

查找算法根据构建哈夫曼树算法衍生而来,我们在构建二叉树时需要查找出哪些数据最小,以符合我们哈夫曼树的最优解情况。

查找权重值最小的两个结点的思想是:从待处理数据的头部位置开始,首先找到两个无父结点的结点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需要考虑:

l  如果比两个结点中较小的那个还小,就保留这个结点,删除原来较大的结点;

l  如果介于两个结点权重值之间,替换原来较大的结点;

其代码可以表示为:

//HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
void Select(HuffmanTree HT, int end, int *s1, int *s2) {
    int min1, min2;
//遍历数组初始下标为 1
    int i = 1;
//找到还没构建树的结点
    while(HT[i].parent != 0 && i <= end) {
        i++;
    }
    min1 = HT[i].weight;
    *s1 = i;
    i++;
    while(HT[i].parent != 0 && i <= end) {
        i++;
    }
//对找到的两个结点比较大小,min2为大的,min1为小的
    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;
        }
//如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if(HT[j].weight < min1) {
            min2 = min1;
            min1 = HT[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
//如果介于两者之间,min2赋值为新的结点的位置下标
        else if(HT[j].weight >= min1 && HT[j].weight < min2) {
            min2 = HT[j].weight;
            *s2 = j;
        }
    }
}

 

2.哈夫曼编码

哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

哈夫曼编码,主要目的是根据使用频率来最大化节省字符(编码)的存储空间。

哈夫曼树查找算法与编码(C语言实现代码)

 

霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合,也包括文件传输的场合。

如果考虑到进一步节省存储空间,就应该将出现概率大(占比多)的字符用尽量少的0-1进行编码,也就是更靠近根(节点少),这也就是最优二叉树-哈夫曼树。

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/25194.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定