哈夫曼编码的实验报告

今天药忘吃喽~ 2022-12-24 13:56 106阅读 0赞

### 哈夫曼编码实验报告 ###

##### 一、实验目的 #####

通过哈夫曼编、译码算法的实现，巩固二叉树及哈夫曼树相关知识的理解掌握，训练学生运用所学知识，解决实际问题的能力。

##### 二.实验内容 #####

已知每一个字符出现的频率，构造哈夫曼树，并设计哈夫曼编码。  
基本要求：  
（1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树；  
（2）打印每一个字符对应的哈夫曼编码。  
（3）对从终端读入的字符串进行编码，并显示编码结果。  
（4）对从终端读入的编码串进行译码，并显示译码结果。

##### 三、实验方案设计 #####

（对基本数据类型定义要有注释说明,解决问题的算法思想描述要完整，算法结构和程序功能模块之间的逻辑调用关系要清晰，关键算法要有相应的流程图，对算法的时间复杂度要进行分析）

**1.算法思想：**  
（1）构造两个结构体分别存储结点的字符及权值、哈夫曼编码值：

typedef struct
    {
        
     char ch;
     float weight;
     int lchild,rchild,parent;
    }hufmtree;  // 存储结点的字符及权值
    typedef struct
    {
        
     char bits[n];   //位串
     int start;      //编码在位串中的起始位置
     char ch;        //字符
    }codetype;  //存储哈夫曼编码值
    （2）读取前n个结点的字符及权值，建立哈夫曼树：
    void huffman(hufmtree tree[])//建立哈夫曼树
    {
        
     int i,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标
     float small1,small2,f;
     char c;
     for(i=0;i<m;i++)    //初始化
     {
        
      tree[i].parent=0;
      tree[i].lchild=-1;
      tree[i].rchild=-1;
      tree[i].weight=0.0;
     }
     printf("【依次读入前%d个结点的字符及权值(中间用空格隔开)】\n",n);
     for(i=0;i<n;i++)  //读入前n个结点的字符及权值
     {
        
      printf("输入第%d个字符和权值:",i+1);
      scanf("%c %f",&c,&f);
      getchar();
      tree[i].ch=c;
      tree[i].weight=f;
     }
     for(i=n;i<m;i++)      //进行n-1次合并，产生n-1个新结点
     {
        
      p1=0;p2=0;
      small1=maxval;small2=maxval;   //maxval是float类型的最大值
      for(j=0;j<i;j++)    //选出两个权值最小的根结点
       if(tree[j].parent==0)
        if(tree[j].weight<small1)
        {
        
         small2=small1;  //改变最小权、次小权及对应的位置
         small1=tree[j].weight;
         p2=p1;
         p1=j;
        }
        else
         if(tree[j].weight<small2)
         {
        
          small2=tree[j].weight;  //改变次小权及位置
          p2=j;
         }
      tree[p1].parent=i;
      tree[p2].parent=i;
      tree[i].lchild=p1;  //最小权根结点是新结点的左孩子
      tree[i].rchild=p2;  //次小权根结点是新结点的右孩子
      tree[i].weight=tree[p1].weight+tree[p2].weight;
     }
    }//哈夫曼树的建立

（2）读取前n个结点的字符及权值，建立哈夫曼树：

void huffman(hufmtree tree[])//建立哈夫曼树
    {
        
     int i,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标
     float small1,small2,f;
     char c;
     for(i=0;i<m;i++)    //初始化
     {
        
      tree[i].parent=0;
      tree[i].lchild=-1;
      tree[i].rchild=-1;
      tree[i].weight=0.0;
     }
     printf("【依次读入前%d个结点的字符及权值(中间用空格隔开)】\n",n);
     for(i=0;i<n;i++)  //读入前n个结点的字符及权值
     {
        
      printf("输入第%d个字符和权值:",i+1);
      scanf("%c %f",&c,&f);
      getchar();
      tree[i].ch=c;
      tree[i].weight=f;
     }
     for(i=n;i<m;i++)      //进行n-1次合并，产生n-1个新结点
     {
        
      p1=0;p2=0;
      small1=maxval;small2=maxval;   //maxval是float类型的最大值
      for(j=0;j<i;j++)    //选出两个权值最小的根结点
       if(tree[j].parent==0)
        if(tree[j].weight<small1)
        {
        
         small2=small1;  //改变最小权、次小权及对应的位置
         small1=tree[j].weight;
         p2=p1;
         p1=j;
        }
        else
         if(tree[j].weight<small2)
         {
        
          small2=tree[j].weight;  //改变次小权及位置
          p2=j;
         }
      tree[p1].parent=i;
      tree[p2].parent=i;
      tree[i].lchild=p1;  //最小权根结点是新结点的左孩子
      tree[i].rchild=p2;  //次小权根结点是新结点的右孩子
      tree[i].weight=tree[p1].weight+tree[p2].weight;
     }
    }//哈夫曼树的建立

