资源描述：
《哈弗曼编码实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一•实验目的1、掌握哈夫曼树的构造和应用2、利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统.二•实验内容1、哈夫编码/译码器简介本例说明，先前快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。在传送电文时，希望总长尽可能地短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，以减少经费。哈夫曼树就是根据此原理设计出來的一种存储结构。2、问题描述哈夫曼树很易求出给定字符集及其概率（或频度）分布的最优前缀码。哈夫曼编码正是一种应用广泛II非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20%至9
2、0%,其压缩效率取决于被压缩文件的特征。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时，降低传输成本。但是，这要求在发送端通过一个编码系统对待传送电文须预先编码，在接收须将传送來的数据进行译码。请自行设计实现一个具有初始化、编码、译码、输入/输出等功能的哈夫曼码的编码/译码系统。并实现以下报文的编码和译码：“thisprogramismyfavorite”。3•测试数据某通信的电文字符集为26个英文字母及空格字符，其出现频度如下表所示：4、设计思想描述⑴问题分析。⑵哈夫曼树中各结点的结构描述（如上图）。（3）哈夫曼树的存储结构描述。5、主要算法设计与实现⑴
3、哈弗曼树的定义（动态分配数组存储哈夫曼树）typedefstruct{charch;〃键值intweight;//权值intselected;//编码值intparentjchild,rchild;〃各节点的值}HTNode,HuffmanTree;//动态分配数组存储哈夫曼树⑵定义用于译码的树typedefstructTreeNode{structTreeNodeIchild;//结构指针structTreeNoderchild;charcode;chardata;}TreeNode,Tree;⑶哈夫曼树函数的设计voidHuffmanCoding（HuffmanTr
4、ee&H7；HuffmanCode&HC,int&w,intn）{〃建立哈弗曼树intm=2n-l/i/j/sl/s2zstart/f;charcd;HuffmanTreep;if(n<=l)return;HT=(HuftmanTree)malloc((m+l)sizeof(HTNode));//0号单元未使用for(p=HT+l,i=l;i<=n;i++,p++,w++){p->weight=(w+l);p->selected=p->lchild=p->rchild=p->parent二0;}for(;i<=m;i++,p++)p->selected=p->paren
5、t=p->lchild=p->rchild=O;for(i=n+l;i<=m;i++){//建立哈弗曼树Select(HT,i・l,&sl,&s2);HT[sl].parent=i;HT[s2].parent=i;HT[i].lchild=sl;HT[i].rchild=s2;HT[i].weight=HT[sl].weight+HT[s2].weight;}printf("哈弗曼树表”);〃打印哈弗曼树表printf("iweightparentIchildrchildrT);for(p=HT+l/i=l；i<=m;i++,p++)printf("%2d%6
6、d%6d%6d%6d"/i,p->weight,p->parent,p->lchild/p->rchild);printf("M);〃从叶子到根逆向求每个字符的哈夫曼编码HC=(HuffmanCode)malloc((n+l)sizeof(char));〃分配n个字符编码的头指针向量cd=(char)malloc(nsizeof(char));〃分配求编码的工作空间cd[n・l]- ：〃编码结束符for(i=l;i<=n;i++){〃逐个字符求哈夫曼编码start=n-l;//编码结束位置for(j=i,f=HT[i].parent;f!=0;j=f/f=HT
7、[f].parent)!//从叶子到根逆向求编码if(HT[f].lchild==j)cd[-start]='O';elsecd[-start]='l';}HC[i]=(char)malloc((n-start)sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);〃从cd复制编码到HC}free(cd);〃释放工作空间}⑷对编码函数的设计voidCodelnput(intn,int&wzchar&code){//字符及权值的输入inti;w=(int)malloc((n+l)sizeo
