精华内容
下载资源
问答
  • 哈夫曼树编码实验报告.doc
    2021-05-20 12:13:16

    数据结构课程设计

    报告

    题 目: 哈夫曼编码/译码

    学 院 数学与信息科学学院

    学科门类 理科

    专 业 数学类

    学 号 2013433033

    姓 名 田娟

    2014年 12 月30日

    目 录

    一、需求分析

    程序的功能··················································3

    2.输入输出的要求··············································3

    3.测试数据····················································3

    二、概要设计

    1.本程序所用的抽象数据类型的定义·······························3

    主程序模块···················································3

    主模块的流程及各子模块的主要功能·····························4

    模块之间的层次关系···········································4

    三、详细设计

    1.采用c语言定义相关的数据类型·································4

    2. 伪码算法·····················································5

    四、调试分析

    1.调试中遇到的问题及对问题的解决方法···························15

    五、使用说明及测试结果

    1.建立哈夫曼树,输入叶子结点个数,权值,字符集··················15

    2.编码··························································15

    3.译码··························································16

    4.显示码文······················································16

    5.显示哈夫曼树··················································16

    六、源程序

    一、需求分析

    1.程序的功能;

    哈夫曼编码是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率,加快信息传输速度,降低传输成本。数据压缩的过程称为编码,解压缩的过程称为译码。进行信息传递时,发送端通过一个编码系统对待传数据(明文)预先编码,而接收端将传来的数据(密文)进行译码。

    2.输入输出的要求;:

    2.1.构造哈夫曼树及哈夫曼编码:从终端读入字符集大小n、n个字符以及n个对应的权值,建立哈夫曼树;利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码,并保存。

    2.2编码:利用已构造的哈夫曼编码对“明文”文件中的正文进行编码,然后将结果存入“密文”文件中。

    2.3.译码:将“密文”文件中的0、1代码序列进行译码。

    2.4.打印“密文”文件:将文件以紧凑格式显示在终端上,每行30个代码;同时,将此字符形式的编码文件保存。

    2.5.打印哈夫曼树及哈夫曼编码:将已在内存中的哈夫曼树以凹入表形式显示在终端上,同时将每个字符的哈夫曼编码显示出来;并保存到文件。

    3.测试数据。

    3.1.令叶子结点个数N为4,权值集合为{1,3,5,7},字符集合为{A,B,C,D},且字符集与权值集合一一对应。

    3.2.请自行选定一段英文文本,统计给出的字符集,实际统计字符的频度,建立哈夫曼树,构造哈夫曼编码,并实现其编码和译码。

    二、概要设计

    1.本程序所用的抽象数据类型的定义;

    class HuffmanTree //哈夫曼树

    {

    private:

    HuffmanNode *Node; //Node[]存放哈夫曼树

    int LeafNum; //哈夫曼树的叶子个数,也是源码个数

    2.主程序模块

    main()

    2.2 建立哈夫曼树函数

    // 函数功能:建立哈夫曼树

    void HuffmanTree::CreateHuffmanTree()

    2.3 函数功能:为哈夫曼树编码

    void HuffmanTree::Encoder()

    2.4 函数功能:对哈夫曼树

    更多相关内容
  • 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵哈夫曼树哈夫曼树的结点结构包括权值,双亲,左右孩子;假如由n个字符来构造一棵哈夫曼树,则...
  • 哈夫曼树编码

    2014-04-24 23:25:26
    输入字符串,生成对应的哈弗曼数编码……大一数据结构课程实验。
  • 本文实例为大家分享了C++实现哈夫曼树编码解码,供大家参考,具体内容如下 代码: #pragma once #include #include using namespace std; #define m 20 stack<int> s; /*哈夫曼树结点类HuffmanNode声明*/ ...
  • 主要介绍了Python完成哈夫曼树编码过程及原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 哈夫曼树编码解码.c

    2019-11-21 19:16:53
    该文件是关于用C语言构建哈夫曼树的代码,其中包括对字符的统计、对文档读取然后包括建树的过程,和对哈夫曼树解码的过程。
  • 利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读人),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 (3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码,结果...
  • 实 验 报 告 实验目的 掌握哈夫曼树的基本概念及所用的存储结构 掌握哈夫曼树的建立算法 掌握哈夫曼树的应用哈夫曼树编码和译码 实验内容 给定权值529781423311建立哈夫曼树输出哈夫曼编码对上述给定的哈夫曼树及...
  • 使用文件的技术对输入的数据进行哈夫曼编码,并能产生相应的编码表和译码表
  • 哈夫曼树
  • 哈夫曼树编码-C语言

    千次阅读 多人点赞 2019-11-10 17:02:45
    哈夫曼树编码 1.实验目的 了解二叉树的定义,理解二叉树的基本性质和存储结构,掌握哈夫曼树的构造,实现哈夫曼编码与译码算法。 2.实验内容 从键盘输入一串电文字符与权值,输出对应的哈夫曼编码;从键盘输入一...

    哈夫曼树编码

    1.实验目的

    了解二叉树的定义,理解二叉树的基本性质和存储结构,掌握哈夫曼树的构造,实现哈夫曼编码与译码算法。

    2.实验内容

    从键盘输入一串电文字符与权值,输出对应的哈夫曼编码;从键盘输入一串二进制代码,输出对应的电文字符串。具体步骤如下:

    1. 构造一棵哈夫曼树;
    2. 实现哈夫曼编码;
    3. 对哈夫曼编码生成的二进制串进行译码;
    4. 要求程序中字符和权值是可变的,实现程序的灵活性。

    3.实验工具

    Dev-C++

    4.实验代码

    //Authors:xioabei
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    typedef char **HuffmanCode;   //动态分配数组存储哈夫曼编码表 
    typedef struct{
     int weight;
     int parent,lchild,rchild;
    }HTNode,*HuffmanTree;
    typedef struct Code{
     char ch;
     int weight;
     Code *next;
    }*CodeLink;
    //创建字符与权值 
    void CreateCouple(CodeLink &Couple,int n){
     int i;
     CodeLink r,p;
     Couple = (CodeLink)malloc(sizeof(Code));
     Couple->next = NULL;
     r = Couple;
     for(i = 1;i<=n;i++){
      p = (CodeLink)malloc(sizeof(Code));
      printf("[请输入第%d个字符与权值:]\n>>>",i);
      getchar();
      scanf("%c %d",&Couple[i].ch,&Couple[i].weight);
      p->next = NULL;
      r->next = p;
      r = p;
     }
     printf("\n[成功创建字符与权值]\n");
    }
    //选择最小的两个 
    void Select(HuffmanTree HT,int n,int *s1, int *s2){
     int i,min,max;
     for(i=1;i<=n;i++){
      if(HT[i].parent == 0){
       *s2 = i;
       max = i;
       *s1 = i;
      }
     }
     for(i=1;i<=n;i++){
      if(HT[*s1].weight>HT[i].weight && HT[i].parent == 0)
       *s1 = i;
      if(HT[max].weight<HT[i].weight && HT[i].parent == 0)
       max = i;
     }
     min = HT[*s1].weight;
     HT[*s1].weight = HT[max].weight;
     for(i=1;i<=n;i++)
      if(HT[*s2].weight>HT[i].weight && HT[i].parent == 0)
       *s2 = i;
     HT[*s1].weight = min;
     printf("%d--%d\n",HT[*s1].weight,HT[*s2].weight);
    }
    //创建哈夫曼树 
    void CreateHuffmanTree(HuffmanTree &HT,CodeLink Couple,int n){
     printf("\n---------开始创建哈夫曼树---------\n");
     int m,i,s1=1,s2=1,*p = &s1,*q = &s2;
     //构造哈夫曼树HT
     if(n<=1)
      return;
     m=2*n-1;
     HT =  (HTNode*)malloc(sizeof(HTNode)*(m+1)); //由于0号单元未用,所以需要动态分配m+1个单元,HT[m]表示根结点 
     for(i=1;i<=m;i++){       //将1~m号单元初始化为0 
      HT[i].parent = 0;
      HT[i].lchild = 0;
      HT[i].rchild = 0;
     }
     printf("\n初始化成功……\n"); 
     for(i=1;i<=n;i++)       //输入前n个单元叶子结点权值
      HT[i].weight = Couple[i].weight;
    //---------- 初始化工作结束,开始创建哈夫曼树 -----------// 
     for(i=n+1;i<=m;i++){
    //  通过n-1次选择、删除、合并来创建哈夫曼树
      Select(HT,i-1,p,q);
    //  在HT[k](1<=k<=i-1)中选择双亲域为0且权值最小的结点,并且返回它们在HT中序号s1,s2
      HT[s1].parent = i;
      HT[s2].parent = i;
    //  得到新结点i,从森林中删除s1,s2,将s1,s2双亲域由0改为i
      HT[i].lchild = s1;      //s1,s2分别作为i的左右孩子 
      HT[i].rchild = s2;
      HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权值为左右孩子权值之和 
     }
     printf("\n---------结束创建哈夫曼树---------\n");
    }
    //创建哈夫曼编码 
    void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
     int c,f,start,i;
     char *cd; 
     //从叶子结点逆向求每个字符的哈夫曼编码,存储在编码表HC中 
     HC = (HuffmanCode)malloc(sizeof(char*)*(n+1));  //分配n个字符编码表空间 
     cd = (char*)malloc(sizeof(char)*n);    //分配临时存放每个字符编码动态数组空间 
     cd[n-1] = '\0';         //编码结束符 
     for(i=1;i<=n;i++){        //逐个字符求哈夫曼编码 
      start = n-1;   //start开始指向最后,即编码结束位置 
      c = i;
      f = HT[i].parent;  //f指向c的双亲结点
      while(f!=0){   //从叶子结点开始向上回溯,直到根结点 
       --start;   //回溯一次start向前指一个位置 
       if(HT[f].lchild==c)
        cd[start] = '0';//结点c是f的左孩子,则生成代码"0" 
       else
        cd[start] = '1';//结点c是f的右孩子,则生成代码"1" 
       c = f;
       f = HT[f].parent; //继续向上回溯 
      }      //求出第i个字符编码 
      HC[i] = (char*)malloc(sizeof(char)*(n-start)); //为第i个字符编码分配空间 
      strcpy(HC[i],&cd[start]);//将求得的编码从临时空间cd中复制到HC当前行中
      puts(HC[i]);
     }
     free(cd);     //释放临时空间 
     printf("\n---------哈夫曼树编码成功---------\n");
    }
    //编码 
    void Encode(HuffmanCode HC,CodeLink Couple,char T[],int n){
     int i,j,k,t;
     printf("[编码如下:]\n");
     for(i=0;T[i]!='\0';i++)
      for(j=1;j<=n;j++){
       if(Couple[j].ch==T[i]){
        for(k=1;k<=n;k++){
         if(Couple[j].weight==Couple[k].weight)
          puts(HC[k]);
        }
       } 
     }
    }
    //译码 
    void Decode(HuffmanCode HC,CodeLink Couple,char T[],int n){
     int i,j,k,location = 0,len,tag;
     printf("[译码如下:]\n");
     for(i=0;T[location+1]!='\0';i++){
      for(j=1;j<=n;j++){
       len = strlen(HC[j]);
       tag = 1;
       for(k=0;k<len;k++){
        if(HC[j][k]!=T[location+k]){
         tag = 0;
         break;
        }
       }
       if(tag==1){
        printf("%c",Couple[j].ch);
        break;
       }
      }
      len = strlen(HC[j]);
      location += len;
     }
    }
    // 打印菜单 
    void PrintMenu(){
     printf("\n**********菜单**********\n");
     printf("\n1.创建字符与权值;\n");
     printf("2.创建哈夫曼树;\n");
     printf("3.生成哈夫曼编码;\n");
     printf("4.编码;\n");
     printf("5.译码;\n");
     printf("0.退出;\n");
     printf("\n************************\n");
     printf("[请输入你的选择:]\n>>>");
    }
    //主函数 
    int main(){
     HuffmanTree HT;
     HuffmanCode HC;
     CodeLink Couple; 
     int i,n,user;
     char T[100];
     while(1){
      PrintMenu();
      scanf("%d",&user);
      switch(user){
       case 1:{
        printf("[请输入叶子结点数:]\n>>>");
        scanf("%d",&n);
        CreateCouple(Couple,n);
        break;
       }
       case 2:CreateHuffmanTree(HT,Couple,n);break;
       case 3:CreateHuffmanCode(HT,HC,n);break;
       case 4:{
        printf("[请输入要编码的字符:]\n>>>");
        getchar();
        gets(T);
        Encode(HC,Couple,T,n);
        break;
       }
       case 5:{
        printf("[请输入要编码的字符:]\n>>>");
        getchar();
        gets(T);
        Decode(HC,Couple,T,n);
        break; 
       } 
       case 0:exit(0);
      }
     }
     return 0;
    }

    5.实验结果

    Haffuman

    Haffuman

    6.实验分析

    1.HT初态

    HT初态
    2.HT终态
    HT终态
    3.示意图
    哈夫曼树

    7.资料

    1951年,哈夫曼在麻省理工学院(MIT)攻读博士学位,他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺(Robert Fano)出的学期报告题目是:查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,哈夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。哈夫曼使用自底向上的方法构建二叉树,避免了次优算法香农-范诺编码(Shannon–Fano coding)的最大弊端──自顶向下构建树。

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

    在计算机数据处理中,哈夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。

    展开全文
  • 数据结构课程 实验报告 实验名称 哈弗曼编码和译码 专业班级 电子信息科学与技术0904 姓 名 秦杰 学 号 1404090506 指导教师 胡志坤 2011年 11月 实验四哈夫曼编码和译码 实验目的和要求 掌握哈夫曼树的基本概念及其...
  • 哈夫曼树编码压缩

    2015-11-04 23:49:21
    利用哈夫曼树编码的无损压缩与解压软件,c++语言版本,操作简单,将文件拖至窗口即可,显示压缩比,程序设计课程会用到
  • 根据创建好的哈夫曼树创建一张哈夫曼编码表  3.输入一串哈夫曼序列,输出原始字符  三.设计思想:  1.首先要构造一棵哈夫曼树哈夫曼树的结点结构包括权值,双亲,左右孩子;假如由n个字符来构造一棵哈夫曼...
  • C语言 哈夫曼树编码、译码、输出。

    千次阅读 2022-02-15 21:10:07
    使用下标模拟指针和结构体指针构建哈夫曼树

    哈夫曼树的知识点概述网上有很多了,就不再补充,主要是分享一下自己对一道题的解题思路。
    在这里插入图片描述
    在这里插入图片描述

    概述:构建哈夫曼树时,先用下标模拟数组,从叶子结点开始往上构建完整棵哈夫曼树。但和普通二叉树不同,叶子结点在1-n (0号位不用,n为输入的字符个数),根结点在 2n-1 ,其他位置为构造出的中介结点。
    在这里插入图片描述

    虽然哈夫曼树构建好了,很多操作树的方法得依赖于下标模拟的指针实现,每次方法调用的参数都得传入整个结构体数组。所以在构建时,多定义一个结构体指针。构建好哈夫曼树之后,每次操作树的时候可以通过传入树根的指针,当作一棵普通的二叉树来操作整棵树。(详细代码在哈夫曼树构建。)

    (笔者第一次写博客,内容难免有些浅显或错误之处,还请大家指出一起探讨,共勉。)

    走个流程。

    1. 树结点结构体。
    二叉树可以用下标模拟指针(属性 L、R),也可以自己定义结构体指针(LChild、RChild)。这里笔者为了方便后面的先序输出哈夫曼树存储的字符,就定义了结构体指针。

    #define M N * 2 - 1   // 30个字符,计算可得出总节点个数。
    #define N 30          // 叶子节点个数。假设最多输入30个字符。
    #define MAX 999
    // 哈夫曼树结构体。
    typedef struct tree {
        char ch;         // 字符。
        double weight;   // 权重。
        int parent;     // 父结点。
        int L, R;        // 左右子树的下标。
        struct tree *LChild;	// 左孩子结点指针。
        struct tree *RChild;	// 右孩子结点指针。
        char hashcode[N];   // 字符的哈希编码。
        int is_leaves;		// 是否是叶子结点标记。
    } tree, Htree[M];		// tree 是单个结点,Htree 是结构体数组。
    

    2. 哈夫曼树构建。

    // 选择最小权重的两个节点
    // 具体代码实现大同小异。找出权重最小的两个结点,标记下标位置,再修改父亲结点参数,下次不再进行参与比较排序。
    void Select(Htree ht, int n, int *s1, int *s2) {
        int i;
        double min1 = MAX, min2 = MAX;
        *s1 = 0;
        *s2 = 0;
        for (i = 1; i <= n; i++) {
            if (ht[i].parent == 0) {
                if (ht[i].weight < min1) {
                    min2 = min1;
                    *s2 = *s1;
                    min1 = ht[i].weight;
                    *s1 = i;
                } else if (ht[i].weight < min2) {
                    min2 = ht[i].weight;
                    *s2 = i;
                }
            }
        }
    }
    
    // 构建哈夫曼树
    void crateHtree(Htree ht, int n) {
        int i;
        // 初始化叶子节点。
        // 叶子结点从1-n。(0号位不用)
        char s[10];
        for (i = 1; i <= n; i++) {
            ht[i].parent = 0;
            ht[i].L = 0;
            ht[i].R = 0;
            ht[i].is_leaves = 1;
            ht[i].RChild = NULL;
            ht[i].LChild = NULL;
        }
        // 初始化树的非叶子节点。 n+1项开始。
        for (i = n + 1; i <= 2 * n - 1; i++) {
            ht[i].weight = 0;
            ht[i].parent = 0;
            ht[i].L = 0;
            ht[i].R = 0;
            ht[i].is_leaves = 0;	
            ht[i].RChild = NULL;
            ht[i].LChild = NULL;
        }
        // 开始构建哈夫曼树。
        // 和平时的构建树方法不同,从下往上构建,新的结点为现有结点的父亲结点,新结点的左右孩子指针指向原有参与构建的两个结点。
        int s1, s2;
        for (i = n + 1; i <= n * 2 - 1; i++) {
            Select(ht, i - 1, &s1, &s2);
            // 新的中介结点。
            ht[i].weight = ht[s1].weight + ht[s2].weight;
            ht[i].parent = 0;
            ht[s1].parent = i;
            ht[s2].parent = i;
            // 新结点下标模拟的指针初始化。
            ht[i].L = s1;
            ht[i].R = s2;
            // 新节点结构体指针初始化。
            ht[i].RChild = &ht[s2];		
            ht[i].LChild = &ht[s1];
        }
    }
    
    

    3. 哈夫曼编码。

    // 根据哈夫曼树创建哈夫曼编码,从叶子节点开始。
    void crateTcode(Htree ht, int n) {
        int i;
        char cd[n];
        for (i = 1; i <= n; i++) {
        	// 编码长度最大为n-1。c为当前结点的下标,p为当前结点的父亲结点下标
            int start = n - 1, c = i, p = ht[i].parent;
            while (p != 0) {
                start--;
                if (ht[p].L == c)
                    cd[start] = '0';
                else
                    cd[start] = '1';
                // 迭代更新
                c = p;
                p = ht[c].parent;
            }
            // 将处理后的哈希节点存入哈希结构体数组。
            // tps: 编码不一定是最大长度,中间可能有没处理的其他字符,需要判断是否是0,1编码才存入字符串中。
            int t = 0;
            for (int j = 0; j < n; j++) {
                if (cd[j] == '0' || cd[j] == '1') {
                    ht[i].hashcode[t] = cd[j];
                    t++;
                }
            }
            memset(cd, 0, sizeof cd);     // 清空cd字符串。
        }
    }
    

    4. 译码。

    // 翻译编码
    // 优:不用预先设置字符串数组存储翻译后的内容,也不用考虑长度范围。
    // 缺:无论编码是否能翻译,都会输出"original:"。
    void Search(Htree ht, const char String[2000], int n) {
        int t = 2 * n - 1;
        printf("original:");
        unsigned long len = strlen(String); // 函数结果返回无符号长整型。
        for (int i = 0; i < len; i++) {
            if (String[i] == '0') {
                t = ht[t].L;
                if (ht[t].is_leaves) {
                    printf("%c", ht[t].ch);
                    t = 2 * n - 1;
                }
            } else {
                t = ht[t].R;
                if (ht[t].is_leaves) {
                    printf("%c", ht[t].ch);
                    t = 2 * n - 1;
                }
            }
        }
    }
    

    5. 输出。

    // 先序输出所有的节点哈希编码。
    // 递归实现先序遍历。
    void PreOder(tree *root) {
        if (root->is_leaves)
            printf("%c:%s\n", root->ch, root->hashcode);
        if (root->LChild) PreOder(root->LChild);
        if (root->RChild) PreOder(root->RChild);
    }
    

    6. 主函数

    int main() {
        Htree ht;
        char String[2000];
        int n;
        scanf("%d", &n);
        // 输出并存储数据。
        for (int i = 1; i <= n; i++) {
            char s[10];
            scanf("%s", s);
            ht[i].ch = s[0];                                            // 取出第一个字符。
            ht[i].weight = strtod(strcpy(s, s + 1), NULL);  // 取出字符后的权值。
        }
        scanf("%s", String);            // 读入需要翻译的编码。
        crateHtree(ht, n);              // 构建哈夫曼树。
        crateTcode(ht, n);              // 构建哈夫曼编码。
        PreOder(&ht[2 * n - 1]);        // 哈夫曼树树根最后形成。传入树根,可以通过指针遍历(先序)。
        Search(ht, String, n);          // 传入结构体数组。(传入指针可以更优,注:这里写的方法参数是结构体数组。)
        return 0;
    }
    

    完整代码。

    #include<stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    #define M N * 2 - 1   // 30个词频,叶子节点个数。
    #define N 30          // 总节点个数。
    #define MAX 999
    // 哈夫曼树结构体。
    typedef struct tree {
        char ch;         // 字符
        double weight;   // 权重
        int parent;     // 父节点
        int L, R;        // 左右子树
        struct tree *LChild;
        struct tree *RChild;
        char hashcode[N];   // 字符的哈希编码
        int is_leaves;
    } tree, Htree[M];
    
    // 选择最小权重的两个节点
    void Select(Htree ht, int n, int *s1, int *s2) {
        int i;
        double min1 = MAX, min2 = MAX;
        *s1 = 0;
        *s2 = 0;
        for (i = 1; i <= n; i++) {
            if (ht[i].parent == 0) {
                if (ht[i].weight < min1) {
                    min2 = min1;
                    *s2 = *s1;
                    min1 = ht[i].weight;
                    *s1 = i;
                } else if (ht[i].weight < min2) {
                    min2 = ht[i].weight;
                    *s2 = i;
                }
            }
        }
    }
    
    // 构建哈夫曼树
    void crateHtree(Htree ht, int n) {
        int i;
        // 初始化叶子节点。
        char s[10];
        for (i = 1; i <= n; i++) {
            ht[i].parent = 0;
            ht[i].L = 0;
            ht[i].R = 0;
            ht[i].is_leaves = 1;
            ht[i].RChild = NULL;
            ht[i].LChild = NULL;
        }
        // 初始化树的非叶子节点。 n+1项开始。
        for (i = n + 1; i <= 2 * n - 1; i++) {
            ht[i].weight = 0;
            ht[i].parent = 0;
            ht[i].L = 0;
            ht[i].R = 0;
            ht[i].is_leaves = 0;
            ht[i].RChild = NULL;
            ht[i].LChild = NULL;
        }
        // 开始构建哈夫曼树。
        int s1, s2;
        for (i = n + 1; i <= n * 2 - 1; i++) {
            Select(ht, i - 1, &s1, &s2);
            ht[i].weight = ht[s1].weight + ht[s2].weight;
            ht[i].parent = 0;
            ht[s1].parent = i;
            ht[s2].parent = i;
            ht[i].L = s1;
            ht[i].R = s2;
            ht[i].RChild = &ht[s2];
            ht[i].LChild = &ht[s1];
        }
    }
    
    // 根据哈夫曼树创建哈夫曼编码,从叶子节点开始。
    void crateTcode(Htree ht, int n) {
        int i;
        char cd[n];
        for (i = 1; i <= n; i++) {
            int start = n - 1, c = i, p = ht[i].parent;
            while (p != 0) {
                start--;
                if (ht[p].L == c)
                    cd[start] = '0';
                else
                    cd[start] = '1';
                c = p;
                p = ht[c].parent;
            }
            // 将处理后的哈希节点存入哈希结构体数组。
            // tps: 中间可能有其他字符。
            int t = 0;
            for (int j = 0; j < n; j++) {
                if (cd[j] == '0' || cd[j] == '1') {
                    ht[i].hashcode[t] = cd[j];
                    t++;
                }
            }
            memset(cd, 0, sizeof cd);     // 清空cd字符串。
        }
    }
    
    // 先序输出所有的节点哈希编码。
    // 递归实现先序遍历。
    void PreOder(tree *root) {
        if (root->is_leaves)
            printf("%c:%s\n", root->ch, root->hashcode);
        if (root->LChild) PreOder(root->LChild);
        if (root->RChild) PreOder(root->RChild);
    }
    
    // 翻译编码
    void Search(Htree ht, const char String[2000], int n) {
        int t = 2 * n - 1;
        printf("original:");
        unsigned long len = strlen(String); // 函数结果返回无符号长整型。
        for (int i = 0; i < len; i++) {
            if (String[i] == '0') {
                t = ht[t].L;
                if (ht[t].is_leaves) {
                    printf("%c", ht[t].ch);
                    t = 2 * n - 1;
                }
            } else {
                t = ht[t].R;
                if (ht[t].is_leaves) {
                    printf("%c", ht[t].ch);
                    t = 2 * n - 1;
                }
            }
        }
    }
    
    int main() {
        Htree ht;
        char String[2000];
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            char s[10];
            scanf("%s", s);
            ht[i].ch = s[0];                                            // 取出第一个字符。
            ht[i].weight = strtod(strcpy(s, s + 1), NULL);  // 取出字符后的权值。
        }
        scanf("%s", String);            // 读入需要翻译的编码。
        crateHtree(ht, n);              // 构建哈夫曼树。
        crateTcode(ht, n);              // 构建哈夫曼编码。
        PreOder(&ht[2 * n - 1]);   		// 传入树根,可以通过结构体指针遍历(先序)。
        Search(ht, String, n);          // 传入结构体数组。(传入指针可以更优,注:这里写的方法参数是结构体数组。)
        return 0;
    }
    
    
    
    展开全文
  • 哈夫曼树和哈夫曼树编码一、名词介绍二、哈夫曼树的基本概念三、构建哈夫曼树四、哈弗曼树中结点结构五、哈弗曼树中的查找算法六、构建哈弗曼树的代码实现七、哈夫曼编码八、完整代码(可运行)九、总结 一、名词...

    一、名词介绍

    (1)路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径。

    (2)路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

    (3)结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。例如,图 1 中结点 a 的权为 7,结点 b 的权为 5。

    (4)结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如,图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

    树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为:

    WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

    在这里插入图片描述

    二、哈夫曼树的基本概念

    当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”

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

    三、构建哈夫曼树

    对于给定的有各自权值的 n 个结点,构建哈夫曼树有一个行之有效的办法:
    (1)在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;
    (2)在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;
    (3)重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树。
    在这里插入图片描述
    上图中,(A)给定了四个结点a,b,c,d,权值分别为7,5,2,4;第一步如(B)所示,找出现有权值中最小的两个,2 和 4 ,相应的结点 c 和 d 构建一个新的二叉树,树根的权值为 2 + 4 = 6,同时将原有权值中的 2 和 4 删掉,将新的权值 6 加入;进入(C),重复之前的步骤。直到(D)中,所有的结点构建成了一个全新的二叉树,这就是哈夫曼树。

    四、哈弗曼树中结点结构

    构建哈夫曼树时,首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始,不断地构建新的父结点,直至树根,所以结点中应包含指向父结点的指针。但是在使用哈夫曼树时是从树根开始,根据需求遍历树中的结点,因此每个结点需要有指向其左孩子和右孩子的指针。

    所以,哈夫曼树中结点构成用代码表示为:

    //哈夫曼树结点结构
    typedef struct 
    {
      int weight;  //结点权重
      int parent, left, right;  //父结点、左孩子、右孩子在数组中的位置下标
    }HTNode, *HuffmanTree;

    五、哈弗曼树中的查找算法

    构建哈夫曼树时,需要每次根据各个结点的权重值,筛选出其中值最小的两个结点,然后构建二叉树。

    查找权重值最小的两个结点的思想是:从树组起始位置开始,首先找到两个无父结点的结点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需要考虑:

    (1)如果比两个结点中较小的那个还小,就保留这个结点,删除原来较大的结点;
    (2)如果介于两个结点权重值之间,替换原来较大的结点;

    代码实现:

    //HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
    void Select(HuffmanTree HT, int end, int *s1, int *s2)
    {
      int min1, min2;
      //遍历数组初始下标为 1
      int i = 1;
      //找到还没构建树的结点
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      min1 = HT[i].weight;
      *s1 = i;
      i++;
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      //对找到的两个结点比较大小,min2为大的,min1为小的
      if(HT[i].weight < min1)
      {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
      }
      else
      {
        min2 = HT[i].weight;
        *s2 = i;
      }
      //两个结点和后续的所有未构建成树的结点做比较
      for(int j=i+1; j <= end; j++)
      {
        //如果有父结点,直接跳过,进行下一个
        if(HT[j].parent != 0)
        {
          continue;
        }
        //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if(HT[j].weight < min1)
        {
          min2 = min1;
          min1 = HT[j].weight;
          *s2 = *s1;
          *s1 = j;
        }
        //如果介于两者之间,min2赋值为新的结点的位置下标
        else if(HT[j].weight >= min1 && HT[j].weight < min2)
        {
          min2 = HT[j].weight;
          *s2 = j;
        }
      }
    }

    注意:s1和s2传入的是实参的地址,所以函数运行完成后,实参中存放的自然就是哈夫曼树中权重值最小的两个结点在数组中的位置。

    六、构建哈弗曼树的代码实现

    //HT为地址传递的存储哈夫曼树的数组,w为存储结点权重值的数组,n为结点个数
    void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
    {
      if(n <= 1) 
        return;   // 如果只有一个编码就相当于0
      int m = 2*n-1;   // 哈夫曼树总节点数,n就是叶子结点
      *HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode));   // 0号位置不用
      HuffmanTree p = *HT;
      // 初始化哈夫曼树中的所有结点
      for(int i = 1; i <= n; i++)
      {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
      //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
      for(int i = n+1; i <= m; i++)
      {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
      //构建哈夫曼树
      for(int i = n+1; i <= m; i++)
      {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
      }
    }

    七、哈夫曼编码

    哈夫曼编码就是在哈夫曼树的基础上构建的,这种编码方式最大的优点就是用最少的字符包含最多的信息内容

    根据发送信息的内容,通过统计文本中相同字符的个数作为每个字符的权值,建立哈夫曼树。对于树中的每一个子树,统一规定其左孩子标记为 0 ,右孩子标记为 1 。这样,用到哪个字符时,从哈夫曼树的根结点开始,依次写出经过结点的标记,最终得到的就是该结点的哈夫曼编码。

    文本中字符出现的次数越多,在哈夫曼树中的体现就是越接近树根,编码的长度越短

    在这里插入图片描述
    如上图所示,字符 a 用到的次数最多,其次是字符 b 。字符 a 在哈夫曼编码是 0 ,字符 b 编码为 10 ,字符 c 的编码为 110 ,字符 d 的编码为 111 。

    使用程序求哈夫曼编码有两种方法:

    1)从叶子结点一直找到根结点,逆向记录途中经过的标记。
    例如,图 3中字符 c 的哈夫曼编码从结点 c 开始一直找到根结点,结果为:0 1 1 ,所以字符 c 的哈夫曼编码为:1 1 0(逆序输出)。
    
    (2)从根结点出发,一直到叶子结点,记录途中经过的标记。
    例如,求图 中字符 c 的哈夫曼编码,就从根结点开始,依次为:1 1 0

    采用方法(1)的实现代码为:

    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
      cd[n-1] = '\0';//字符串结束符
      for(int i=1; i<=n; i++)
      {
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while(j != 0)
        {
          // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
          if(HT[j].left == c)
            cd[--start] = '0';
          else
            cd[--start] = '1';
          //以父结点为孩子结点,继续朝树根的方向遍历
          c = j;
          j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i], &cd[start]);
      }
      //使用malloc申请的cd动态数组需要手动释放
      free(cd);
    }

    采用方法(2)的实现代码为:

    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      int m = 2*n-1;
      int p = m;
      int cdlen = 0;
      char *cd = (char *)malloc(n*sizeof(char));
      //将各个结点的权重用于记录访问结点的次数,首先初始化为0
      for (int i=1; i<=m; i++) 
      {
        HT[i].weight = 0;
      }
      //一开始 p 初始化为 m,也就是从树根开始。一直到p为0
      while (p) 
      {
        //如果当前结点一次没有访问,进入这个if语句
        if (HT[p].weight == 0) 
        {
          HT[p].weight = 1;  //重置访问次数为1
          //如果有左孩子,则访问左孩子,并且存储走过的标记为0
          if (HT[p].left != 0) 
          {
            p = HT[p].left;
          }
          else if(HT[p].right == 0) // 当前结点没有左孩子,也没有右孩子,说明为叶子结点,直接记录哈夫曼编码
          {
            (*HC)[p] = (char*)malloc((cdlen+1)*sizeof(char));
            cd[cdlen] = '\0';
            strcpy((*HC)[p], cd);
          }
        }
        else if(HT[p].weight == 1) // 如果weiget为1,说明访问过一次,即使是左孩子返回的
        {
          HT[p].weight = 2;  //设置访问次数为2
          //如果有右孩子,遍历右孩子,记录标记值 1
          if (HT[p].right != 0) 
          {
            p = HT[p].right;
            cd[cdlen++] = '1';
          }
        }
        else //如果访问次数为2,说明左孩子都遍历完了,返回父结点
        {
          HT[p].weight = 0;
          p = HT[p].parent;
          --cdlen;
        }
      }
    }

    八、完整代码(可运行)

    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    
    //哈夫曼树结点结构
    typedef struct 
    {
      int weight;//结点权重
      int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
    }HTNode, *HuffmanTree;
    //动态二维数组,存储哈夫曼编码
    typedef char **HuffmanCode;
    //HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
    void Select(HuffmanTree HT, int end, int *s1, int *s2)
    {
      int min1, min2;
      //遍历数组初始下标为 1
      int i = 1;
      //找到还没构建树的结点
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      min1 = HT[i].weight;
      *s1 = i;
      i++;
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      //对找到的两个结点比较大小,min2为大的,min1为小的
      if(HT[i].weight < min1)
      {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
      }
      else
      {
        min2 = HT[i].weight;
        *s2 = i;
      }
      //两个结点和后续的所有未构建成树的结点做比较
      for(int j=i+1; j <= end; j++)
      {
        //如果有父结点,直接跳过,进行下一个
        if(HT[j].parent != 0)
        {
          continue;
        }
        //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if(HT[j].weight < min1)
        {
          min2 = min1;
          min1 = HT[j].weight;
          *s2 = *s1;
          *s1 = j;
        }
        else if(HT[j].weight >= min1 && HT[j].weight < min2)   // 如果介于两者之间,min2赋值为新的结点的位置下标
        {
          min2 = HT[j].weight;
          *s2 = j;
        }
      }
    }
    
    //HT为地址传递的存储哈夫曼树的数组,w为存储结点权重值的数组,n为结点个数
    void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
    {
      if(n<=1) 
        return;     // 如果只有一个编码就相当于0
      int m = 2*n-1;   // 哈夫曼树总节点数,n就是叶子结点
      *HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号位置不用
      HuffmanTree p = *HT;
      // 初始化哈夫曼树中的所有结点
      for(int i = 1; i <= n; i++)
      {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
    
      //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
      for(int i = n+1; i <= m; i++)
      {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
    
      //构建哈夫曼树
      for(int i = n+1; i <= m; i++)
      {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
      }
    }
    
    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
      cd[n-1] = '\0';//字符串结束符
      for(int i=1; i<=n; i++)
      {
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while(j != 0)
        {
          // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
          if(HT[j].left == c)
            cd[--start] = '0';
          else
            cd[--start] = '1';
          //以父结点为孩子结点,继续朝树根的方向遍历
          c = j;
          j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i], &cd[start]);
      }
      //使用malloc申请的cd动态数组需要手动释放
      free(cd);
    }
    
    //打印哈夫曼编码的函数
    void PrintHuffmanCode(HuffmanCode htable, int *w, int n)
    {
      printf("Huffman code : \n");
      for(int i = 1; i <= n; i++)
        printf("%d code = %s\n",w[i-1], htable[i]);
    }
    
    int main(void)
    {
      int w[5] = {2, 8, 7, 6, 5};
      int n = 5;
      HuffmanTree htree;
      HuffmanCode htable;
      CreateHuffmanTree(&htree, w, n);
      HuffmanCoding(htree, &htable, n);
      PrintHuffmanCode(htable, w, n);
    
      return 0;
    }

    运行结果:

    Huffman code :
    2 code = 100
    8 code = 11
    7 code = 01
    6 code = 00
    5 code = 101

    九、总结

    程序运行效果图如下:
    在这里插入图片描述
    本节的程序中对权重值分别为 2,8,7,6,5 的结点构建的哈夫曼树如上图(A)所示。图 中(B)是另一个哈夫曼树,两棵树的带权路径长度相同。

    程序运行效果图之所以是(A)而不是(B),原因是在构建哈夫曼树时,结点 2 和结点 5 构建的新的结点 7 存储在动态树组的最后面,所以,在程序继续选择两个权值最小的结点时,直接选择了的叶子结点 6 和 7 。

    展开全文
  • 哈夫曼编码 哈夫曼编码基于哈夫曼树而产生的一种好编码,具体干嘛的我不说了,百度一下你就知道,因为现在已经很晚了,我想一夜干完,哈哈哈 上面已经完成哈夫曼树的构成了,那么编码就是左子树上的为0,右子树上的...
  • NULL 博文链接:https://128kj.iteye.com/blog/1637940
  • 2. 编码:利用建好的哈夫曼树,对从文件ToBeTran中读入的正文进行编码,然后将结果存入文件CodeFile中。 3. 译码:利用建好的哈夫曼,从CodeFile中读取编码数据并进行译码,结果存入文件TextFile中。 4. 在终端上以...
  • 哈夫曼树使用c语言实现编码以及译码,有文章讲解哦
  • 哈夫曼树编码与解码

    2018-03-11 15:45:39
    利用哈夫曼树(1) 读入待编码的文字,统计各字符出现的频率 (2) 构造哈夫曼树 (3) 得到各字符的哈夫曼编码 (4) 对原文进行编码 (5) 发送、接收 (6) 还原(译码)收到的文字 (7) 利用哈夫曼树,从...
  • 数据结构课程设计哈夫曼树编码解码。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,685
精华内容 7,074
关键字:

哈夫曼树编码