C++数据结构与算法之哈夫曼树的实现方法

本文实例讲述了C++数据结构与算法之哈夫曼树的实现方法。分享给大家供大家参考,具体如下:

哈夫曼树又称最优二叉树,是一类带权路径长度最短的树。

对于最优二叉树,权值越大的结点越接近树的根结点,权值越小的结点越远离树的根结点。

前面一篇图文详解JAVA实现哈夫曼树对哈夫曼树的原理与java实现方法做了较为详尽的描述,这里再来看看C++实现方法。

具体代码如下:

#include <iostream>
using namespace std;
#if !defined(_HUFFMANTREE_H_)
#define _HUFFMANTREE_H_
/*
 * 哈夫曼树结构
 */
class HuffmanTree
{
public:
  unsigned int Weight;
  unsigned int Parent;
  unsigned int lChild;
  unsigned int rChild;
};
typedef char **HuffmanCode;
/*
 * 从结点集合中选出权值最小的两个结点
 * 将值分别赋给s1和s2
 */
void Select(HuffmanTree* HT,int Count,int *s1,int *s2)
{
  unsigned int temp1=0;
  unsigned int temp2=0;
  unsigned int temp3;
  for(int i=1;i<=Count;i++)
  {
    if(HT[i].Parent==0)
    {
      if(temp1==0)
      {
        temp1=HT[i].Weight;
        (*s1)=i;
      }
      else
      {
        if(temp2==0)
        {
          temp2=HT[i].Weight;
          (*s2)=i;
          if(temp2<temp1)
          {
            temp3=temp2;
            temp2=temp1;
            temp1=temp3;
            temp3=(*s2);
            (*s2)=(*s1);
            (*s1)=temp3;
          }
        }
        else
        {
          if(HT[i].Weight<temp1)
          {
            temp2=temp1;
            temp1=HT[i].Weight;
            (*s2)=(*s1);
            (*s1)=i;
          }
          if(HT[i].Weight>temp1&&HT[i].Weight<temp2)
          {
            temp2=HT[i].Weight;
            (*s2)=i;
          }
        }
      }
    }
  }
}
/*
 * 霍夫曼编码函数
 */
void HuffmanCoding(HuffmanTree * HT,
          HuffmanCode * HC,
          int *Weight,
          int Count)
{
  int i;
  int s1,s2;
  int TotalLength;
  char* cd;
  unsigned int c;
  unsigned int f;
  int start;
  if(Count<=1) return;
  TotalLength=Count*2-1;
  HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)];
  for(i=1;i<=Count;i++)
  {
    HT[i].Parent=0;
    HT[i].rChild=0;
    HT[i].lChild=0;
    HT[i].Weight=(*Weight);
    Weight++;
  }
  for(i=Count+1;i<=TotalLength;i++)
  {
    HT[i].Weight=0;
    HT[i].Parent=0;
    HT[i].lChild=0;
    HT[i].rChild=0;
  }
  //建造哈夫曼树
  for(i=Count+1;i<=TotalLength;++i)
  {
    Select(HT, i-1, &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;
  }
  //输出霍夫曼编码
  (*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
  cd = new char[Count*sizeof(char)];
  cd[Count-1]='\0';
  for(i=1;i<=Count;++i)
  {
    start=Count-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] = new char [(Count-start)*sizeof(char)];
      strcpy((*HC)[i], &cd[start]);
    }
  }
  delete [] HT;
  delete [] cd;
}
/*
 * 在字符串中查找某个字符
 * 如果找到,则返回其位置
 */
int LookFor(char *str, char letter, int count)
{
  int i;
  for(i=0;i<count;i++)
  {
    if(str[i]==letter) return i;
  }
  return -1;
}
void OutputWeight(char *Data,int Length,
         char **WhatLetter,
         int **Weight,int *Count)
{
  int i;
  char* Letter = new char[Length];
  int* LetterCount = new int[Length];
  int AllCount=0;
  int Index;
  int Sum=0;
  float Persent=0;
  for(i=0;i<Length;i++)
  {
    if(i==0)
    {
      Letter[0]=Data[i];
      LetterCount[0]=1;
      AllCount++;
    }
    else
    {
      Index=LookFor(Letter,Data[i],AllCount);
      if(Index==-1)
      {
        Letter[AllCount]=Data[i];
        LetterCount[AllCount]=1;
        AllCount++;
      }
      else
      {
        LetterCount[Index]++;
      }
    }
  }
  for(i=0;i<AllCount;i++)
  {
    Sum=Sum+LetterCount[i];
  }
  (*Weight) = new int[AllCount];
  (*WhatLetter) = new char[AllCount];
  for(i=0;i<AllCount;i++)
  {
    Persent=(float)LetterCount[i]/(float)Sum;
    (*Weight)[i]=(int)(1000*Persent);
    (*WhatLetter)[i]=Letter[i];
  }
  (*Count)=AllCount;
  delete [] Letter;
  delete [] LetterCount;
}
#endif
void main()
{
  HuffmanTree * HT = NULL;
  HuffmanCode HC;
  char Data[100];
  char *WhatLetter;
  int *Weight;
  int Count;
  cout<<"请输入一行文本数据:"<<endl;
  cin>>Data;
  cout<<endl;
  OutputWeight(Data,strlen(Data),
    &WhatLetter,
    &Weight,
    &Count);
  HuffmanCoding(HT, &HC, Weight, Count);
  cout<<"字符 出现频率 编码结果"<<endl;
  for(int i = 0; i<Count; i++)
  {
    cout<<WhatLetter[i]<<"   ";
    cout<<Weight[i]/1000.0<<"%\t";
    cout<<HC[i+1]<<endl;
  }
  cout<<endl;
}

