文档介绍：:掌握二叉树基本操作的实现方法掌握二叉树基本操作的实现方法了解哈夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力熟悉C++语言的基本编程方法,掌握集成编译环境的调试方法,熟练改错方法。熟悉设计算法的过程进一步掌握指针、异常处理的使用实验内容:利用二叉树结构实现赫夫曼编/解码器。基本要求:初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立赫夫曼树建立编码表(CreateTable):利用已经建好的赫夫曼树进行编码,并将每个字符的编码输出。编码(Encoding):根据编码表对输入的字符串进行编码,并将编码后的字符串输出。译码(Decoding):利用已经建好的赫夫曼树对编码后的字符串进行译码,并输出译码结果。打印(Print):以直观的方式打印赫夫曼树(选作)计算输入的字符串编码前和编码后的长度,并进行分析,讨论赫夫曼编码的压缩效果。测试数据:IlovedataStructure,:1、用户界面可以设计为“菜单”方式:能够进行交互。2、根据输入的字符串中每个字符出现的次数统计频度,对没有出现的字符一律不用编码。代码要求:1、必须要有异常处理,比如删除空链表时需要抛出异常;2、保持良好的编程的风格:代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程,,二叉树是每个结点最多两个子树的有序树,十分适合计算机处理问题,而哈夫曼树是一种特殊的二叉树,它将权值大的数据放在了离根较近的结点处,这样使得带权路径长度最短,是非常好的存储方式。:根(下面结点的父结点)结点:左孩子右孩子 ……structhnode//哈夫曼树结点的结构体{ intweight; intparent; intlchild; intrchild; chardata;};结点存储示意图::Structhcode//编码表结构体{ chardata;//字符 charcode[100];//编码内容};示意图为:chardatacharcode[100]:structnode{ intnum; chardata;};intnumchardata关键算法分析: A)Init初始化:统计需要编码的字符串中每个字符的频度并建立哈夫曼树实现:在函数中设置了一个数组type用来统计字符串中字符的类型,no数组则用于统计每种字符串的个数,count用于存储每类字符的相应的个数。voidHuffman::Init()//将输入的数据保存至类中{ cout<<"请输入需要编译压缩的内容"<<endl; (in,500,'\n'); n=0; no=0; count=newnode[127];//type for(intj=0;j<127;j++)//对每一种字符的个数进行初始化 { count[j].num=0; } while(in[no]!='\0')//结束之前,每输入一个字符,则对应的数目增1 { ++count[in[no]].num; count[in[no]].data=in[no]; ++no; } for(intk=0;k<127;k++) { if(count[k].num>0) { n++; cout<<count[k].data<<count[k].num<<endl; } }}将初始化的数据用于建立哈夫曼树:voidHuffman::createht(){ no=0; htree=newhnode[2*n-1];//含有n种字符的哈夫曼树需要2*n-1个结点 for(inti=0;i<n;i++) { while(count[no].num==0)//该字符没有出现,跳过,继续找出现过的字符{ no++; } htree[i].weight=count[no].num;//将count里统计的次数传入哈夫曼树的节点中,作为字符权重 htree[i].lchild=-1; htree[i].rchild=-1; htree[i].parent=-1;//将左右孩子结点和父节点都置空 htree[i].data=count[no].data;//将字符传入哈夫曼树的结点 no++; } intx=-1,y=-1; for(i