解析C++哈夫曼树编码和译码的实现_C 语言

一．背景介绍：

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

二．实现步骤：

1.构造一棵哈夫曼树

2.根据创建好的哈夫曼树创建一张哈夫曼编码表

3.输入一串哈夫曼序列，输出原始字符

三．设计思想：

1.首先要构造一棵哈夫曼树，哈夫曼树的结点结构包括权值，双亲，左右孩子；假如由n个字符来构造一棵哈夫曼树，则共有结点2n-1个；在构造前，先初始化，初始化操作是把双亲，左右孩子的下标值都赋为0；然后依次输入每个结点的权值

2.第二步是通过n-1次循环，每次先找输入的权值中最小的两个结点，把这两个结点的权值相加赋给一个新结点，，并且这个新结点的左孩子是权值最小的结点，右孩子是权值第二小的结点；鉴于上述找到的结点都是双亲为0的结点，为了下次能正确寻找到剩下结点中权值最小的两个结点，每次循环要把找的权值最小的两个结点的双亲赋值不为0（i）.就这样通过n-1循环下、操作，创建了一棵哈夫曼树，其中，前n个结点是叶子（输入的字符结点）后n-1个是度为2的结点

 3.编码的思想是逆序编码，从叶子结点出发，向上回溯，如果该结点是回溯到上一个结点的左孩子，则在记录编码的数组里存“0”，否则存“1”，注意是倒着存；直到遇到根结点（结点双亲为0），每一次循环编码到根结点，把编码存在编码表中，然后开始编码下一个字符（叶子）

4．译码的思想是循环读入一串哈夫曼序列，读到“0”从根结点的左孩子继续读，读到“1”从右孩子继续，如果读到一个结点的左孩子和右孩子是否都为0，如果是说明已经读到了一个叶子（字符），翻译一个字符成功，把该叶子结点代表的字符存在一个存储翻译字符的数组中，然后继续从根结点开始读，直到读完这串哈夫曼序列，遇到结束符便退出翻译循环

四．源代码：

/***************************************
目的：1.根据输入的字符代码集及其权值集，
构造赫夫曼树，输出各字符的赫夫曼编码
2.输入赫夫曼码序列，输出原始字符代码
作者：Dmego  时间：2016-11-11
****************************************/
#include<iostream>
#define MAX_MA 1000
#define MAX_ZF 100
using namespace std;

//哈夫曼树的储存表示
typedef struct
{
 int weight; //结点的权值
 int parent, lchild, rchild;//双亲，左孩子，右孩子的下标
}HTNode,*HuffmanTree; //动态分配数组来储存哈夫曼树的结点

//哈夫曼编码表的储存表示
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码

//返回两个双亲域为0且权值最小的点的下标
void Select(HuffmanTree HT, int n, int &s1, int &s2)
{
 /*n代表HT数组的长度
 */

 //前两个for循环找所有结点中权值最小的点（字符）
 for (int i = 1; i <= n; i++)
 {//利用for循环找出一个双亲为0的结点
  if (HT[i].parent == 0)
  {
   s1 = i;//s1初始化为i
   break;//找到一个后立即退出循环
  }
 }
 for (int i = 1; i <= n; i++)
 {/*利用for循环找到所有结点（字符）权值最小的一个
  并且保证该结点的双亲为0*/
  if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
   s1 = i;
 }
 //后两个for循环所有结点中权值第二小的点（字符）
 for (int i = 1; i <= n; i++)
 {//利用for循环找出一个双亲为0的结点，并且不能是s1
  if (HT[i].parent == 0 && i != s1)
  {
   s2 = i;//s2初始化为i
   break;//找到一个后立即退出循环
  }
 }

 for (int i = 1; i <= n; i++)
 {/*利用for循环找到所有结点（字符）权值第二小的一个，
  该结点满足不能是s1且双亲是0*/
  if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i!= s1)
   s2 = i;
 }

}