希望本文所述对大家C++程序设计有所帮助。

(0)

相关推荐

  • C++数据结构与算法之判断一个链表是否为回文结构的方法

    本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构

  • 图文详解JAVA实现哈夫曼树

    前言  我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的"最优二叉树",为了纪念他呢,我们称之为"哈夫曼树".哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等.今天一起来看看哈夫曼树到底是什么东东. 概念 当然,套路之一,首先我们要了解一些基本概念. 1.路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度. 2.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

  • C++数据结构与算法之双缓存队列实现方法详解

    本文实例讲述了C++数据结构与算法之双缓存队列实现方法.分享给大家供大家参考,具体如下: "双缓存队列"是我在一次开发任务中针对特殊场景设计出来的结构.使用场景为:发送端持续向接收端发送数据包--并且不理会接收端是否完成业务逻辑.由于接收端在任何情况下停止响应即可能产生数据丢失,因此无法简单的设计一条线程安全队列来对数据写入或读取(读取数据时将队列上锁视为对写入的停止响应). 鉴于此,我的设计思路如下: 接收端首先向A队列中写入数据,然后当数据处理请求到来的时候切换到B队列继续写入,之

  • C++ 哈夫曼树对文件压缩、加密实现代码

    在以前写LZW压缩算法的时候,遇到很多难受的问题,基本上都在哈夫曼编码中解决了,虽然写这代码很费神,但还是把代码完整的码出来了,毕竟哈夫曼这个思想确实很牛逼.哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题,就是压缩后文本的分割.比如用lzw编码abc,就是1,2,3.但这个在存为文件的时候必须用分割符把1,2,3分割开,非常浪费空间,否则会和12 23 123 产生二义性.而哈夫曼树,将所有char分布在叶节点上,在还原的时候,比如1101110,假设110是叶节点,那么走到110

  • C++数据结构与算法之反转链表的方法详解

    本文实例讲述了C++数据结构与算法之反转链表的方法.分享给大家供大家参考,具体如下: 算法概述:要求实现将一条单向链表反转并考虑时间复杂度. 算法分析: 数组法(略): 将列表元素逐个保存进数组,之后再逆向重建列表 点评:实现逻辑最简单,需要额外的内存开销. 移动指针: 通过三个指针逐个从链表头开始逐一反转链表元素的指针 点评:不需要额外的内存开销,会改变原始链表. 递归: 以递归的方式首先找到链表尾部,再逐一反转指针 点评:不需要额外的内存开销,不会改变原始链表. 算法实现: 构建链表结构 /

  • java哈夫曼树实例代码

    本文实例为大家分享了哈夫曼树java代码,供大家参考,具体内容如下 package boom; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Queue; class Node<T> implements Comparable<Node<T>>{ private T

  • C#求解哈夫曼树,实例代码

    复制代码 代码如下: class HuffmanTree    {        private Node[] data;        public int LeafNum { get; set; }        public Node this[int index]        {            get { return data[index]; }            set { data[index] = value; }        }        public Hu

  • C++实现哈夫曼树简单创建与遍历的方法

    本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法,比较经典的C++算法. 本例实现的功能为:给定n个带权的节点,如何构造一棵n个带有给定权值的叶节点的二叉树,使其带全路径长度WPL最小. 据此构造出最优树算法如下: 哈夫曼算法: 1. 将n个权值分别为w1,w2,w3,....wn-1,wn的节点按权值递增排序,将每个权值作为一棵二叉树.构成n棵二叉树森林F={T1,T2,T3,T4,...Tn},其中每个二叉树都只有一个权值,其左右字数为空 2. 在森林F中选取根节点权值最小二叉树,

  • C++数据结构之文件压缩(哈夫曼树)实例详解

    C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

  • 解析C++哈夫曼树编码和译码的实现

    一.背景介绍: 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 二.实现步骤: 1.构造一棵哈夫曼树 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵哈夫曼树,哈夫曼树的结点结构包括权值,双亲,左右孩子:假如由n个字符来构造一棵哈夫曼树,则共有结点2n-1个:在构造前,先初始化

随机推荐