哈夫曼编码/译码一、【实验内容】【问题描述】利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统.【基本要求】：一个完整的系统应以下功能:(1) I. 初始化(Initialization)。
从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存放在文件hfmTree中. (2) E. 编码(Encoding)。
利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中.(3) D. 译码(Decoding)。
利用已建好的哈夫曼树,对传输到达的Cod eFile中的数据代码进行译码,将译码结果存入文件TextFile中. (4) P. 印文件代码(Print)。
将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码文件写入文件CodePri n中。
(5) T. 印哈夫曼树(TreePrinting)。
将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
测试数据：(1) 利用教科书例6-2中的数据调试程序。
(2) 用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”.。
字符 A B C D E F G H I J K L M频数 186 64 13 22 32 103 21 15 47 57 15 32 20字符 N O P Q R S T U V W X Y Z 频数 57 63 15 1 48 51 80 23 8 18 1 16 1二、实验目的树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.三、实验文档：哈夫曼编码/译码一、需求分析1、利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
本次设计就是为这样的信息收发站写的一个哈夫曼的编/译码器。
本实验要求：2、本演示程序中，用户可以输入键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码3、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。
4、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。
5、在本系统中，用户可以对任意长的字符串可进行编码/译码。
6、程序执行的命令包括：1) 初始化(I)2) 编码(E)3) 译码(D)4) 印代码文件(P)5) 印哈夫曼树(T)6) 退出(Q)７、测试数据：（１）利用教科书例6-2中的数据调试程序。
（２）用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”.。
字符 A B C D E F G H I J K L M频数 186 64 13 22 32 103 21 15 47 571 5 32 20字符 N O P Q R S T U V W X Y Z频数 57 63 15 1 48 51 80 23 8 181 16 1二、概要设计为实现上述程序功能，应以指针存储结点。
为此，需要定义一个抽象数据类型。
1. 抽象数据类型定义为：ADT HuffmanTree{数据对象：D={ai| ai∈CharSet,i=1,2,……,n,n≥0}数据关系：R={< ai-1, ai > ai-1, ai∈D, ai-1<ai ,i=2，3，……，n}基本操作P：HuffmanTree(); 构造函数~ HuffmanTree(); 析构函数Initialization(int WeightNum);操作结果：构造哈夫曼树。
Encoder()初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。
操作结果：对字符串进行编码Decoder();初始条件：哈夫曼树已存在且已编码。
操作结果：对二进制串进行译码Print()初始条件：编码文件已存在。
操作结果：把已保存好的编码文件显示在屏幕TreePrinting()初始条件：哈夫曼树已存在。
操作结果：将已在内存中的哈夫曼树以直观的方式显示在终端上2.本程序包含三个模块：1)主程序模块：void main(){初始化；do{接受命令；处理命令；}while(“命令”=”退出”)}2)、建树模块——实现定义的抽象数据类型3)、编/译码模块——实现字符串的编/译码各模块之间的调用关系如下：主程序模块建树模块编/译码模块三、详细设计程序代码如下// 程序名：HuffmanTree.h// 程序功能：哈夫曼树类的头文件(并用其来实现编/译码) // 作者：刘伟高// 日期：2006.11.27// 版本：1.0//对应类实现文件: HuffmanTree.cpp//对应主程序文件: main.cpp#include<iostream>#include<fstream>#include<string>using namespace std;struct HuffmanNode //定义哈夫曼树各结点{int weight; //存放结点的权值，假设只考虑处理权值为整数的情况int parent; //记录结点父亲位置，-1表示为根结点，否则表示为非根结点int lchild,rchild; //分别存放该结点的左、右孩子的所在单元的编号};class HuffmanTree //建立哈夫曼树类{private:HuffmanNode *Node; //哈夫曼树中结点的存储结构char *Info; //用来保存各字符信息int LeafNum; //树中的叶子结点总数public:HuffmanTree(); //构造函数~HuffmanTree(); //析构函数void Initialization(int WeightNum); //初始化函数：根据Wei ghtNum个权值建立一棵哈夫曼树void Encoder(); //编码函数：利用构造好的哈夫曼树对字符进行编码void Decoder(); //译码函数：对二进制串进行译码void Print(); //印文件函数：把已保存好的编码文件显示在屏幕void TreePrinting(); //印哈夫曼树函数：将已在内存中的哈夫曼树以直观的方式显示在终端上};// 程序名：HuffmanTree.cpp// 程序功能：实现哈夫曼树类的源文件(并用其来实现编/译码) // 作者：刘伟高// 日期：2006.11.27// 版本：1.0#include"HuffmanTree.h"#include<string>using namespace std;/////////////////////////////////////////////////////////////// ///////////////// 构造函数// 函数功能：将结点指针初始化为NULL// 函数参数：无// 参数返回值：无HuffmanTree::HuffmanTree(){Node=NULL; //将树结点初始化为空Info=NULL; //将字符数组初始化为空LeafNum=0; //将叶子数初始化为0}/////////////////////////////////////////////////////////////////// ///////////// 析构函数// 函数功能：将所有结点的空间释放// 函数参数：无// 参数返回值：无HuffmanTree::~HuffmanTree(){delete[] Node; //释放结点空间delete[] Info; //释放字符存储空间}//////////////////////////////////////////////////////////////////////////////// 初始化函数// 函数功能：从终端读入字符集大小n，以及n个字符和n个权值, // 建立哈夫曼树,并将它存放在文件hfmTree中.// 函数参数：int WeightNum表示代码个数// 参数返回值：无void HuffmanTree::Initialization(int WeightNum) //初始化{int i,j,pos1,pos2,max1,max2; //Node=new HuffmanNode[2*WeightNum-1]; //WeightNum 权值对应的哈夫曼树中的结点总数为2*WeightNum-1个Info=new char[2*WeightNum-1];for(i=0;i<WeightNum;i++){cout<<"请输入第"<<i+1<<"个字符值";getchar(); //丢弃字符'\t'与'\n'Info[i]=getchar(); //输入一个字符,主要是考虑输入空格而采用这种形式的getchar();cout<<"请输入该字符的权值或频度";cin>>Node[i].weight; //输入权值Node[i].parent=-1; //为根结点Node[i].lchild=-1; //无左孩子Node[i].rchild=-1; //无右孩子}for(i=WeightNum;i<2*WeightNum-1;i++) //表示需做Weigh tNum-1次合并{pos1=-1;pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号max1=32767; //32767为整型数的最大值max2=32767; //分别用来存放当前找到的最小值和次小值 for(j=0;j<i;j++) //在跟节点中选出权值最小的两个if(Node[j].parent==-1) //是否为根结点if(Node[j].weight<max1) //是否比最小值要小{max2=max1; //原最小值变为次小值max1=Node[j].weight; //存放最小值pos2=pos1; //修改次小值所在单元编号pos1=j; //修改最小值所在单元编号}elseif(Node[j].weight<max2) //比原最小值大但比原次小值要小{max2=Node[j].weight; //存放次小值pos2=j; //修改次小值所在的单元编号}//forNode[pos1].parent=i; //修改父亲位置Node[pos2].parent=i;Node[i].lchild=pos1; //修改儿子位置Node[i].rchild=pos2;Node[i].parent=-1; //表示新结点应该是根结点Node[i].weight=Node[pos1].weight+Node[pos2].weight; } //forLeafNum=WeightNum;char ch;cout<<"是否要替换原来文件(Y/N):";cin>>ch;if(ch=='y'||ch=='Y'){ofstream fop; //以二进制方式打开hfmTree.dat文件，并当重新运行时覆盖原文件fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);if(fop.fail()) //文件打开失败cout<<"文件打开失败！\n";fop.write((char*)&WeightNum,sizeof(WeightNum)); //写入WeightNumfor(i=0;i<WeightNum;i++) //把各字符信息写入文件{fop.write((char*)&Info[i],sizeof(Info[i]));flush(cout);}for(i=0;i<2*WeightNum-1;i++) //把个节点内容写入文件 {fop.write((char*)&Node[i],sizeof(Node[i]));flush(cout);}fop.close(); //关闭文件}cout<<"哈夫曼树已构造完成。