c数据结构实验哈夫曼树

《c数据结构实验哈夫曼树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验报告1.实验要求实验目的：(1)掌握二叉树基本操作的实现方法(2)掌握二叉树基本操作的实现方法(3)丫解哈夫曼树的思想和相关概念(4)学习使用二叉树解决实际问题的能力(5)法熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法，熟练改错方O(6)熟悉设•算法的过程(7)进-步掌握指针、异常处理的使川ii.实验内容：利川二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(Init):能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateT

2、able):利用己经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding):根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding):利用己经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print):以直观的方式打印赫夫曼树(选作)6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：TlovedataStructure，TloveComputer.Iwilltrymybesttostudyd

3、atastructure.提示：1、用户界而可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串中每个字符出现的次数统汁频度，对没有出现的字符一律不用编码。iii.代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出1.程序分析树形结构是一种非线性结构可以用结点之间的分支来表示层次关系，二叉树是毎个结点最多

4、两个子树的有序树，十分适合计算机处理问题，而哈夫曼树是一种特殊的二叉树，它将权值大的数据放在了离根较近的结点处，这样使得带权路径长度最短，是非常好的存储方式。2.1存储结构1.结点结构的存储方式：右孩子structhnode{intweight;intparent;intlchild;intrchild;chardata;//哈夫曼树结点的结构体姑点存储示意图:intweightintparentintlchildintrchildchardata2.编码表的实现中使用了以下结构体：Structhco

5、de//编码表结构体chardata;charcode[100];//字符//编码内容chardatacharcodeflOOl};75意图力:3.在select函数中使用的结构体:structnode{intnum;chardata;intnumchardata};2.2关键算法分析：A)Init初始化：统计需要编码的字符串屮每个字符的频度并建立哈夫曼树实现：在函数中没置了一个数组type用來统计字符串中字符的类型，no数组则用于统计每种字符串的个数，count用于存储每类字符的相应的个数。//将输

6、入的数据保存至类中cout«"请输入需要编译压缩的内容”《endl;cin.getline(in,500,*');n=0;no=0;count=newnode[127J;for(intj=O;j<127;j++)//type//对每一种字符的个数进行初始化countfjl.num=0;}while(in[no]!='*)//结朿之前，每输入一个字符，则对应的数目增I++count[infnoll.num;countfinfno]].clata=infno];++no;}for(intk=0;k

7、<127;k++){if(countfkl.num〉0){n++;cout«count[k].data«count[k].num«endl;将初始化的数据用于建立哈夫曼树:voidHuffman::createht()no=0;htree=newhnode[2*n-1];//含有n种字符的哈夫曼树需要2*n_r个结点for(inti=0;i〈n;i++){while(count[no],num==0)//该字符没有出现，跳过，继续找出现过的字no++;}htree[i].weight=count[no

8、],num;节点中，作为字符权重htree[i].lchild=-1;htree[i].rchild=-1;htree[iLparent=-1;htree[i].data=count[no],data;no++;//将count里统计的次数传入哈夫曼树的//将左右孩子结点和父节点都置空//将字符传入哈夫曼树的结点intx=—1，y=-1;for(inti=n;i++){SelectMin(x,y,i);个htree[x].parent=htree[y].