资源描述：
《实验九 哈夫曼编码-译码器》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验十哈夫曼编/译码器一、实验目的（1）掌握哈夫曼树的构造和应用（2）利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统二、实验内容[问题描述]（设计性实验）哈夫曼树很易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件的特征。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时，降低传输成本。但是，这要求在发送端通过一个编码系统对待传送电文须预先编码，在接收须将传送来的数据进行译码
2、。请自行设计实现一个具有初始化、编码、译码、输入/输出等功能的哈夫曼码的编码/译码系统。并实现以下报文的编码和译码：“thisprogramismyfavorite”。[测试数据]某通信的电文字符集为26个英文字母及空格字符，其出现频度如下表所示：[实现提示]如何创建哈夫曼树及如何求得各结点对应的哈夫曼编码算法：参见ppt。1、设计思想描述（1）问题分析。（2）哈夫曼树中各结点的结构描述（提示：图示）。（3）哈夫曼树的存储结构描述（提示：分析采用顺序存储还是利用链式存储等）。2、主要算法设计与实现[要求]1)、利用类模
3、板来实现。2)、类中各成员函数要求给出自行设计的算法步骤描述及主要设计思想。3)、给出类中各成员函数算法设计实现。4)、对自行设计的各算法进行评估（提示：时间复杂度、空间复杂度等）。#include#includeusingnamespacestd;constintMAX=1000;classHTree;classHTNode{friendclassHTree;unsignedintweight;unsignedintparent,lchild,rchild;};classHuCod
4、e{friendclassHTree;char*ch;//字符的编码chardata;//被编码的字符};//动态分配数组存储哈夫曼编码表。classHTree{HTNode*HT;//动态数组HuCode*HC;intn;public:HTree(intw[],intn);voidSelect(intk,int&s1,int&s2);voidQHuffmanCode(charch[],intn);//求出n个字符的赫夫曼编码HCvoidprintHuffmantree(intn);voidprintHuffmanCo
5、de(intn);char*MessageCoding(char*s1,intn);//对报文进行编码,n为字符集中字符的个数char*MessageEnCoding(char*s1,intn);//对报文的编码进行译码，n为字符集中字符的个数};HTree::HTree(intw[],intn){//w存放n个字符的权值(均>0),构造赫夫曼树HTinti,m,s1,s2;if(n<=1){cout<<"error!";exit(0);}m=2*n-1;//注:有n个字符,其构造成一颗Huffman树后,将有n+n-
6、1个结点.HT=newHTNode[m+1];//0号单元未使用for(i=1;i<=n;++i){//初始化Huffman树的各叶子结点HT[i].weight=w[i];HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}for(;i<=m;++i){//初始化其它树结点;HT[i].weight=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}for(i=n+1;i<=m;++i){//建赫夫曼树,在HT[1..i-1]选择p
7、arent为0且weight最小的两个结点,其序号分别为s1和s2;Select(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;//双亲结点的修改}}voidHTree::Select(intk,int&s1,int&s2){//在HT[1..k]中选出没有双亲的结点,且其权值最小的两个结点的下标赋给s1,s2.int
8、w1,w2,i=1;w1=w2=MAX;s1=s2=i;for(i=1;i<=k;i++){if(!HT[i].parent){if(HT[i].weight
