精华内容
下载资源
问答
  • 哈夫曼树编码实验报告.doc
  • 北邮数据结构实验哈夫曼树,含有报告以及源代码程序
  • 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本,试设计一个哈夫曼编码系统。
  • 压缩包中包含实验报告,运行视频,是数据结构实验课程作业,可以借鉴参考。其中功能包括输入字母及频率,然后生成相应的哈夫曼编码,然后编码txt文件中的文本,输出,并且会把输出结果存入文件。重新打开控制台,...
  • 数据结构课程 实验报告 实验名称 哈弗曼编码和译码 专业班级 电子信息科学与技术0904 姓 名 秦杰 学 号 1404090506 指导教师 胡志坤 2011年 11月 实验四哈夫曼编码和译码 实验目的和要求 掌握哈夫曼树的基本概念及其...
  • 哈夫曼树及其编码 数据结构课程设计 (源代码附实验报告) 已调试成功
  • 哈夫曼编码实验报告

    千次阅读 多人点赞 2020-11-28 19:49:24
    哈夫曼编码实验报告 一、实验目的         通过哈夫曼编、译码算法的实现,巩固二叉树及哈夫曼树相关知识的理解掌握,训练学生运用所学知识,解决实际问题的能力。 二.实验...

    哈夫曼编码实验报告

    一、实验目的

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

    二.实验内容

            已知每一个字符出现的频率,构造哈夫曼树,并设计哈夫曼编码。
    基本要求:
    (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)哈夫曼树译码流程图:
    在这里插入图片描述

    (2)总流程图:
    在这里插入图片描述

    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:

    在这里插入图片描述

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

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

    在这里插入图片描述
    完整代码:

    #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
    
    展开全文
  • 构建哈夫曼树,对其进行编码,实现译码功能,数据结构的实验报告。。
  • 哈夫曼编码实验报告 实验一 哈夫曼编码 一实验目的 1掌握哈夫曼编码原理 2熟练掌握哈夫曼树的生成方法 3理解数据编码压缩和译码输出编码的实 现 二实验要求 实现哈夫曼编码和译码的生成算法 三实验内容 先统计要压缩...
  • 哈夫曼树实验报告

    2013-12-29 10:09:38
    c++2010环境下的哈夫曼树实验报告并且里面附有完整的源代码工参考使用。
  • 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码
  • . 教育资料 软件学院设计性实验报告 专业...理解哈夫曼树的特征及其应用在对哈夫曼树进行理解的基础上构造哈夫曼树并用构造的哈夫曼树进行编码和译码通过该实验使学生对数据结构的应用有更深层次的理解 实验仪器或设备
  • 哈夫曼编码实验报告

    2014-12-15 19:08:19
    统计一篇文章中字母’a’~’z’(不分大小写)出现概率,对字母完成Huffman编码算法的设计与实现。
  • 数据结构哈夫曼树编码译码实验报告--15页.pdf
  • 2008 级数据结构实验报告 实验名称 实验三实现哈夫曼树 学生姓名 * 班 级 * 班内序号 * 学 号 * 日 期 2009 年 11 月 14 日 1实验要求 利用二叉树结构实现赫夫曼编 / 解码器 基本要求 1 初始化 (Init) 能够对输入的...
  • 2.根据哈夫曼树对字符进行哈夫曼编码,并保存这些编码。 三、实验原理、方法和手段  试构造出问题模型,并编程实现这一问题的求解。根据实验内容编程,上机调试、得出正确的运行程序;编译运行程序,观察运行情况...

     

    二、实验内容

    1.根据给出的字符以及这些字符的使用频率构建哈夫曼树。

    2.根据哈夫曼树对字符进行哈夫曼编码,并保存这些编码。

    三、实验原理、方法和手段

        试构造出问题模型,并编程实现这一问题的求解。根据实验内容编程,上机调试、得出正确的运行程序;编译运行程序,观察运行情况和输出结果。

    六、实验步骤

    1. 建立哈夫曼树的存储结构和哈夫曼编码的存储结构。

    2. 建立哈夫曼树的函数;

    3. 哈夫曼编码的函数;

    4.哈夫曼编码的解码函数

    5. 设计测试用例进行测试。

    七、实验报告

    记录数据结构与算法设计的过程及实验步骤、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。格式见实验报告模板。测试数据及测试结果请在上交的资料中写明。

    #include <stdio.h>
    #include <string.h>
    #define N 50
    #define M 2*N-1	
    const int INF=1e9+7;
    typedef struct//哈夫曼树的存储结构 
    {
    	char data[6];
    	double weight;	
    	int parent;	
    	int lchild;		
    	int rchild;		
    } HTNode;
    typedef struct//存放哈夫曼码存储结构 
    {
    	char cd[N];		
    	int start;
    } HCode;
    void CreateHT(HTNode ht[],int n0)	//建立哈夫曼树的函数 
    {	
    	int i,k,lnode,rnode;
    	double min1,min2;
    	for (i=0;i<2*n0-1;i++)		
    		ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
    	for (i=n0;i<=2*n0-2;i++)		
    	{	
    		min1=min2=INF;//min1存最小的权值,min2存次小权值		
    		lnode=rnode=-1;
    		for (k=0;k<i;k++)//寻找ht里面未使用的最小的两个数 
    			if (ht[k].parent==-1) 
    			{	
    				if(ht[k].weight<min1)
    				{	
    					min2=min1;//保证min1<=min2 
    					rnode=lnode;
    					min1=ht[k].weight;
    					lnode=k;
    				}
    				else if(ht[k].weight<min2)
    				{	
    					min2=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=i;
    		ht[rnode].parent=i;
    	}
    }
    
    void CreateHCode(HTNode ht[],HCode hcd[],int n0)	//构造哈夫曼树编码
    {	
    	int i,f,c;
    	HCode hc;
    	for (i=0;i<n0;i++)			
    	{	
    		hc.start=n0;c=i;
    		f=ht[i].parent;
    		while (f!=-1)				
    		{	
    			if (ht[f].lchild==c)
    				hc.cd[hc.start--]='0';
    			else				
    				hc.cd[hc.start--]='1';
    			c=f;
    			f=ht[f].parent;	
    		}
    		hc.start++;			
    		hcd[i]=hc;
    	}
    }
    
    void DispHCode(HTNode ht[],HCode hcd[],int n0) 
    {
    	int i,k,temp=0;
    	double sum=0;
    	int j;
    	printf("  输出");
    	for(i=0;i<8;i++)
    		printf("%s",ht[i].data);
    	printf("的哈夫曼编码:\n");
    	for (i=0;i<n0;i++)
    	{
    		printf("    %s:\t\t",ht[i].data);
    		for (k=hcd[i].start;k<=n0;k++)
    			printf("%c",hcd[i].cd[k]);
    		printf("\n"); 
    	}	
    }
    
    void Decode(HTNode ht[],char code[]) //解码 
    {
    	printf("\n\n  对“%s”解码:\n",code);
    	int p=ht[0].parent;
    	int m;//根 
    	while(p!=-1)//找到根 
    	{
    		m=p;
    		p=ht[m].parent;	
    	}
    	int t;
    	int a1=0,a2=0;
    	for(int i=0;i<strlen(code);)
    	{
    		a1=a2;
    		t=m;
    		while(ht[t].lchild!=-1&&ht[t].rchild!=-1&&i<strlen(code)) 
    		{
    			if(code[i]== '0')                
    				t=ht[t].lchild;           
    			else  if(code[i]== '1')             
    				t=ht[t].rchild;
    			i++;			    
    		}
    		a2=i;
    		if(t==-1||ht[t].lchild!=-1&&ht[t].rchild!=-1)
    		{
    			int j=i-1;
    			printf("   ");
    			for(int j=a1;j<a2;j++)
    				printf("%c",code[j]);
    			printf(":\t错误\n");
    		} 	
    		else
    		{
    			printf("   ");
    			for(int j=a1;j<a2;j++)
    				printf("%c",code[j]);
    			printf(":%6s\n",ht[t].data);
    		}			
    	} 
    	printf("\n");
    }
    int main()
    {
    	int n=8,i;		//n表示初始字符串的个数
    	char str[][2]={"a","b","c","d","e","f","g","h"};
    	double fnum[]={0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.1};
    	char code[40];
    	HTNode ht[M];//存哈夫曼树 
    	HCode hcd[N];//存哈夫曼编码 
    	for (i=0;i<n;i++) 
    	{
    		strcpy(ht[i].data,str[i]);
    		ht[i].weight=fnum[i];
    	}
    	CreateHT(ht,n);
    	CreateHCode(ht,hcd,n);
    	DispHCode(ht,hcd,n);
    	printf("\n");
    	printf("  请输入编码:"); 
    	scanf("%s",code);
    	Decode(ht,code);
    	return 1;
    }
     
    

     

    展开全文
  • 简单课程设计哈夫曼树编码译码实验报告,内容小白,大神请飘过。。。
  • 这是本人在《数据结构》课上的 “ 哈夫曼树编码和译码” 的实验报告及程序。建议手动敲一遍加深印象。
  • 昆明理工大学信息工程与自动化学院学生实验报告 2011 2012 学年 第 1 学期 课程名称算法设计与分析 开课实验室信自楼机房 444 2011 年 11 月 02 日 年级专业班 学号 姓名 成绩 实验项目名称 哈夫曼编码 指导教师 教 ...
  • 北京邮电大学信息与通信工程学院 第 PAGE 1页 北京邮电大学电信工程学院 第 PAGE 1页 2008级数据结构实验报告 实验名称 实验三实现哈夫曼树 学生姓名 * 班 级 * 班内序号 * 学 号 * 日 期 200 1实验要求 利用二叉树...
  • 哈夫曼树编码译码实验报告.doc
  • 数据结构哈夫曼树编码译码实验报告.doc
  • 哈夫曼编码实验报告C++实现

    千次阅读 2020-07-04 11:33:02
    1、主要数据类型与变量 1.1使用到的头文件 #include <... //map数据结构存储HT编码表 #include <queue> //构建的节点的优先性 #include <string> //字符串方便输入输出 #include <itera

    1、主要数据类型与变量

    1.1使用到的头文件

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <map>    //map数据结构存储HT编码表
    #include <queue>  //构建的节点的优先性
    #include <string> //字符串方便输入输出
    #include <iterator> //迭代器输出map展示
    #include <fstream> //读写文件
    

    1.2 使用类代替结构体,这里重载比较运算符,便于排序和构造优先队列。

    class HTNode{
    public:
        char ch; //字符
        int weight;//权重
        HTNode *left;//左孩子
        HTNode *right;//右孩子
        HTNode(int weight) : weight(weight) {}
        //重载比较运算符,便于排序,构造优先队列
        bool operator<(const HTNode &htnode) const{
            return weight > htnode.weight;
        }
        //两个构造函数
        HTNode(char ch, int weight, HTNode *left, HTNode *right) : ch(ch), weight(weight), left(left), right(right) {}
        HTNode(char ch, int weight) : ch(ch), weight(weight) {}
    };
    1.3函数结构说明
    /**
     * 通过优先队列构建赫夫曼树
     * @param queue
     */
    void CreateHuffmanTree(priority_queue<HTNode> &queue);
    /**
     * 通过字符串统计字符的频率
     * @param s 需要统计的源数据
     * @return 返回一个优先队列,方便赫夫曼树筛选最小节点
     */
    priority_queue<HTNode> count(string s);
    /**
     * 展示每个字符对应的权重
     * @param q 优先字符队列
     */
    void show(priority_queue<HTNode> q);
    /**
     * 通过路径读取文件
     * @param path 需要读的文件路径
     * @return //以字符串类型返回文件中的数据
     */
    string readFile(string path);
    /**
     * 根据路径写入文件
     * @param path 文件路径
     * @param data 需要写入文件的内容(字符串类型)
     */
    void writeFile(string path,string data);
    void writeFile(string path,char data);//重载写文件函数,以char类型写入
    static map<char,string> huffmanCode; //静态的全局变量map集合:key为字符,string为对应编码,用来作为编码表
    /**
     * 获取编码表,此处配合静态的Map集合存入编码
     * @param root 赫夫曼树的根节点
     * @param code 路径编码,右为1,左为0
     * @param prefix 到该节点的路径,因为使用递归,所以要传入地址
     */
    void getCodes(HTNode *root,string code,string &prefix);
    /**
     * 打印编码表
     * @param codes 通过map集合配合迭代器输出每个字符对应的编码
     */
    void printCode(map<char,string> codes);
    /**
     * 通过编码表和文件读取出的数据来生成->编码数据
     * @param codetTable 编码表
     * @param data 数据源
     * @return 返回字符串展示编码数据
     */
    string BecomeCode(map<char,string> codetTable,string data);
    /**
     * 解码:通过编码表和编码后的数据
     * @param codetTable 编码表
     * @param CodeData 编码数据
     */
    void deCode(map<char,string> codetTable,string CodeData);
    

    2、算法或程序模块

    2.1 程序流程解释:
    ①创建赫夫曼树:统计字符的频率由小到大放入优先队列,通过队列找出最小频率构建赫夫曼树。
    ②生成赫夫曼编码和赫夫曼编码后的数据:通过递归遍历赫夫曼树,通过Map集合创建编码表,再使用编码表和源数据生成编码后的数据。
    ③使用赫夫曼编码解码:通过查找编码后的数据配合编码表,通过查找方式输出对应的字符
    核心函数解释
    构造赫夫曼树:最小左右孩子的权重相加,生成父节点,然后父节点进队列

    /**
     * 创建赫夫曼树
     * @param queue 构造的节点队列
     * @return 返回哈夫曼树的根节点
     */
    void CreateHuffmanTree(priority_queue<HTNode> &queue){
        while (queue.size()>1){
            HTNode *left = new HTNode(queue.top()); queue.pop(); //队列弹出左右孩子
            HTNode *right = new HTNode(queue.top()); queue.pop();
            HTNode parent('R',left->weight + right->weight,left,right);//通过最小的两个节点权重相加构造父节点
            queue.push(parent);//父节点进队列
        }
    }
    
    统计每个字符出现的频率:字符范围是ASCALL:0-128
    priority_queue<HTNode> count(string s){
        int a[128] = {0};
        priority_queue<HTNode> queue;
        for (int i = 0; i < s.length();i++) {
            if (s[i] >= 0 && s[i] <= 127) { a[s[i]]++; }//筛选每个字符出现的频率
        }
        for (int i = 0; i < 128;i++) {
            if (a[i]!=0){ //如果有该字符那就进队列
                HTNode *htNode = new HTNode((char)i,a[i]);
                queue.push(*htNode);
            }
        }
        return queue;
    }
    这里使用了二叉树的DFS方法,进行递归搜索叶子节点,然后存入map编码表中
    /**
     * 获取编码表,此处配合静态的Map集合存入编码
     * @param root 赫夫曼树的根节点
     * @param code 路径编码,右为1,左为0
     * @param prefix 到该节点的路径,因为使用递归,所以要传入地址
     */
    void getCodes(HTNode *root,string code,string &prefix){
        string s=prefix;//拷贝该节点的路径
        s.append(code);/通过append方法连接该节点的路径
    //判断节点是否为空
        if(root){
    //如果不是叶子节点
            if (root->ch==82){
                getCodes(root->left,"0",s);//向左递归
                getCodes(root->right,"1",s);//向右递归
            }else{如果是叶子节点
                huffmanCode[root->ch] = s;
            }
        }
    }
    编码:字符串的append追加函数来连接源数据对应的编码表
    解码:双层循环移动指针来截取字符串,然后找到对应的编码表,输出字符到文件中
    string BecomeCode(map<char,string> codetTable,string data){
        string res="";
        for (int i = 0; i < data.length(); ++i) {
            res.append(codetTable[data[i]]); //主要使用了字符串的append追加函数来连接源数据对应的编码表
        }
      ...
    }
    void deCode(map<char,string> codetTable,string CodeData){
    		......  
        for (int i = 0; i < CodeData.length(); ++i) { //双指针循环截取字符串
            for (int j = 0; j < 10; ++j) {
                sub = CodeData.substr(i,j); //截取字符串:从i开始,截取j个字符
                it = codetTable.begin();
                while(it != codetTable.end()){
                    if(sub == it->second){
                        char s = it->first;
                        cout<<s;
                        writeFile("D:\\解码文件.txt",s);
                        i = j + i ; //移动指针
                        j = 0;//移动指针
                        break;
                    }
                    ++it;
     		......
    通过路径读文件和写文件
    string readFile(string path){
        ifstream ifs;
        ifs.open(path,ios::in);//1、创建输入流对象,并打开
        if (!ifs.is_open())
        {
            cout << "文件打开失败" << endl;return "";
        }
        string res;
        while (getline(ifs, res))
        {
            cout <<"读取的信息为: "<< res << endl;
        }
        ifs.close();//关闭文件
        return res;
    }
    // 写文件
    void writeFile(string path,string data)
    {
        //1、创建输出流对象,并打开
        ofstream ofs(path, ios::out);
        //2、写文件
        ofs<<data<<endl;
        //3、关闭文件
        ofs.close();
    }
    
    主程序main函数
    int main(){
        string s = readFile("D:\\源文件.txt");//打开数据源文件
        priority_queue<HTNode>  queue = count(s);//获取单词的频率,通过升序进入优先队列
        show(queue);//输出队列
        CreateHuffmanTree(queue);//创建赫夫曼树
        string bulid="";
        HTNode root = queue.top();//获取树根节点
        getCodes(&root,"",bulid);//开始生成编码表
        printCode(huffmanCode);//展示编码表
        string res = BecomeCode(huffmanCode,s);//生成编码数据
        writeFile("D:\\编码文件.txt",res);//写入生成的01数据放入编码文件
        deCode(huffmanCode,res);//将编码数据解码
        return 0;
    }.
    

    程序源代码

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <map>    //map数据结构存储HT编码表
    #include <queue>  //构建的节点的优先性
    #include <string> //字符串方便输入输出
    #include <iterator> //迭代器输出map展示
    #include <fstream> //读写文件
    using namespace std;
    class HTNode{
    public:
        char ch; //字符
        int weight;//权重
        HTNode *left;//左孩子
        HTNode *right;//右孩子
        HTNode(int weight) : weight(weight) {}
        //重载比较运算法,便于排序,构造优先队列
        bool operator<(const HTNode &htnode) const{
            return weight > htnode.weight;
        }
        //两个构造函数
        HTNode(char ch, int weight, HTNode *left, HTNode *right) : ch(ch), weight(weight), left(left), right(right) {}
        HTNode(char ch, int weight) : ch(ch), weight(weight) {}
    };
    /**
     * 通过优先队列构建赫夫曼树
     * @param queue
     */
    void CreateHuffmanTree(priority_queue<HTNode> &queue);
    /**
     * 通过字符串统计字符的频率
     * @param s 需要统计的源数据
     * @return 返回一个优先队列,方便赫夫曼树筛选最小节点
     */
    priority_queue<HTNode> count(string s);
    /**
     * 展示每个字符对应的权重
     * @param q 优先字符队列
     */
    void show(priority_queue<HTNode> q);
    /**
     * 通过路径读取文件
     * @param path 需要读的文件路径
     * @return //以字符串类型返回文件中的数据
     */
    string readFile(string path);
    /**
     * 根据路径写入文件
     * @param path 文件路径
     * @param data 需要写入文件的内容(字符串类型)
     */
    void writeFile(string path,string data);
    void writeFile(string path,char data);//重载写文件函数,以char类型写入
    static map<char,string> huffmanCode; //静态的全局变量map集合:key为字符,string为对应编码,用来作为编码表
    /**
     * 获取编码表,此处配合静态的Map集合存入编码
     * @param root 赫夫曼树的根节点
     * @param code 路径编码,右为1,左为0
     * @param prefix 到该节点的路径,因为使用递归,所以要传入地址
     */
    void getCodes(HTNode *root,string code,string &prefix);
    /**
     * 打印编码表
     * @param codes 通过map集合配合迭代器输出每个字符对应的编码
     */
    void printCode(map<char,string> codes);
    /**
     * 通过编码表和文件读取出的数据来生成->编码数据
     * @param codetTable 编码表
     * @param data 数据源
     * @return 返回字符串展示编码数据
     */
    string BecomeCode(map<char,string> codetTable,string data);
    /**
     * 解码:通过编码表和编码后的数据
     * @param codetTable 编码表
     * @param CodeData 编码数据
     */
    void deCode(map<char,string> codetTable,string CodeData);
    
    /**
     * 创建哈夫曼树
     * @param queue 构造的节点队列
     * @return 返回哈夫曼树的根节点
     */
    void CreateHuffmanTree(priority_queue<HTNode> &queue){
        while (queue.size()>1){
            HTNode *left = new HTNode(queue.top()); queue.pop();
            HTNode *right = new HTNode(queue.top()); queue.pop();
            HTNode parent('R',left->weight + right->weight,left,right);
            queue.push(parent);
        }
    }
    
    
    priority_queue<HTNode> count(string s){
        int a[128] = {0};
        priority_queue<HTNode> queue;
        for (int i = 0; i < s.length();i++) {
            if (s[i] >= 0 && s[i] <= 127) { a[s[i]]++; }
        }
        for (int i = 0; i < 128;i++) {
            if (a[i]!=0){
                HTNode *htNode = new HTNode((char)i,a[i]);
                queue.push(*htNode);
            }
        }
        return queue;
    }
    void show(priority_queue<HTNode> q){
        while(!q.empty()){
            HTNode node = q.top(); q.pop();
            cout<<node.ch<<": "<<node.weight<<endl;
        }
    }
    
    void getCodes(HTNode *root,string code,string &prefix){
        string s=prefix;
        s.append(code);
        if(root){
            if (root->ch==82){
                getCodes(root->left,"0",s);
                getCodes(root->right,"1",s);
            }else{
                huffmanCode[root->ch] = s;
            }
        }
    }
    void printCode(map<char,string> codes){
        map<char,string>::const_iterator it = codes.begin();
        while(it != codes.end()){
            cout<<"符号: "<<it->first<<"编码:"<<it->second<<endl;
            ++it;
        }
    }
    /**
     * 生成赫夫曼编码数据
     * @param codes 赫夫曼编码表
     * @param data 需要编码的字符串
     * @return
     */
    string BecomeCode(map<char,string> codetTable,string data){
        string res="";
        for (int i = 0; i < data.length(); ++i) {
            res.append(codetTable[data[i]]);
        }
        return res;
    }
    void deCode(map<char,string> codetTable,string CodeData){
        map<char,string>::const_iterator it;
        string sub="";
        for (int i = 0; i < CodeData.length(); ++i) {
            for (int j = 0; j < 10; ++j) {
                sub = CodeData.substr(i,j);
                it = codetTable.begin();
                while(it != codetTable.end()){
                    if(sub == it->second){
                        char s = it->first;
                        cout<<s;
                        writeFile("解码文件.txt",s);
                        i = j + i ;
                        j = 0;
                        break;
                    }
                    ++it;
                }
            }
    
        }
    }
    string readFile(string path){
        ifstream ifs;
        ifs.open(path,ios::in);
        if (!ifs.is_open())
        {
            cout << "文件打开失败" << endl;return "";
        }
        string res;
        while (getline(ifs, res))
        {
            cout <<"读取的信息为: "<< res << endl;
        }
        ifs.close();
        return res;
    }
    // 写文件
    void writeFile(string path,string data)
    {
        //1、创建输出流对象,并打开
        ofstream ofs(path, ios::out);
        //2、写文件
        ofs<<data<<endl;
        //3、关闭文件
        ofs.close();
    }
    void writeFile(string path,char data)
    {
        //2、创建输出流对象,追加方式写入
        ofstream ofs(path, ios::app);
        //4、写文件
        ofs<<data;
        //5、关闭文件
        ofs.close();
    }
    int main(){
        string s = readFile("源文件.txt");//打开数据源文件
        priority_queue<HTNode>  queue = count(s);//获取单词的频率,通过升序进入优先队列
        show(queue);//输出队列
        CreateHuffmanTree(queue);//创建赫夫曼树
        string bulid="";
        HTNode root = queue.top();//获取树根节点
        getCodes(&root,"",bulid);//开始生成编码表
        printCode(huffmanCode);//展示编码表
        string res = BecomeCode(huffmanCode,s);//生成编码数据
        writeFile("编码文件.txt",res);//写入生成的01数据放入编码文件
        deCode(huffmanCode,res);//将编码数据解码
        return 0;
    }
    
    展开全文
  • 实验报告 3哈夫曼编 / 译码器 题目哈夫曼编 /译码器 一题目要求 写一个哈夫曼码的编 /译码系统 要求能对要传输的报文进行编码和解码 构造哈夫曼树时 权值小的放左 子树权值大的放右子树编码时右子树编码为 1左子树...
  • 实验报告 3哈夫曼编/译码器;... } 四调试分析与心得体会 虽然哈夫曼树的建立有书上的参考但是实际写整个代码的时候还是问题重重首先就是哈弗曼树忘 记了初始的赋值导致最后出现了问题这样的错误还是很容易解决
  • 实验报告与总结 一实验目的 1掌握哈夫曼编码原理 2熟练掌握哈夫曼树的生成方法 理解数据编码压缩和译码输出编码的实现 二实验要求 实现哈夫曼编码和译码的生成算法 三实验内容 先统计要压缩编码的文件中的字符字母...
  • 哈夫曼编码译码器实验报告,内有源代码,vc++6.0写的
  • 哈夫曼树实验报告 需求分析 从终端读入一串字符 利用建立好的哈夫曼树对其进行编码 储存到文件当中去 然后从文件读入 哈夫曼编码针对每个字母对其进行译码翻译为原来的信息 二概要设计 程序分为以下几个模块 1从终端...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 438
精华内容 175
关键字:

哈夫曼树编码实验报告