北邮--第三次---哈夫曼树.docx

《北邮--第三次---哈夫曼树.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告实验名称：实验三-------哈夫曼树学生姓名：李雨薇班级：201221116班内序号：24学号：2012210178日期：2013年12月1日1．实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)

2、：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2.程序分析2.1存储结构（1）二叉树temp

3、lateclassBiTree{public:BiTree();//构造函数，其前序序列由键盘输入~BiTree(void);//析构函数BiNode*Getroot();//获得指向根结点的指针protected:BiNode*root;//指向根结点的头指针};//声明类BiTree及定义结构BiNodeData：二叉树是由一个根结点和两棵互不相交的左右子树构成。二叉树中的结点具有相同数据类型及层次关系。示意图：rootlchildparentrchild（2）静态三叉链表structHNod

4、e//哈夫曼树的静态三叉链表{unsignedintweight;//结点权值unsignedintparent;//双亲指针unsignedintLchild;//左孩子指针unsignedintRchild;//右孩子指针};示意图：parentRchildLchilddata(3)编码表的节点结构structHCode//字符及其编码结构{chardata;charcode[100];};示意图：charcode[100]chardata2.2关键算法分析一：关键算法(一)创建哈夫曼树（1）算法自然语言1.创建一个长度

5、为2*letter-1的三叉链表2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空3.从三叉链表的第n个结点开始，i=n3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4.根据哈夫曼树创建编码表（2）源代码voidHuffman::

6、HTree()//建立哈弗曼树{LNode*p=lroot;inti=0;troot=newTNode[2*Letter-1];while(p=p->next)//建立叶子节点{troot[i].weight=p->weight;troot[i].Parent=-1;troot[i].Lchild=-1;troot[i].Rchild=-1;i++;};for(inti=Letter;i<2*Letter-1;i++)troot[i].Parent=-1;intx,y,begin=0;//是两个最小值的角标for(intj=

7、Letter;j<2*Letter-1;j++){while(troot[begin].Parent!=-1)begin++;SelectMin(x,y,begin,j);troot[j].weight=troot[x].weight+troot[y].weight;troot[j].Lchild=x;troot[j].Rchild=y;troot[j].Parent=-1;troot[x].Parent=j;troot[y].Parent=j;}};(3)时间复杂度在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O

8、(n),故该函数的时间复杂度为O（n^2）（二）选择两个最小权值的函数（1）算法自然语言1.先暂时将前两个叶子结点作为权值最小的两个结点t1，t22.从第三个叶子结点开始，每一个结点的权值与t1，t2进行比较，如果此结点权值比t1权值要小，则将t1结点赋给t2，此结点赋给t1。3.如果此结