（3）根据哈夫曼树求出哈夫曼编码：

void huffmancode(codetype code[],hufmtree tree[])//根据哈夫曼树求出哈夫曼编码
    //codetype code[]为求出的哈夫曼编码
    //hufmtree tree[]为已知的哈夫曼树
    {
        
     int i,c,p;
     codetype cd;   //缓冲变量
     for(i=0;i<n;i++)
     {
        
      cd.start=n;
      cd.ch=tree[i].ch;
      c=i;       //从叶结点出发向上回溯
      p=tree[i].parent;   //tree[p]是tree[i]的双亲
      while(p!=0)
      {
        
       cd.start--;
       if(tree[p].lchild==c)
        cd.bits[cd.start]='0';   //tree[i]是左子树，生成代码'0'
       else
        cd.bits[cd.start]='1';   //tree[i]是右子树，生成代码'1'
       c=p;
       p=tree[p].parent;
      }
      code[i]=cd;    //第i+1个字符的编码存入code[i]
     }
    }//求哈夫曼编码

（4）读入电文，根据哈夫曼树译码：

void decode(hufmtree tree[])//依次读入电文，根据哈夫曼树译码
    {
        
     int i,j=0;
     char b[maxsize];
     char endflag='2';    //电文结束标志取2
     i=m-1;             //从根结点开始往下搜索
     printf("输入发送的编码(以'2'为结束标志)：");
     gets(b);
     printf("译码后的字符为");
     while(b[j]!='2')
     {
        
      if(b[j]=='0')
       i=tree[i].lchild;   //走向左孩子
      else
       i=tree[i].rchild;   //走向右孩子
      if(tree[i].lchild==-1)     //tree[i]是叶结点
      {
        
       printf("%c",tree[i].ch);
       i=m-1;      //回到根结点
      }
      j++;
     }
     printf("\n");
     if(tree[i].lchild!=-1&&b[j]!='2')   //电文读完，但尚未到叶子结点
      printf("\nERROR\n");  //输入电文有错
    }//译码

**2.算法流程图：**  
(1)哈夫曼树译码流程图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center]

（2）总流程图：  
![在这里插入图片描述][20201128193658108.png_pic_center]

**3.算法时间复杂度：**  
（1）建立哈夫曼树时进行n-1次合并，产生n-1个新结点，并选出两个权值最小的根结点: O（n²）;  
（2）根据哈夫曼树求出哈夫曼编码: O（n²）;  
（3）读入电文，根据哈夫曼树译码: O(n).

**四、该程序的功能和运行结果**  
（至少有三种不同的测试数据和相应的运行结果，充分体现该程序的鲁棒性）  
1.输入字符A,B,C,D,E,F及其相应权值16、12、9、30、6、3：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center 1]

2.输入字符F,E,N,G,H,U,I及其相应权值30、12、23、22、12、7、9：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center 2]

3.输入字符A,B,C,D,E,F,G,H,I,G及其相应权值19、23、25、18、12、67、23、9、32、33：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center 3]  
完整代码：