//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT, int n)
{
/*-----------初始化工作-------------------------*/
 if (n <= 1)
  return;
 int m = 2 * n - 1;
 HT = new HTNode[m + 1];
 for (int i = 1; i <= m; ++i)
 {//将1~m号单元中的双亲，左孩子，右孩子的下标都初始化为0
  HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;
 }
 for (int i = 1; i <= n; ++i)
 {
  cin >> HT[i].weight;//输入前n个单元中叶子结点的权值
 }
/*-----------创建工作---------------------------*/
 int s1,s2;
 for (int i = n + 1; i <= m; ++i)
 {//通过n-1次的选择，删除，合并来构造哈夫曼树
  Select(HT, i - 1, s1, s2);
  /*cout << HT[s1].weight << " , " << HT[s2].weight << endl;*/
  /*将s1,s2的双亲域由0改为i
  (相当于把这两个结点删除了，这两个结点不再参与Select()函数)*/
  HT[s1].parent = i;
  HT[s2].parent = i;
  //s1,与s2分别作为i的左右孩子
  HT[i].lchild = s1;
  HT[i].rchild = s2;
  //结点i的权值为s1,s2权值之和
  HT[i].weight = HT[s1].weight + HT[s2].weight;
 }
}

//从叶子到根逆向求每个字符的哈夫曼编码，储存在编码表HC中
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
 HC = new char*[n + 1];//分配储存n个字符编码的编码表空间
 char *cd = new char[n];//分配临时存储字符编码的动态空间
 cd[n - 1] = '\0';//编码结束符
 for (int i = 1; i <= n; i++)//逐个求字符编码
 {
  int start = n - 1;//start 开始指向最后，即编码结束符位置
  int c = i;
  int f = HT[c].parent;//f指向结点c的双亲
  while (f != 0)//从叶子结点开始回溯，直到根结点
  {
   --start;//回溯一次，start向前指向一个位置
   if (HT[f].lchild == c) cd[start] = '0';//结点c是f的左孩子，则cd[start] = 0;
   else cd[start] = '1';//否则c是f的右孩子，cd[start] = 1
   c = f;
   f = HT[f].parent;//继续向上回溯
  }
  HC[i] = new char[n - start];//为第i个字符编码分配空间
  strcpy(HC[i], &cd[start]);//把求得编码的首地址从cd[start]复制到HC的当前行中
 }
 delete cd;
}

