哈弗曼树编码译码实验报告

《哈弗曼树编码译码实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、安徽师范大学数学计算机科学学院实验报告专业名称计算机科学与技术实验室6号实验楼401室实验课程数据结构实验名称哈弗曼树编码和译码姓名陈阳学号130704069同组人员无实验日期2014-12-51、实验目的熟悉了对哈夫曼树的使用方法，了解编码和译码得过程并加以使用.2、实验原理1.首先构建哈弗曼树，再对哈弗曼树进行初始化，再利用对各结点得遍历处理进行寻找双亲，修改结点信息。接着利用函数对其生产得哈弗曼树进行编码，最后再进行译码。2.定义一个结构体，用于存放哈弗曼树得结点信息。3.定义一个结构体，

2、用于存放权重信息4.构建哈弗曼树，利用上述存储结构实现4.1初始化:将ht[0„m-1]中2n-1个结点里的指针均置为空，权值置为0。4.2传值：读入n个叶子的权值存于向量的前n个分量中。它们是初始森林中n个孤立的根结点上的权值。4.3合并：对森林中的树共进行n-1次合并，所产生的新结点依次放入向量ht的第i个分量中。每次合并分两步：①当前森林ht[0„i-1]的所有结点中，选取权最小和次小的两个根点[s1]和 [s2]作为合并对象，这里0≤s1，s2≤i-1。 ② 将根为ht[s1]和ht[s

3、2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点ht[i]。具体操作：将ht[s1]和ht[s2]的parent置为i，将ht[i]的lchild和rchild分别置为s1和s2 .新结点ht[i]的权值置为ht[s1]和ht[s2]的权值之和。5.哈夫曼的编码：约定左子为0，右子为1，则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。 3.需求分析对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。求得编码就是以n种字符出现的

4、频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能：(1)哈夫曼树的建立；(2)哈夫曼编码的生成；(3)编码文件的译码。4.概要设计哈夫曼编码主要是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码为哈夫曼编码。主流程图：哈夫曼树的建立过程哈夫曼树的建立由哈夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的

5、第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n－1次合并，所以共产生n－1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有2n－1个结点，其中n个结点是初始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n--1的一维数组来存储哈夫曼树中的结点。哈夫曼编码得译码译码的基本思想是：读文件中编码，并与原先生成的哈夫曼编码表比较，遇到相等时，即取出其对

6、应的字符存入一个新串中。5.详细设计结构定义：typedefstruct{intweight;//权值intparent;//父节节点intlchild;//左子节点intrchild;//右子节点}HTNode,Huffman[M+1];//huffman树typedefstructNode{intweight;//叶子结点的权值charc;//叶子结点intnum;//叶子结点的二进制码的长度}WNode,WeightNode[N];哈弗曼树得算法：/********创建HuffmanTre

7、e********/voidCreateHuffmanTree(Huffmanht,WeightNodew,intn){inti,j;ints1,s2;//初始化哈夫曼树for(i=1;i<=n;i++){ht[i].weight=w[i].weight;ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}for(i=n+1;i<=2*n-1;i++){ht[i].weight=0;ht[i].parent=0;ht[i].lchild=0;ht[i].r

8、child=0;}for(i=n+1;i<=2*n-1;i++){for(j=1;j<=i-1;j++)if(!ht[j].parent)break;s1=j;//找到第一个双亲为零的结点for(;j<=i-1;j++)if(!ht[j].parent)s1=ht[s1].weight>ht[j].weight?j:s1;ht[s1].parent=i;ht[i].lchild=s1;for(j=1;j<=i-1;j++)if(!ht[j].parent)break;s2=j;//找到第二个双亲