精华内容
下载资源
问答
  • 哈夫曼树 C++算法

    2010-12-27 20:43:56
    数据结构的哈夫曼树,能输入任意字符串,并计算出现频率,同时统计编码长度,可编码,可解码,能计算压缩比,可执行程序包括实验报告
  • 哈夫曼解码算法(C实现)

    千次阅读 2017-08-08 19:10:43
    记得在毕业前去找工作,应聘康佳集团移动应用工程师的笔试题出了这么一道题。 传输文本字符”BADCADFEED”,只能出现”ABCDEF”这六个...接收方可以根据每3个bit进行一次字符解码的方式还原文本传输的信息,但是这样的

    记得在毕业前去找工作,应聘康佳集团移动应用工程师的笔试题出了这么一道题。

    传输文本字符”BADCADFEED”,只能出现”ABCDEF”这六个字符,使用以下的编码方式:



    如传输字符:BADCADFEED          接收编码:001000011010000011101100100011

     

    接收方可以根据每3个bit进行一次字符解码的方式还原文本传输的信息,但是这样的传输效率太低了,需要30bit才发送10个字符。如何编码来提高传输以及接收效率???请写出你的编码方式以及算法思想。

    我当时并没有想到解决方法,GG了。最近运用到霍夫曼树,现在回想起来不就是这个算法吗,哈哈哈,太好了。在这里总结一下。

     

    引入:

    要提高效率,必须要从编码方式去改变,这是无疑的。这里运用了避免每一个字符都占有相同的bit位。如



    如传输字符:BADCADFEED          接收编码:1001010010101001000111100 

    改进编码方式之后,可以看到发送相同的字符,需要25bit位就可以表示10个字符了。这种编码明显是有很大优势的。

     

    问题:这个编码方式有什么规律呢?怎么得到呢?又是如何在接收方解码的呢?下面来揭开神奇的面纱。

    假定经过统计得出ABCDEF在所需传输报文出现的概率如下:

     

    霍夫曼树算法: 

    给定实数w1,w2,···,wt且 w1<=w2<=···<=wt           

    (1)连接w1,w2为权的两片树叶,得一分支点,其权为w1+w2 ;

    (2)在w1+w2, w3+···+wt中选出两个最小的权,连接它们对应的顶点(不一定都是树叶),得分支点及所带的权;

    (3)重复(2),直到形成t – 1个分支点,t片树叶为止

     

    或者这样描述算法:

    1、给定n个数值{ v1, v2, …, vn}

    2.根据这n个数值构造二叉树集合F

    F = { T1, T2, …, Tn}           Ti的数据域为vi,左右子树为空

    3.在F中选取两棵根结点的值最小的树作为左右子树构造一棵新的二叉树,这棵二叉树的根结点中的值为左右子树根结点中的值之和

    4.在F中删除这两棵子树,并将构造的新二叉树加入F中

    5.重复3和4,直到F中只剩下一个树为止。这棵树即霍夫曼树

     

    图解上面算法过程:(不想用电脑画图了,直接简单粗暴用手画一个)


    Huffman树中,左边分支置为0,右边分支置为1,就行形成了每个结点的哈夫曼编码了


    哈夫曼树的应用:

    主要用途是实现数据压缩。在某些通讯场合,需将传送的文字转换成由二进制字符组成的字符串进行传输,也是现代压缩软件中运用到的算法的基础


    测试结果:


    C实现代码:

    // Huffman.h
    
    #ifndef HUFFMANBITREE_H_H  
    #define HUFFMANBITREE_H_H  
    
    //数据封装 
    typedef int LeafNode;  
      
    // 哈夫曼树结点结构体  
    typedef struct HuffmanTree  
    {  
        LeafNode weight;        //结点权重 
        LeafNode index;        // index用来主要用以区分权值相同的结点,这里代表了下标  
        
        struct HuffmanTree* lchild;  
        struct HuffmanTree* rchild;  
    }HuffmanNode;  
    
    //创建哈夫曼树 
    HuffmanNode* createHuffmanTree(int* Arr, int n);  
    
    //打印哈夫曼树   
    void PrintHuffmanTree(HuffmanNode* hufmTree);
    
    // 哈夫曼编码 
    void HuffmanCode(HuffmanNode* hufmTree, int depth);      // depth是哈夫曼树的深度 
    
    //哈夫曼解码 
    void HuffmanDecode(char DecodeStr[], HuffmanNode* hufmTree, char NodeStr[]);  // DecodeStr是要解码的01串,NodeStr是结点对应的字符
      
    #endif  
    //Huffman.c
    #include <stdio.h>  
    #include <stdlib.h> 
    #include <string.h>
    #include "Huffman.h"
    
    // 构建哈夫曼树  
    HuffmanNode* createHuffmanTree(int* Arr, int n)  
    {  
        int i, j;  
        HuffmanNode **Total_HuffmanNode, *hufmTree;  
        Total_HuffmanNode = malloc(n*sizeof(HuffmanNode));  
        
        for (i=0; i<n; ++i)          // 将数组a中的权值赋给结点中的weight  
        {  
            Total_HuffmanNode[i] = (HuffmanNode*)malloc(sizeof(HuffmanNode));  
            Total_HuffmanNode[i]->weight = Arr[i];  
            Total_HuffmanNode[i]->index = i;  
            Total_HuffmanNode[i]->lchild = Total_HuffmanNode[i]->rchild = NULL;  
        }  
      
        for (i=0; i<n-1; ++i)          // 构建哈夫曼树需要n-1合并  
        {  
            int FirstSmall=-1, SecondSmall;      // FirstSmall=, S_small分别作为最小和次小权值的下标  
            for (j=0; j<n; ++j)         // 先将最小的两个下标赋给FirstSmall、SecondSmall(注意:对应权值未必最小)  
            {  
                if (Total_HuffmanNode[j] != NULL && FirstSmall==-1)  
                {  
                    FirstSmall = j;  
                    continue;  
                } else if(Total_HuffmanNode[j] != NULL)  
                {  
                    SecondSmall = j;  
                    break;  
                }  
            }  
      
            for (j=SecondSmall; j<n; ++j)    // 比较权值,挪动FirstSmall和SecondSmall使之分别成为最小和次小权值的下标  
            {  
                if (Total_HuffmanNode[j] != NULL)  
                {  
                    if (Total_HuffmanNode[j]->weight < Total_HuffmanNode[FirstSmall]->weight)  
                    {  
                        SecondSmall = FirstSmall;  
                        FirstSmall = j;  
                    } else if (Total_HuffmanNode[j]->weight < Total_HuffmanNode[SecondSmall]->weight)  
                    {  
                        SecondSmall = j;  
                    }  
                }  
            }  
            hufmTree = (HuffmanNode*)malloc(sizeof(HuffmanNode));  
            hufmTree->weight = Total_HuffmanNode[FirstSmall]->weight + Total_HuffmanNode[SecondSmall]->weight;  
            hufmTree->lchild = Total_HuffmanNode[FirstSmall];  
            hufmTree->rchild = Total_HuffmanNode[SecondSmall];  
      
            Total_HuffmanNode[FirstSmall] = hufmTree;  
            Total_HuffmanNode[SecondSmall] = NULL;  
        }  
        free(Total_HuffmanNode);  
        return hufmTree;  
    }  
      
    // 打印哈夫曼树  
    void PrintHuffmanTree(HuffmanNode* hufmTree)  
    {  
        if (hufmTree)  
        {  
            printf("%d", hufmTree->weight);  
            if (hufmTree->lchild != NULL || hufmTree->rchild != NULL)  
            {  
                printf("(");  
                PrintHuffmanTree(hufmTree->lchild);  
                printf(",");  
                PrintHuffmanTree(hufmTree->rchild);  
                printf(")");  
            }  
        }  
    }  
      
    // 递归进行哈夫曼编码  
    void HuffmanCode(HuffmanNode* hufmTree, int depth)      // depth是哈夫曼树的深度  
    {  
        static int code[10];  
        if (hufmTree)  
        {  
            if (hufmTree->lchild==NULL && hufmTree->rchild==NULL)  
            {  
                printf("index为%d权值为%d的结点的哈夫曼编码 ", hufmTree->index, hufmTree->weight);  
                int i;  
                for (i=0; i<depth; ++i)  
                {  
                    printf("%d", code[i]);  
                }  
                printf("\n");  
            } else  
            {  
                code[depth] = 0;  
                HuffmanCode(hufmTree->lchild, depth+1);  
                code[depth] = 1;  
                HuffmanCode(hufmTree->rchild, depth+1);  
            }  
        }  
    }  
      
    // 哈夫曼解码  
    void HuffmanDecode(char DecodeStr[], HuffmanNode* hufmTree, char NodeStr[])  // DecodeStr是要解码的01串,NodeStr是结点对应的字符  
    {  
        int i;  
        int CodeNum[100];  
        HuffmanNode* Total_HuffmanNodeTree = NULL;  
        for (i=0; i<strlen(DecodeStr); ++i)  
        {  
            if (DecodeStr[i] == '0')  
                CodeNum[i] = 0;  
            else  
                CodeNum[i] = 1;  
        }  
        if(hufmTree)  
        {  
            i = 0;      // 计数已解码01串的长度  
            while(i<strlen(DecodeStr))  
            {  
                Total_HuffmanNodeTree = hufmTree;  
                while(Total_HuffmanNodeTree->lchild!=NULL && Total_HuffmanNodeTree->rchild!=NULL)  
                {  
                    if (CodeNum[i] == 0)  
                    {  
                        Total_HuffmanNodeTree = Total_HuffmanNodeTree->lchild;  
                    } else  
                    {  
                        Total_HuffmanNodeTree = Total_HuffmanNodeTree->rchild;  
                    }  
                    ++i;  
                }  
                printf("%c", NodeStr[Total_HuffmanNodeTree->index]);     // 输出解码后对应结点的字符  
            }  
        }  
    }  


    
    

    
    
    //mian.c 
    #include <stdio.h>  
    #include <stdlib.h>  
    #include <string.h>  
    #include "Huffman.h"  
    
    int main()  
    {  
        int i, n;  
        printf("请输入结点的个数:\n");  
        while(1)  
        {  
            scanf("%d", &n);  
            if (n>1)  
                break;  
            else  
                printf("错误,请重新输入n值!");  
        }  
      
        int* ArrLeafNode_Weight;  
        ArrLeafNode_Weight=(int*)malloc(n*sizeof(LeafNode));  
        printf("请输入%d个结点的权值:\n", n);  
        
        for (i=0; i<n; ++i)  
        {  
            scanf("%d", &ArrLeafNode_Weight[i]);  
        }  
      
        char DecodeStr[100], NodeStr[100];  
        printf("请输入这%d个结点所代表的字符:\n", n);  
        fflush(stdin);      // 强行清除上面输入权值结束时的回车符  
        gets(NodeStr);  
      
        HuffmanNode* hufmTree = NULL;  
        hufmTree = createHuffmanTree(ArrLeafNode_Weight, n);  
      
        printf("此哈夫曼树的形式为:\n");  
        PrintHuffmanTree(hufmTree);  
        
        printf("\n各结点的哈夫曼编码为:\n");  
        HuffmanCode(hufmTree, 0);  
      
        printf("请输入编码的文本信息:\n");  
        gets(DecodeStr);  
        printf("解码输出为:\n");  
        HuffmanDecode(DecodeStr, hufmTree, NodeStr);  
        printf("\n");  
      
        free(ArrLeafNode_Weight);  
        free(hufmTree);  
      
        return 0;  
    }  
    
    
    展开全文
  • MP3解码哈夫曼解码快速算法

    千次阅读 2013-12-18 12:31:47
    哈夫曼(huffman)解码用查表法,数据组织采用形结构,若采用二叉树,一次处理一位(bit),效率是比较低的。从一些杂志上看到关于哈夫曼(huffman)解码的快速算法介绍,直接用位流索引一次处理N(4  MP3解码处理主数据...

          哈夫曼(huffman)解码用查表法,数据组织采用树形结构,若采用二叉树,一次处理一位(bit),效率是比较低的。从一些杂志上看到关于哈夫曼(huffman)解码的快速算法介绍,直接用位流索引一次处理N(4<N<=32)位,这种方法实际上是不可行的,原因是构造出的码表很长,如果一次处理8位,可以编写程序构造出码表,不过可以肯定的是码表的长度会超过我们事先的想象,以至于没有多大的实用价值。一次处理多位(一位以上)码表中冗余度很大导致码表很长。

          MP3解码处理主数据(main_data)的第一步就是对主数据进行哈夫曼解码。MP3编解码用到的哈夫曼表由ISO/IEC 11172-3 的附录B中给出,大值区用到31张码表(其中第0、4、14号码表未使用),小值区用到两张码表。从ISO/IEC 11172-3复制出两张原始的码表来分析,解码大值区的码表:

    Huffman code table 7
     x  y hlen hcod
     0  0   1   1
     0  1   3   010
     0  2   6   001010
     0  3   8   00010011
     0  4   8   00010000
     0  5   9   000001010
     1  0   3   011
     1  1   4   0011
     1  2   6   000111
     1  3   7   0001010
     1  4   7   0000101
     1  5   8   00000011
     2  0   6   001011
     2  1   5   00100
     2  2   7   0001101
     2  3   8   00010001
     2  4   8   00001000
     2  5   9   000000100
     3  0   7   0001100
     3  1   7   0001011
     3  2   8   00010010
     3  3   9   000001111
     3  4   9   000001011
     3  5   9   000000010
     4  0   7   0000111
     4  1   7   0000110
     4  2   8   00001001
     4  3   9   000001110
     4  4   9   000000011
     4  5  10   0000000001
     5  0   8   00000110
     5  1   8   00000100
     5  2   9   000000101
     5  3  10   0000000011
     5  4  10   0000000010
     5  5  10   0000000000

     

    解码小值区的码表:

    Huffman code table 17
     x  y hlen hcod
     0  0  1   1
     0  1  4   0101
     0  2  4   0100
     0  3  5   00101
     0  4  4   0110
     0  5  6   000101
     0  6  5   00100
     0  7  6   000100
     0  8  4   0111
     0  9  5   00011
     0  10 5   00110
     0  11 6   000000
     0  12 5   00111
     0  13 6   000010
     0  14 6   000011
     0  15 6   000001

     

    所有码表中,大值区的x=0..15,y=0..15,码长hlen=1..19。

     

    一次处理多位应该如何实现呢?首先构造出码表,如果每次处理2比特,构造码表暂存数据时用4叉树;如果一次处理3比特,则用8叉树,以此类推。编程从一个文本文件中读入如上所示的原始的哈夫曼表数据,将其插入到N叉树中相应的位置。假如一次处理2位而码字(hcod)是5位(hlen=5),那么在hcod最后分别补上0和1凑足2的整数倍位数,这就导致了构造出的哈夫曼表冗余度,即一个码字对应多个码表中元素。一次处理的位数越多,构造出的码表的冗余度越大。

     

    根据自己解码设计构造出码比较费事,解码过程挺简单。

     

    实际编程中,可以用数组来存储N叉树,只需要将指针域的值改为元素在数组中的下标值。以大值区解码一次处理2比特为例,x和y取值范围为0..15,只需占用4比特;码长hlen取值范围为1..19,存储hlen只需5比特。存储一个码值只需要13比特,可以将一个码值存储在16位整数中,低4位是y,接下来的4位是x,再接下来的5位是hlen。高3位全为零表示该数组元素存储的是一个码值,最高位为1(表示负数)则其绝对什表示该数组元素存储的是数组的下标值。经过这样处理后解码大值区的码表“Huffman code table 7”:

    C代码:

    static short htbv7[72] = {
      -4, -68, 256, 256,  -8, -48, -64,1041, -12, -28, -40, -44, -16, -20, -24,2069,
    2645,2629,2644,2643,2357,2357,2372,2372,2341,2341,2386,2386,2129, -32,2128, -36,
    2309,2309,2356,2356,2371,2371,2355,2355,2084,2114,1812,1812,1857,1857,1856,1856,
     -52, -56, -60,1554,2052,2083,2098,2051,1811,1811,1841,1841,1840,1840,1826,1826,
    1313,1313,1538,1568, 769, 769, 784, 784};


     

    解码小值区的码表“Huffman code table 17”一次处理4比特:

    static short htc0[80] = {
     -16, -32, -48, -64,1026,1025,1028,1032, 256, 256, 256, 256, 256, 256, 256, 256,
    1547,1547,1547,1547,1551,1551,1551,1551,1549,1549,1549,1549,1550,1550,1550,1550,
    1543,1543,1543,1543,1541,1541,1541,1541,1289,1289,1289,1289,1289,1289,1289,1289,
    1286,1286,1286,1286,1286,1286,1286,1286,1283,1283,1283,1283,1283,1283,1283,1283,
    1290,1290,1290,1290,1290,1290,1290,1290,1292,1292,1292,1292,1292,1292,1292,1292};

    码表构造好了,如何解码呢?从码流中读入4字节暂存到unsigned int umask,解码大值区得到x和y:

    y = ptab[umask >> 30];	// 一次处理2比特,ptab指向码表(如ptab=htbv7)
    while (y < 0) {
    	umask <<= 2;
    	y = ptab[(umask >> 30) - y];
    }
    x = y >> 8;		// hlen
    num -= x;			// num为umask中剩余的比特数
    umask <<= x;
    x = (y >> 4) & 0xf;		// 得到x值
    y &= 0xf;			// 得到y值

    解码小值区得到y值的代码:

    C代码
    y = ptab[umask >> 28];		// 一次处理4比特
    while (y < 0) {
    	umask <<= 4;
    	y = ptab[(umask >> 28) - y];
    }
    x = y >> 8;	// hlen
    num -= x;
    umask <<= x;
    
    y &= 0xf;		// 得到y值

    每解码完一个码字,重新刷新umask和num。以上解码方法正确与否可以用“Huffman code table 7”或“Huffman code table 17”内的数据去检查。

    一次处理N比特肯定比一次处理1比特效率高。兼顾效率和存储空间开销,解码大值区采用一次处理2位到4位,解码小值区一次处理4位,这样比较好。

     

    展开全文
  • 二叉树的存储结构Ⅲ 哈夫曼树及编码A. 构造哈夫曼树a. 频度统计b. 生成哈夫曼树B. 哈夫曼编码C. 解码 Ⅰ 树 由于树的应用场合很少,不是很实用,所以在此只做简单介绍。 A. 树的概念 树状图是一种数据结...

    Ⅰ 前言

    在前面的文章里,我详细讲解了树与二叉树。这篇文章,我们就来看一看二叉树的一种情况——最优二叉树,也称哈夫曼树(Huffman Tree)

    对二叉树这个数据结构还不完全清楚的同学可以跳转去下面的文章。

    【数据结构与算法】->数据结构->树与二叉树

    Ⅱ 什么是哈夫曼树

    在前面我们说了,哈夫曼树是二叉树的一种,那到底是什么是哈夫曼树呢?这里我给出一个定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。

    完全不知道这个定义在说什么。

    不要急,我们慢慢来。

    首先来看几个概念。

    • 路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。比如从根节点到 a ,就是一条路径。
    • 路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。比如根节点到 c 和 d 都是 3。
    • 结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。比如 b 的权是 5。
    • 结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。比如 b 带权路径长度 = 2 * 5 = 10
    • 树的带权路径长度:指树中所有叶子结点的带权路径长度之和。通常记作 “WPL”。比如下图中的树的带权路径长度 WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 36。

    在这里插入图片描述
    所以,当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,也叫“哈夫曼树”。

    在构建哈夫曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。在图 1 中,因为结点 a 的权值最大,所以理应直接作为根结点的孩子结点。

    有了这个概念,我们就可以开始构建哈夫曼树了。

    Ⅲ 哈夫曼树的生成及哈夫曼编码

    在构建哈夫曼树之前,我们先要知道什么是哈夫曼压缩。

    压缩算法有很多种,哈夫曼压缩是一种频度压缩。我举一个例子。

    假设一个文本文件全部由英文字母构成,那么哈夫曼压缩就是将出现次数(频度)最高的字母用最短的编码来表示。ASCII码占1byte,即8bit,那么将其用2bit的编码来取代,则每个字符会节省6bit的空间。

    哈夫曼压缩对应的就是哈夫曼编码,而哈夫曼编码就需要通过哈夫曼树来生成。现在我们来走一遍这个哈夫曼树生成以及哈夫曼编码构建的过程。

    A. 构造哈夫曼树

    我用一个字符串当作例子来构造一棵哈夫曼树。

    egeaefebaeeauefffeeffeebe

    a. 频度统计

    要构造一棵哈夫曼树,我们需要先知道每个字符的频度。

    字符频度
    a3
    b2
    e12
    f6
    g1
    u1

    b. 生成哈夫曼树

    我们需要找到最小频度的节点,然后生成新节点,生成过程如下👇
    第一步
    在这里插入图片描述
    第二步
    在这里插入图片描述
    第三步
    在这里插入图片描述
    第四步
    在这里插入图片描述
    第五步
    在这里插入图片描述
    这样,一棵哈夫曼树就构造完成了。

    B. 哈夫曼编码

    上一步我们构造出了一棵哈夫曼树,根据这棵树我们现在进行编码。
    首先,我们对方向编码,可以向左是0向右是1,也可以反过来,这只是一个编码规则。我定为向左为0.
    在这里插入图片描述
    接下来就是从根节点沿着这棵树编码。
    比如e,从根节点向左一次就到了,所以e的编码为:0
    同样的,比如f,需要从根节点先向右,再向左,所以f的编码是:10

    按照以上规律,我们可以写出哈夫曼编码

    字符编码
    a110
    b1110
    e0
    f10
    g11110
    u11111

    所以egeaefebaeeauefffeeffeebe转化成哈夫曼编码为:
    011110011001001110110001101111101010100010100011100

    哈夫曼编码完成。

    C. 解码

    解码依旧是根据构造的哈夫曼树,以及你制定的编码规则。

    011110011001001110110001101111101010100010100011100

    根据这个编码,我做几个解码。
    从根节点,先向左,到了e,所以第一个是e,然后回到根节点。
    向右,向右,向右,向右,向左,到了g,所以第二个是g,再回到根节点。

    根据这个规律,按照之前构造的哈夫曼树还原出这串字符串。
    这就是解码的实现。

    Ⅳ 总结

    哈夫曼编码其实在生活中非常常用到,因为它的压缩率比较高,而且丢包率也很低。

    这篇文章只是作为一个引子,简单讲述了哈夫曼编码的生成原理以及思想,下面的两篇文章就是实战了,我们将用哈夫曼编码的思想,实现一个真正可以压缩解压缩文件的程序,大家若有兴趣可以来看一看,自己动手和我一起实现一个有意思的程序。

    【C语言->数据结构与算法】->哈夫曼压缩&解压缩->第一阶段->哈夫曼编码&解码的实现

    【C语言->数据结构与算法】->哈夫曼压缩&解压缩->终局->压缩率百分之八十六

    展开全文
  • 哈夫曼树及哈夫曼编码和解码

    千次阅读 2018-11-02 23:07:35
    哈夫曼树,又称最优树,是带权路径最小的树。 基本概念: 节点间的路径长度:两个节点间所包含的边的数目。 树的路径长度:从根到树中任意节点的路径长度之和。 权:将节点赋予一定的量值,该量值成为权。 树的带权...

    哈夫曼树,又称最优树,是带权路径最小的树。
    基本概念:
    节点间的路径长度:两个节点间所包含的边的数目。
    树的路径长度:从根到树中任意节点的路径长度之和。
    权:将节点赋予一定的量值,该量值成为权。
    树的带权路径长度:树中所有叶子结点的带权路径长度。

    哈夫曼算法:给定一个保存权值的数组,求最优树的算法。对于此权值数组找出其中最小的权值和第二小的权值,用这两个权值创建树,并把这两个权值相加所得作为一个新权值放入到原数组中(注意:此时数组中已经去掉了刚才用过的权值),重复以上操作即可建立最优树。

    哈弗曼编码和解码的优点不再赘述。

    哈夫曼树的实现
    1.建立结构体,比较简单

    typedef struct Tree{
    	struct Tree *left;
    	struct Tree *right;
    	int data;
    }Tree;
    

    2.利用权值数组创建哈夫曼树(代码注释已相对清晰)

    Tree *create(int *a,int n){//对数组 a 进行实现哈夫曼树 a 中存放的为权值, n 为数组的长度
    	Tree *tree;
    	Tree **b;
    	int i,j; 
    	b = malloc(sizeof(Tree)*n);//动态一维数组的申请来保存权值 
    	for(i = 0; i < n; i++){
    		b[i] = malloc(sizeof(Tree));
    		b[i]->data = a[i];
    		b[i]->left = b[i]->right = NULL;
    	} 
    	//创建哈夫曼树
    	for(i = 1; i < n; i++){
    		int small1 = -1,small2;//small1指向权值最小,small2是第二小,其初始指向分别是数组的前两个元素
    								//注意前两个元素并不一定是最小的和第二小的
    		//下面一个 for 循环是让small1指向第一个权值,small2指向第二个权值 
    		for(j = 0; j < n; j++){  
    			if(b[j] != NULL && small1 == -1){
    				small1 = j;
    				continue;
    			}
    			if(b[j] != NULL){
    				small2 = j;
    				break;
    			}
    		} 
    		//接下来就是对数组剩下的权值逐个与small1、small2比较,找出最小与第二小的权值 
    		for(j = small2; j < n; j++){
    			if(b[j] != NULL){
    				if(b[j]->data < b[small1]->data){
    					small2 = small1;
    					small1 = j;
    				}
    				else if(b[small2]->data > b[j]->data){
    					small2 = j;
    				}
    			}
    		} 
    		
    		//由两个最小权值建立新树,tree 指向根节点 
    		tree = malloc(sizeof(Tree));
    		tree->data = b[small1]->data + b[small2]->data;
    		tree->left = b[small1];
    		tree->right = b[small2];
    		
    		//以下两步是用于重复执行 
    		b[small1] = tree;
    		b[small2] = NULL; 
    		
    	} 
    	
    	free(b);
    	return tree;
    }
    

    3.打印哈夫曼树

    //打印哈夫曼树 
    void print(Tree *tree){
    	if(tree){
    		printf("%d ",tree->data);
    		if(tree->left && tree->right){
    			printf("(");
    			print(tree->left);
    			if(tree->right)
    			printf(",");
    			print(tree->right);
    			printf(")");
    		}
    	}
    }
    

    4.获取哈夫曼树的带权路径长度

    //获得哈夫曼树的带权路径长度
    int getWeight(Tree *tree,int len){
    	if(!tree)
    	return 0;
    	if(!tree->left && !tree->right)//访问到叶子结点 
    	return tree->data * len;
    	return getWeight(tree->left, len + 1) + getWeight(tree->right,len + 1);//访问到非叶子结点 
    }
    

    5.下面便是哈夫曼编码与解码,思路也较为简单

    //哈夫曼编码 
    void getCoding(Tree *tree,int len){
    	if(!tree)
    	return;
    	static int a[20]; //定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一
    	int i;
    	if(!tree->left && !tree->right){
    		printf(" %d  的哈夫曼编码为:",tree->data);
    		for(i = 0; i < len; i++)
    		printf("%d",a[i]);
    		printf("\n");
    	}
    	else{//访问到非叶子结点时分别向左右子树递归调用,并把分支上的0、1编码保存到数组a ,的对应元素中,向下深入一层时len值增1 
    		a[len] = 0;
    		getCoding(tree->left, len + 1);
    		a[len] = 1;
    		getCoding(tree->right, len + 1);
    		
    	}
    }
    

    6.哈夫曼解码,比较容易实现
    节点与左子节点之间记为 0 ,节点与右节点之间记为 1 ,如图
    在这里插入图片描述

    //哈夫曼解码
    void Decoding(Tree *tree){
    	printf("请输入要解码的字符串\n");
    	char ch[100];//输入的待解码的字符串 
    	gets(ch);
    	int i;
    	int num[100];//用于保存字符串对应的0 1 编码对应的节点 
    	Tree *cur;
    	for(i = 0; i < strlen(ch); i++){
    		if(ch[i] == '0')
    		num[i] = 0;
    		else
    		num[i] = 1;
    	}
    	
    	if(tree){
    		i = 0;
    		while(i < strlen(ch)){
    			cur = tree;
    			while(cur->left && cur->right){
    				
    				if(num[i] == 0)
    				cur = cur->left;
    				else
    				cur = cur->right;
    				i++;
    			}
    			printf("%d",cur->data);
    		}
    		
    	}
    } 
    

    完整代码如下

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct Tree{
    	struct Tree *left;
    	struct Tree *right;
    	int data;
    }Tree;
    
    
    Tree *create(int *a,int n){//对数组 a 进行实现哈夫曼树 a 中存放的为权值, n 为数组的长度
    	Tree *tree;
    	Tree **b;
    	int i,j; 
    	b = malloc(sizeof(Tree)*n);//动态一维数组的申请来保存权值 
    	for(i = 0; i < n; i++){
    		b[i] = malloc(sizeof(Tree));
    		b[i]->data = a[i];
    		b[i]->left = b[i]->right = NULL;
    	} 
    	//创建哈夫曼树
    	for(i = 1; i < n; i++){
    		int small1 = -1,small2;//small1指向权值最小,small2是第二小,其初始指向分别是数组的前两个元素
    								//注意前两个元素并不一定是最小的和第二小的
    		//下面一个 for 循环是让small1指向第一个权值,small2指向第二个权值 
    		for(j = 0; j < n; j++){  
    			if(b[j] != NULL && small1 == -1){
    				small1 = j;
    				continue;
    			}
    			if(b[j] != NULL){
    				small2 = j;
    				break;
    			}
    		} 
    		//接下来就是对数组剩下的权值逐个与small1、small2比较,找出最小与第二小的权值 
    		for(j = small2; j < n; j++){
    			if(b[j] != NULL){
    				if(b[j]->data < b[small1]->data){
    					small2 = small1;
    					small1 = j;
    				}
    				else if(b[small2]->data > b[j]->data){
    					small2 = j;
    				}
    			}
    		} 
    		
    		//由两个最小权值建立新树,tree 指向根节点 
    		tree = malloc(sizeof(Tree));
    		tree->data = b[small1]->data + b[small2]->data;
    		tree->left = b[small1];
    		tree->right = b[small2];
    		
    		//以下两步是用于重复执行 
    		b[small1] = tree;
    		b[small2] = NULL; 
    		
    	} 
    	
    	free(b);
    	return tree;
    }
    
    //打印哈夫曼树 
    void print(Tree *tree){
    	if(tree){
    		printf("%d ",tree->data);
    		if(tree->left && tree->right){
    			printf("(");
    			print(tree->left);
    			if(tree->right)
    			printf(",");
    			print(tree->right);
    			printf(")");
    		}
    	}
    }
    
    //获得哈夫曼树的带权路径长度
    int getWeight(Tree *tree,int len){
    	if(!tree)
    	return 0;
    	if(!tree->left && !tree->right)//访问到叶子结点 
    	return tree->data * len;
    	return getWeight(tree->left, len + 1) + getWeight(tree->right,len + 1);//访问到非叶子结点 
    }
    
    //哈夫曼编码 
    void getCoding(Tree *tree,int len){
    	if(!tree)
    	return;
    	static int a[20]; //定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一
    	int i;
    	if(!tree->left && !tree->right){
    		printf(" %d  的哈夫曼编码为:",tree->data);
    		for(i = 0; i < len; i++)
    		printf("%d",a[i]);
    		printf("\n");
    	}
    	else{//访问到非叶子结点时分别向左右子树递归调用,并把分支上的0、1编码保存到数组a ,的对应元素中,向下深入一层时len值增1 
    		a[len] = 0;
    		getCoding(tree->left, len + 1);
    		a[len] = 1;
    		getCoding(tree->right, len + 1);
    		
    	}
    }
    
    //哈夫曼解码
    void Decoding(Tree *tree){
    	printf("请输入要解码的字符串\n");
    	char ch[100];//输入的待解码的字符串 
    	gets(ch);
    	int i;
    	int num[100];//用于保存字符串对应的0 1 编码对应的节点 
    	Tree *cur;
    	for(i = 0; i < strlen(ch); i++){
    		if(ch[i] == '0')
    		num[i] = 0;
    		else
    		num[i] = 1;
    	}
    	
    	if(tree){
    		i = 0;
    		while(i < strlen(ch)){
    			cur = tree;
    			while(cur->left && cur->right){
    				
    				if(num[i] == 0)
    				cur = cur->left;
    				else
    				cur = cur->right;
    				i++;
    			}
    			printf("%d",cur->data);
    		}
    		
    	}
    } 
    
    int main(int argc, char *argv[]) {
    	int a[4] = {2,6,7,3};
    	Tree *tree = create(a,4);
    	print(tree);
    	printf("\n哈夫曼树的权值为:");
    	printf("%d\n",getWeight(tree,0));
    	getCoding(tree,0);
    	printf("解码时请参照上方编码\n");
    	Decoding(tree); 
    }
    

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

    展开全文
  • 基于哈夫曼树的数据压缩算法

    千次阅读 多人点赞 2019-05-13 13:14:40
    综合实验2 基于哈夫曼树的数据压缩算法 实验日期 2019.04.29 综合实验二 基于哈夫曼树的数据压缩算法 一、实验目的 1.掌握哈夫曼树的构造算法 2.掌握哈夫曼编码的构造算法 二、实验内容 输入一串字符串,根据给.....
  • 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 构造过程:...
  • //字符的个数 //初始化哈夫曼树ht void initHt() { FILE * fp; char ch; int i=0; //从文件document/character.txt中读出要编码的字符和权值 if((fp=fopen("document/character.txt","r"))==NULL){ printf("can not...
  • 哈夫曼树与哈夫曼编码以及解码

    千次阅读 多人点赞 2020-07-22 16:23:13
    哈夫曼树即是带权路径最小的二叉树 可以看出,哈夫曼树的特点是 1.权值越大的叶子节点靠根节点越近,越小的越远; 2.只有度为0(叶子节点)和度为2(分支节点)的节点,不存在度为一的节点;(这一特点很重要) ...
  • 哈夫曼树以及编解码

    万次阅读 多人点赞 2016-09-10 14:43:39
    这一篇要总结的是树中的最后一种,即哈夫曼树,我想从以下几点对其进行总结: 1,什么是哈夫曼树? 2,如何构建哈夫曼树? 3,哈夫曼编码? 4,算法实现? 回到顶部 一,什么是哈夫曼树 什么是...
  • 哈夫曼树以其编码解码 本人大二学渣,写的不好的地方大神勿喷! 哈夫曼树以其编码解码要求: 1.从终端读入字符集大小为n(即字符的个数),逐一输入n个字符和相应的n个权值(即字符出现的频度),建立哈夫曼树,进行...
  • 哈夫曼树解码

    2018-01-12 16:24:13
    输入格式如下 6 abcdef 6 1 5 4 2 4 代码如下: #include #include #include #include #include ... printf("哈夫曼树解码结果如下:\n");  print(); }
  • 代码: #pragma once #include<iostream> #include<stack> using namespace std;.../*哈夫曼树结点类HuffmanNode声明*/ template<class T> class HuffmanNode { private: Hu...
  • 最小堆实现哈夫曼树的构造及哈夫曼编码、解码

    千次阅读 多人点赞 2018-12-03 22:49:15
    最大堆(最小堆思想差不多)这里就不再多说,这里主要讲讲哈夫曼树的定义及实现。 Huffman Tree 相关概念: 结点的路径长度:从根结点到该结点的路径上分支的数目。 树的路径长度:树中每个结点的路径长度之和。...
  • 综合训练2 利用哈夫曼树进行编码与解码 一、主要目的: 理解哈夫曼树的概念、掌握哈夫曼树的建立以及利用利用哈夫曼树进行哈夫曼编码的方法。 二、主要内容: 在基于哈夫易树进行哈夫易编码的基础理论之上,完成...
  • 哈夫曼树哈夫曼树编码

    千次阅读 2015-09-09 15:50:57
    本文转自哈夫曼树哈夫曼树编码 在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用...
  • 下图为代码测试的(数组格式) 代码实现: import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = { 4, 6, 8, 5, 9 }; heapSort(arr); Syst...
  • 最近完成了数据结构课程设计,被分到的题目是《哈夫曼编码和解码》,现在在这篇博文里分享一下自己的成果。  我在设计时,在网上参考了很多老师和前辈的算法和代码,向他们表示感谢!他们的成果给了我很多启示和...
  • 纠结了两天,终于解决了这个问题,分享给大家自己的思路。 将一组无序数列建立最小堆,从最小堆中...2、没有度为1的节点 3、哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树 4、n个叶子结点的哈夫曼树共有2n-1个
  • 设计一个算法,对给定的若干码串进行相应的解码,并输出解码结果。 Input: 有多组测试数据,每组数据由结点信息和码串两部分组成。结点信息部分的第一行为一个整数n(n),表示以下有n个结点信息,每个结点信息...
  • 哈夫曼编码解码及压缩存储

    千次阅读 2018-11-19 19:37:45
    哈夫曼树即最优二叉树,算法如下: (1)在当前未使用结点中找出两个权重最小的作为左右孩子,计算出新的根结点 (2)新的根结点继续参与过程(1),直至所有结点连接为一棵树 如下图,symbol为具体字符,Frequency...
  • void Encode() 哈夫曼树解码 void WPL() 计算带权路径长度 所选实例: 所选实例 创建哈夫曼树 步骤: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的...

空空如也

空空如也

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

哈夫曼树解码算法