//哈夫曼译码
void TranCode(HuffmanTree HT,char a[],char zf[],char b[],int n)
{
 /*
 HT是已经创建好的哈夫曼树
 a[]用来传入二进制编码
 b[]用来记录译出的字符
 zf[]是与哈夫曼树的叶子对应的字符（叶子下标与字符下标对应）
 n是字符个数，相当于zf[]数组得长度
 */

 int q = 2*n-1;//q初始化为根结点的下标
 int k = 0;//记录存储译出字符数组的下标
 int i = 0;
 for (i = 0; a[i] != '\0';i++)
 {//for循环结束条件是读入的字符是结束符（二进制编码）
  //此代码块用来判断读入的二进制字符是0还是1
  if (a[i] == '0')
  {/*读入0，把根结点(HT[q])的左孩子的下标值赋给q
   下次循环的时候把HT[q]的左孩子作为新的根结点*/
   q = HT[q].lchild;
  }
  else if (a[i] == '1')
  {
   q = HT[q].rchild;
  }
  //此代码块用来判断HT[q]是否为叶子结点
  if (HT[q].lchild == 0 && HT[q].rchild == 0)
  {/*是叶子结点，说明已经译出一个字符
  该字符的下标就是找到的叶子结点的下标*/
   b[k++] = zf[q];//把下标为q的字符赋给字符数组b[]
   q = 2 * n - 1;//初始化q为根结点的下标
   //继续译下一个字符的时候从哈夫曼树的根结点开始
  }
 }
 /*译码完成之后，用来记录译出字符的数组由于没有结束符输出的
 时候回报错，故紧接着把一个结束符加到数组最后*/
 b[k] = '\0';
}
//菜单函数
void menu()
{
 cout << endl;
 cout << "  ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓" << endl;
 cout << "  ┃  ★★★★★★★哈夫曼编码与译码★★★★★★★  ┃" << endl;
 cout << "  ┃     1. 创建哈夫曼树      ┃" << endl;
 cout << "  ┃     2. 进行哈夫曼编码      ┃" << endl;
 cout << "  ┃     3. 进行哈夫曼译码      ┃" << endl;
 cout << "  ┃     4. 退出程序       ┃" << endl;
 cout << "  ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛" << endl;
 cout << "      <><注意：空格字符用'- '代替><>" << endl;
 cout << endl;
}
void main()
{
 int falg;//记录要编码的字符个数
 char a[MAX_MA];//储存输入的二进制字符
 char b[MAX_ZF];//存储译出的字符
 char zf[MAX_ZF];//储存要编码的字符
 HuffmanTree HT = NULL;//初始化树为空数
 HuffmanCode HC = NULL;//初始化编码表为空表
 menu();
 while (true)
 {
  int num;
  cout << "<><请选择功能(1-创建 2-编码 3-译码 4-退出)><>: ";
   cin >> num;
   switch (num)
   {
   case 1 :
    cout << "<><请输入字符个数><>:";
    cin >> falg;
    //动态申请falg个长度的字符数组，用来存储要编码的字符
    /*char *zf = new char[falg];*/
    cout << "<><请依次输入" << falg << "个字符:><>: ";
    for (int i = 1; i <= falg; i++)
     cin >> zf[i];
    cout << "<><请依次输入" << falg << "个字符的权值><>: ";
    CreateHuffmanTree(HT, falg);//调用创建哈夫曼树的函数
    cout << endl;
    cout << "<><创建哈夫曼成功！,下面是该哈夫曼树的参数输出><>：" << endl;
    cout << endl;
    cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "双亲" << "\t" << "左孩子" << "\t" << "右孩子" << endl;
    for (int i = 1; i <= falg * 2 - 1; i++)
    {
     cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HT[i].parent << "\t" << HT[i].lchild << "\t" << HT[i].rchild << endl;
    }
    cout << endl;
    break;
   case 2:
    CreatHuffmanCode(HT, HC, falg);//调用创建哈夫曼编码表的函数
    cout << endl;
    cout << "<><生成哈夫曼编码表成功！,下面是该编码表的输出><>：" << endl;
    cout << endl;
    cout << "结点i"<<"\t"<<"字符" << "\t" << "权值" << "\t" << "编码" << endl;
    for (int i = 1; i <= falg; i++)
    {
     cout << i << "\t"<<zf[i]<< "\t" << HT[i].weight << "\t" << HC[i] << endl;
    }
    cout << endl;
    break;
   case 3:
    cout << "<><请输入想要翻译的一串二进制编码><>：";
    /*这样可以动态的直接输入一串二进制编码，
    因为这样输入时最后系统会自动加一个结束符*/
    cin >> a;
    TranCode(HT, a, zf, b, falg);//调用译码的函数，
     /*这样可以直接把数组b输出，因为最后有
     在数组b添加输出时遇到结束符会结束输出*/
    cout << endl;
    cout << "<><译码成功！翻译结果为><>：" << b << endl;
    cout << endl;
    break;
   case 4:
    cout << endl;
    cout << "<><退出成功！><>" << endl;
    exit(0);
   default:
    break;
   }
 }

 //-abcdefghijklmnopqrstuvwxyz
 //186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1
 //000101010111101111001111110001100100101011110110

}

五．运行截图：

原文链接：http://www.cnblogs.com/dmego/p/6064069.html

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索c++
， 实现
哈夫曼树
哈夫曼树编码译码、哈夫曼树的编码和译码、哈夫曼树编码与译码、哈夫曼树编码和译码、哈夫曼树编码 c语言，以便于您获取更多的相关知识。

时间： 2024-08-26 06:50:57

解析C++哈夫曼树编码和译码的实现_C 语言的相关文章

