C++实现Huffman编码

C++实现Huffman编码一问题描述二算法基本思路三算法复杂性分析四C++代码五运行结果截图一问题描述用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。给出现频率高的字符较短的编码,出现频率较低的字符以较长的编码,贪心算法使平均码长达到最小的前缀码编码方案。输入:字符集C和每一字符的频率。输出:每一字符的编码。二算法基本思路编码字符集C中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时确定算法当前要合并的两棵具有最小频率的树。一旦两棵具有最小频率的树合并后,产生一.

一 问题描述

用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。给出现频率高的字符较短的编码,出现频率较低的字符以较长的编码,贪心算法使平均码长达到最小的前缀码编码方案。
输入:字符集C和每一字符的频率。
输出:每一字符的编码。

二 算法基本思路

编码字符集C中每一字符c的频率是f(c)。
以f为键值的优先队列Q用在贪心选择时确定算法当前要合并的两棵具有最小频率的树。
一旦两棵具有最小频率的树合并后,产生一棵新的树,其频率为合并的两棵树的频率之和,并将新树插入优先队列Q。
经过n-1次的合并后,优先队列中只剩下一棵树,即所要求的树T。
伪代码

HUFFMAN(C)
	n = |C|
	Q = C
	for i=1 to n-1
	allocate a new node z
	z.left = x =EXTRACT-MIN(Q)
	z.right = y =EXTRACT-MIN(Q)
	z.freq = x.freq + y.freq
	INSERT(Q,z)
	return EXTRACT-MIN(Q)

三 算法复杂性分析

时间复杂度:O(nlogn)
假定Q是使用最小二叉堆实现的,对一个n个字符的集合C,在第2行用BUILD-MIN-HEAP过程将Q初始化,花费时间为O(n)。第3~8行的for循环执行了n-1次,且每个堆操作需要O(logn)的时间,所以循环对总时间的贡献为O(nlogn)。
空间复杂度:O(n)

四 C++代码

#include <iostream>
#include <string.h>
using namespace std;
// Huffman编码:T(n) = O(nlogn)

typedef struct{ 
   
    unsigned int weight; // 结点权重
    unsigned int parent,lchild,rchild; // 父节点、左右孩子
    char character; // 字符
}HTNode,*HuffmanTree; // 动态分配数组存储Huffman树

typedef char **HuffmanCode; // 动态分配数组存储Huffman编码表

// 在所有结点中选择权值最小的2个结点s1、s2
void Select(HuffmanTree HT, int n, int &s1, int &s2){ 
   
    if(n<2) return;
   int w1=-1,w2=-1;
    for(int i=1;i<=n;i++){ 
   
        if(HT[i].parent==0){ 
   
            if(w1==-1||HT[i].weight<=w1){ 
   
                w1=HT[i].weight;
                s1=i;
            }
        }
    }
    for(int i=1;i<=n;i++){ 
   
        if(HT[i].parent==0&&i!=s1){ 
   
            if(w2==-1||HT[i].weight<=w2&&HT[i].weight>=w1){ 
   
                w2=HT[i].weight;
                s2=i;
            }
        }
    }
}

// Huffman编码
// w存放n个字符的权值(均>0),构造Huffman树HT,并求出n个字符的Huffman编码HC
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, char *&character, int n){ 
   
    if(n<=1) return;
    int m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 构造Huffman树,0号单元未用
    HuffmanTree p;
    int i;
    for(p=HT+1,i=1;i<=n;++i,++p,++w,++character){ 
   
        *p={ 
   *w,0,0,0,*character}; // n个字符character和它们的权重w
    }
    for(;i<=m;++i,++p)
        *p={ 
   0,0,0,0,'\0'}; // 初始化剩余结点
    for(i=n+1;i<=m;++i){ 
    // 建Huffman树
        //在HT[1..i-1]选择parent为0且weight最小的两个结点,其序号分别为s1和s2,合并后放入HT[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;
    }
    // 从叶子到根逆向求每个字符的赫夫曼编码
    HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); // 分配n个字符编码的头指针向量
    char *cd=(char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
    cd[n-1]='\0';
    for(i=1;i<=n;i++){ 
    // 逐个字符求赫夫曼编码
        int start=n-1; // 编码结束符位置
        int c,f;
        for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){ 
    // 从叶子到根逆向求编码
            if(HT[f].lchild==c) cd[--start]='0';
            else cd[--start]='1';
        }
        HC[i]=(char *)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间
        strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC
    }
    free(cd);
}

int main(){ 
   
    cout<<"课件上的例子……"<<endl;
    char *character = "ETAOINSRHLDCU";
    int freq[] = { 
   125,93,80,76,72,71,65,61,55,41,40,31,27};
    int n = 13;
    cout<<"13个字符及它们的频率分别是:"<<endl;
    for(int i=0;i<13;i++)
        cout<<character[i]<<": "<<freq[i]<<endl;
    HuffmanTree HT;
    HuffmanCode HC;
    HuffmanCoding(HT,HC,freq,character,n);
    cout<<endl<<"Huffman编码:"<<endl;
    for(int i=1;i<=n;i++){ 
   
        cout<<HT[i].character<<": "<<HC[i]<<endl;
    }
    return 0;
}

五 运行结果截图

在这里插入图片描述
在这里插入图片描述

今天的文章C++实现Huffman编码分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/9231.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注