精华内容
下载资源
问答
  • 哈夫曼译码
    2018-06-14 17:27:22

    通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数void ccode(haffnode  hafftree[],int n)即可。

    const int maxvalue=100;

    const int maxbit=100;

    const int maxn=100;

     #include "iostream"

    #include "stdio.h"

    #include "stdlib.h"

    using namespace std;

    struct haffnode

    {

     char ch; 

    int weight; 

    int flag; 

    int parent;

     int leftchild; 

    int rightchild;

    };

    struct code

    int bit[maxn];

     int start;

     int weight; 

    char ch;

    }; 

    void haffman(int weight[],char text[],int n,haffnode hafftree[])

    int j,m1,m2,x1,x2,i; 

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

    if(i < n) 

    hafftree[i].weight=weight[i]; 

    hafftree[i].

    ch=text[i];

     } 

    else

     { 

    hafftree[i].weight=0; 

    hafftree[i].ch='#'; 

    hafftree[i].parent=0;

     hafftree[i].flag=0;

     hafftree[i].leftchild=-1;

     hafftree[i].rightchild=-1;

     } 

    for(i=0;i< n-1;i++) 

    m1=m2=maxvalue;

     x1=x2=0; 

    for(j=0;j< n+i;j++) 

    if(hafftree[j].weight< m1&&hafftree[j].flag==0) 

    m2=m1;

     x2=x1;

     m1=hafftree[j].weight;

     x1=j; 

    else if(hafftree[j].weight< m2&&hafftree[j].flag==0)

     { 

    m2=hafftree[j].weight; x2=j;

     } 

    hafftree[x1].parent=n+i; 

    hafftree[x2].parent=n+i;

     hafftree[x1].flag=1; 

    hafftree[x2].flag=1; 

    hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight; 

    hafftree[n+i].leftchild=x1; hafftree[n+i].rightchild=x2;

     } 

    void haffmancode(haffnode hafftree[],int n,code haffcode[])

    code cd; int i,j; int child,parent;

     for( i=0;i< n;i++)

     { 

    cd.start=n-1; 

    cd.weight=hafftree[i].weight; 

    cd.ch=hafftree[i].ch; 

    child=i; 

    parent=hafftree[child].parent; 

    while(parent!=0)

     { 

    if(hafftree[parent].leftchild==child) 

    cd.bit[cd.start]=0; 

    else cd.bit[cd.start]=1; 

    cd.start--; 

    child=parent; 

    parent=hafftree[child].parent; 

    for(j=cd.start+1;j< n;j++) 

    haffcode[i].bit[j]=cd.bit[j];

     haffcode[i].start=cd.start;

     haffcode[i].weight=cd.weight; 

    haffcode[i].ch=cd.ch;

     } 

    void ccode(haffnode hafftree[],int n)

    { }

     int main( )

    int n=8; 

    int weight[]={5,29,7,8,14,23,3,11};

     char text[]={'a','b','c','d','e','f','g','h'}; 

    haffnode myhafftree[maxvalue]; 

    code myhaffcode[maxvalue];

     haffman(weight,text,n,myhafftree);

     haffmancode(myhafftree,n,myhaffcode); 

    ccode(myhafftree,n); 

    return 0;

    }

    输入

    
     

    根据哈夫曼树编码表,针对字符串做好的编码结果。

    根据哈夫曼树编码表,针对字符串做好的编码结果。

    输出

    对每一行需要解码的串,进行解码,并输出解码后的结果。
    

    对每一行需要解码的串,进行解码,并输出解码后的结果。

    样例输入

    000100011011101110

    样例输出

    aabcc
    #include "iostream" 
    #include "string"
    #include "stdio.h" 
    #include "stdlib.h" 
    using namespace std; 
       
    const int maxvalue=100; 
    const int maxbit=100; 
    const int maxn=100; 
       
    struct haffnode 
    { 
        char ch; 
        int weight; 
        int flag; 
        int parent; 
        int leftchild; 
        int rightchild; 
    }; 
       
    struct code 
    { 
        int bit[maxn]; 
        int start; 
        int weight; 
        char ch; 
    }; 
       
    void haffman(int weight[],char text[],int n,haffnode hafftree[]) 
    { 
        int j,m1,m2,x1,x2,i; 
           
        for(i=0;i< 2*n-1;i++) 
        { 
            if(i < n) 
            { 
                hafftree[i].weight=weight[i]; 
                hafftree[i].ch=text[i]; 
            } 
            else 
            { 
                   
                hafftree[i].weight=0; 
                hafftree[i].ch='#'; 
            } 
            hafftree[i].parent=0; 
            hafftree[i].flag=0; 
            hafftree[i].leftchild=-1; 
            hafftree[i].rightchild=-1; 
               
        } 
        for(i=0;i< n-1;i++) 
        { 
            m1=m2=maxvalue; 
            x1=x2=0; 
            for(j=0;j< n+i;j++) 
            { 
                if(hafftree[j].weight< m1&&hafftree[j].flag==0) 
                { 
                    m2=m1; 
                    x2=x1; 
                    m1=hafftree[j].weight; 
                    x1=j; 
                } 
                   
                else if(hafftree[j].weight< m2&&hafftree[j].flag==0) 
                { 
                    m2=hafftree[j].weight; 
                    x2=j; 
                } 
            } 
            hafftree[x1].parent=n+i; 
            hafftree[x2].parent=n+i; 
            hafftree[x1].flag=1; 
            hafftree[x2].flag=1; 
            hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight; 
            hafftree[n+i].leftchild=x1; 
            hafftree[n+i].rightchild=x2; 
        } 
           
    } 
       
       
    void haffmancode(haffnode hafftree[],int n,code haffcode[]) 
    { 
        code cd; 
        int i,j; 
        int child,parent; 
        for( i=0;i< n;i++) 
        { 
            cd.start=n-1; 
            cd.weight=hafftree[i].weight; 
            cd.ch=hafftree[i].ch; 
            child=i; 
            parent=hafftree[child].parent; 
               
            while(parent!=0) 
            { 
                if(hafftree[parent].leftchild==child) 
                    cd.bit[cd.start]=0; 
                else 
                    cd.bit[cd.start]=1; 
                cd.start--; 
                child=parent; 
                parent=hafftree[child].parent; 
            } 
               
            for(j=cd.start+1;j< n;j++) 
                haffcode[i].bit[j]=cd.bit[j]; 
            haffcode[i].start=cd.start; 
            haffcode[i].weight=cd.weight; 
            haffcode[i].ch=cd.ch; 
        } 
           
    } 
       
    void ccode(haffnode hafftree[],int n) 
    { 
        string str; cin >> str;
        int pt = 0;
        while (hafftree[pt].parent != 0)
        {
            pt = hafftree[pt].parent;
        }
        for (int i = 0; i < str.length(); i++)
        {
            int current = pt, child;
       
            while (1)
            {
                if(str[i] - '0' == 0) child = hafftree[current].leftchild;
                else child = hafftree[current].rightchild;
                   
                current = child;
       
                if(hafftree[current].leftchild == -1 && 
                    hafftree[current].rightchild == -1) 
                {
                    cout << hafftree[current].ch;
                    break;
                }
                else
                {
                    i++;
                }
            }
               
        }
    } 
       
       
    int main( ) 
    { 
        int n=8; 
        int weight[]={5,29,7,8,14,23,3,11}; 
        char text[]={'a','b','c','d','e','f','g','h'}; 
        haffnode myhafftree[maxvalue]; 
        code myhaffcode[maxvalue]; 
        haffman(weight,text,n,myhafftree); 
        haffmancode(myhafftree,n,myhaffcode); 
        ccode(myhafftree,n); 
        return 0; 
    }

    更多相关内容
  • 拥有界面的哈夫曼译码器,可以自行输入字符及其频度来生成哈夫曼树,生成树之后可以做译码及编码操作。另外附带二叉树的三种遍历(树的存储方式为左孩子右兄弟),能够进行树与二叉树之间的相互转换。
  • 哈夫曼译码流程图

    2014-03-28 18:52:33
    哈夫曼译码流程图,数据结构课程设计需要,用visio画的
  • 986: 哈夫曼译码

    2021-05-08 12:39:03
    (建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数void ccode(haffnode hafftree[],int n)即可。 题目给出的代码如下,已经过格式调整与注释: const int maxvalue=100; const int maxbit=100; ...

    题目描述
    通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数void ccode(haffnode hafftree[],int n)即可。

    题目给出的代码如下,已经过格式调整与注释:

    const int maxvalue=100;
    const int maxbit=100;
    const int maxn=100;
    #include "iostream"
    #include "stdio.h"
    #include "stdlib.h"
    #include<string.h>
    using namespace std;
    struct haffnode
    {
        char ch;
        int weight;
        int flag;
        int parent;
        int leftchild;
        int rightchild;
    };
    struct code
    {
        int bit[maxn];
        int start;
        int weight;
        char ch;
    };
    void haffman(int weight[],char text[],int n,haffnode hafftree[])
    {
        int j,m1,m2,x1,x2,i;
        //i、j是下标
        //m1,m2是两个最小值,更小的为左子树的值
        //较大的是右子树的值
        //x1是左子树,x2是右子树
        for(i=0;i<2*n-1;i++)
        {
            if(i < n)//前n个是叶子结点,有权值和结点值
            {
                hafftree[i].weight=weight[i];
                hafftree[i].ch=text[i];
            }
            else// [n,2*n-2] 是双亲结点,初始时没有权值,结点值置为‘#’号
            {
                hafftree[i].weight=0;
                hafftree[i].ch='#';
            }
            //每个结点的其余数据都置初值
            hafftree[i].parent=0;
            hafftree[i].flag=0;
            hafftree[i].leftchild=-1;
            hafftree[i].rightchild=-1;
        }
        for(i=0;i<n-1;i++)
        {
            m1=m2=maxvalue;
            //两个最小值置为最大值,待会好比较
            x1=x2=0;
            //左右子树
            for(j=0;j<n+i;j++)//从中取出两个权值最小的点
            {
                if(hafftree[j].weight< m1&&hafftree[j].flag==0)//并且未被访问
                {
                    //遇到更小的m1(左子树权值)
                    //则把前一个m1的值给m2,因为要满足左子树比右子树小
                    m2=m1;
                    x2=x1;
                    m1=hafftree[j].weight;
                    x1=j;
                }
                else if(hafftree[j].weight< m2&&hafftree[j].flag==0)
                {
                    m2=hafftree[j].weight; x2=j;
                }
            }
                //选出两个子结点,构成一个父结点
                hafftree[x1].parent=n+i;
                hafftree[x2].parent=n+i;
                hafftree[x1].flag=1;//标志已访问
                hafftree[x2].flag=1;//标志已访问
                hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
                //父节点权重
                hafftree[n+i].leftchild=x1; hafftree[n+i].rightchild=x2;
                //父节点的左右子树
        }
    
    }
    
    void haffmancode(haffnode hafftree[],int n,code haffcode[])
    {
        code cd;//临时哈夫曼编码
        int i,j;
        int child,parent;
        for(i=0;i<n;i++)//一共n个叶子节点
        {
            cd.start=n-1;//从该叶子结点开始,从下往上遍历树
            cd.weight=hafftree[i].weight;
            cd.ch=hafftree[i].ch;
            child=i;
            parent=hafftree[child].parent;
            while(parent!=0)//从下往上,到根节点为止
            {
                //哈夫曼树转编码时,左子树为0,右子树为1
                if(hafftree[parent].leftchild==child)//当前子树是左子树
                cd.bit[cd.start]=0;
                else cd.bit[cd.start]=1;
                cd.start--;
                child=parent;//往上
                parent=hafftree[child].parent;
            }
            for(j=cd.start+1;j<n;j++)//从头开始设置该根节点的哈夫曼编码的值
            haffcode[i].bit[j]=cd.bit[j];
    
            haffcode[i].start=cd.start;
            haffcode[i].weight=cd.weight;
            haffcode[i].ch=cd.ch;
        }
    
    }
    
    void ccode(haffnode hafftree[],int n)
    {
    
    }
    
    int main( )
    {
        int n=8;
        int weight[]={5,29,7,8,14,23,3,11};
        char text[]={'a','b','c','d','e','f','g','h'};
        haffnode myhafftree[maxvalue];
        //maxvalue个哈夫曼结点构成一棵哈夫曼树
        code myhaffcode[maxvalue];
        haffman(weight,text,n,myhafftree);
        //先得出哈夫曼树
        haffmancode(myhafftree,n,myhaffcode);
        //根据哈夫曼树来创建哈夫曼编码
        ccode(myhafftree,n);
        //打表
        return 0;
    
    }
    
    

    题目说:”你只需要填写译码函数void ccode(haffnode hafftree[],int n)即可。“
    但题目代码中又有
    struct node
    code myhaffcode[maxvalue]
    haffmancode(myhafftree,n,myhaffcode)
    这里用不上这些数据。
    把哈弗曼树创建起来,就可以解码了。所谓解码,是指从根结点出发,根据给出的解码符号是0还是1,选择走二叉树结点的左分支还是右分支。为什么根据0,1选左右分支呢?因为进行哈夫曼树编码时,左分支都置为0,右分支都置为1.故解码时,从根节点出发,可根据0,1判断走左分支还是右分支。一直走到叶子结点,即可输出数据。

    题目中的哈夫曼树如下图所示:
    在这里插入图片描述

    输入
    根据哈夫曼树编码表,针对字符串做好的编码结果。

    输出
    对每一行需要解码的串,进行解码,并输出解码后的结果。

    样例输入

    000100011011101110
    

    样例输出

    aabcc
    
    const int maxvalue=100;
    const int maxbit=100;
    const int maxn=100;
    #include "iostream"
    #include "stdio.h"
    #include "stdlib.h"
    #include<string.h>
    using namespace std;
    struct haffnode
    {
        char ch;
        int weight;
        int flag;
        int parent;
        int leftchild;
        int rightchild;
    };
    struct code
    {
        int bit[maxn];
        int start;
        int weight;
        char ch;
    };
    void haffman(int weight[],char text[],int n,haffnode hafftree[])
    {
        int j,m1,m2,x1,x2,i;
        //i、j是下标
        //m1,m2是两个最小值,更小的为左子树的值
        //较大的是右子树的值
        //x1是左子树,x2是右子树
        for(i=0;i<2*n-1;i++)
        {
            if(i < n)//前n个是叶子结点,有权值和结点值
            {
                hafftree[i].weight=weight[i];
                hafftree[i].ch=text[i];
            }
            else// [n,2*n-2] 是双亲结点,初始时没有权值,结点值置为‘#’号
            {
                hafftree[i].weight=0;
                hafftree[i].ch='#';
            }
            //每个结点的其余数据都置初值
            hafftree[i].parent=0;
            hafftree[i].flag=0;
            hafftree[i].leftchild=-1;
            hafftree[i].rightchild=-1;
        }
        for(i=0;i<n-1;i++)
        {
            m1=m2=maxvalue;
            //两个最小值置为最大值,待会好比较
            x1=x2=0;
            //左右子树
            for(j=0;j<n+i;j++)//从中取出两个权值最小的点
            {
                if(hafftree[j].weight< m1&&hafftree[j].flag==0)//并且未被访问
                {
                    //遇到更小的m1(左子树权值)
                    //则把前一个m1的值给m2,因为要满足左子树比右子树小
                    m2=m1;
                    x2=x1;
                    m1=hafftree[j].weight;
                    x1=j;
                }
                else if(hafftree[j].weight< m2&&hafftree[j].flag==0)
                {
                    m2=hafftree[j].weight; x2=j;
                }
            }
                //选出两个子结点,构成一个父结点
                hafftree[x1].parent=n+i;
                hafftree[x2].parent=n+i;
                hafftree[x1].flag=1;//标志已访问
                hafftree[x2].flag=1;//标志已访问
                hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
                //父节点权重
                hafftree[n+i].leftchild=x1; hafftree[n+i].rightchild=x2;
                //父节点的左右子树
        }
    
    }
    
    void haffmancode(haffnode hafftree[],int n,code haffcode[])
    {
        code cd;//临时哈夫曼编码
        int i,j;
        int child,parent;
        for(i=0;i<n;i++)//一共n个叶子节点
        {
            cd.start=n-1;//从该叶子结点开始,从下往上遍历树
            cd.weight=hafftree[i].weight;
            cd.ch=hafftree[i].ch;
            child=i;
            parent=hafftree[child].parent;
            while(parent!=0)//从下往上,到根节点为止
            {
                //哈夫曼树转编码时,左子树为0,右子树为1
                if(hafftree[parent].leftchild==child)//当前子树是左子树
                cd.bit[cd.start]=0;
                else cd.bit[cd.start]=1;
                cd.start--;
                child=parent;//往上
                parent=hafftree[child].parent;
            }
            for(j=cd.start+1;j<n;j++)//从头开始设置该根节点的哈夫曼编码的值
            haffcode[i].bit[j]=cd.bit[j];
    
            haffcode[i].start=cd.start;
            haffcode[i].weight=cd.weight;
            haffcode[i].ch=cd.ch;
        }
    
    }
    
    void ccode(haffnode hafftree[],int n)
    {
        int Treenode;
        char str[maxvalue];
        scanf("%s",str);
        int len=strlen(str);
        //此处长度不为n,长度为输入字符串的长度
        Treenode=2*n-2;
        for(int j=0;j<len;j++)
        {
            if(str[j]=='0')//为0朝左分支走
            {
                Treenode=hafftree[Treenode].leftchild;
            }else
            if(str[j]=='1')//为1朝右分支走
            {
                Treenode=hafftree[Treenode].rightchild;
            }
            if(hafftree[Treenode].leftchild==-1||hafftree[Treenode].rightchild==-1)//走到叶子结点即可输出符号
            {
                printf("%c",hafftree[Treenode].ch);
                Treenode=2*n-2;
            }
        }
    }
    
    int main( )
    {
        int n=8;
        int weight[]={5,29,7,8,14,23,3,11};
        char text[]={'a','b','c','d','e','f','g','h'};
        haffnode myhafftree[maxvalue];
        //maxvalue个哈夫曼结点构成一棵哈夫曼树
        code myhaffcode[maxvalue];
        haffman(weight,text,n,myhafftree);
        //先得出哈夫曼树
        haffmancode(myhafftree,n,myhaffcode);
        //根据哈夫曼树来创建哈夫曼编码
        ccode(myhafftree,n);
        //打表
        return 0;
    
    }
    
    
    展开全文
  • 题目描述 通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对...(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数void ccode(haffnode hafftree[],int n)即可。

    题目描述

    通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数void ccode(haffnode hafftree[],int n)即可。

    const int maxvalue=100;
    
    const int maxbit=100;
    
    const int maxn=100;
    
    #include "iostream"
    
    #include "stdio.h"
    
    #include "stdlib.h"
    
    using namespace std;
    
    struct haffnode
    
    {
    
    	char ch;
    	
    	int weight;
    	
    	int flag;
    	
    	int parent;
    	
    	int leftchild;
    	
    	int rightchild;
    
    };
    
    struct code
    
    {
    
    	int bit[maxn];
    	
    	int start;
    	
    	int weight;
    	
    	char ch;
    
    };
    
    void haffman(int weight[],char text[],int n,haffnode hafftree[])
    
    {
    
    	int j,m1,m2,x1,x2,i;
    	
    	for(i=0;i< 2*n-1;i++)
    
    {
    
    if(i < n)
    
    {
    
    	hafftree[i].weight=weight[i];
    	
    	hafftree[i].
    	
    	ch=text[i];
    
    }
    
    else
    
    {
    
    	hafftree[i].weight=0;
    	
    	hafftree[i].ch='#';
    
    }
    
    hafftree[i].parent=0;
    
    hafftree[i].flag=0;
    
    hafftree[i].leftchild=-1;
    
    hafftree[i].rightchild=-1;
    
    }
    
    for(i=0;i< n-1;i++)
    
    {
    
    m1=m2=maxvalue;
    
    x1=x2=0;
    
    for(j=0;j< n+i;j++)
    
    {
    
    if(hafftree[j].weight< m1&&hafftree[j].flag==0)
    
    {
    
    m2=m1;
    
    x2=x1;
    
    m1=hafftree[j].weight;
    
    x1=j;
    
    }
    
    else if(hafftree[j].weight< m2&&hafftree[j].flag==0)
    
    {
    
    m2=hafftree[j].weight; x2=j;
    
    }
    
    }
    
    hafftree[x1].parent=n+i;
    
    hafftree[x2].parent=n+i;
    
    hafftree[x1].flag=1;
    
    hafftree[x2].flag=1;
    
    hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
    
    hafftree[n+i].leftchild=x1; hafftree[n+i].rightchild=x2;
    
    }
    
    }
    
    void haffmancode(haffnode hafftree[],int n,code haffcode[])
    
    {
    
    code cd; int i,j; int child,parent;
    
    for( i=0;i< n;i++)
    
    {
    
    cd.start=n-1;
    
    cd.weight=hafftree[i].weight;
    
    cd.ch=hafftree[i].ch;
    
    child=i;
    
    parent=hafftree[child].parent;
    
    while(parent!=0)
    
    {
    
    if(hafftree[parent].leftchild==child)
    
    cd.bit[cd.start]=0;
    
    else cd.bit[cd.start]=1;
    
    cd.start--;
    
    child=parent;
    
    parent=hafftree[child].parent;
    
    }
    
    for(j=cd.start+1;j< n;j++)
    
    haffcode[i].bit[j]=cd.bit[j];
    
    haffcode[i].start=cd.start;
    
    haffcode[i].weight=cd.weight;
    
    haffcode[i].ch=cd.ch;
    
    }
    
    }
    
    void ccode(haffnode hafftree[],int n)
    
    { }
    
    int main( )
    
    {
    
    int n=8;
    
    int weight[]={5,29,7,8,14,23,3,11};
    
    char text[]={'a','b','c','d','e','f','g','h'};
    
    haffnode myhafftree[maxvalue];
    
    code myhaffcode[maxvalue];
    
    haffman(weight,text,n,myhafftree);
    
    haffmancode(myhafftree,n,myhaffcode);
    
    ccode(myhafftree,n);
    
    return 0;
    
    }
    
    

    输入

    根据哈夫曼树编码表,针对字符串做好的编码结果。

    输出

    对每一行需要解码的串,进行解码,并输出解码后的结果。

    样例输入

    000100011011101110

    样例输出

    aabcc

    参考程序

    #include<iostream>
    #include<cstring>
    using namespace std;
    typedef struct//哈夫曼树
    {
        char data;
        double weight;
        int parent;
        int lchild;
        int rchild;
    }HTNode;
     
    HTNode ht[3000];
    char code[1000];
    int n;
    void CreateHT()//构造哈弗曼树
    {
        int i,k,lnode,rnode;
        double minL,minR;
        for(i=0;i<2*n-1;i++)
            ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
        for(i=n;i<2*n-1;i++)
        {
            minL=minR=50000;
            lnode=rnode=-1;
            for(k=0;k<i;k++)
                if(ht[k].parent==-1)
                {
                    if(ht[k].weight<minL)
                    {
                        minR=minL;rnode=lnode;
                        minL=ht[k].weight;lnode=k;
                    }
                    else if(ht[k].weight<minR)
                    {  minR=ht[k].weight;rnode=k;}
                }
            ht[i].weight=ht[lnode].weight+ht[rnode].weight;
            ht[i].lchild=lnode;ht[i].rchild=rnode;
            ht[lnode].parent=ht[rnode].parent=i;
        }
    }
     
    void ccode()//解码
    {
        int L=strlen(code),i,root=14;
        for(i=0;i<L;i++)
        {
            if(code[i]=='0')
                root=ht[root].lchild;
            else if(code[i]=='1')
                root=ht[root].rchild;
            if(ht[root].lchild==-1)
            {
                cout<<ht[root].data;
                root=14;
            }
        }
    }
     
    int main()
    {
        int i;
        n=8;
        int weight[]={5,29,7,8,14,23,3,11};
        char data[]={'a','b','c','d','e','f','g','h'}; 
        for(i=0;i<n;i++)
        {
            ht[i].weight=weight[i];
            ht[i].data=data[i];
        }
        CreateHT();
        cin>>code;
        ccode();
        return 0;
    }
    
    
    

    注意

    该程序仅供学习参考!

    展开全文
  • hafuman.rar_哈夫曼译码

    2022-09-19 14:20:46
    实现哈夫曼编码和译码,具有很强大的健壮性和实用性。
  • swust.oj986: 哈夫曼译码

    千次阅读 2020-06-11 14:28:15
    986: 哈夫曼译码 题目描述 通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数void ccode...

    986: 哈夫曼译码
    题目描述

    通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数void ccode(haffnode hafftree[],int n)即可。

    输入

    根据哈夫曼树编码表,针对字符串做好的编码结果。

    输出

    对每一行需要解码的串,进行解码,并输出解码后的结果。

    样例输入

    000100011011101110

    样例输出

    aabcc

    void ccode(haffnode hafftree[], int n)
    {
        char in[1000] ; //输入的编码
        scanf("%s",&in);
        int m = 2 * n - 1;//二叉树节点数 
        int i = m - 1;
        char it;
        int z=strlen(in);
        for(int j=0;j<z;j++)
    //    for (string::const_iterator it = in.begin(); it != in.end(); ++it)
        {
        	it=in[j];
            if (it == '0') //为0则找左节点
            {
                i = hafftree[i].leftchild;
            }
            else  //否则找右节点
            {
                i = hafftree[i].rightchild;
            }
            if (hafftree[i].leftchild == -1)    //如果等于-1就输出
            {
                cout << hafftree[i].ch;
                i = m - 1;
            }
        }
    }
    

    哈夫曼树**

    定义:

    哈夫曼树是一种最优二叉树。给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树。 这个定义里面涉及到了几个陌生的概念,下面就是一颗哈夫曼树,我们来看图解答。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2b0FFuyQ-1591856815922)(https://github.com/wangkuiwu/datastructs_and_algorithm/blob/master/pictures/tree/huffman/01.jpg?raw=true)]

    (01) 路径和路径长度

    定义:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。 例子:100和80的路径长度是1,50和30的路径长度是2,20和10的路径长度是3。

    (02) 结点的权及带权路径长度

    定义:若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。 例子:节点20的路径长度是3,它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60。

    (03) 树的带权路径长度

    定义:树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。 例子:示例中,树的WPL= 1100 + 2*50* + 320 + 3**10 = 100 + 100 + 60 + 30 = 290。

    哈夫曼树的创建:

    假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,哈夫曼树的构造规则为:

    1. 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); 
    
    2. 在森林中选出根结点的权值最小的两棵树进行合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和; 
    
    3. 从森林中删除选取的两棵树,并将新树加入森林; 
    
    4. 重复(02)、(03)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
    

    以{5,6,7,8,15}为例,来构造一棵哈夫曼树。

    img

    第1步:创建森林,森林包括5棵树,这5棵树的权值分别是5,6,7,8,15。

    第2步:在森林中,选择根节点权值最小的两棵树(5和6)来进行合并,将它们作为一颗新树的左右孩子(谁左谁右无关紧要,这里,我们选择较小的作为左孩子),并且新树的权值是左右孩子的权值之和。即,新树的权值是11。 然后,将"树5"和"树6"从森林中删除,并将新的树(树11)添加到森林中。

    第3步:在森林中,选择根节点权值最小的两棵树(7和8)来进行合并。得到的新树的权值是15。 然后,将"树7"和"树8"从森林中删除,并将新的树(树15)添加到森林中。

    第4步:在森林中,选择根节点权值最小的两棵树(11和15)来进行合并。得到的新树的权值是26。 然后,将"树11"和"树15"从森林中删除,并将新的树(树26)添加到森林中。

    第5步:在森林中,选择根节点权值最小的两棵树(15和26)来进行合并。得到的新树的权值是41。 然后,将"树15"和"树26"从森林中删除,并将新的树(树41)添加到森林中。 此时,森林中只有一棵树(树41)。这棵树就是我们需要的哈夫曼树!

    应用:

    哈夫曼编码原理:

    能否使编码总长度更短呢?

    实际应用中各字符的出现频度不相同,用短(长)编码表示频率大(小)的字符,使得编码序列的总长度最小,使所需总空间量最少

    数据的最小冗余编码问题

    在上例中,若假设 A, B, C, D 的编码分别为 0,00,1,01,则电文 ‘ABACCDA’ 便为 ‘000011010’(共 9 位),但此编码存在多义性:可译为: ‘BBCCDA’、‘ABACCDA’、‘AAAACCACA’ 等。

    译码的惟一性问题

    要求任一字符的编码都不能是另一字符编码的前缀,这种编码称为前缀编码(其实是非前缀码)。 在编码过程要考虑两个问题,数据的最小冗余编码问题,译码的惟一性问题,利用最优二叉树可以很好地解决上述两个问题

    用二叉树设计二进制前缀编码

    以电文中的字符作为叶子结点构造二叉树。然后将二叉树中结点引向其左孩子的分支标 ‘0’,引向其右孩子的分支标 ‘1’; 每个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如此得到的即为二进制前缀编码。

    img

    编码: A:0, C:10,B:110,D:111 任意一个叶子结点都不可能在其它叶子结点的路径中。

    文件的编码和解码

    1、输入各字符和权值

    2、构造哈夫曼树

    3、进行哈夫曼编码

    4、查找树,得到各个字符的哈夫曼编码

    展开全文
  • OJ哈夫曼译码.cpp

    2021-06-03 12:15:54
    西南科技大学学生
  • 哈夫曼译码 swustoj

    千次阅读 2018-05-22 21:46:07
    哈夫曼译码 1000(ms) 10000(kb) 1570 / 3422通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写...
  • swustoj哈夫曼译码

    2019-05-03 22:27:32
    现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。 输入 根据哈夫曼树编码表,针对字符串做好的编码结果。 输出 对每一行需要解码的串,进行解码,并输出解码后的结果。 样例输入 ...
  • 哈夫曼编码译码--数据结构

    热门讨论 2011-12-08 20:24:53
    哈夫曼编码译码 包括默认编码 和 自定义编码 ...进行哈夫曼译码 \n") ; printf(" 5.退出哈夫曼操作 \n"); printf(" 请输入1.2.3.4.5 \n"); printf(" ---------------------------------------------\n");
  • 哈夫曼编码译码器.rar

    2020-07-11 15:53:03
    利用哈夫曼树生成最优编码,程序可以写文件,进而从写文件中再读取文件,然后对读取的文件进行哈夫曼编码,对文件进行编码,然后将编码文件存储成huf文件,然后再对huf文件进行译码译码后再将译码文件保存成txt...
  • 数据结构课程设计,哈夫曼译码器代码加报告文档
  • 哈夫曼编码译码

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

    千次阅读 2022-05-13 16:48:38
    哈夫曼编码/译码
  • 7-2 哈夫曼编码译码

    千次阅读 多人点赞 2022-03-09 23:09:30
    编写一个哈夫曼编码译码程序。 按词频从小到大的顺序给出各个字符(不超过30个)的词频,根据词频构造哈夫曼树,给出每个字符的哈夫曼编码,并对给出的语句进行译码。 为确保构建的哈夫曼树唯一,本题做如下限定:...
  • 哈夫曼编码与译码的c++实现,主要功能哈夫曼树的创建,可把数据转换为编码后存入文件,也可以对文件中的信息进行编码与译码,代码清晰整洁,源码内有详细的注释可辅助理解,功能符合课程设计的要求,并加以扩展。
  • 信息论哈夫曼编码译码程序,适用于多进制哈夫曼编译码。
  • 哈夫曼树 哈夫曼译码

    2010-12-07 11:00:36
    编—译码系统的设计 内容: 读入待编码的文字,统计各字符出现的频率 构造哈夫曼树 得到各字符的哈夫曼编码 对原文进行编码 发送、接收 还原(译码)收到的文字 利用哈夫曼树,从根到叶子读0、1序列,直到终止,再...
  • matlab哈夫曼译码

    2021-04-23 13:47:55
    信源编码和译码,而是事先规定一个 译码差错率的......2013 Vol.36 No.20 31 基于 Matlab 文本文件哈夫曼编解码仿真 王向鸿 (中国人民解放军 93995 部队,陕西 西安 摘 710306) 过程和特点, 采用 Matlab 软件编程........
  • 这是哈夫曼编码译码的vc程序,在vc++6.0下编译通过,并运行正确
  • 哈夫曼编码译码

    2017-12-29 23:10:39
    数据结构课程设计,实现哈夫曼编码,译码,打印哈夫曼
  • 哈夫曼编/译码器 问题描述:给定电文进行哈夫曼编码,给定编码进行哈夫曼译码。要求电文存储在文件1中,编码后的结果存储在文件2中,给定编码存储在文件3中,译码后的结果存储在文件4中。
  • const int maxvalue=100; const int maxbit=100; const int maxn=100; #include "iostream" #include "stdio.h" #include "stdlib.h" using namespace std;... ...
  • 哈夫曼译码/编码器

    2012-12-02 23:54:28
    本程序应用树的知识,可以进行哈夫曼译码与编码,操作简单
  • 哈夫曼编/译码的实现

    2022-01-05 13:40:50
    (4)对哈夫曼编码生成的二进制串进行译码。 2)要求编一菜单,根据选项逐个调用各函数执行,并在每一步后有适当的输出,以验证你编程序的正确性。 #include<iostream> #include<std
  • 哈夫曼编码/译码实现

    2010-11-14 18:23:51
    建立一个文本文件,统计该文件中各字符频率,...3.对编码文件进行译码(涉及到哈夫曼译码和写文件)。 4.输出要求:输出原文、译文、打印编码规则、打印哈夫曼树。 5.哈夫曼树构造时,要求左孩子的值比右孩子的值小
  • 实现哈夫曼编码译码,内含丰富注释,可以作为demo使用

空空如也

空空如也

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

哈夫曼译码