首页 技术 正文
技术 2022年11月23日
0 收藏 895 点赞 3,499 浏览 3160 个字

1、描述

Huffman编码,将字符串利用C++编码输出该字符串的Huffman编码。

Huffman树是一种特殊结构的二叉树,由Huffman树设计的二进制前缀编码,也称为Huffman编码在通信领域有着广泛的应用。在word2vec模型中,在构建层次Softmax的过程中,也使用到了Huffman树的知识。

在通信中,需要将传输的文字转换成二进制的字符串,假设传输的报文为:“AFTERDATAEARAREARTAREA”,现在需要对该报文进行编码。

2、实现过程

  • 统计字符串中出现字符的频率
  • 列出字符串的Huffman树

3、实现代码

#include<iostream>#include<string>using namespace std;struct huffTree{    int parent;//父亲    int lchild;//左孩子    int rchild;//右孩子    int weight;//权重    string flag;//标志};struct Lowest_Node//第0级节点的字符与频度{    char ch;    int ch_num;};//确定每个字符的huffman编码,输出参数为a、bvoid coding(int length, huffTree tree[], int n, int &a, int &b){    int i;    int r, s;    r = s = length;//节点个数最大不会超过字符串的长度    for (i = 0; i < n; i++)    {        if ((tree[i].weight < r) && (tree[i].parent == -1))        {            r = tree[i].weight;            a = i;        }    }    for (i = 0; i < n; i++)    {        if ((tree[i].weight < s) && (i != a) && (tree[i].parent == -1))        {            s = tree[i].weight;            b = i;        }    }}//计算每个字符出现的频度并排序void frequency(string str){    int length = str.length();//长度    // 开辟结构体数组    Lowest_Node *node = new Lowest_Node[length];//声明最0级节点    int i, j;//循环因子    for (i = 0; i < length; i++)        node[i].ch_num = 0;//初始化频度    int char_type_num = 0;//初始为0种字符    for (i = 0; i < length; i++)//循环整个字符串    {        for (j = 0; j < char_type_num; j++)            if (str[i] == node[j].ch || // 判断字符频率结构中,这个字符是否相等                (node[j].ch >= 'a'&&node[j].ch <= 'z'&& //判断是否为字符                    str[i] + 32 == node[j].ch  //判断字符串的大写是否与字符频率结构中字符相等                    ))                break;//该字符没有出现过,跳出循环        if (j < char_type_num)//该字符重复出现,对应的记数器加1            node[j].ch_num++;        else//新出现的字符,记录到ch[j]中,对应计数器加1        {            if (str[i] >= 'A'&&str[i] <= 'Z')                node[j].ch = str[i] + 32;   //字符转换为大写存储起来            else                node[j].ch = str[i];            node[j].ch_num++;            char_type_num++;//字符的种类数加1        }    }    //按频度从大到小排序    for (i = 0; i < char_type_num; i++) //字符长度    {        for (j = 0; j < char_type_num-1; j++)        {            //判断为字符就往下走,否则就不往下            if (node[j].ch >= 'a'&&node[j].ch <= 'z')            {                if (node[j].ch_num < node[j + 1].ch_num)//如果前一个小于后一个,交换                {                    int temp;//临时频度                    char ch_temp;//临时字符                    temp = node[j].ch_num;                    ch_temp = node[j].ch;                    node[j].ch_num = node[j + 1].ch_num;                    node[j].ch = node[j + 1].ch;                    node[j + 1].ch_num = temp;                    node[j + 1].ch = ch_temp;                }            }        }    }    for (i = 0; i < char_type_num; i++)//打印字符频度        cout << "字符" << node[i].ch << "出现了" << node[i].ch_num << "次" << endl;    huffTree *huff = new huffTree[2 * char_type_num - 1];//此变量的声明需位于确定char_type_num值后    huffTree temp;    string *code = new string[2 * char_type_num - 1];//存放各个字符的编码    for (i = 0; i < 2 * char_type_num - 1; i++)//节点初始化    {        huff[i].lchild = -1;        huff[i].parent = -1;        huff[i].rchild = -1;        huff[i].flag = -1;    }    for (j = 0; j < char_type_num; j++)//将排序后的第0级节点权重赋给树节点    {        huff[j].weight = node[j].ch_num;    }    int min1, min2;    for (int k = char_type_num; k < 2 * char_type_num - 1; k++)//赋值0级之上的节点    {        coding(length, huff, k, min1, min2);        huff[min1].parent = k;        huff[min2].parent = k;        huff[min1].flag = "0";        huff[min2].flag = "1";        huff[k].lchild = min1;        huff[k].rchild = min2;        huff[k].weight = huff[min1].weight + huff[min2].weight;    }    for (i = 0; i < char_type_num; i++)    {        temp = huff[i];        while (1)        {            code[i] = temp.flag + code[i];            temp = huff[temp.parent];            if (temp.parent == -1)                break;        }    }    cout << "字符串的每个字符huffman编码为:" << endl;    for (i = 0; i < char_type_num; i++)        cout << node[i].ch << "  " << code[i] << endl;    cout << "整个字符串的huffman编码为:" << endl;    for (i = 0; i < length; i++)    {        for (j = 0; j < char_type_num; j++)        {            if (str[i] == node[j].ch)                cout << code[j];        }    }    //释放内存    delete[] node;    node = NULL;    delete[] huff;    huff = NULL;    delete[] code;    code = NULL;}int main(){    int length = 0;//字符串长度    string str; //目标字符串    cout << "请输入一个字符串:";    cin >> str;    frequency(str);//求各个元素的频度    printf("\n");    system("pause");    return 0;}

4、参考

数据结构和算法——Huffman树和Huffman编码
http://blog.csdn.net/google19890102/article/details/54848262

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:8,048
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:4,905
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:5,737
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,593
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:6,806
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:4,235