实验二：用Huffman树进行编码与解码算法.doc

《实验二：用Huffman树进行编码与解码算法.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、（规格为A4纸或A3纸折叠）（用五号宋体和TimesNewRoman,A4纸双面打印）一、实验目的；1、通过本实验，熟悉二叉树、Huffman树的基本概念，掌握二叉树的存储结构与各种算法。2、熟悉用Huffman树进行电文的加密与解密算法。二、实验内容；1、Huffman树的存储方式。2、加密与解密算法在电文编码中的应用。三、实验原理；给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，又称为哈夫曼树（Huffmantree）。Huffman树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，

2、通过统计字符的频度，能够达到编码电文的最小化。假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、…、wn，则哈夫曼树的构造规则为：（1）将w1、w2、…，wn看成是有n棵树的森林（每棵树仅有一个结点）；（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；（3）从森林中删除选取的两棵树，并将新树加入森林；（4）重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。四、实验步骤；1.调试下列程序“二叉树程序一”，掌握链式二叉树构造

3、的算法和实现方式。2.根据二叉树程序的学习，完成Huffman树的构造、编码和解码的实现。（1）统计电文中字符的出现频率。（2）用统计频率建立Huffman树，并生成前缀码；（3）建立Huffman树的解码算法。（4）用随机输入的电文完成编码与解码过程。五、程序源代码及注释#include#include#includetypedefstruct{charch;intweight;intparent,lchild,rchild;}HTnode,*Huffmantree;//动态分配数组

4、存储赫夫曼树typedefchar**Huffmancode;//动态分配数组存储赫夫曼编码表intmain(){//------------构造赫夫曼树及赫夫曼编码-------------------HuffmantreeHT;HuffmancodeHC;char*cd,s[100],g[100];intn,mm,m,i,j=0,f,start,c,s1=0,s2=0,temp1,temp2;intw[26];inta[26]={0};printf("请输入字符：");gets(s);n=strlen(s);HT=(Huffmantree

5、)malloc((m+1)*sizeof(HTnode));//0号单元未用for(i=0;i

6、parent=HT[i].lchild=HT[i].rchild=0;}for(;i<=m;++i)HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;//除叶子外的节点赋初值for(i=n+1;i<=m;i++){//建赫夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个节点，其序号为别为s1,s2.temp1=temp2=100;for(j=1;j<=i-1;j++)if(HT[j].parent==0)if(HT[j].weight

7、1=HT[j].weight;s1=j;}for(j=1;j<=i-1;j++)if(HT[j].parent==0&&j!=s1)if(HT[j].weight

8、");for(i=1;i<=m;i++)printf("%-4d%4d%8d%8d%8d%6c",i,HT[i].weight,HT[i].lchild,H