精华内容
下载资源
问答
  • 哈夫曼树的构建及哈夫曼树编码

    万次阅读 2018-09-09 14:56:29
    哈夫曼树的构建: 注意:(1).首先把一组数3 5 6 8 9 12 15从小到大排列 (2).选取里面最小2个,顶点出为2个数的和 (3).新产生的顶点在与原先的...(4)....哈夫曼树编码: 注意:(1).上图的a b c d e f假如...

    哈夫曼树的构建:

    注意:(1).首先把一组数3 5 6 8 9 12 15从小到大排列

    (2).选取里面最小2个,顶点出为2个数的和

    (3).新产生的顶点在与原先的数字进行比较,在里面选取2个最小的数,重复(2)的步骤

    (4).为了使哈夫曼树的结构唯一,让哈夫曼树的每个节点的左子树根节点的值小于等于右子树根节点的值

    哈夫曼树编码:

    注意:(1).上图的a b c d e f假如出现的频率为 9 12 6 3 5 15,就把他们出现的频率作为字符节点权值,构建哈夫曼树

    (2).然后在每个节点的左树根标上0,右树根标上1

    (3).所以a:00 

                       b:01 

                       c:100

    …………

    展开全文
  • 图解哈夫曼树:https://blog.csdn.net/lee18254290736/article/details/77618201构建哈夫曼及哈夫曼编码实现:https://blog.csdn.net/wtfmonking/article/details/17150499#
    展开全文
  • 实验题:构造哈夫曼树生成哈夫曼编码 编写一个程序,构造一棵哈夫曼树,输出对应的哈夫曼编码和平均查找长度,并对下表(所示的数据进行验证。 单词出现的频度 单词: The of a to and in that he is at on for ...

    实验题:构造哈夫曼树生成哈夫曼编码
    编写一个程序,构造一棵哈夫曼树,输出对应的哈夫曼编码和平均查找长度,并对下表(所示的数据进行验证。

    单词及出现的频度
    单词: The of a to and in that he is at on for His are be
    频度 :1192 677 541 518 462 450 242 195 190 181 174 157 138 124 123

    #include <iostream>
    #define N 50
    #define M 2*N-1
    using namespace std;
    //哈夫曼树结点定义
    typedef struct
    {
        string data;
        double weight;
        int parent;
        int lchild;
        int rchild;
    }HTNode;
    //哈夫曼编码结点定义
    typedef struct
    {
        char cd[N];
        int start;
    }HCode;
    //创建哈夫曼树
    void CreateHT(HTNode ht[], int n)
    {
        int i, k, lnode, rnode;
        double min1, min2;//min1用于记录较小的那个结点,min2记录较大的那个
        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++)//开始构造哈夫曼树
        {
            min1 = min2 = INT_MAX;
            lnode = rnode = -1;//记录可用的最小的两个结点的位置
            for (k = 0; k <= i - 1; k++)//随着过程的进行,会加入两个选用结点构成的新结点,所以判断条件为k<=i-1
            {
                if (ht[k].parent == -1)//可用结点
                {
                    if (ht[k].weight < min1)//比最小的那个结点更小
                    {
                        min2 = min1; 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 n)
    {
        int i, f, c;
        HCode hc;
        for (i = 0; i < n; i++)
        {
            hc.start = n; c = i;//从该节点倒着回到根结点,编码长度最大也不会超过n
            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 n)
    {
        int i, k;
        int sum = 0, m = 0, j;//sum存储树的带权路径长度,m存储权和,j存储路径长度
        cout << "输出哈夫曼编码:" << endl; //输出哈夫曼编码
        for (i = 0; i < n; i++)
        {
            j = 0;
            cout << ht[i].data << '\t';
            for (k = hcd[i].start; k <= n; k++)//输出哈夫曼编码
            {
                cout << hcd[i].cd[k];
                j++;//路径长度+1
            }
            m += ht[i].weight;
            sum += ht[i].weight * j;
            cout << endl;
        }
        cout << "平均长度=";
        cout << 1.0 * sum / m;
    }
    int main()
    {
        int n = 15, i;
        string str[] = { "The","of","a","to","and","in","that","he","is","at","on","for","His","are","be" };
        int fnum[] = { 1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123 };
        HTNode ht[M];
        HCode hcd[N];
        for (i = 0; i < n; i++)
        {
            ht[i].data = str[i];
            ht[i].weight = fnum[i];
        }
        CreateHT(ht, n);//创建哈夫曼树
        CreateHCode(ht, hcd, n);//求得哈夫曼编码
        DispHCode(ht, hcd, n);//输出哈夫曼编码和平均查找长度
        return 0;
    }
    

    运行结果:
    在这里插入图片描述
    如果本文对你有帮助的话,请👍哦(●ˇ∀ˇ●)

    展开全文
  • 文章目录哈夫曼树构建及编码一、什么是哈夫曼树二、什么是哈夫曼编码三、怎么建哈夫曼树、求哈夫曼编码四、为什么哈夫曼编码能实现压缩 声明:关于文件压缩,不是本文的重点,本文只说明并讨论哈夫曼树构建和...

    哈夫曼树的构建及编码


    声明:关于文件压缩,不是本文的重点,本文只说明并讨论哈夫曼树的构建和编码,不考虑文件压缩,实际上这个算法可以实现文件的压缩,但是我水平比较有限,涉及到文件操作,就不说了,另外本文后面编码和解码只是示范性举例型说明,并非真正实现了对文件的压缩。

    如果对哈夫曼树文件压缩感兴趣,想要成型的代码,可以直接将自己电脑的文件实现实质性压缩,移步至哈夫曼树编码压缩

    一、什么是哈夫曼树

    百科:

    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    解释:

    “带权路径长度”:也就是WPL,它是所有“带权节点”的“权值(或者称为权重)”与距离根节点的“路径长度”乘积之和。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3Sm3ekhx-1622211552152)(D:\f2a8531350e394c2d2f7eaaddd1b04c6.jpeg)]

    “带权节点”中存有原始数值,在建树过程中往往需要两个较小节点权值相加得到新节点再进行新一轮大小比较和筛选。比如如图5和3,它们的父母节点为8,但是,这个节点中的8并不是“原始”或者说不是“初始”数值,不能称为“带权节点”,所以图上该节点未作出标识,该节点确实存有8,但是不计入“带权路径长度”的计算中。

    “路径长度”可看作该“带权节点”到根节点所要走的线段数,比如以图中3为例,显然有4段线段才能到根节点,所以3的“路径长度”为4。

    上图为例:带权路径长度计算

    WPL = 3 * 4 + 5 * 4 + 11 * 3 + 23 * 2 + 29 * 2 + 14 * 3 + 7 * 4 + 8 * 4 = 271

    注:哈夫曼树的创建虽然有规则,但是创建结果不是唯一的,我们唯一可以作为标准的不是树的形状或者结构,而是“带权路径”,即WPL,无论什么结构,WPL值一定唯一且相等!

    二、什么是哈夫曼编码

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-i9AbxTIO-1622211552154)(D:\9775ccda4cde7f94ad9bdaa0867a0a22.jpeg)]

    哈夫曼编码即在哈夫曼树的基础上,左边路径标0,右边路径标1

    举个例子,这时候,i可以表示为00,即从根往下读路径数字。

    三、怎么建哈夫曼树、求哈夫曼编码

    这里就不拿书里面做法说了,书上面是顺序存储,这里介绍链式存储。

    方法 && 步骤:

    1. 改造“轮子”,主要是利用C++中STL库中的“优先队列(priority_queue)",优先队列(priority queue)介绍:

      普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。

      优先队列的特性,假如是小根堆的有限队列,依次进队5 6 4 2 1那么,其实在队列中顺序是 1 2 4 5 6,队头为1,队尾元素为6,相当于通过进队,在队中实现了排序,接下来要取出较小元素,取出队头即可。

      上面就是对于“轮子”的介绍,接下来改造一下

      为啥要改造?因为加入是一个队列元素是一个数字,优先队列完全不用任何其他操作,自动按照数字大小排序,但是如果队列元素是一个结构体,结构体中包含很多数据,优先队列不知道按照哪一个数据进行排序,这时候就需要“重载”函数,对优先队列中默认的“元素的比较规则”实现自定义重构,然后把我们规定的规则加入 优先队列中即可

    2. 经过改造轮子,我们可以轻松得两个较小节点。两个节点数值的和与两个较小节点构成“父母-左孩子-右孩子”,再将父母节点入优先队列。重复操作即可。便可实现构建哈夫曼树,下面是重载函数:

      struct myCmp
      {
          bool operator()(const tree &a, const tree &b)
      	{
          	
              return a->data > b->data;
          }
      };
      

      构建哈夫曼树总代码:

      #include <iostream>
      #include <vector>
      #include <cstdio>
      #include <string>
      #include <queue>
      #include <cstring>
      
      using namespace std;
      
      const int N = 1010;
      
      char st_c[N], str[N];
      //st_c[]数组存放输入的待编码的0-26英文字符
      //str[]数组读入原始带编码的英文字符,str_c[]数组存放的字
      //符是不同种类字符,无重复,而原始数组str[]中可能有重复
      int  st_n[N], ct_a;
      //st_n[]数组对应st_c[]中每个字符出现的次数
      double st_p[N];
      //st_p[]数组对应st_c[]中每个字符出现的比率
      char xtr[100], st_t[100][N];
      //xtr[]数组用来存放路径结果0/1
      typedef struct node
      {
      	double data;
      	struct node* lc, *rc;
      	
      }node, * tree;
      
      struct myCmp
      {
          bool operator()(const tree &a, const tree &b)
      	{
          	
              return a->data > b->data;
          }
      };
      
      void to_be_node(tree &T, tree T1, tree T2, double x)
      {
          T = new node;
          T->data = x;
          T->lc = T1, T->rc = T2;
          return;
      }
      
      int In(char ch)
      {
      	for (int i = 1; st_c[i]; ++ i){
      	 
      		if (st_c[i] == ch) return i;
      	}
      	  
      	return 0;
      }
      
      void preorder(tree &T, int cnt)//递归实现“编码”
      //类似于DFS(深度优先搜索)
      {	
      //    cout << "cnt = " << cnt << endl;
      	if (!T->lc && !T->rc)//递归出口
      	{
      		int temp = 0;
      		for (int i = 1; st_p[i]; ++ i){
      			
      			if (st_p[i] == T->data) { 
      //			   cout << "i = " << i << ' ' << "xtr = " << xtr << endl;
                     st_p[i] = -1;//防止出现概率相同的,第二次把第一次盖了 
      			   strcpy(st_t[i], xtr);//找到带权节点,拷贝路径到st_t[]数组中
      			   return;
      			} 
      		} 
      		return;
      	}
      	
      	xtr[cnt] = '0';//左边走路径为0
      	preorder(T->lc, cnt+1);
      	xtr[cnt] = '1';//右边走路径为1
      	preorder(T->rc, cnt+1);
      	xtr[cnt] = '\0';//一条路搜完了,回退,清空后一步的0/1
      }
      
      void preordtraver(tree T)//先序遍历
      {
          if (T == NULL) return;
          
          cout << T->data << endl;
          
          preordtraver(T->lc);
          preordtraver(T->rc);
      }
      
      tree build_hfmtree()//构建哈夫曼树
      {
      	priority_queue <tree, vector<tree>, myCmp> hm;
      	//优先队列
      	int judge, i = 1, j = 0;
      	
      	cin >> str;
      
      	while (str[j])
      	{
      		ct_a ++;
      		judge = In(str[j]);
      		if (judge) st_n[judge] ++;
      		else 
      		{
      		    st_c[i] = str[j];
      		    st_n[i] ++, i ++;
      		}
      		j ++; 
      	}
      	
      	cout << "占比如下:" << endl;
      	
      	for (int i = 1; st_c[i]; ++ i)
      	{
      		st_p[i] = (double)st_n[i] / ct_a;
      		cout << st_c[i] << ' ' << st_p[i] << endl;
      	} 
          cout << endl << endl;
          //将每个节点进队
      	for (int i = 1; st_p[i]; ++ i) 
          {
              node* T = new node;
              to_be_node(T, NULL, NULL, st_p[i]);
               
              hm.push(T);
          }
         
          while (hm.size() && hm.size() != 1)//当队中仅有1个节点时退出,这时候树就建成了。
          {
              node* t1 = hm.top(); hm.pop();
              node* t2 = hm.top(); hm.pop();
              
              node* T = NULL;
              to_be_node(T, t1, t2, t1->data + t2->data);
              
              hm.push(T);
          }
          
          node* T = hm.top(); hm.pop();
          //返回哈夫曼树根节点的指针
          return T;
      } 
      
      void encode()
      {
      	FILE *fp = NULL;
      	
      	fp = fopen("D:/HDU/teile.txt", "w");//建文件,路径自己写
      	if (fp == NULL) {
      		
      		cout << "sbai!" << endl;
      		exit(0); 
      	}
      	for (int i = 0; str[i]; ++ i)//将哈夫曼码写入文件
      	{
      		int s = In(str[i]);
      		
      		fputs(st_t[s], fp);
      	}
      	fclose(fp);
      }
      
      void decode()
      {
      	FILE *fp = NULL;
      	char ch, cstr[N] = {0}, cx[N] = {0};
      	
      	fp = fopen("D:/HDU/teile.txt", "r");//打开文件
      	if (fp == NULL) {
      		
      		cout << "sbai!!" << endl;
      		exit(0); 
      	}
      	int i = 0;
      	while (!feof(fp))//读取文件中字符
      	{
      		ch = fgetc(fp);
      		cstr[i ++] = ch;
      	
      		for (int j = 1; st_c[j]; ++ j)
      		{
      			if (!strcmp(cstr, st_t[j]))//进行解码
      			{
      				cout << st_c[j];
      			    while (i) cstr[i --] = '\0';
      				break;
      			}
      		}
      	}
      	fclose(fp);
      	
      	return;
      }
      
      int main()
      {	
          tree T = build_hfmtree();
          
          cout << "哈夫曼树建立完成!" << endl; 
          
          cout << "*******前缀码*****" << endl << endl;
      	
      	preorder(T, 0);
      	
      	for (int i = 1; st_c[i]; ++ i) cout << st_c[i] << " : "<< st_t[i] << endl; 
      	
      	cout << "******************" << endl << endl;
      	 
      	encode();
      	cout << "文件解密如下:\n";
      	
      	decode();
      	   
          return 0;
      }
      //测试:AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCDDDDDDDDEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFGGGHHHHHHHHHHH
      /*-------------------------测试时间:2021.5.26  21:25------------------------*/
      
      /*运行结果: 
      part 1.文件 
      1111111111111111111111111101010101010101010101010101010101010101010101
      0101010101010111011101110111011101110111000000000000000000000000011011
      0110110110110110110110110110110110110010101010101010101010101010101010
      1010101010101111101111011110001001001001001001001001001001001
      
      part 2. 运行窗口
      AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCDDDDDDDDEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFGGGHHHHHHHHHHH
      占比如下:
      A 0.05
      B 0.29
      C 0.07
      D 0.08
      E 0.14
      F 0.23
      G 0.03
      H 0.11
      
      
      哈夫曼树建立完成!
      *******前缀码*****
      
      A : 11111
      B : 10
      C : 1110
      D : 000
      E : 110
      F : 01
      G : 11110
      H : 001
      ******************
      
      文件解密如下:
      AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCDDDDDDDDEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFGGGHHHHHHHHHHH
      
      */
      

    四、为什么哈夫曼编码能实现压缩

    这个很难解释,查资料吧…哈夫曼编码

    展开全文
  • 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径...
  • 哈夫曼树构建

    2020-01-14 21:20:26
    哈弗曼树构建过程 将带权值的节点进行排序,形成有序的链表。 取出链表头两个节点,权值相加形成新节点,并加入上述链表中重新排序,两节点分别为构建为左右子树,新创建的节点为父节点。 重复步骤2直到链表节点...
  • 哈夫曼树构建 哈夫曼编码

    千次阅读 2015-11-22 22:48:17
    哈夫曼树:给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 哈夫曼...
  • //从1--i-1中选择最小的、且parent为0的两个结点,以i结点为这两个结点的父结点,从而构建哈夫曼树 int s1,s2; Select(*HT,i-1,&s1,&s2); (*HT)[s1].parent=(*HT)[s2].parent=i; (*HT)[i].lchild=s1; (*HT)...
  • 常见应用:压缩,最基本的压缩编码的方法,使得总体的编码长度缩短,减少不必要的空间。什么可以称为哈夫曼树?公式判断:WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)Wi : 表示第i...哈夫曼树构建的步骤:① 给定n个权值{...
  • 计算WPL·哈夫曼树构建及带权路径长计算题目信息输入输出测试样例解答想法 题目信息 Huffman编码是通信系统中常用的一种不等长编码,它的特点是:能够使编码之后的电文长度最短。 输入 第一行为要编码的符号数量n 第...
  • 哈夫曼树及哈夫曼编码

    千次阅读 2019-07-23 21:59:26
    知识点一:哈夫曼树 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离...
  • 哈夫曼树以及哈夫曼编码构建

    千次阅读 2020-06-30 01:59:53
    最终的哈夫曼树,得到每个字符的哈夫曼编码。 请将上述设计哈夫曼编码的过程,用代码来实现,并输出各个字母的哈夫曼编码。(有 代码,有运行结果的截图 #include <stdio.h> #include <s
  • 实验目的:哈夫曼树构建以及哈夫曼编码的输出 实验思想:1.先构建一个哈夫曼树  2.每个叶子节点为结点的名称  3.然后进行遍历  4.向左为0 向右为1  5.存入一个字符数组中 最后在输出 ① 头文件的构建:...
  • 利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读人),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 (3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码,结果...
  • 哈夫曼树原理,构造方法

    万次阅读 多人点赞 2018-08-05 12:13:21
    哈夫曼树(最优二叉树) 百度百科:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin 一. 目的: 找出存放一串字符所需的最少的二进制编码 二. 构造方法: 首先统计出每...
  • 哈夫曼树/赫夫曼树 Python实现赫夫曼树 Python实现哈夫曼树 哈夫曼编码 哈夫曼压缩 哈夫曼解压 最简单的方式实现哈夫曼树
  • 总体思路:先构建一棵最小生成,然后左孩子给它标上‘0’,右孩子标上‘1’,然后从叶子节点追溯到根,存储到数组cd【】中。 构建最小生成的方法:从权重中选择两个最小的,构成一棵,并将新生成的权重加入...
  • 举例理解哈夫曼树与哈夫曼编码

    万次阅读 2020-07-02 08:52:56
    举例理解哈夫曼树,C语言实现哈夫曼树
  • 哈夫曼树及哈夫曼编码详解【完整版代码】

    万次阅读 多人点赞 2018-06-17 11:42:30
    赫夫曼(Huffman Tree),又称最优二叉树,是一类带权路径长度最短的。假设有n个权值{w1,w2,…,wn},如果构造一棵有n个叶子节点的二叉树,而这n个叶子节点的权值是{w1,w2,…,wn},则所构造出的带权路径长度最小...
  • 介绍哈夫曼树及哈夫曼编码
  • 构建哈夫曼树编码

    2013-01-03 17:11:39
    自己写的哈夫曼树还行 各位看官来下载吧 测试无错误
  • 文章目录数据结构(C++)——哈夫曼树及哈夫曼编码一、哈夫曼树的介绍概念二、哈夫曼树的构造打印①哈夫曼树的存储结构②构造哈夫曼树③Select()函数的代码实现④打印哈夫曼树⑤测试的完整代码二、哈夫曼编码①...
  • 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,哈夫曼树的构造规则为: 1. 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); 2. 在森林中选出根结点的权值最小...
  • #include <stdio.h> #include <stdlib.h> typedef int ElemType;...//根据传入的数组a,其中n个元素作为其权值,构建一颗哈夫曼树,返回根节点 BTreeNode* CreateHuffman(ElemType a[], int n) { int i, j;
  • 【数据结构】哈夫曼树及哈夫曼编码

    万次阅读 多人点赞 2017-04-30 21:02:11
    哈夫曼树 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 树节点...

空空如也

空空如也

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

哈夫曼树的构建及哈夫曼树编码