数据结构 哈夫曼编码 c++_给定报文中26个字母a-z及空格的出现频率{64, 13, 22, 32, 103, 21, 15,-程序员宅基地

技术标签: c++  数据结构  

哈夫曼编码

要求:

给定报文中26个字母a-z及空格的出现频率{64, 13, 22, 32, 103, 21, 15, 47, 57, 1, 5, 32, 20, 57, 63, 15, 1, 48, 51, 80, 23, 8, 18, 1, 16, 1, 168},构建哈夫曼树并为这27个字符编制哈夫曼编码,并输出。模拟发送端,从键盘输入字符串,以%为结束标记,在屏幕上输出输入串的编码;模拟接收端,从键盘上输入0-1哈夫曼编码串,翻译出对应的原文。

64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1 168

a b c d e f g h I j k l m n o p q r s t u v w x y z

操作实例:

模拟发送端
输入:I love you
输出:01101111011110011100000010111100011100100001

模拟接收端 输入
输入:01101101111011000111111010111101101001100001
输出:it is a dog

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int n,s1,s2,m,i,j,count2;
typedef struct HTNode
{
    
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;

void Select(HuffmanTree &HT, int end, int &s1, int &s2)
{
    
    int min1=66666,min2=66666;
    for(int i=1;i<=end;i++)
    {
    
        if(HT[i].parent==0&&HT[i].weight<min1)
        {
    
            min1 = HT[i].weight;
            s1 = i;
        }
    }
    for(int i=1;i<=end;i++)
    {
    
        if(HT[i].parent==0&&HT[i].weight<min2&&s1!=i)
        {
    
            min2 = HT[i].weight;
            s2 = i;
        }
    }
}

void CreatHuffmanTree(HuffmanTree &HT, int n)
{
    
    m = 2*n-1;
    HT = new HTNode[m+1];
    for(i=1;i<=m;i++)
    {
    
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    for(i=1;i<=n;i++)
    {
    
        cin>>HT[i].weight;
    }
    for(i=n+1;i<=m;i++)
    {
    
        Select(HT,i-1,s1,s2);
        HT[i].weight = HT[s1].weight+HT[s2].weight;
        HT[s1].parent = i;
	 	HT[s2].parent = i;
	 	HT[i].lchild = s1;
	 	HT[i].rchild = s2;
    }

}

void creatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
    
    int start,c,f;
    HC=new char*[n+1];
    char *cd=new char[n];
    cd[n-1]='\0';
    for(int i=1; i<=n; i++)
    {
    
        start = n-1;
        c=i;
        f=HT[c].parent;
        while(f!=0)
        {
    
            start--;
            if(HT[f].lchild==c)
            {
    
                cd[start]='0';
            }
            else
            {
    
                cd[start]='1';
            }
            c=f;
            f=HT[f].parent;
        }
        HC[i] = new char[n-start];
        strcpy(HC[i],&cd[start]);
    }
    delete cd;
}



void TransCode(HuffmanTree HT,char a[],char ch[],char b[],int n)
{
    
    count2=0;
    int q=2*n-1;
    int k=0;
    for(int i=0; a[i]!='%'; i++)
    {
    
        if(a[i]=='0')
        {
    
            q=HT[q].lchild;
        }
        else if(a[i]=='1')
        {
    
            q=HT[q].rchild;
        }
        if(HT[q].lchild==0 && HT[q].rchild==0)
        {
    
            b[k++]=ch[q-1];
            q=2*n-1;
        }
    }
    count2=k;
    b[k]='\0';
}

void show()
{
    
    cout<<"********************************************************************"<<endl;
    cout<<"********* 1.输入HuffmanTree的参数.                        **********"<<endl;
    cout<<"********* 2.初始化HuffmanTree参数(含有26字母及空格).      **********"<<endl;
    cout<<"********* 3.创建HuffmanTree和编码表.                      **********"<<endl;
    cout<<"********* 4.输出编码表.                                   **********"<<endl;
    cout<<"********* 5.输入编码,并翻译为字符.                       **********"<<endl;
    cout<<"********* 6.输入字符,并实现编码.                         **********"<<endl;
    cout<<"********* 7.退出.                                         **********"<<endl;
    cout<<"********* 以%为结束标识                                   **********"<<endl;
    cout<<"********************************************************************"<<endl;
}

int main()
{
    
    HuffmanTree HT;
    HuffmanCode HC;
    int OpCode;
    int count1=0;
    char a[1000];
    char b[1000];
    char c[1000];
    char ch[27]={
    'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',' '};
    show();
    bool flag=true;
    while(flag)
    {
    
        cout<<"请输入操作码:"<<endl;
        cin>>OpCode;
        if(OpCode==1)
        {
    
            cout<<"请输入编码字符个数: ";
            cin>>n;
        }
        else if(OpCode==2)
        {
    
            cout<<"请输入权值: ";
            CreatHuffmanTree(HT,n);
        }
        else if(OpCode==3)
        {
    
            creatHuffmanCode(HT,HC,n);
        }
        else if(OpCode==4)
        {
    
            cout<<"结点"<<"\t"<<"字符"<<"\t"<<"权值"<<"\t"<<"编码"<<endl;
            for(int i=1;i<=n;i++)
            {
    
                cout<<i<<"\t"<<ch[i-1]<<"\t"<< HT[i].weight<<"\t"<<HC[i]<<endl;
            }
            cout<<endl;
        }
        else if(OpCode==5)
        {
    
            cout<<"输入二进制编码: ";
            for(i=0;i<1000;i++)
            {
    
                cin>>a[i];
                char data = a[i];
                if(a[i]=='%')
                {
    
                    break;
                }

            }
            TransCode(HT,a,ch,b,n);
            cout<<"输出: ";
            for(i=0;i<count2;i++)
            {
    
                cout<<b[i];
            }
            cout<<endl;
        }
        else if(OpCode==6)
        {
    
            count1=0;
            cout<<"请输入一串字符: ";
            for(i=0;i<1000;i++)
            {
    
                cin>>c[i];
                char data = c[1];
                count1++;
                if(c[i]=='%')
                {
    
                    break;
                }
            }
            cout<<"输出: ";
            for(i=0;i<count1-1;i++)
            {
    
                for(j=0;j<n;j++)
                {
    
                    if(c[i]==ch[j])
                    {
    
                        cout<<HC[j+1];
                        break;
                    }
                }
            }
            cout<<endl;
        }
        else if(OpCode==7)
        {
    
            flag=false;
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44223180/article/details/107116153

智能推荐

linux vi编辑器 乱码,vi编辑器笔记 + vim乱码的解决-程序员宅基地

文章浏览阅读367次。vi 文件名 进入命令模式命令模式--i、a、o、I、A、O-->插入模式--ESC键-->命令模式i:在光标之前添加文本I:在光标行首添加文本a:在光标之后添加文本A:在光标行末添加文本o:在光标下插入新行O:在光标上插入新行命令模式--:-->编辑模式--回车-->命令模式:set nu 回车设置行号:set nonu 回车取消行号:n 移至文件的第n行:n1,n2d ..._vi unicode乱码

Verilog编程之道-- task 和 function_verilog function可综合吗-程序员宅基地

文章浏览阅读2.8k次。注意:task和function 都是可以综合的,但是有诸多的要求和限制,所以要谨慎使用不同点 1function 不能包含时序控制语句,只能在一个时间单位执行,而task就可以包含时序控制语句 2 function 不能调用task,而task 可以调用function 3 function至少要有一个input参数,不能有output 和 inout 类型参数,而task既可以没有参数,也可以有各种类型参数 4 function..._verilog function可综合吗

poj2386 dfs_poj2386算法思路-程序员宅基地

文章浏览阅读116次。题意:有一个N*M的院子,八连通的积水是认为被连接在一的,求有几个水洼。思路:从每个M开始向八个方向搜,把搜过的M变成.知道搜不到为止。时间复杂度O(8*N*M)Sample Input10 12W........WW..WWW.....WWW....WW...WW..........WW..........W....W......W...W.W.....WW.W.W.W........_poj2386算法思路

Windows Server 配置(七)VPN服务器的安装-程序员宅基地

文章浏览阅读5.2k次。VPN服务器是双网卡或多网卡的配置,一块网卡连接内网,另一块连接外网,同时外网或远程的客户端可以通过建立VPN连接访问到内网资源。两块网卡分别设置好地址,外网网卡的地址是否能做的,或者是在路由器上做NAT需要进一步了解。VPN的配置VPN的配置创建用户以上操作完成后在VPN服务器上就创建了可以远程连接的用户。

Light oj 1045 (求某个数的阶乘在x进制下的位数)_求x进制下的位数-程序员宅基地

文章浏览阅读437次。Digital Of factorialTime Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %lluSubmit Status Practice LightOJ 1045 uDebugDescriptionFactorial of an integer is defi_求x进制下的位数

URDF/COLLADA file is not a valid robot model.解决方法-程序员宅基地

文章浏览阅读1.9k次。URDF/COLLADA file is not a valid robot model.解决方法很多次遇到URDF/COLLADA file is not a valid robot model,是各种各样的错误导致的,写下来希望能对我这样的新手有所帮助。很可能是在打开moveit_setupassistant前,没有打开roscore.1.通过SolidWorks生产URDF文件之后,是不是没有编译? 新建一个文件夹,在文件夹内部创建src文件夹,把SolidWorks生成的URDF文件夹放进sr_urdf/collada file is not a valid robot model.

随便推点

java 连接 sftp失败_关于java调用sftp下载文件报 No such File 错误的问题总结-程序员宅基地

文章浏览阅读2.2k次。/*** 对账文件入库*@paramtyjSaleActrDTOList*@throwsIOException*/private String cmPaymentCheckInsertData(List tyjSaleActrDTOList) throwsIOException {logger.info("====对账文件入库开始========");String flag= "0";Calend..._java new sftp连接失败不抛出异常

python能在excel运行吗-Python:使用Python运行Excel宏-程序员宅基地

文章浏览阅读611次。我需要通过python运行一个Excel宏,我总是会得到以下错误:result = self._oleobj_.InvokeTypes(*(dispid, LCID, wFlags, retType, argTypes) + args)pywintypes.com_error: (-2147352567, 'Exception occurred.', (0, None, None, None, 0..._excel trigger python 环境运行

session入memcache_session 入memcache-程序员宅基地

文章浏览阅读321次。<?phpini_set("session.save_handler", "memcache");ini_set("session.save_path", "tcp://localhost:11211");session_start();header("Content-type:text/html;charset=utf-8");$_SESSION['view'] = 'zhangsan_session 入memcache</div>

创建Tableau Public个人站点_创建tableau站点-程序员宅基地

文章浏览阅读2.4k次。Tableau Public是Tableau的免费版本,所以不能进行本地的保存,只能在Tableau的服务器创建个人的站点,进行可视化图谱的保存,每个用户有 10G的空间,可以进行发布。所以我们需要进行站点注册站点注册注册在Tableau Public的网站进行注册【链接】,点击注册创建配置文件在完善配置文件之后,即可创建个人站点个人中心查看以上,就表示个人站点已经创建成功,在使用Tableau Public创建文件,需要发布可视化图谱之后,即可发布到个人站点。..._创建tableau站点

先访问redis再访问mysql_Redis和MySQL数据一致中出现的几种情况-程序员宅基地

文章浏览阅读476次。1. MySQL持久化数据,Redis只读数据redis在启动之后,从数据库加载数据。读请求:不要求强一致性的读请求,走redis,要求强一致性的直接从mysql读取写请求:数据首先都写到数据库,之后更新redis(先写redis再写mysql,如果写入失败事务回滚会造成redis中存在脏数据)2.MySQL和Redis处理不同的数据类型MySQL处理实时性数据,例如金融数据、交易数据Redis处..._为什么要先从redis里获取数据再数据库

apt 软件安装_aptlite 安装软件-程序员宅基地

文章浏览阅读994次。文章目录一、安装卸载二、配置软件源一、安装卸载对应英文:Advanced Packaging Toolapt 是 Linux 系统中的 安装包管理工具序号命令作用01sudo apt install 软件名安装软件02sudo apt remove 软件名卸载软件03sudo apt uograde升级已安装的软件包二、配置软件源..._aptlite 安装软件

推荐文章

热门文章

相关标签