实验三哈夫曼树实验报告.doc

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

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

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

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

4、/哈夫曼树的静态三叉链表{unsignedintweight;//结点权值unsignedintparent;//双亲指针unsignedintLchild;//左孩子指针unsignedintRchild;//右孩子指针};范文..示意图：parentRchildLchilddata(3)编码表的节点结构structHCode//字符及其编码结构{chardata;charcode[100];};示意图：charcode[100]chardata2.2关键算法分析一：关键算法(一)初始化函数voidHuf

5、fman::Init(inta[],intn)（1）算法自然语言1.创建一个长度为2*n-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结点的权

6、值，i结点的双亲设置为空4.根据哈夫曼树创建编码表（2）源代码voidHuffman::Init(inta[],intn)//创建哈夫曼树{//二叉树只有度为和度为的结点时，总结点数为（n-1）个HTree=newHNode[2*n-1];//根据权重数组a[1—范文..>n]初始化哈夫曼树inti,x,y;for(i=0;i

7、1;}for(inti=n;i<2*n-1;i++)//开始建哈夫曼树，从底层向顶层搭建{SelectMin(HTree,i,x,y);//从--(i-1)中选出两个权值最小的结点HTree[x].parent=i;HTree[y].parent=i;//左右孩子权值相加为父结点的权值HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].Lchild=x;HTree[i].Rchild=y;HTree[i].parent=-1;}范文..}(3)时

8、间复杂度在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数的时间复杂度为O（n^2）（二）统计字符出现频度的代码（1）算法自然语言①用cin.getline（）函数获取一段字符串。同时设置一个权值数组weight，以及暂时统计和存放权值的数组s。②用strlen（）函数获取未编码时的字符串长度。③从字符串的起始位置进行权值统计，即获得str[i]每个字符的ASⅡ编码，并在s[(int)st