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

    万次阅读 2018-09-09 14:56:29
    哈夫曼树的构建: 注意:(1).首先把一组数3 5 6 8 9 12 15从小到大排列 (2).选取里面最小2个,顶点出为2个数的和 (3).新产生的顶点在与原先的数字进行比较,在里面选取2个最小的数,重复(2)的步骤 (4...

    哈夫曼树的构建:

    注意:(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

    …………

    展开全文
  • 构建最小生成树的方法:从权重中选择两个最小的,构成一棵树,并将新生成的权重加入之前的权重中HT【i】.weight中,直到构成一棵完整的二叉树。 话不多说,直接上代码。 #include "stdio.h" #include "stdlib.h" #...

    总体思路:先构建一棵最小生成树,然后左孩子给它标上‘0’,右孩子标上‘1’,然后从叶子节点追溯到根,存储到数组cd【】中。

    构建最小生成树的方法:从权重中选择两个最小的,构成一棵树,并将新生成的权重加入之前的权重中HT【i】.weight中,直到构成一棵完整的二叉树。

    话不多说,直接上代码。

    #include "stdio.h"
    #include "stdlib.h"
    #include "string.h"
    
    
    typedef struct
    {
        unsigned int weight;
        unsigned int parent,lchild,rchild;
    }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
    
    typedef char ** HuffmanCode;//动态分配数组存储哈夫曼编码
    
    //不能出现TH[1]->parent的结构
    void Select(HuffmanTree HT,int j,int *s1,int *s2)//j为结点的个数,s1为最小值的下标,s2为次小值的下标
    {
        int cmin = 100,min = 100;
        int k = 1;
        while(k <= j)
        {
            if((HT[k]).parent == 0)
            {
                if(HT[k].weight < min)
                {
                   min = HT[k].weight;
                   *s1 = k;
                }
                else if(HT[k].weight >= min&&HT[k].weight <= cmin)
                {
                  cmin = HT[k].weight;
                  *s2 = k;
                }
            }
            k++;
        }
        HT[*s1].parent = 0;
        HT[*s2].parent = 0;
    }
    
    
    //w用来存放n个字符的权值(w > 0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
    void HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,int *w,int n)//HC使用三重指针的原因,将HC的值带出去
    {
        HuffmanTree p;
        int s1,s2,m,i;//s1为最小数的下标,s2为次小数的下标
        int start,c,f;//start字符最开始的下标,c为
        char *cd;//用来存储哈夫曼编码
        if(n <= 1)
            return;
        m = 2 * n - 1;
        HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
        for(p = HT,i = 1;i <= n;i++,w++)//给前n个结点赋初值,从1开始
        {
            p[i].weight = *w;
            p[i].lchild = 0;
            p[i].rchild = 0;
            p[i].parent = 0;
        }
    
        //建一棵哈夫曼树
        for(i = n + 1;i <= m;i++)
        {
           Select(HT,i - 1,&s1,&s2);//挑选出最小和次小元素,并用s1,s2带出
           HT[s1].parent = i;
           HT[s2].parent = i;
           HT[i].lchild = s1;
           HT[i].rchild = s2;
           HT[i].weight = HT[s1].weight + HT[s2].weight;
           HT[i].parent = 0;
        }
         //求哈夫曼编码
         (*HC) = (HuffmanCode)malloc((n + 1) * sizeof(char *));//分配n个字符编码的头指针向量
         cd = (char *)malloc(n * sizeof(char));//分配求编码的工作空间
         cd[n - 1] = '\0';
         for(i = 1;i <= n;i++)
         {
             start = n - 1;//编码结束的位置
             for(c = i,f = HT[i].parent;f != 0;c = f,f = HT[f].parent) //从叶子到根逆向求编码
             {
                 if(HT[f].lchild == c)
                    cd[--start] = '0';
                 else
                    cd[--start] = '1';
              }
              (*HC)[i] = (char*)malloc((n-start) * sizeof(char));//为第i个字符编码分配空间
              strcpy((*HC)[i],&cd[start]);//此处不能传cd,因为下标不一定从0开始
         }
         free(cd);
    }
    
    int main()
    {
       int w[] = {15,25,45,5,10};
       int n,i;
       HuffmanTree HT = NULL;
       HuffmanCode HC = NULL;
       n = sizeof(w)/sizeof(int);
       HuffmanCoding(HT,&HC,w,n);
       for(i = 1;i <= n;i++)
       {
           printf("%d的哈夫曼编码为:",w[i - 1]);
           printf("%s\n",HC[i]);
       }
        return 0;
    }
    
    
    展开全文
  • 编码依据:最优二叉树(哈夫曼树) 相关概念: 节点权(w):赋予叶子结点有意义值 节点路径长度(L):从根节点到当前节点个数 节点带权路径长度:w*L 一棵二叉树带权路径长度:二叉树所有叶子节点...

    哈夫曼树相关概念

    • 应用领域:压缩(提高了网络的传输效率)
    • 编码依据:最优二叉树(哈夫曼树)
    • 相关概念:
      • 节点的权(w):赋予叶子结点有意义的值
      • 节点的路径长度(L):从根节点到当前节点的个数
      • 节点的带权路径长度:w*L
      • 一棵二叉树的带权路径长度:二叉树的所有叶子节点的带权路径长度之和
      • 最优二叉树:二叉树的带权路径长度最小
    • 最优二叉树的特点:
      • 最优二叉树没有单亲节点,只有双亲节点和叶子结点
      • 若叶子节点的个数是n,那么双亲节点的个数是n-1

    最优二叉树的构建总体思路

    • 以每一个节点为根节点构建的树组成森林;
    • 从森林中获取权值最小的和次小的二叉树,构成新的二叉树,再放回森林;
    • 重复第二步,直至森林中只有一棵树。

    哈夫曼编码的总体思路

    • 哈夫曼树采用的是数组存储
    • 哈夫曼编码使用指针数组进行存储。数组首元素存储的是,哈夫曼编码的长度。
    • 在求哈夫曼编码时,是从叶子结点开始回溯的。即从叶子结点找到双亲节点的下标,如果此叶子结点是双亲节点的左子女,则编码为0;若是右子女,则编码为1。循环在 叶子结点的双亲为-1结束

    哈夫曼树的实现

    • 用链表存储哈夫曼树

      • 存储形式:

        • 节点:
          这里写图片描述

        • 森林:用数组存储

      • 算法描述
        1.定义节点类型
    //节点的结构
    typedef struct node{
        struct node *left,*right;//储存指向左右节点的指针
        char word;//存储节点的表示
        int weight;//存储节点的权重 
    }HuffNode;
          2.定义森林数组并初始化
    
        HuffNode **F;//指向动态数组的指针
        int n;//数组的长度 
    
        //从键盘输入数组长度 
        printf("请输入数组长度:");
        scanf("%d",&n); 
    
        //定义储存森林的数组
        F = (HuffNode **)malloc(n*sizeof(HuffNode*));
    
        //初始化森林
        for(int i = 0;i<n;i++){
            int w;//表示权重 
            char ch;//表示节点 
    
            //新建二叉树节点
            F[i] = (HuffNode*)malloc(sizeof(HuffNode));
            printf("请输入节点的表示");
            scanf("%c",ch);
            printf("请输入节点的权重:");
            scanf("%d",w);
            F[i]->word = ch;
            F[i]->weight = w; 
            F[i]->left =  F[i]->right = NULL;
        } 
          3.最优二叉树的构建
    思路:输入的节点只能是叶子结点。所以构建二叉树的过程,就是创建双亲节点。根据最优二叉树的特点(若叶子节点的个数是n,那么双亲节点的个数是n-1),构建最优二叉树的循环次数为n-1次。而在每一循环中,都要从森林中获取最小以及次小的二叉树,作为新二叉树的左右节点,并返回森林,参与下一次循环
    
    //构建最优二叉树
    HuffNode *createHuffTree(HuffNode **F,int n){
        int loop;//表示循环次数
        HuffNode *newF; //表示新生成的节点 
        for(loop = 1;loop < n;loop++){
            int k1,k2;//k1表示最小节点的位置,k2表示次小节点的位置
            k1 = k2 = -1;
    
            //获取最小以及次小节点位置的初值 
            for(int i = 0;i < n && k2 == -1;i++){
                //F[i]=NULL时,表示该元素已经有双亲节点,不能参与最小以及次小的选取。
                if(k1 == -1 && F[i]){
                    k1 = i;
                }else if(F[i]){
                    k2 = i;
                }
            }
            //获取最小以及次小节点的位置
            for(int j = k2;j < n;j++){
                if(F[j]){
                    if(F[j]->weight < F[k1]->weight){
                        k2 = k1;
                        k1 = j;
                    }else if(F[j]->weight < F[k2]->weight){
                        k2 = j;
                    }
                }
            }
    
            //生成新的节点
             newF = (HuffNode*)malloc(sizeof(HuffNode));
    
             //将找到的最小以及次小节点挂到新的节点 
             newF->left = F[k1];
             newF->right = F[k2];
             newF->weight = F[k2]->weight + F[k1]->weight;
             newF->word = ' ';
    
             //将新生成的节点放回森林
             F[k1] = newF;
             F[k2] = NULL;
        }
        return newF; 
    } 
    • 用数组形式存储哈夫曼树

      • 存储形式

        • 节点
          这里写图片描述
        • 森林
          这里写图片描述
      • 算法描述
        1.定义节点的类型

    //定义节点的类型
    typedef struct {
        char word;//节点表示
        int weight;//节点的权重
        int parent,left,right;//用数组下标表示节点的双亲,左右子女节点
        int *code;//用指针数组表示哈夫曼编码
    }Huff;

    2.定义森林数组并初始化
    思路:在节点初始化过程中,左右子节点以及它的双亲节点设为-1

        Huff *F;//表示节点
        int n;//表示节点的个数
        printf("请输入节点个数");
        scanf("%d",&n);
        fflush(stdin);
    
        F = (Huff *)malloc((2*n-1)* sizeof(Huff));//申明指针数组
    
        //初始化节点并存入数组
        for (int i = 0; i < n; ++i) {
            int w;//表示权重
            char ch;//表示节点
            printf("请输入节点的表示");
            scanf("%c",&ch);
            F[i].word = ch;
            fflush(stdin);
            printf("请输入节点的权重");
            scanf("%d",&w);
            F[i].weight = w;
            fflush(stdin);
    
            F[i].left = F[i].parent = F[i].right = -1;
            F[i].code = (int *)malloc(n*sizeof(int));//声明哈夫曼编码空间
        }

    3.构建最优二叉树
    思路:

    • 构造最优二叉树的过程,其实就是构造双亲节点的过程,根据最优二叉树的特点(若叶子节点的个数是n,那么双亲节点的个数是n-1)。故构造双亲节点的次数就是n-1。
    • 节点的左右子节点以及双亲节点皆用数组的下标表示。
    • 当节点的parent为-1时,表示还没有构造其双亲节点。若parent不为-1,则表示双亲节点在数组的位置,此节点不能参与构造双亲节点的过程中
    //构造最优二叉树
    void createHuffTree(Huff *F,int n){
        //loop表示构造双亲节点的次数
        //k1表示最小节点,k2表示次小节点
        int loop,k1,k2,j;
    
        for (loop = 0; loop < n-1; ++loop) {
    
            //找到初始k1,k2的值
            //注意创建的双亲节点,如果parent也为-1,同样也要参与最小值以及次小值的选取
            for (k1 = 0; k1 < n+loop && F[k1].parent != -1; ++k1);
            for (k2 = k1+1; k2 < n+loop && F[k2].parent != -1; ++k2);
    
            //找出最小值以及次小值
            for (j = k2; j < loop+n; ++j) {
                if (F[j].parent ==-1){
                    if(F[j].weight < F[k1].weight){
                        k2 = k1;
                        k1 = j;
                    }else if(F[j].weight < F[k2].weight){
                        k2 = j;
                    }
                }
            }
            //跳出循环后,j正好表示紧接着已分配的数组元素的尚未分配的数组元素
            //双亲节点的设置
            F[j].word = ' ';
            F[j].left = k1;
            F[j].right = k2;
            F[j].weight = F[k1].weight + F[k2].weight;
            F[j].parent = -1;
            F[j].code = NULL;
    
            //左右子节点双亲节点的设置
            F[k1].parent = F[k2].parent = j;
        }
    }

    4.求出叶子结点的哈夫曼编码并储存到code指针指向的数组

    //储存哈夫曼编码
    void createHuffcode(Huff *f,int n)
    {
        for (int i = 0; i < n; ++i) {
            int c = i;
            int *temp = f[i].code;//temp指向存储哈夫曼编码的数组
            //循环结束的条件时节点的双亲亲为-1
            while(f[c].parent != -1)
            {
                int p = f[c].parent;//指向节点的双亲
                //若该节点是双亲的左子女,则编码为0;为右子女,则为1。哈夫曼编码长度加1
                if(f[p].left ==c)
                {
                    temp[++temp[0]] = 0;
                } else if (f[p].right ==c){
                    temp[++temp[0]] = 1;
                }
                c = p;
            }
        }
    }

    5.输出哈夫曼编码

    //输出哈夫曼编码
    void printHuffmancode(Huff *f,int n)
    {
        for (int i = 0; i < n; ++i) {
            int *temp = f[i].code;
            printf("%c:\t",f[i].word);
            for (int j = temp[0]; j >0 ; --j) {
                printf("%d",temp[j]);
            }
            printf("\n");
        }
    }
    展开全文
  • 编写一个程序,构造一棵哈夫曼树,输出对应哈夫曼编码和平均查找长度,并对下表(所示数据进行验证。 单词出现频度 单词: The of a to and in that he is at on for His are be 频度 :1192 677 541 518 ...

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

    单词及出现的频度
    单词: 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;
    }
    

    运行结果:
    在这里插入图片描述

    展开全文
  • 哈夫曼树的生成及哈夫曼编码

    千次阅读 2017-12-20 22:43:07
    首先构造哈夫曼树结构体,初始化哈夫曼树的四个无符号整型域,输入文本,统计各个字符的权值,然后构建哈夫曼树,从根到叶子逆向求哈夫曼树的编码。#include"stdio.h" #include"string.h" #include"malloc.h" #...
  • 构建哈夫曼树算法实现可以分为两大部分。 (1)初始化:首先动态申请2n个单元;然后循环2n-1次,从1号单元开始,依次将1至2n-1所有单元中双亲、左孩子、右孩子下标都初始化为0;最后再循环n次,输入前n个单元...
  • 一、哈夫曼树(一)什么是哈夫曼树(二)哈夫曼树的构建(三)哈夫曼树的几个特点(四)java代码构建哈夫曼树二、哈夫曼树拓展:构建最优k叉树三、哈夫曼编码 一、哈夫曼树 (一)什么是哈夫曼树 哈夫曼树也叫最优树...
  • 秉着能不写就不写的理念,关于哈夫曼树的原理及其构建,还是贴一篇博客吧。 https://www.jb51.net/article/97396.htm 其大概流程 哈夫曼编码代码 # 树节点类构建 class TreeNode(object): def __init__(self, ...
  • 哈夫曼树的构建及哈夫曼编码的生成与转换 代码先放这,有时间写注释及解析 #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; typedef struct{ int weight; int parent,lchild,rchild;...
  • 将一组无序数列建立最小堆,从最小堆中弹出两个最小的元素作为左右儿子其和为父节点构建一个树,将父节点加入最小堆,再次调用以上方法重复构建树,最终即可构建一棵哈夫曼树,哈夫曼树的特点有3个:1、 所有的序列...
  • 一.原理: 1.哈夫曼树:给定n个权值作为n个叶子...2.哈夫曼树构建:选取权值最小的两个值,将其作为新树的左右子树,且新树的根结点权值为其左右子树根节点权值之和。删除上两棵树,将新树加入森林 二.思路:...
  • 构建哈夫曼树的关键在于找最小树,在F中选择两棵根结点,权值最小的数作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值和。 #include<stdio.h> #include<stdlib...
  • 计算WPL·哈夫曼树构建及带权...对应哈夫曼树的带权路径长度WPL 测试样例 测试样例1 5 7 5 2 4 9 WPL=60 测试样例2 5 2 4 2 3 3 WPL=32 解答 想法 假设我们给定a,b,c,d,e,f的权值分别为9,12,6,3,5,15 1、首先,
  • 有讲到了哈夫曼树的原理及哈夫曼编码解码的过程。原理讲解直接移步上述链接,就不再画蛇添足。作为巩固随手练习一道题: 给定一篇文章,统计里面的各个字符出现的频次,并构建哈夫曼树,实现哈夫曼编码和解码的过程...
  • 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(HuffmanTree),或霍夫曼树。 赫夫曼树是带权路径长度最短的树,权值较大的结点离根...
  • 最近在看《tensorflow实战》中关于RNN一节,里面关于word2vec中涉及到了哈夫曼树,因此在查看了很多博客(文末)介绍后,按自己的理解对概念进行了整理(拼凑了下TXT..),最后自己用python实现Haffuman树的构建及编码。...
  • 作者:melonstreet链接:... Huffman1952年发明一种构建极小多余编码的方法。在计算机数据处理中,霍夫曼编码使用变长编码表对源符号进行编码,出现频率较高源符号采用较...
  • 哈姆曼树的构建: 赫夫曼树的外结点和内结点的区别:外节点是携带了关键数据的结点, 而内部结点没有携带这种数据, 只作为导向最终的外结点所走的路径而使用,所以,我们主要关心的是赫夫曼树的外结点上, 而不是内...
  • C/C++ 哈夫曼树的构造、编码以及译码

    万次阅读 多人点赞 2017-01-05 15:10:34
    题目:假设用于通信的电文由字符集{a,b,c,d,e...哈夫曼树的构造 哈夫曼编码及译码的实现 我从课本上面摘抄了一个题目,题目大概是上面这样的,我们这里只是详细的说明一下哈弗曼树要怎么构建。借用一下这个题目。哈夫曼
  • 2.实现了从 字符频率统计、构建权值集合、创建哈夫曼树、生成哈夫曼编码,最后对 给定字符串的编码、解码功能。//文件名:"HfmTree.h" #pragma once #include "SortedList.h" //"C1_Test....
  • 1,哈夫曼编码的基本思想是以字符使用频率作为权来构建一棵哈夫曼树,然后利用哈夫曼树对字符进行编码哈夫曼树是通过将所要编码的字符作为叶子结点。将该字符在文件中使用频率作为叶子结点权值,由自底向上...
  • 数据结构--哈夫曼树建立打印编码

    千次阅读 2017-11-07 14:40:31
    对输入英文大写字母进行统计概率 然后构建哈夫曼树,输出是按照概率降序排序输出Huffman编码。#include #include #include #include #include #include using namespace std;class Node {

空空如也

空空如也

1 2 3
收藏数 47
精华内容 18
关键字:

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