精华内容
下载资源
问答
  • 哈夫曼译码

    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 "iost...

    通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数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; 
    }

    展开全文
  • 哈夫曼树的创建,哈夫曼编码哈夫曼译码C语言实现代码 哈夫曼树的创建哈夫曼编码哈夫曼译码C语言实现代码markdown书写的html格式 如果需要将文件编码或译码,则应该加入文件操作,将文件的字符读入。其权重应该为...

    哈夫曼树的创建,对文件进行哈夫曼编码哈夫曼译码C语言实现代码下载(代码详细注释,便于理解):

    对文件进行哈夫曼编码哈夫曼译码C语言实现代码下载

    (课设题目)输入节点信息与权重,创建哈夫曼树,将编码信息存储至文件中,译码时从文件中再读取编码信息,对输入的二进制码串进行译码,C语言代码实现下载:

    创建哈夫曼树进行编码到文件并从文件读编码进行译码下载

    (课设题目)输入字符串从而计算字符串中每个字符出现的次数作为权重,依据节点信息和权重创建哈弗曼树,进行哈夫曼编码,再对二进制码串进行译码下载:

    输入字符串从而计算字符串中每个字符出现的次数_并创建哈弗曼树_并进行哈夫曼编码及译码代码下载devc++编译器版本

    输入字符串从而计算字符串中每个字符出现的次数_并创建哈弗曼树_并进行哈夫曼编码及译码代码下载vs编译器版本

    (课设题目)输入字符集及其权重生成哈弗曼树_并将树保存至文件_从文件读取哈弗曼树进行编码与译码C语言实现下载:

    输入字符集及其权重生成哈弗曼树_并将树保存至文件_从文件读取哈弗曼树进行编码与译码

    • 图例
      1.手动输入节点信息以及节点所对应的权值,创建哈弗曼树进行编码与译码
      在这里插入图片描述 在这里插入图片描述
      在这里插入图片描述 在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      2.输入一个字符串,计算字符串中每种字符出现的次数作为权重,创建哈弗曼树,并哈弗曼编码,再对二进制码串进行译码。
      在这里插入图片描述
      以上图例解释:
      这里写图片描述
    • 如果需要将文件编码或译码,则应该加入文件操作,将文件的字符读入。其权重应该为在整个文件中该字符所出现的次数。
    展开全文
  • 哈夫曼译码流程图

    2014-03-28 18:52:33
    哈夫曼译码流程图,数据结构课程设计需要,用visio画的
  • 拥有界面的哈夫曼译码器,可以自行输入字符及其频度来生成哈夫曼树,生成树之后可以做译码及编码操作。另外附带二叉树的三种遍历(树的存储方式为左孩子右兄弟),能够进行树与二叉树之间的相互转换。
  • 哈夫曼译码/编码器

    2012-12-02 23:54:28
    本程序应用树的知识,可以进行哈夫曼译码与编码,操作简单
  • 数据结构课程设计,哈夫曼译码器代码加报告文档
  • 哈夫曼译码 swustoj

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

    通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数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

    就是把他给的代码瞎改就a了;

    const int maxvalue=100;
    const int maxbit=100;
    const int maxn=100;
    #include "iostream"
    #include "stdio.h"
    #include "string.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 i,j=0,m=2*n-1;
        char b[maxn];
        memset(b,'\0',sizeof(b));
        i=m-1;                      
        scanf("%s",b);
        while(b[j]!='\0')
        {
            if(b[j]=='0')
                i=hafftree[i].leftchild;              
            else
                i=hafftree[i].rightchild;              
            if(hafftree[i].leftchild==-1)         
            {
                printf("%c",hafftree[i].ch);
                i=m-1;      
            }
            j++;
        }
    }
    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;
    }

    展开全文
  • 哈夫曼树 哈夫曼译码

    2010-12-07 11:00:36
    编—译码系统的设计 内容: 读入待编码的文字,统计各字符出现的频率 构造哈夫曼树 得到各字符的哈夫曼编码 对原文进行编码 发送、接收 还原(译码)收到的文字 利用哈夫曼树,从根到叶子读0、1序列,直到终止,再...
  • 986: 哈夫曼译码 题目描述 通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数void ccode...

    986: 哈夫曼译码

    题目描述
    通常要求根据给定的编码本对密文进行解码。现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。(建立哈夫曼树以及编码、主函数等都已经给出,你只需要填写译码函数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

    思路:

    • 我对哈夫曼的理解是,把哈夫曼比作是一个密码小本本,我们只有按照小本本上面的东西来翻译才能把特殊密码翻译出来。这道题相当于把小本本给了我们,我们只需要读懂小本本的编码方式按部就班的解码就能得出答案,总的来说其实并不难。

    由于题干中涉及到的只有哈夫曼解码,下面的内容中关于哈夫曼树的基本概念和构造方法只做简略介绍,重点讲解哈夫曼的解码过程:

    1. 解释题干中的代码(电脑喜欢的小本本)
    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;
    
    }
    
    
    1. 根据题干画出哈夫曼树的逻辑结构(人类喜欢的小本本)
      在这里插入图片描述
    2. 哈夫曼解码:从根节点开始,左走零,右走一,走到叶子节点就输出,重复以上步骤至编码解完。
    3. 完整答案:
    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;
    
    }
    
    
    

    感谢西南科技大学->拉图的分享
    以上方法仅供参考,欢迎互联网广大朋友们提出指正。

    展开全文
  • swust.oj986: 哈夫曼译码

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

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

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

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

    2014-06-23 09:46:42
    #include #include #include #include #define N 27 #define TYPE int typedef struct { TYPE w; int f,l,r; }HNode,*Htree; typedef struct { char c; char code[10]; }Hcode, *Huffman;...void creat_Huf
  • 字符集中的字符的使用频率是不同的(比如e和t的使用较之q和z要频繁得多),哈夫曼编码可以使得编码的总长最短,从而相同的位长可以传送更多的信息。本程序以下面的字符及使用频率为例:字符权值a0.12b0.40c0.15d0.08e...
  • const int maxvalue=100; const int maxbit=100; const int maxn=100; #include "iostream" #include "stdio.h" #include "stdlib.h" using namespace std;... ...
  • 实现哈夫曼编码译码,内含丰富注释,可以作为demo使用
  • 《数据结构C语言哈夫曼编码译码》由会员分享,可在线阅读,更多相关《数据结构C语言哈夫曼编码译码(16页珍藏版)》请在人人文库网上搜索。1、实训报告题 目: 哈夫曼树编码译码院 系: 信息工程系专 业: 计算机科学...
  • 哈夫曼编码译码系统

    2021-01-15 08:04:05
    文章目录实验目的实验设备与环境实验过程及结果分析1. 构造哈夫曼树2. SelectSmall函数3. 哈夫曼编码4. 哈夫曼译码5. 实验结果实验代码main.cppHuffman.h 实验目的 完成Huffman Tree 编码、译码系统的设计 自行设计...
  • C语言哈夫曼编码译码

    2009-12-12 13:28:42
    哈夫曼编码译码数据结构作业 数据结构作业哈夫曼编码译码哈夫曼编码译码
  • 哈夫曼编码译码

    2014-03-19 18:33:55
    哈夫曼编码译码,数据结构课程设计,C++语言
  • 哈夫曼译码

    2012-11-25 17:10:00
    哈夫曼编码文件的译码,若有比较好的方式或者有问题请留言。
  • 哈夫曼编码译码

    2017-12-29 23:10:39
    数据结构课程设计,实现哈夫曼编码,译码,打印哈夫曼

空空如也

空空如也

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

哈夫曼译码