北京邮电大学信通院数据结构试验三-哈夫曼树试验报告

1、2009级数据结构实验报告实验名称：实验三一一哈夫曼编/解码器的实现学生姓名：陈聪捷日 期：2010年11月28日.实验要求一、实验目的：了解哈夫曼树的思想和相关概念；二、实验内容：利用二叉树结构实现哈夫曼编 /解码器.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。.打印：以直观的方式打印哈夫曼树。.计算输入的字符串编码前和编码后的长度，并进行分析，讨

2、论哈夫曼编码的压缩效果。.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现 的次数统计频度，对没有出现的字符一律不用编码。.程序分析存储结构二叉树template class BiTreepublic:ThOataatccharThharcdBeeree师Tnsigiined int count*T p%enbous edvoi,d NHuemwee:Input)算法伪代码：.初始化链表的头结点.获得输入字符串的第一个字符，并将其插入到链表尾部，n=1（n记录的是链表中字符的个数）.从字符串第2个字符开始，逐个取出字符串中的字符将当前取出的字符与链表中已经存在的字符逐

3、个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到链表尾部，同时n+ =n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数).创建哈夫曼树 6.销毁链表 源代码：void HuffmanTree:Init(string Input) (Node *front=new Node;建哈夫曼树(void HuffmanTree:CreateCodeTable(Node *p)算法伪代码：.创建一个长度为 2*tSize-1的三叉链表.将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个

4、结点的data域，并将对应结点的孩子域和双亲域赋为空.从三叉链表的第tSize个结点开始，i=tSize从存储字符及其权值的链表中取出两个权值最小的结点x,y,记录其下标 x,y。将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i 结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结 点的双亲设置为空.根据哈夫曼树创建编码表源代码：void HuffmanTree:CreateHTree(Node *p,int n) (root= new BiNode2*n-1;ata=front-count;rooti.lchild=

5、-1;rooti.rchild=-1;rooti.parent=-1;front=front-next; front=p; int New1,New2; for(i=n;icharacter; arent;odek=0; k+; while(parent!=-1) child) odek=0; else HCodeTablei.codek=1; k+; child=parent; parent=rootchild.parent; HCodeTablei.codek=0; Reverse(HCodeTablei.code); ata HCodeTablei.codeendl; 时间复杂度： 需要

6、遍历哈夫曼树获取编码，时间复杂度为O (n2)4.选择两个最小权值的函数( void HuffmanTree二SelectMin(int &New1,int &New2,int begin,int end) 算法伪代码： 1.从下标为begin的结点开始，寻找第一个没用过的结点 2.遍历哈夫曼树中从下标为begin到下标为end的结点序列，寻找没用过的同时权值又是最小的结点。 3.暂时改变找到的权值最小结点的双亲域，防止第2次找到相同的结点。4.将权值最小结点的下标记录下来。 5.重复步骤14,找到第2个权值最小的结点 源代码：void HuffmanTree:SelectMin(int &N

7、ew1,int &New2,int begin,int end) ( int min; for(int j=0；j2；j+)arent=-1)ata;sign=i;break;)for(i=begin;irooti.data) ( min=rooti.data; sign=i; ) ) )rootsign.parent=0;将字符串倒序的函数(void HuffmanTree:Reverse(char *pch) 算法伪代码：.得到字符串的长度.初始化两个记录下标的变量，一个为字符串开头字符所在的下标i,另一个为字符串结尾字符所在的下标j.将下标为i和j的字符交换. i+,j -时间复杂度：时

8、间复杂度为O (n)6.编码函数(void HuffmanTree:Encode(string &s,string &d) 算法伪代码：.从s开头的字符开始，逐一对s中的字符进行编码.在编码表中查找与当前字符对应的字符.如果找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末 尾。.重复以上步骤，直到所有待编码串中的字符都编码完毕.输出编码后的字符串 源代码：void HuffmanTree:Encode(string &s,string &d) ( for(int j=0;j();j+)ata)(HCodeTablei.code); 码函数 (void HuffmanTree:De

9、code(string &s,string &d) 算法伪代码：.得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针.逐个读取待解码串中的字符，若为0,则指向哈夫曼树当前结点的指针指向当前结点的左孩子，若为 1,则指向当前结点的右孩子.指向待解码串的指针指向解码串中的下一个字符，直到指向哈夫曼树结点 的指针的孩子结点为空.如果哈夫曼树只有一个叶子结点，直接将待解码串中的编码转换为对应的 字符.如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对 应的字符追加到解码串中。.输出解码串源代码：void HuffmanTree:Decode(string &s,string

10、 &d) (for(int i=0;i();)(child!=-1) child;child;ata);计算 哈夫曼编码的压缩比(voidint parent=2*tSize-1-1; elsei+;if(tSize=1)HuffmanTree:Calculate(string s1,string s2)算法伪代码：.获得编码前字符串的长度，即其占用的字节数.获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字节数.压缩比将两个相除源代码：void HuffmanTree:Calculate(string s1,string s2)(int cal1=();int cal2=();

11、cal2=ceill(float)cal2/8);打印哈夫曼树 (voidHuffmanTree:PrintTree(int TreeNode,int layer) )算法伪代码：.如果待打印结点为空，则返回.递归调用函数打印当前结点的右子树.根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打 印当前结点的权值.递归调用函数打印当前结点的左子树源代码：void HuffmanTree:PrintTree(int TreeNode,int layer)(if(TreeNode=-1)child,layer+1); ataendl;child,layer+1);菜单函数(void H

12、uffmanTree:Menu()算法伪代码：.逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的 string变量中，直到读到回车输入符为止.删除string变量末尾的回车输入符.利用string变量创建哈夫曼树，初始化编码表。.直观打印哈夫曼树.对输入的字符串进行编码.对编码后的字符串进行解码.计算编码前后的压缩比并输出源代码：void HuffmanTree:Menu()(cout请输入你要编码的文本，按回车键确定输入endl;string Input;char letter;do于题目要求能输入任意长的字符串，所以本程序采用了 string变量来记录输入的字符串，并采用 s

13、tring类的类成员函数来完成 各项任务.打印哈夫曼树时采用了递归函数，且采用了凹凸表的形式打印哈夫曼树。.为了输入空格，输入时采取逐个字符输入的方式3.程序运行结果主函数流程图:结束运行结果:请输入伤要编制的文本K按回车键确定输入 I loue data st met Lire, I loue camputep. 1 will try1 叫 best to study lata struc tu re.编石裱为：I 11B00111 1 000t n 0016 v EJHW1 e 0111 d 11M01 a 0011 t S 0100 r 1310 u 1011 c UB10 ,B1100

14、Q m 01010 p 11gMi .R1R11 u 011010 i nilA11 y 11011 b 06B00直观打印哈夫曼树IS271250612 G231183 GIQ21182428433484is47231编43后的字符串为阻n0阑1豳1面目硼1目阻110曲“u工m 随1日01日ioignuswi日阻口iu日H01 itmtinii（Miiiubt）iaimiiii m 的身 i mhihi 时on11110001110110100110110001000111110010161101111101010110111110000001110100100111Q10Q111Q1Q11帆码后的字符串i laue datra si-ruic-tLive, I Iovb computrei* I