#include<stdio.h>
    #define n 5  //叶子数目
    #define m (2*n-1)    //结点总数
    #define maxval 10000.0
    #define maxsize 100   //哈夫曼编码的最大位数
    typedef struct
    {
     char ch;
     float weight;
     int lchild,rchild,parent;
    }hufmtree;
    typedef struct
    {
     char bits[n];   //位串
     int start;      //编码在位串中的起始位置
     char ch;        //字符
    }codetype;
     
    void huffman(hufmtree tree[]);//建立哈夫曼树
    void huffmancode(codetype code[],hufmtree tree[]);//根据哈夫曼树求出哈夫曼编码
    void decode(hufmtree tree[]);//依次读入电文，根据哈夫曼树译码
     
    void main()
    {
     printf("                            ——哈夫曼编码——\n");
     printf("总共有%d个字符\n",n);
     hufmtree tree[m];
     codetype code[n];
     int i,j;//循环变量
     huffman(tree);//建立哈夫曼树
     huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码
     printf("【输出每个字符的哈夫曼编码】\n");
     for(i=0;i<n;i++)
     {
      printf("%c: ",code[i].ch);
      for(j=code[i].start;j<n;j++)
       printf("%c ",code[i].bits[j]);
      printf("\n");
     }
     printf("【读入电文，并进行译码】\n");
     decode(tree);//依次读入电文，根据哈夫曼树译码
    }
     
    void huffman(hufmtree tree[])//建立哈夫曼树
    {
     int i,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标
     float small1,small2,f;
     char c;
     for(i=0;i<m;i++)    //初始化
     {
      tree[i].parent=0;
      tree[i].lchild=-1;
      tree[i].rchild=-1;
      tree[i].weight=0.0;
     }
     printf("【依次读入前%d个结点的字符及权值(中间用空格隔开)】\n",n);
     for(i=0;i<n;i++)  //读入前n个结点的字符及权值
     {
      printf("输入第%d个字符为和权值",i+1);
      scanf("%c %f",&c,&f);
      getchar();
      tree[i].ch=c;
      tree[i].weight=f;
     }
     for(i=n;i<m;i++)      //进行n-1次合并，产生n-1个新结点
     {
      p1=0;p2=0;
      small1=maxval;small2=maxval;   //maxval是float类型的最大值
      for(j=0;j<i;j++)    //选出两个权值最小的根结点
       if(tree[j].parent==0)
        if(tree[j].weight<small1)
        {
         small2=small1;  //改变最小权、次小权及对应的位置
         small1=tree[j].weight;
         p2=p1;
         p1=j;
        }
        else
         if(tree[j].weight<small2)
         {
          small2=tree[j].weight;  //改变次小权及位置
          p2=j;
         }
      tree[p1].parent=i;
      tree[p2].parent=i;
      tree[i].lchild=p1;  //最小权根结点是新结点的左孩子
      tree[i].rchild=p2;  //次小权根结点是新结点的右孩子
      tree[i].weight=tree[p1].weight+tree[p2].weight;
     }
    }//huffman
     
    void huffmancode(codetype code[],hufmtree tree[])//根据哈夫曼树求出哈夫曼编码
    //codetype code[]为求出的哈夫曼编码
    //hufmtree tree[]为已知的哈夫曼树
    {
     int i,c,p;
     codetype cd;   //缓冲变量
     for(i=0;i<n;i++)
     {
      cd.start=n;
      cd.ch=tree[i].ch;
      c=i;       //从叶结点出发向上回溯
      p=tree[i].parent;   //tree[p]是tree[i]的双亲
      while(p!=0)
      {
       cd.start--;
       if(tree[p].lchild==c)
        cd.bits[cd.start]='0';   //tree[i]是左子树，生成代码'0'
       else
        cd.bits[cd.start]='1';   //tree[i]是右子树，生成代码'1'
       c=p;
       p=tree[p].parent;
      }
      code[i]=cd;    //第i+1个字符的编码存入code[i]
     }
    }//huffmancode
     
    void decode(hufmtree tree[])//依次读入电文，根据哈夫曼树译码
    {
     int i,j=0;
     char b[maxsize];
     char endflag='2';    //电文结束标志取2
     i=m-1;             //从根结点开始往下搜索
     printf("输入发送的编码(以'2'为结束标志)：");
     gets(b);
     printf("译码后的字符为");
     while(b[j]!='2')
     {
      if(b[j]=='0')
       i=tree[i].lchild;   //走向左孩子
      else
       i=tree[i].rchild;   //走向右孩子
      if(tree[i].lchild==-1)     //tree[i]是叶结点
      {
       printf("%c",tree[i].ch);
       i=m-1;      //回到根结点
      }
      j++;
     }
     printf("\n");
     if(tree[i].lchild!=-1&&b[j]!='2')   //电文读完，但尚未到叶子结点
      printf("\nERROR\n");  //输入电文有错
    }//decode

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a3c4bc70aa654efeb4eb158fc0f66524.png
[20201128193658108.png_pic_center]: /images/20221120/94c3f470fc0c428fbd3ab4d0f65d2f30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201128194128139.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201128194144665.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201128194200819.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pYW5uaWFueGk=,size_16,color_FFFFFF,t_70#pic_center