北邮数据结构实验—huffman编码解码器

《北邮数据结构实验—huffman编码解码器》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构实验报告实验名称：Huffman编码/解码器学生姓名：班级：班内序号：学号：日期：1.实验要求利用二叉树结构实现哈夫曼编/解码器。基本要求：1.初始化(Init):能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树2.建立编码表(CreateTable):利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。3.编码(Encoding):根裾编码表对输入的字符申进行编码，并将编码后的字符申输出。4.译码(Decoding):利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。5.计算输入的字符串编码前和编码后的长度，并进行分析，讨论

2、赫夫曼编码的压缩效果。2.程序分析2.1存储结构静态三叉链表WeightLchildRchildparent2.2程序流程(或程序结构、或类关系图等表明程序构成的内容，一般为流程等)2.2.1.流程图统计各个字符的频度，并对各叶f节点的权重赋值初始化各节点的Lchild，Rchild和parent进行哈弗曼编码是计算分析内存占用情况2.2.1.伪代码1.输入进行编码的字符串2.遍历字符串，并为叶子节点权重赋值3.依次对各字符进行哈弗曼编码，自下往上，若是双亲节点左孩子则编码前插入‘0’，若是双亲节点右孩子则编码钱插入‘1’。4.显示各字符的哈弗曼编码。5.对字符串进行编码，挨个

3、遍历字符，找到相应的编码，复制到总的编码里，最后输出字符串的编码。6.对字符串的哈弗曼码进行译码。自上往下，若是‘0’，则递归到左孩子，若是‘1’，则递归到右孩子，知道叶子节点，输出该叶子节点代表字符，再继续遍历。7.分析内存占用情况。若用ASCII编码，每个字符占1个字节，即8bit,该情况下占用内存就是(字符长度)*8。若用哈弗曼编码，占用内存是各(字符频度)*(每个字符占用位数)之和。2.3关键算法分析该程序关键算法即哈弗曼编码，语句如下：voidCHTree::huffmancode(){inti;if(n<=1)return;m=2*n-l;for(i=l;i<=n;

4、i++)//叶子节点的初始化{htfil.parent=O;ht[i].lchild=O;ht[i].rchild=O;}for(;i<=m;i++)//非叶子节点的初始化{htril.weight=O;ht[i].parent=O;ht[i].lchild=O;htliJ.rchild=O;Jfor(i=n+1;i<=m;++i)//构造哈夫曼树sl=select(i-l);//函数在ht[l]到ht[i-l]中选择parent为0且weight最小的绍点，并将結点序号返s，并将ht[sl].parent设为-1s2=select(i-l);ht[sl].parent=i;h

5、t[s2].parent=i;ht[i].lchild=sl;ht[i].rchild=s2;ht[i].weight=ht[sl].weight+ht[s2].weight;}intc，f;for(i=l;i<=n;++i){for(c=i，f=ht[i].parent;f!=O;c=f，f=ht[f].parent)//逆向求叶子结点的哈夫曼编码if(ht[f].lchild==c){str[i].insert(O，"O"，O，l);}//在字符串str[i]的第0位置插入字符“0”else{str[i].insert(0，T，0，l);}//在字符串str[i]的第0位置

6、插入字符“1”分析：这段语句实现的功能是根据统计出来的各字符的频度，建立哈弗曼。建立哈弗曼树的过程如程序所展示，每次选取权重最小且无双亲节点的节点组合，并将其权重之和赋给其双亲节点，加入到总结中进行下次判断。哈弗曼树建立完全以后，开始对各字符进行编码，从下往上，以叶子节点为起始点，若它是双亲节点的左孩子，其编码前插入‘0’，若是右孩子则插入‘1’。再判断双亲节点使其双亲节点的左孩子还是右孩子，以此类推直到根节点。依次对每个字符进行上述过程编码。算法复杂度：最好情况为只有根结点和叶子节点：O(n)最坏情况为满二叉树情况：O(n*logn/2)1.程序运行结果分析t输入进行编码的字

7、符串:k（usnrugerhaerhSuiff〃an编沾如下:C:UsersAdministratordocumentsvisualstudio2010ProjectshuffmanDebughuffman.e...付22113221哈夫壘编码0111001110111100101110010宇符编码为0111001JL1011110010001110100110010JL01001JL0才编碑译碑后所得字符：gwcnvugerhaerhitlbit廣始编献占内.存Ihuff