c数据结构实验哈夫曼树.docxVIP

数据结构实验报告1．实验要求实验目的:掌握二叉树基本操作的实现方法掌握二叉树基本操作的实现方法了解哈夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法，熟练改错方法。熟悉设计算法的过程进一步掌握指针、异常处理的使用实验内容：利用二叉树结构实现赫夫曼编/解码器。基本要求：初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。打印(Print)：以直观的方式打印赫夫曼树（选作）计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据： I love data Structure, I love Computer.I will try my best to study data structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出2. 程序分析树形结构是一种非线性结构可以用结点之间的分支来表示层次关系，二叉树是每个结点最多两个子树的有序树，十分适合计算机处理问题，而哈夫曼树是一种特殊的二叉树，它将权值大的数据放在了离根较近的结点处，这样使得带权路径长度最短，是非常好的存储方式。2.1 存储结构1.结点结构的存储方式：根（下面结点的父结点）结点：左孩子右孩子……structhnode//哈夫曼树结点的结构体{int weight;int parent;int lchild;int rchild;char data;};结点存储示意图：int weightint parentint lchildint rchildchardata2.编码表的实现中使用了以下结构体：Struct hcode//编码表结构体{char data;//字符char code[100];//编码内容};示意图为：char datachar code[100]3.在select函数中使用的结构体：structnode{int num;char data;};int numchar data关键算法分析：A)Init初始化：统计需要编码的字符串中每个字符的频度并建立哈夫曼树实现：在函数中设置了一个数组type用来统计字符串中字符的类型，no数组则用于统计每种字符串的个数，count用于存储每类字符的相应的个数。voidHuffman::Init() //将输入的数据保存至类中{cout 请输入需要编译压缩的内容 endl;cin.getline(in, 500, \n);n = 0;no = 0;count = newnode[127]; //typefor (int j = 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 (int k = 0; k127; k++){if (count[k].num0){n++;cout count[k].data count[k].num endl;}}}将初始化的数据用于建立哈夫曼树：voidHuffman::createht(){no = 0;htree = newhnode[2 * n - 1];//含有n种字符的哈夫曼树需要2*n-1个结点for (int i = 0; in; i++){while (count[no].num == 0) //该字符没有出现，跳过，继续找出现过的字符{no++;}htree[i].weight = count[no].num; //将count里统计的次数传入哈夫曼树的节点中，作为字符权重htree[i].lchild = -1;htree[i].rchi