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

数据结构试验汇报试验名称:试验三树学生姓名:班级:班内序号:学号:日期:12月7号试验要求利用二叉树结构实现赫夫曼编/解码器。基础要求:初始化(Init):能够对输入任意长度字符串s进行统计,统计每个字符频度,并建立赫夫曼树建立编码表(CreateTable):利用已经建好赫夫曼树进行编码,并将每个字符编码输出。编码(Encoding):依据编码表对输入字符串进行编码,并将编码后字符串输出。译码(Decoding):利用已经建好赫夫曼树对编码后字符串进行译码,并输出译码结果。打印(Print):以直观方法打印赫夫曼树(选作)计算输入字符串编码前和编码后长度,并进行分析,讨论赫夫曼编码压缩效果。测试数据:IlovedataStructure,puter。:1、用户界面能够设计为“菜单”方法:能够进行交互。2、依据输入字符串中每个字符出现次数统计频度,对没有出现字符一律不用编码。2、(1)二叉树template<classT>classBiTree{public:BiTree(); //结构函数,其前序序列由键盘输入~BiTree(void); //析构函数 BiNode<T>*Getroot(); //取得指向根结点指针protected:BiNode<T>*root; //指向根结点头指针};//申明类BiTree及定义结构BiNodeData:二叉树是由一个根结点和两棵互不相交左右子树组成。二叉树中结点含有相同数据类型及层次关系。示意图:rootlchildparentrchild(2)静态三叉链表structHNode//哈夫曼树静态三叉链表{unsignedintweight;//结点权值unsignedintparent;//双亲指针unsignedintLchild;//左孩子指针unsignedintRchild;//右孩子指针};示意图:parentRchildLchilddata(3)编码表节点结构structHCode//字符及其编码结构{chardata;charcode[100];};示意图:charcode[100]:关键算法(一)初始化函数voidHuffman::Init(inta[],intn)(1)算法自然语言创建一个长度为2*n-1三叉链表将存放字符及其权值链表中字符逐一写入三叉链表前n个结点data域,并将对应结点孩子域和双亲域赋为空从三叉链表第n个结点开始,i=n从存放字符及其权值链表中取出两个权值最小结点x,y,统计其下标x,y。将下标为x和y哈夫曼树结点双亲设置为第i个结点将下标为x结点设置为i结点左孩子,将下标为y结点设置为i结点右孩子,i结点权值为x结点权值加上y结点权值,(2)源代码voidHuffman::Init(inta[],intn)//创建哈夫曼树{//二叉树只有度为和度为结点时,总结点数为(n-1)个HTree=newHNode[2*n-1];//依据权重数组a[1—>n]初始化哈夫曼树inti,x,y;for(i=0;i<n;i++)//n个叶子结点{HTree[i].weight=a[i];HTree[i].Lchild=-1;HTree[i].Rchild=-1;HTree[i].parent=-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)时间复杂度在选择两个权值最小结点函数中要遍历链表,时间复杂度为O(n),故该函数时间复杂度为O(n^2)(二)统计字符出现频度代码(1)算法自然语言①()函数获取一段字符串。同时设置一个权值数组weight,和临时统计和存放权值数组s。②用strlen()函数获取未编码时字符串长度。③从字符串起始位置进行权值统计,即取得str[i]每个字符ASⅡ编码,并在s[(int)str[i]]数组中进行+1统计,为字符出现一次。④i进行自加,统计下面字符出现频度,在对应数组元素中进行+1统计。⑤继续循环,直到字符串结束。(2)源代码(在main()函数中实现)inti,j=0,v;ints[20