精华内容
下载资源
问答
  • 哈夫曼编码译码
    2021-05-23 11:36:00

    《数据结构C语言哈夫曼编码译码》由会员分享,可在线阅读,更多相关《数据结构C语言哈夫曼编码译码(16页珍藏版)》请在人人文库网上搜索。

    1、实训报告题 目: 哈夫曼树编码译码院 系: 信息工程系专 业: 计算机科学与技术(网络方向)姓 名: 梁展荣 学 号: 指导教师: 赵莹莹 刘欣 日 期: 2013年7月3日 桂林电子科技大学信息科技学院目 录一、设计思想11.1建立哈夫曼树的思想11.2建立哈夫曼编码表21.3对文件进行编码21.4对文件进行解码2二、算法流程图3三、运行结果8四、遇到的问题及解决10五、心得体会13一、设计思想要完成哈夫曼的编码和解码需要首先建立哈夫曼树,之后对所有字符根据权重进行编码,最后再对文件内容进行编码和解码。1.1建立哈夫曼树的思想。首先定义适合哈夫曼树的节点类型,需要定义的有当前节点的字符,当前。

    2、节点的左子、右子和父亲指针。在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录,并且定义一个可以筛选出最小权重的函数。初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符,将这两个字符分别作为新节点的左子和右子建立一个小的二叉树,并将两个字符的权重之和赋值给新节点,将新二叉树放入筛选字符中,再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选,直到根节点(如果编码表共有N个字符,则2*N-1就为最终根节点)为止,也就是当筛选列表为空的时候,哈夫曼树即建立完成。对于哈夫曼编码树来说,由于哈夫曼编码是前缀码,所以所有要编码的字符最。

    3、终都将是这颗树的叶子节点,而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后,对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。1.2建立哈夫曼编码表。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子则对其编码0,如果当前节点为右子则对其编码1。以此类推进行编码直到根节点为止。此时的编码是逆向的,所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作,即可得到当前哈夫曼树的编码表。对于码值的逆向存储可以使用栈结构,先将一个码的每一步编码存入栈,再在一个码结束后出栈至空。当然也可以定义一个。

    4、字符型数组,将值从后向前存入数组,再将数组有值部分粘贴到新的数组中进行存储。本次采用了后者,因为个人认为为此一步操作建立栈结构不划算,而且前一个设计也已经熟练掌握了栈的方法,此处进行新的尝试会更好。1.3对文件进行编码。首先需要建立一个原始文件,在文件中输入需要编码的内容。之后将文件打开,将其中的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码,将字符逐一读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比较,找出相同的对象,并将当前节点的编码打印到屏幕,并将编码存入到新建的密码文件当中。1.4对文件进行解码。先打开密码文件,将之前编码后得到的密文内容存储到字符串中以便解码调。

    5、用。开始对密文的字符串进行解码,树索引从根节点开始走,当密文中的当前字符是0的时候,则索引走向左子节点;当是1的时候,则走向右子节点。以此类推,一直走到叶子节点为止,则当前叶子节点所代表的字符即为前一段密文的解码结果,。再对下一个字符依次从根节点开始解码,如此循环对每一段密文进行解码直到解码结束。将解码打印到屏幕,并将解码结果存入到新的解码文件当中。在解码之前,还应该先确认之前是否建立了哈夫曼树并且是否构建了编码表。不过由于本次将a到z都进行了编码,所以此步省略了,因为编码表是唯一的。需要的时候可以在Encoder 函数中先进行判定。将编码和解码写在了一起,可以在运行时进行选择调用。二、算法流。

    6、程图第一步:建立哈夫曼树。图1建立哈夫曼树的算法流程图第二步:构建哈夫曼编码表。图2构建哈夫曼编码表的算法流程图第三步:编码。图3 编码算法流程图第四步:解码。图4 解码算法流程图四、运行结果原文文件:图5 中缀转后缀运行结果图编码图:图6 编码图密文文件:图7 密文文件图解码图:图8 解码图译文文件:图9 译文文件图整体运行图:图10 编码解码整体运行图五、遇到的问题及解决这部分我主要遇到了如下两个问题,其内容与解决方法如下所列:l 第一个问题是权重的筛选部分出现了错误解决办法:一开始对于筛选最小权重的代码编写如下:void SelectMin(HFMT T,int i,int *p1,in。

    7、t *p2) int j, min=999;for(j=0;jTj.weight)min=Tj.weight; *p1=j; min=999; for(j=0;jTj.weight&j!=(*p1)min=Tj.weight; *p2=j; 因为权重中最大的就是字符e的权重103,所以为初始值min赋值时觉得999就已经是无限大了。但是后来发现编码不知确,就开始思考是什么问题。发现每次筛选都将会把最小的两个权重进行相加,所以很快就会超过999,编码自然就出现了问题。所以后来将min定义成了long型,并赋值,问题就解决了。l 第二个问题是生成编码表的时候如何将逆向编码正向存储解决办法:对于求编。

    8、码的时候,由于是从叶子节点向根顺次而求,所以编码结果将是逆向的。一开始想到的办法是利用栈的结构,将编码依次存入栈中,再在一个字符编码结束时将栈倒空,这样就可以将编码正向存储了。但是又在考虑如果不用栈时候也可以做到。后来想到了strcpy函数对字符数组进行链接。所以就可以定义一个数组,从后向前存储编码,再在一个字符编码结束时将这个数组有值的重新存入新数组中,即可以成为正向编码了。最终实现编码如下:HFCode hfEn(HFMT T) int i,f,c,start;HFCode hc;char *cd;hc=(char *)malloc(N+1)*sizeof(char*); cd=(char。

    9、)malloc(N*sizeof(char); cdN-1=0; for(i=0;iN;i+) start=N-1;for(c=i,f=Ti.parent;f!=-1;c=f,f=Tf.parent)if(Tf.left=c) cd-start=0;else cd-start=1;hci=(char *)malloc(N-start)*sizeof(char); strcpy(hci,&cdstart); return hc;六、心得体会通过对本次的编写,使我掌握了哈夫曼编码的特点、存储方法和基本原理,培养了我运用C语言正确编写程序以及调试程序的能力。哈夫曼编码的结构取决于可能出现的字符的个数和其所对应的权值,权值大的编码短,权值小的编码长。这样的结构会利用比较小的空间存储数据。而且,利用树的结构对其编码和对其解码,也是比较规格话,比较方便的。本次编程还运用了结构体,便捷的对树节点和树以及编码表进行定义和调用。并且了解到当求解一个算法时,不是拿到问题就不假思索去做,而应该首先对它有个整体的概念,再一步步对其进行分析。在分析的过程中也应该学会随时总结问题,将遇到的问题融会贯通,以便在将来需要的时候能够应用自如。本次设计中也存在一些一开始不容易解决的问题,但当对算法的进一步分析和对相关信息的查阅,也比较顺利的完成了设计。虽然路途比较艰辛,但奋斗的经历却成为了最宝贵的人生经验。

    更多相关内容
  • 哈夫曼编码译码

    2017-12-29 23:10:39
    数据结构课程设计,实现哈夫曼编码译码,打印哈夫曼树
  • PAGE / NUMPAGES 实 验 报 告 2015 / 2016学年 第二学期 课程名称 数据结构A 实验名称 二叉树的基本操作及哈夫曼编码译码系统的实现 实验时间 2016 年 4 月 14 日 指导单位 计算机科学与技术系 指导教师 骆健 学生...
  • 哈夫曼编码译码

    千次阅读 多人点赞 2021-12-31 19:36:16
    编写一个哈夫曼编码译码程序。 按词频从小到大的顺序给出各个字符(不超过30个)的词频,根据词频构造哈夫曼树,给出每个字符的哈夫曼编码,并对给出的语句进行译码。 为确保构建的哈夫曼树唯一,本题做如下限定: ...

    题目

    编写一个哈夫曼编码译码程序。

    按词频从小到大的顺序给出各个字符(不超过30个)的词频,根据词频构造哈夫曼树,给出每个字符的哈夫曼编码,并对给出的语句进行译码。

    为确保构建的哈夫曼树唯一,本题做如下限定:

    (1)选择根结点权值最小的两棵二叉树时,选取权值较小者作为左子树。

    (2)若多棵二叉树根结点权值相等,按先后次序分左右,先出现的作为左子树,后出现的作为右子树。

    生成哈夫曼编码时,哈夫曼树左分支标记为0,右分支标记为1。

    【输入格式】

    第一行输入字符个数n;

    第二行到第n行输入相应的字符及其权值;

    最后一行输入需进行译码的串

    【输出格式】

    首先按树的先序顺序输出所有字符的编码,每个编码占一行;

    最后一行输出需译码的原文,加上original:字样。

    输出中均无空格

    【样例输入】

    3

    m1

    n1

    c2

    10110

    【样例输出】

    c:0

    m:10

    n:11

    original:mnc

    题意:就是构建一颗哈夫曼树,根据该树确定每个字符的编码,根据编码解码

    注意

    • 权值不等,左小右大

    • 权值相等,先出现的为左。

    • 左为0,右为1

    如何实现

    哈夫曼树(最优二叉树),使用树的数据结构来存储比较贴切,使用其他的数据结构也行,办法不止一种。

    解题步骤:

    1. 创建哈夫曼树
    2. 根生成的树,前序遍历输出每个字符的哈夫曼编码。
    3. 根据哈夫曼编码解码

    1.创建哈夫曼树

    用一个结构体将输入的数据存放起来,哈夫曼树是最优二叉树,所以只需要定义两个孩子结点

    树的节点,可以定义为

    struct ThreeNode{
        double data; //词频,因为题意说可以是小数。所以使用double
        char ch;//字符 
        ThreeNode *left;//左孩子
        ThreeNode *right;//右孩子
    };
    

    创建过程如下:

    image-20211231184242372

    image-20211231184425781

    image-20211231184853524

    一个细节:

    因为需要每次都拿最小的两个值进行合并,并且生成一个新的节点。也就是说每次会减少一个需要构建的节点。那就是需要构建n-1次,直到最后剩下一个结点,无需合并,它就是根节点。使用长度为2n-1的结构体数组来保存每一个结点。

    TreeNode v[2*n-1];
    

    当构建完后它的结构应该是这样的,生成的结点用红色标志

    image-20211231185907741

    需要一个排序规则,方便我们进行对这个结构体数组排序。

    这里使用升序排序,这样我们从左往右遍历的时候,能满足数是最小的和最先出现的两个条件

    bool cmp(ThreeNode a, ThreeNode b)
    {
        return a.data < b.data; //根据权值升序排序
    }
    

    因为我们不断合成结点,每次合并之前需要对其排序,此时我们已经完成结构体是按照升序排序的功能了。只需要将没有合成过的结点的第1个和第2个拿出来,那他们就是最小的了。直接合成然后放进最后即可。这里使用两个索引记录我们合成到哪个位置,生成的结点该插入哪个位置即可。

    TreeNode* createTree(TreeNode *v,int n){  
        int i=0,index=n-1; //i为0 ,从位置0开始合成。index是生成的结点该放的地方
        while(i<2*n-1) //当i走到最后一个结点,无需再构建,也可以使用index控制
        {
            //1.先排序
            sort(v+i,v+index,cmp);  //只对范围内的排序。随两个索引变化,排序的范围也变化
            //2.合并:拿出排好序序列中的前两个结点。
            TreeNode* node1 = &v[i++];//TreeNode* node1 = &v[i];i++;
            TreeNode* node2 = &v[i++];
    
            //3.生成新节点,给结点赋值
            TreeNode newNode=v[index];
            newNode.data=node1->data+node2->data; //权值相加
            newNode.ch='-';//随意设置,表示其为中间结点。
            newNode.left=node1;//设置左右孩子
            newNode.right=node2;
    
            //4.新节点放入到序列中
            v[++index]=newNode;
        }
        return &v[index-1]; //最后一个为根节点
    }
    

    2.获取每个字符的编码

    我们已经拿到了哈夫曼树,且我们之前设置了新生成的结点的符号是-,使用先序遍历到结点的字符不是-的时候,就输出编码就ok。

    同时,我们的到了编码,也可以将每个字符的编码使用map记录下来,方便下一步查询。

    编码使用一个整型数组存储,location记录路径(索引),如果是左孩子,就将设置为0。

    /**
     * 先序顺序输出所有字符的编码
     */
    void printCode(TreeNode *root,char code[],int location){
        if (root == NULL) {
            return;
        }
        if(root->ch!='-')//说明已经遍历到叶子节点,输出序列
        {   
            printf("%c:",root->ch);
            string key="";//准备字符串拼接,也就是map的key
            for(int i=0;i<location;i++){//输出记录的长度。
                printf("%d",code[i]);   
                key+=to_string(code[i]);//to_string()将参数转为string类型
            }
            printf("\n");
           	//cout<<"key:"<<key<<","<<"value:"<<root->ch<<endl;
            m.insert(make_pair(key, root->ch));//将值以键值对的形式插入到map中,下一步使用
        }
        //该节点是左孩子,路径设0        
            code[location]=0; 
            location++;//下一个位置给下一个节点用
            printCode(root->left,code,location); //递归该节点。
            location--;//该节点递归完成。取消该节点的记录。
        
        //右孩子,1
            code[location]=1;
            location++;
            printCode(root->right,code,location);
            location--;
    }
    

    3.根据哈夫曼编码解码

    我们使用了map记录每个字符的编码。

    根据给的译码原文。去匹配map即可

    for(i=0;i<len;i++)
    {
        str+=decoding[i];//拼接key
        if(m.find(str)!=m.end()){//找到了key,输出
            printf("%c",m[str]); 
            str="";//清空key,重新拼接
        }
        else
        {
            //找不到key,什么也不用做,继续拼接,这个可以去掉
        }
    }
    

    4.完整代码

    可以将一些注释打开,能输出一些信息,帮助你理解和调试该程序。

    #include <iostream>
    #include<string>
    #include<vector>
    #include<map>
    #include<algorithm>
    #include<sstream>
    using namespace std;
    
    /**
     *  树结点
     */
    struct TreeNode{
        double data; //权值
        char ch;//字符
        struct TreeNode *left=NULL;//左孩子,默认指向空
        struct TreeNode *right=NULL;//右孩子
    };
    map<string,char> m;  //定义一个map
    bool cmp(TreeNode a,TreeNode b);
    TreeNode* createTree(TreeNode *v,int n);
    void printCode(struct TreeNode *root,char code[],int location);
    void f_decode(string decoding,int len);
    //升序 
    
    int main()
    {
        
        int n;
        cin>>n;
        getchar();//吸收回车字符
        //定义n个结点,使用vector存放
        TreeNode nodes[2*n-1];
        //输入n个结点
        for(int i=0;i<n;i++){
        	string line;
        	getline(cin,line);
        	stringstream inputline(line);
            inputline>>nodes[i].ch>>nodes[i].data;  
         
        }   
        //输入需进行译码的串
        string decoding; 
        getline(cin,decoding);
        int len = decoding.length();//统计长度
      
        //创建哈希树
    	TreeNode* root=createTree(nodes,n);     
    	char code[60]={0};//存储字符的编码
        //先序顺序输出所有字符的编码
        printCode(root,code,0);
    
        //解码
        /*
        for(int i=0;i<4;i++){//打印输入的一串字符
            printf("%c",decoding[i]);
        }
    	printf("\n");
        
        cout<<"输出map:"<<endl; 
        for(auto  &it:m){//打印map中的数据 
            string str=it.first;
            cout<<str<<":"<<it.second<<endl;
        }
        printf("\n字符串的长度为:%d\n",len);
        */
        f_decode(decoding,len);                             
        return 0;
    }
    /**
     * 创建树
     */
    TreeNode* createTree(TreeNode *v,int n){  
        
        int i=0,index=n; //i为0 ,从位置0开始合成。index是生成的结点该放的地方
        while(i<2*n-1) //当i走到最后一个结点,无需再构建,也可以使用index控制
        {
            //1.先排序
            sort(v+i,v+index,cmp);  //只对范围内的排序。随两个索引变化,排序的范围也变化
            //2.合并:拿出排好序序列中的前两个结点。
            TreeNode* node1 = &v[i++];//TreeNode* node1 = &v[i];i++;
            TreeNode* node2 = &v[i++];
    
            //3.生成新节点,给结点赋值
            TreeNode newNode;
            newNode.data=node1->data+node2->data; //权值相加
            newNode.ch='-';//随意设置,表示其为中间结点。
            newNode.left=node1;//设置左右孩子
            newNode.right=node2;
    
            //4.新节点放入到序列中
            v[index++]=newNode;
        }
        return &v[2*n-2]; //最后一个为根节点
    }
    
    /**
     * 排序规则 
     */
    bool cmp(TreeNode a, TreeNode b)
    {
        return a.data < b.data; //根据权值升序排序
    }
    
    /**
     *解码 ,码——>原文
     */
    void f_decode(string decoding,int len)
    {
        string str;
        int i=0;
        printf("original:");
        for(i=0;i<len;i++)
        {
            str+=decoding[i];//拼接key
            if(m.find(str)!=m.end()){//找到了key,输出
                printf("%c",m[str]); 
                str="";//清空key,重新拼接
            }
            else
            {
                //找不到key,什么也不用做,继续拼接,这个可以去掉
            }
        }
       
    }
    
    /**
     * 先序顺序输出所有字符的编码
     */
    void printCode(TreeNode *root,char code[],int location){
        if (root == NULL) {
            return;
        }
        if(root->ch!='-')//说明已经遍历到叶子节点,输出序列
        {   
            printf("%c:",root->ch);
            string key="";
            for(int i=0;i<location;i++){//输出记录的长度。
                printf("%d",code[i]);   
                key+=to_string(code[i]);//to_string()将参数转为string类型
            }
            printf("\n");
           	//cout<<"key:"<<key<<","<<"value:"<<root->ch<<endl;
            m.insert(make_pair(key, root->ch));//将值以键值对的形式插入到map中
        }
        //该节点是左孩子,路径设0        
            code[location]=0; 
            location++;//下一个位置给下一个节点用
            printCode(root->left,code,location); //递归该节点。
            location--;//该节点递归完成。取消该节点的记录。
        
        //右孩子,1
            code[location]=1;
            location++;
            printCode(root->right,code,location);
            location--;
    }
    

    在这里插入图片描述

    展开全文
  • 实现哈夫曼编码译码,内含丰富注释,可以作为demo使用
  • 用C++实现的哈夫曼编译码器,可以实现创建哈夫曼树、对txt文件进行编码译码,也可以查看生成的哈夫曼树。数据结构作业参考之必备品。
  • 哈夫曼编码译码器.rar

    2020-07-11 15:53:03
    利用哈夫曼树生成最优编码,程序可以写文件,进而从写文件中再读取文件,然后对读取的文件进行哈夫曼编码,对文件进行编码,然后将编码文件存储成huf文件,然后再对huf文件进行译码译码后再将译码文件保存成txt...
  • 哈夫曼编码译码C语言编写 10 [?标签 哈夫曼, 编码, 译码?] 如上题 C语言编个程序 懂的帮搞个能运行的程序来#11别到网上找那些 我找过了没用的 蝶风待夕魂 回答:2 人气:19 解决时间:2009-05-14 18:44 满意答案 好评率...
  • 哈夫曼编码译码器课程设计.pdf
  • 按词频从小到大的顺序给出各个字符(不超过30个)的词频,根据词频构造哈夫曼树,给出每个字符的哈夫曼编码,并对给出的语句进行译码。 为确保构建的哈夫曼树唯一,本题做如下限定: (1)选择根结点权值最小的两棵...
  • 哈夫曼编码译码C语言编写[参考].pdf
  • 哈夫曼编码译码--数据结构

    热门讨论 2011-12-08 20:24:53
    哈夫曼编码译码 包括默认编码 和 自定义编码 数据结构课程设计 一、题目: 哈夫曼编码/译码的设计与实现 二、目的与要求 1、目的: 通过布置具有一定难度的实际程序设计项目,使学生进一步理解和掌握课堂上所学...
  • 程序设计任务: 设计一个程序,实现哈夫曼编码译码的生成算法。基本要求:输入字符集大小n,以及n个字符和n个权值;构造哈夫曼树,产生每个字符的Huffman编码, 打印之;输入电文,将其翻译成比特流, 打印之;输入...
  • 哈夫曼编码译码系统的实现,主要包含三部分:1、创建哈夫曼树2、编码函数3、译码函数编写代码时为了方便,在这里混用了c++的输入输出流。主体用c语言实现。下面是代码部分:1、头文件,以及储存结构:#include#...

    哈夫曼编码译码系统的实现,主要包含三部分:

    1、创建哈夫曼树

    2、编码函数

    3、译码函数

    编写代码时为了方便,在这里混用了c++的输入输出流。主体用c语言实现。

    下面是代码部分:

    1、头文件,以及储存结构:

    #include

    #include

    using namespace std;

    #define MAX 2000

    typedef char ElemType;

    typedef struct{

    ElemType data;

    int w;

    int parent,lchild,rchild;

    }HFMTNode;

    2、哈夫曼树的创建,Ht储存全部节点的权值,n代表叶子节点数量。

    void menu(HFMTNode Ht [],int n);//原型声明

    void CreatHFMTree(HFMTNode Ht[],int n)//创建哈夫曼树

    {

    int i,j,k,lmin,rmin;

    int min1,min2,m1;

    for(i=1;i<2*n;i++)

    {

    Ht[i].parent=Ht[i].lchild=Ht[i].rchild=-1;

    }

    for(i=n+1;i<2*n;i++)

    {

    min1=min2=MAX;

    lmin=rmin=-1;

    for(k=1;k

    {

    if(Ht[k].parent==-1)//只在尚未构造的二叉树节点中运行

    {

    if(Ht[k].w

    {

    min2=min1;

    rmin=lmin;

    min1=Ht[k].w;

    lmin=k;

    }

    else

    {

    if(Ht[k].w

    {

    min2=Ht[k].w;

    rmin=k;

    }

    }

    }

    else{

    if(Ht[k].wm1)//与创建好的二叉树节点比较,选取w小的一个

    {

    min2=Ht[k].w;

    rmin=k;

    m1=k;

    }

    }

    }

    Ht[lmin].parent=i;//对选择出的结点进行连接

    Ht[rmin].parent=i;

    Ht[i].w=Ht[lmin].w+Ht[rmin].w;

    Ht[i].lchild=lmin;

    Ht[i].rchild=rmin;

    }

    printf("HFMTree have been created\n");

    }

    3、编码译码函数、主函数:

    void encoding(HFMTNode Ht [],int n)//编码

    {

    int k;

    fflush(stdin);

    printf("Please input what you want to encode with the ending of'#' :\n");

    char ch;

    ch=getchar(); //读取字符

    while (ch!='#')

    {

    for(k=1;k<=n;k++)

    {

    if(Ht[k].data==ch)

    {

    break;

    }

    } //找到字符位置

    HFMTNode temp1,temp=Ht[k];

    int flag=0;

    int a[n];

    while(temp.w!=Ht[2*n-1].w)

    {

    temp1=temp;

    temp=Ht[temp.parent];

    if(Ht[temp.lchild].w==temp1.w )

    {

    a[flag]=0;

    flag++;

    }

    else if(Ht[temp.rchild].w==temp1.w )

    {

    a[flag]=1;

    flag++;

    }

    } //用数组记录路径

    for(int f=flag-1;f>=0;f--)

    {

    printf("%d",a[f]);

    } //编码输出

    ch=getchar();

    }

    printf("\nencoding have finished\n");

    system("pause");

    system("cls");

    menu(Ht,n);

    }

    void decoding(HFMTNode Ht [],int n)//译码

    {

    int k=2*n-1;

    fflush(stdin);

    printf("Please input what you want to decode with the ending of'#' :\n");

    char ch;

    ch=getchar(); //依次读取01字符

    HFMTNode temp=Ht[2*n-1];

    while (ch!='#')

    {

    if(ch=='1')

    {

    if(temp.rchild==-1)

    {

    printf("%c",temp.data); //根据01向左右寻找,到达叶子节点时输出

    temp=Ht[2*n-1];

    continue;

    }

    else

    {

    temp=Ht[temp.rchild ];

    ch=getchar();

    }

    }

    else if(ch=='0')

    {

    if(temp.lchild==-1)

    {

    printf("%c",temp.data);

    temp=Ht[2*n-1];

    continue;

    }

    else

    {

    temp=Ht[temp.lchild ];

    ch=getchar();

    }

    }

    }

    printf("%c",temp.data); //输出要译码的最后一个字符

    printf("\ndecoding have finished\n");

    system("pause");

    system("cls");

    menu(Ht,n);

    }

    void menu(HFMTNode Ht [],int n)

    {

    int j;

    printf("Input your choice:\n");

    printf("1.encoding 2.decoding 0.exit\n");

    cin>>j;

    switch (j)

    {

    case 1:encoding(Ht,n);break;

    case 2:decoding(Ht,n);break;

    case 0:break;

    }

    }

    int main()

    {

    printf("Please input the amount of the node:\n");

    int i;

    scanf("%d",&i);

    HFMTNode Ht[2*i];//储存各个节点的数据

    for(int k=1;k<=i;k++)

    {

    printf("Ht[%d]:Please input data :",k);

    cin>>Ht[k].data;

    printf("Ht[%d]:Please input w :",k);

    cin>>Ht[k].w;

    }

    CreatHFMTree(Ht,i);

    menu(Ht,i);

    return 0;

    }

    展开全文
  • 7-2 哈夫曼编码译码

    千次阅读 多人点赞 2022-03-09 23:09:30
    编写一个哈夫曼编码译码程序。 按词频从小到大的顺序给出各个字符(不超过30个)的词频,根据词频构造哈夫曼树,给出每个字符的哈夫曼编码,并对给出的语句进行译码。 为确保构建的哈夫曼树唯一,本题做如下限定:...

    先看题目:


    编写一个哈夫曼编码译码程序。

    按词频从小到大的顺序给出各个字符(不超过30个)的词频,根据词频构造哈夫曼树,给出每个字符的哈夫曼编码,并对给出的语句进行译码。

    为确保构建的哈夫曼树唯一,本题做如下限定:

    (1)选择根结点权值最小的两棵二叉树时,选取权值较小者作为左子树。

    (2)若多棵二叉树根结点权值相等,按先后次序分左右,先出现的作为左子树,后出现的作为右子树。

    生成哈夫曼编码时,哈夫曼树左分支标记为0,右分支标记为1。

    输入格式:

    第一行输入字符个数n;

    第二行到第n行输入相应的字符及其词频(可以是整数,与可以是小数);

    最后一行输入需进行译码的串。

    输出格式:

    首先按树的先序顺序输出所有字符的编码,每个编码占一行;

    最后一行输出需译码的原文,加上original:字样。

    输出中均无空格

    输入样例:

    3
    m1
    n1
    c2
    10110

    输出样例:

    c:0
    m:10
    n:11
    original:mnc


    题目分析:

    题目给出了n个字符以及他们的频率,也就是说给出了n个结点,让我们用这n个结点构建一个Huffman树,然后又给出一段哈夫曼编码,让我们在所构建的Huffman树的基础上,对该编码进行翻译。

    所以这道题难点在于怎么构建这样一颗Huffman树(结点的选取、编码和译码)。

    实验步骤:

    根据Huffman树的性质我们可以知道,Huffman树中没有度为1得结点. 只有度为0和度为2得结点. 则一棵 有n个叶子结点得哈夫曼树共有2n-1个结点

    所以题目给了n个结点(叶子结点),那么我们构建的Huffman树就会有2n-1个结点。

    不妨画图看看?

     我们可以构建出这样一颗Huffman树,首先我们来创建一个树结点的结构体,每一个结点都存有:

     诶呀,图里忘记画 哈夫曼编码 这一项咯QWQ(也就是下图的char* code;)

    对应的代码:

    //Huffman树结点结构体
    typedef struct TreeNode{
    	double weight;//因为频率有可能为小数,所以用double
    	char Ch;//用于存放该节点字符
    	char *code;//用于存放该字符的 Huffman编码
    	int parent,lchild,rchild;//存放每个结点的 父节点 以及 子结点
    }TreeNode;

    然后,将这些结点组合起来,形成一颗树:

     对应的代码:

    //Huffman树结构体
    typedef struct HFTree{
    	TreeNode* data;//用堆实现该Huffman树
    	int length;//该树总结点的个数
    }HFTree;
    

    好的,构建完树的结构体之后呢,我们可以先编写程序的输入(main)部分:

    #include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    #define MAX_INT 1000
    #define MAX_Double (numeric_limits<double>::max)()
    
    using namespace std;
    
    int main(){
    	//输入n个字符
    	int n;
    	scanf("%d",&n);
    	getchar();//吸收缓存中的回车符,以下同理
    	
    	//初始化n个 char和double类型的数组 用于存放 字符和对应的频率
    	char* chNums = (char*)malloc(sizeof(char)*n);
    	double* nuNums = (double*)malloc(sizeof(double)*n);
    	
    	//输入 字符以及相应的频率
    	for(int i=0;i<n;++i){
    		scanf("%c%lf",&chNums[i],&nuNums[i]);
    		getchar();
    	}
    	
    	//输入 需要译码的字符串
    	char str[MAX_INT];
    	scanf("%s",str);
    	getchar();
    
        return 0;
    }

    好的,这样我们就拿到的输入的数据,接下来我们需要对拿到的字符和频率(也就是结点)进行Huffman树的构造咯!

    首先来一个初始化函数:

    //初始化哈夫曼树
    //把输入的 字符 频率 字符个数 传进来
    HFTree* initTree(double* weight,char* ch,int n){
    	HFTree* T = (HFTree*)malloc(sizeof(HFTree));
    	//根据性质,n个结点生成的Huffman树会有2*n-1个结点
    	T->data = (TreeNode*)malloc(sizeof(TreeNode)*(2*n-1));
    	T->length = n;
    	
    	//初始化每个结点,我们先给这n个结点(叶子结点)先初始化,等一下再初始化后面的n-1个(父结点)
    	for(int i = 0; i < n; ++i){
            //给结点中的每一个数据项赋值
    		T->data[i].Ch = ch[i];
    		T->data[i].weight = weight[i];
            
            //没有父节点就默认为0
    		T->data[i].parent = 0;
    
            //没有孩子结点就默认为-1
    		T->data[i].lchild = -1;
    		T->data[i].rchild = -1;
    		
    		//初始化每个结点的code数组
    		T->data[i].code = (char*)malloc(sizeof(char)*MAX_INT);
    		memset(T->data[i].code,'\0',MAX_INT);	
    	}
    	return T;
    }
    

    初始化之后呢,树的状态就为下图所示咯:

     下面就是创建一个Huffmna树的函数咯,但是我们还需要做一些准备:

    因为在创建一颗Huffman树时,需要从所有结点之中,选择两个权值最小的结点来进行组合,所以我们需要编写一个选择最小两个结点的下标的函数:

    //选择两个权值最小的结点,每次都会返回两个最小的结点
    int* selectMin(HFTree* T){
    	//定义两个哨兵变量,他们的值为double所表示的最大值
    	//(numeric_limits<double>::max)();
    	double min = MAX_Double;
    	double secondMin = MAX_Double;
    	//两个最小结点的下标
    	int minIndex;
    	int secondIndex;
    	//先选择第一小的结点
    	for(int i=0;i<T->length;++i){
    		//只要没有父节点就可以选择
    		if(T->data[i].parent == 0){
    			if(T->data[i].weight < min){
    				min = T->data[i].weight;
    				minIndex = i;
    			}
    		}
    	}
    	//其次选择第二小的结点
    	for(int i =0;i<T->length;++i){
    		//没有父节点且不等于第一小的才选择
    		if(T->data[i].parent == 0 && i != minIndex){
    			if(T->data[i].weight < secondMin){
    				secondMin = T->data[i].weight;
    				secondIndex = i;
    			}
    		}
    	}
    	//因为返回两个值,所以可以使用指针
    	int* res = (int*)malloc(sizeof(int)*2);
    	res[0] = minIndex;
    	res[1] = secondIndex;
    	return res;
    }

    有了这玩意之后,我们就可以很开心的来写一个构建Huffmna树的函数咯!

    //创建Huffman树
    void createHFTree(HFTree* T,int nn){
    	int* res;    //用于接收选择的两个最小结点
    	int min;     //第一小结点的下标
    	int secondMin;    //第二小结点的下标
    	int n = T->length * 2 - 1;
    
        //从下标n开始往后构建父子结点
    	for(int i = T->length; i < n;++i){
    		T->data[i].parent = 0;
    		res = selectMin(T);//选择两个最小的结点
    		min = res[0];
    		secondMin = res[1];
    
    		//给父节点赋值
    		T->data[i].weight = T->data[min].weight + T->data[secondMin].weight;
    		T->data[i].lchild = min;
    		T->data[i].rchild = secondMin;
    
    		//给儿子们赋值
    		T->data[min].parent = i;
    		T->data[secondMin].parent = i;
    		T->length++;
    	}
    	//为每个字符编码
    	Hfmcode(T,nn);
    }

    在创建完树之后呢,我们的树就会变成这样咯:

     发现变化了嘛?

    那么这个树的结构算是给我们给整出来了,但是每一个结点都还差自己的一个东西,那就是他们的Huffman编码!

    根据题意:哈夫曼树左分支标记为0,右分支标记为1,那么3个叶子结点的Huffman编码就如下:

     开始编写编码器:

    基本思路:

    我们可以从叶子节点开始回溯,创建一个字符串用来存Huffman编码,左孩子就接‘0’ 右孩子就接‘1’  直到回溯到的结点的父亲为0时停止,拿m来举例:

    最后得到的字符串为:01 这与我们的预期相反 所以我们要逆序将这个字符串加入到结点的哈夫曼编码项中,此时m这个叶子结点的code项就为:10 符合我们的预期!

    //Huffman编码器
    void Hfmcode(HFTree* T,int n){
    	//分别给n个字符编码
    	for(int k=0;k<n;k++){
    	//从0号位的叶子节点开始回溯
    	    int i = 0,j = 0;
    	    int ch = k;
    	    //记录单个字符的编码
    	    char str[MAX_INT];
    	    memset(str,'\0',MAX_INT);
    		int parent = T->data[k].parent;
    			for(i = n-1;parent != 0;i--){
    			//如果该左孩子与 回溯起点index相符
    				if(T->data[parent].lchild == ch){
    					str[j++] = '0';
    					ch = parent;
    					//向上回溯
    					parent = T->data[ch].parent;
    				}else{
    					//同上 右孩子.....
    					str[j++] = '1';
    					ch = parent;
    					parent = T->data[ch].parent;
    				}
    			}
    		int f = 0;
    		//因为是回溯编码,所以需要反转存入结点中
    		for(int s = j-1;s>=0;s--){
    			T->data[k].code[f] = str[s];
    			f++;
    		}
    	}
    }
    

    这时,我们的Huffman树就算是正式构建完毕,所有的结点都有了参数咯,那么我们不妨将它遍历出来看看!

    来写一个遍历函数吧:

    //递归遍历Huffman树 T->length-1为根结点
    void preOrder(HFTree* T,int index){
    	if(index != -1){
            //只遍历叶子结点
    		if(T->data[index].lchild == -1 || T->data[index].rchild == -1)
    			cout << T->data[index].Ch <<":"<<T->data[index].code<<endl;
    		preOrder(T,T->data[index].lchild);
    		preOrder(T,T->data[index].rchild);
    		
    	}
    }

    我们得到了这样的结果:

     嗯嗯,很好,接下来最后一件事情就是给题目给出的这一段谜语来个翻译就欧克!

    再来一个解码函数:

    //Huffman译码
    char* Decode(char* str,int length,HFTree* T){
    	int index = length - 1,ct = 0,j = 0;
    	char ch;
    	ch = str[0];
    	char* res = (char*)malloc(sizeof(char)*MAX_INT);
    	while(true){
    		//当密文字符为0时向左走
    		if(ch == '0'){
    			index = T->data[index].lchild;
    			//为1时向右走
    		}else if(ch == '1'){
    			index = T->data[index].rchild;
    		}
    		//直到遍历到叶子节点
    		if(T->data[index].lchild == -1 || T->data[index].rchild == -1){
    			//此时的字符值即为这一段密文的密码字符
    			res[ct] = T->data[index].Ch;
    			ct++;
    			//回到根结点
    			index = length-1;
    		}
    		//记录当前遍历密文的位置
    		j++;
    		ch = str[j];
    		//当走完时直接及解码完成 退出循环
    		if(j == (int)strlen(str))
    			break;
    	}
    	return res;
    }

    ok大功告成,我们来看看结果吧!

    okok,非常不错,直接上PTA:

     

     全过咯!

    完整代码:

    #include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    #define MAX_INT 1000
    #define MAX_Double (numeric_limits<double>::max)()
    
    using namespace std;
    
    //Huffman树结点结构体
    typedef struct TreeNode{
    	double weight;//因为频率有可能为小数,所以用double
    	char Ch;//用于存放该节点字符
    	char *code;//用于存放该字符的 Huffman编码
    	int parent,lchild,rchild;//存放每个结点的 父节点 以及 子结点
    }TreeNode;
    
    //Huffman树结构体
    typedef struct HFTree{
    	TreeNode* data;//用堆实现该Huffman树
    	int length;//该树总结点的个数
    }HFTree;
    
    //初始化哈夫曼树
    HFTree* initTree(double* weight,char* ch,int n){
    	HFTree* T = (HFTree*)malloc(sizeof(HFTree));
    	//根据性质,n个结点生成的Huffman树会有2*n-1个结点
    	T->data = (TreeNode*)malloc(sizeof(TreeNode)*(2*n-1));
    	T->length = n;
    	
    	//初始化每个结点
    	for(int i = 0; i < n; ++i){
    		T->data[i].Ch = ch[i];
    		T->data[i].weight = weight[i];
    		T->data[i].parent = 0;
    		T->data[i].lchild = -1;
    		T->data[i].rchild = -1;
    		
    		//初始化每个结点的code数组
    		T->data[i].code = (char*)malloc(sizeof(char)*MAX_INT);
    		memset(T->data[i].code,'\0',MAX_INT);	
    	}
    	return T;
    }
    
    //选择两个权值最小的结点
    int* selectMin(HFTree* T){
    	//定义两个哨兵变量,他们的值为double所表示的最大值
    	//(numeric_limits<double>::max)();
    	double min = MAX_Double;
    	double secondMin = MAX_Double;
    	//两个最小结点的下标
    	int minIndex;
    	int secondIndex;
    	//先选择第一小的结点
    	for(int i=0;i<T->length;++i){
    		//只要没有父节点就可以选择
    		if(T->data[i].parent == 0){
    			if(T->data[i].weight < min){
    				min = T->data[i].weight;
    				minIndex = i;
    			}
    		}
    	}
    	//其次选择第二小的结点
    	for(int i =0;i<T->length;++i){
    		//没有父节点且不等于第一小的才选择
    		if(T->data[i].parent == 0 && i != minIndex){
    			if(T->data[i].weight < secondMin){
    				secondMin = T->data[i].weight;
    				secondIndex = i;
    			}
    		}
    	}
    	//因为返回两个值,所以可以使用指针
    	int* res = (int*)malloc(sizeof(int)*2);
    	res[0] = minIndex;
    	res[1] = secondIndex;
    	return res;
    }
    
    //Huffman编码器
    void Hfmcode(HFTree* T,int n){
    	//分别给n个字符编码
    	for(int k=0;k<n;k++){
    	//从0号位的叶子节点开始回溯
    	    int i = 0,j = 0;
    	    int ch = k;
    	    //记录单个字符的编码
    	    char str[MAX_INT];
    	    memset(str,'\0',MAX_INT);
    		int parent = T->data[k].parent;
    			for(i = n-1;parent != 0;i--){
    			//如果该左孩子与 回溯起点index相符
    				if(T->data[parent].lchild == ch){
    					str[j++] = '0';
    					ch = parent;
    					//向上回溯
    					parent = T->data[ch].parent;
    				}else{
    					//同上 右孩子.....
    					str[j++] = '1';
    					ch = parent;
    					parent = T->data[ch].parent;
    				}
    			}
    		int f = 0;
    		//因为是回溯编码,所以需要反转
    		for(int s = j-1;s>=0;s--){
    			T->data[k].code[f] = str[s];
    			f++;
    		}
    	}
    }
    
    //创建Huffman树
    void createHFTree(HFTree* T,int nn){
    	int* res;
    	int min;
    	int secondMin;
    	int n = T->length * 2 - 1;
    	for(int i = T->length; i < n;++i){
    		T->data[i].parent = 0;
    		res = selectMin(T);
    		min = res[0];
    		secondMin = res[1];
    		//给父节点赋值
    		T->data[i].weight = T->data[min].weight + T->data[secondMin].weight;
    		T->data[i].lchild = min;
    		T->data[i].rchild = secondMin;
    		//给儿子们赋值
    		T->data[min].parent = i;
    		T->data[secondMin].parent = i;
    		T->length++;
    	}
    	
    	//为每个字符编码
    	Hfmcode(T,nn);
    }
    
    //递归遍历Huffman树 T->length-1为根结点
    void preOrder(HFTree* T,int index){
    	if(index != -1){
    		if(T->data[index].lchild == -1 || T->data[index].rchild == -1)
    			cout << T->data[index].Ch <<":"<<T->data[index].code<<endl;
    		preOrder(T,T->data[index].lchild);
    		preOrder(T,T->data[index].rchild);
    		
    	}
    }
    
    //Huffman译码
    char* Decode(char* str,int length,HFTree* T){
    	int index = length - 1,ct = 0,j = 0;
    	char ch;
    	ch = str[0];
    	char* res = (char*)malloc(sizeof(char)*MAX_INT);
    	while(true){
    		//当密文字符为0时向左走
    		if(ch == '0'){
    			index = T->data[index].lchild;
    			//为1时向右走
    		}else if(ch == '1'){
    			index = T->data[index].rchild;
    		}
    		//直到遍历到叶子节点
    		if(T->data[index].lchild == -1 || T->data[index].rchild == -1){
    			//此时的字符值即为这一段密文的密码字符
    			res[ct] = T->data[index].Ch;
    			ct++;
    			//回到根结点
    			index = length-1;
    		}
    		//记录当前遍历密文的位置
    		j++;
    		ch = str[j];
    		//当走完时直接及解码完成 退出循环
    		if(j == (int)strlen(str))
    			break;
    	}
    	return res;
    }
    
    
    int main(){
    	//输入n个字符
    	int n;
    	scanf("%d",&n);
    	getchar();
    	
    	//初始化n个 char和double类型的数组 用于存放 字符和对应的频率
    	char* chNums = (char*)malloc(sizeof(char)*n);
    	double* nuNums = (double*)malloc(sizeof(double)*n);
    	
    	//输入 字符以及相应的频率
    	for(int i=0;i<n;++i){
    		scanf("%c%lf",&chNums[i],&nuNums[i]);
    		getchar();
    	}
    	
    	//输入 需要译码的字符串
    	char str[MAX_INT];
    	scanf("%s",str);
    	getchar();
    	//创建一棵Huffman树
    	HFTree* T = initTree(nuNums,chNums,n);
    	createHFTree(T,n);
    	//遍历每个字符及其编码
    	preOrder(T,T->length-1);
    	//遍历解码后的密文
    	cout<<"original:"<<Decode(str,T->length,T)<<endl;
    	
    	return 0;
    }

    博主的编程水平比较菜,写这一题花了挺长时间的,主要卡在了给每个字符编码,但是在写完了编码函数提交之后,第一个测试点不通过,以为是自己的思路有问题,而且PTA也不给测试点的数据,搞得不知道哪里出问题了,改了好几天,最后发现,原来是在判断最小的两个结点时,哨兵的值设置的太小,然后测试点给了一个很大的频率,导致一直没过,也是随便改改提交突然全过了,算是乱碰给碰出来了hhh,发出来给大家借鉴一下,加油!

    展开全文
  • 一、实验目的和要求 目的:1、掌握二叉链表上实现二叉树基本操作...3、理解哈夫曼树的构造算法,学习设计哈夫曼编码译码系统 要求:能成功演示二叉树的有关算法,运算完毕后能成功释放二叉树所有结点占用的系统类存。
  • (3)利用已经建立好的哈夫曼树将 HuffmanCode.txt 中的哈夫曼编码进行译码,结果 存入到 HuffmanText.txt 中。 (4)能够按照垂直输出二叉树的方式,将存储在 HuffmanTree.txt 纯文本文件中的哈 夫曼树垂直输出。并且在...
  • 哈夫曼编码译码器实验报告.rar
  • 设计一个利用哈夫曼算法的编码译码系统,重复地显示并处理以下项目,直到选择退出为止。 基本要求: (1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中) (2)分别采用动态和静态存储...
  • 按词频从小到大的顺序给出各个字符(不超过30个)的词频,根据词频构造哈夫曼树,给出每个字符的哈夫曼编码,并对给出的语句进行译码。为确保构建的哈夫曼树唯一,本题做如下限定: (1)选择根结点权值最小的两棵...
  • 通过读取文件data.txt编译,输出有字符频度表,哈夫曼树,编码表,把编码保存到文件中,再读取文件进行译码。此压缩包内涵使用方法,代码。运行:VS2010 语言:C
  • 用c语言实现的哈夫曼编码译码器,是数据结构中的经典案例。里面含有设计报告和源代码。把好的东西贡献出来,供大家参考一下。
  • 哈夫曼编码译码器实验报告(免费).doc
  • 哈夫曼编码译码系统实验报告,数据结构课程设计.docx哈夫曼编码译码系统实验报告,数据结构课程设计.docx哈夫曼编码译码系统实验报告,数据结构课程设计.docx哈夫曼编码译码系统实验报告,数据结构课程设计.docx哈夫曼...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,911
精华内容 1,564
关键字:

哈夫曼编码译码