数据结构实验之二叉树六：哈夫曼编码

冷不防 2022-07-12 04:07 133阅读 0赞

[sdut原题链接][sdut]  
[sdut原题代码链接][sdut 1]  
数据结构实验之二叉树六：哈夫曼编码  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
字符的编码方式有多种，除了大家熟悉的ASCII编码，哈夫曼编码(Huffman Coding)也是一种编码方式，它是可变字长编码。该方法完全依据字符出现概率来构造出平均长度最短的编码，称之为最优编码。哈夫曼编码常被用于数据文件压缩中，其压缩率通常在20%～90%之间。你的任务是对从键盘输入的一个字符串求出它的ASCII编码长度和哈夫曼编码长度的比值。

Input  
输入数据有多组，每组数据一行，表示要编码的字符串。

Output  
对应字符的ASCII编码长度la，huffman编码长度lh和la/lh的值(保留一位小数)，数据之间以空格间隔。

Example Input  
AAAAABCD  
THE\_CAT\_IN\_THE\_HAT

Example Output  
64 13 4.9  
144 51 2.8

Hint

Author  
xam

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #define MINDATA -1
    typedef struct HNode *Heap;
    struct HNode
    {
        int *Data;
        int Size;
    };
    typedef Heap MinHeap;
    MinHeap CreatHeap(int maxsize)//最小堆的创建函数
    {
        MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
        H->Data = (int *)malloc((maxsize+1)*sizeof(int));
        H->Data[0] = MINDATA;
        H->Size = 0;
        return H;
    }
    void Insert(MinHeap H, int x)//最小堆的元素插入函数
    {
        int i;
        i = ++H->Size;
        for(; H->Data[i/2] > x; i/=2)
            H->Data[i] = H->Data[i/2];
        H->Data[i] = x;
    }
    int Delete(MinHeap H)//最小堆的删除函数
    {
        int MinItem, x, parent, child;
        MinItem = H->Data[1];
        x = H->Data[H->Size--];
        for(parent = 1; parent*2 <= H->Size; parent = child)
        {
            child = parent*2;
            if((child != H->Size) && H->Data[child] > H->Data[child+1])
                child++;
            if(x <= H->Data[child])
                break;
            else
                H->Data[parent] = H->Data[child];
        }
        H->Data[parent] = x;
        return MinItem;
    }
    void PercDown(MinHeap H, int p)
    {
        int parent, child, x;
        x = H->Data[p];
        for(parent = p; parent*2 <= H->Size; parent = child)
        {
            child = parent*2;
            if((child != H->Size) && H->Data[child] > H->Data[child+1])
                child++;
            if(x <= H->Data[child])
                break;
            else
                H->Data[parent] = H->Data[child];
        }
        H->Data[parent] = x;
    }
    void BuildHeap(MinHeap H)//最小堆的建立函数
    {
        int i;
        for(i = H->Size/2; i > 0; i--)
            PercDown(H, i);
    }
    int main()
    {
        double la, lh, ah;
        int len, i;
        char s[199859];
        while(scanf("%s", s) != EOF)
        {
            int n, x1, x2, y, count[256] = {
       0};///初始化
            MinHeap H1;
            H1 = CreatHeap(256);//最小堆的创建操作
            lh = 0;///初始化
    
            len = strlen(s);
            la = len*8;
            for(i = 0; i < len; i++)
            {
                count[s[i]]++;
            }
            for(i = 0; i < 256; i++)
            {
                if(count[i] != 0)
                {
                    H1->Data[++H1->Size] = count[i];
                    //printf("H1->date[]:%d\n", count[i]);
                    //printf("H1->Size:%d\n", H1->Size);
                }
            }
            BuildHeap(H1);//最小堆的建立操作
            n = H1->Size;///H1->Size在删除操作中会发生改变，因此应该提前记录堆中的元素个数
            for(i = 0; i < n-1; i++)
            {
                x1 = Delete(H1);//最小堆的删除操作
                x2 = Delete(H1);//最小堆的删除操作
                y = x1 + x2;
                lh += y;
                Insert(H1, y);//最小堆的插入操作
                ///printf("lh:%.0lf\n", lh);
            }
            ah = la/lh;
            printf("%.0lf %.0lf %.1lf\n", la, lh, ah);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 0ms
    Take Memory: 116KB
    Submit time: 2017-02-09 21:47:31
    ****************************************************/

参考博客中有一个例题， 感谢博客作者的启迪，谢谢。  
例题：一组字符(a,b,c,d)在文中出现的次数分别为(7,6,3,5),字符＇d＇的哈夫曼编码的长度为？

首先构造huffman树  
每一步都将所有数字排序  
方法如下:  
1:  
3 5 6 7  
2:  
6 7 8  
/ \\  
3 5  
3:  
8 13  
/ \\ / \\  
3 5 6 7  
4:  
21  
/ \\  
8 13  
/ \\ / \\  
3 5 6 7  
所以构造哈夫曼树如图  
7 6 3 5 分别对应a b c d  
如果左边为0 ,右边为 1 ,则他们编码分别为:  
a 11  
b 10  
c 00  
d 01  
长度为2

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2008/pid/3345
[sdut 1]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Viewcode/view/sid/2333991