【算法导论】哈夫曼树及编译码

哈夫曼树及编译码 哈夫曼树,又称二叉树,是一类带权路径长度最短的树.所谓路径长度,就是节点到树根之间的路径长度与节点权值的乘积.哈夫曼本人曾在MIT的信息论研究生班学习.Robert Fano教授让学生们自己决定是参加期未考试还是做一个大作业.而哈夫曼选择了后者,原因很简单,因为解决一大作业可能比期未考试更容易通过.Robert Fano教授也是信息论的先驱,学过信息论的都知道有Fano不等式,Shannon-Fano编码.当时这个大作业,Fano也解决不了,哈夫曼并不知道,于是自己尝试,最终产

霍夫曼树编码的实现

#include <stdio.h>#include <stdlib.h>#include <string.h>#include <conio.h>typedef struct{ unsigned int Weight; unsigned int Parent; unsigned int lChild; unsigned int rChild;}HTNode,*HuffmanTree;typedef char **HuffmanCode;int LookFo

数据结构——赫夫曼树

1 基本概念 赫夫曼树(Huffman Tree)又称为最优树,是一类带权路径长度最短的树.本文仅讨论最优二叉树. 树的路径长度是指从树根到树中其余各个结点的路径长度之和.对具有n个结点的二叉树而言,完全二叉树具有最短的树的路径长度. 若在二叉树中,树叶结点带有权值,则有:结点的带权路径长度定义为从树根到该结点之间的路径长度与该结点上所带权值之积. 若树中有n个树叶结点,且每个树叶结点均带有权值,则有:树的带权路径长度定义为树中所有树叶结点的带权路径长度之和,可记为: 有时,也将树的路径长度称为

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

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

编码-霍夫曼树程序，输入字符串统计字符出现次数并译码。请问如何改成从文件读入字符串？

问题描述 霍夫曼树程序,输入字符串统计字符出现次数并译码.请问如何改成从文件读入字符串? //生成HuffmanCode文件的两个函数void HuffmanEncoding(HuffmanTree HTHuffmanCode HC){//根据HuffmanTreeHT求HuffmanCode表HC int cpi; char cd[n]; int start; cd[num] = ''; for(i = 1;i <= num;i++){ start = num; c = i; while((p

优先级队列实现哈夫曼树的编码和译码

//优先级队列实现的哈夫曼树的编码和译码 #include<iostream> #include<queue> #include<string> using namespace std; class Node { public: float weight; Node* left; Node* right; char ch; Node(float w,Node* l=NULL,Node* r=NULL,char c=' '):weight(w),ch(c),left(l)

编码-哈夫曼树，请问大神们，下面的译码部分怎么没有输出？请大神们帮我修改下~~~(最好再加个能有个文件输出)

问题描述 哈夫曼树,请问大神们,下面的译码部分怎么没有输出?请大神们帮我修改下~~~(最好再加个能有个文件输出) #include #include #include #define maxsize 100 #define max 100 typedef struct { char data; int weight; int parent; int lchild; int rchild; }huffnode; typedef struct { char cd[max]; int start; }

编码-赫夫曼树出错 ，编译没错 不知道哪里错了运行不了

问题描述 赫夫曼树出错 ,编译没错 不知道哪里错了运行不了 编译没有错误,运行失败 #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #define STACK_INIT_SIZE 100//存储空间初始分配量 没分号";" #define STACKINCREMENT 10 //存储空间分配增量 #define TRUE 1 #def

c++ 数据结构-一个程序，哈夫曼树的构造遍历打印，编码解码，缺少遍历和打印

问题描述 一个程序,哈夫曼树的构造遍历打印,编码解码,缺少遍历和打印 #include #include /* 数组头文件 / #include #define MAX 999 / 定义长度 / typedef struct{ / 定义哈夫曼编码的结构数组 / char data; int weight; / 定义权值 / int parent; int lchild; int rchild; }huffmannode; typedef struct{ / 定义保存哈夫曼结构体 / char b