《c大数据结构实验哈夫曼树》由会员分享，可在线阅读，更多相关《c大数据结构实验哈夫曼树（22页珍藏版）》请在金锄头文库上搜索。
1、word数据结构实验报告1实验要求i. 实验目的:（1） 掌握二叉树根本操作的实现方法（2） 掌握二叉树根本操作的实现方法（3） 了解哈夫曼树的思想和相关概念（4） 学习使用二叉树解决实际问题的能力（5） 熟悉C+语言的根本编程方法，掌握集成编译环境的调试方法，熟练改错方法。（6） 熟悉设计算法的过程（7） 进一步掌握指针、异常处理的使用ii. 实验内容：利用二叉树结构实现赫夫曼编/解码器。根本要求：1、 初始化(Init)：能够对输入的任意长度的字符串s进展统计，统计每个字符的频度，并建立赫夫曼树2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进展编码，并将每个字符的编码输
2、出。3、 编码(Encoding)：根据编码表对输入的字符串进展编码，并将编码后的字符串输出。4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进展译码，并输出译码结果。5、 打印(Print)：以直观的方式打印赫夫曼树选作6、 计算输入的字符串编码前和编码后的长度，并进展分析，讨论赫夫曼编码的压缩效果。测试数据： I love data Structure, I love puter.I will try my best to study data structure. 提示： 1、用户界面可以设计为“菜单方式：能够进展交互。 2、根据输入的字符串中每个字符出现的次数统计
3、频度，对没有出现的字符一律不用编码。iii. 代码要求：1、必须要有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出2. 程序分析树形结构是一种非线性结构可以用结点之间的分支来表示层次关系，二叉树是每个结点最多两个子树的有序树，十分适合计算机处理问题，而哈夫曼树是一种特殊的二叉树，它将权值大的数据放在了离根较近的结点处，这样使得带权路径长度最短，是非常好的存储方式。2.1 存储结构1.结点结构的存储方式：根下面结点的父结
4、点结点：左孩子右孩子structhnode /哈夫曼树结点的结构体int weight;int parent;int lchild;int rchild;char data;结点存储示意图：int weightint parentint lchildint rchildchardata：Struct hcode/编码表结构体char data;/字符char code100;/编码内容;示意图为：char datachar code1003.在select函数中使用的结构体：structnodeint num;char data;int numchar data2.2 关键算法分析：A)Ini
5、t初始化：统计需要编码的字符串中每个字符的频度并建立哈夫曼树实现：在函数中设置了一个数组type用来统计字符串中字符的类型，no数组如此用于统计每种字符串的个数，count用于存储每类字符的相应的个数。voidHuffman:Init() /将输入的数据保存至类中cout 请输入需要编译压缩的内容 endl;cin.getline(in, 500, n);n = 0;no = 0;count = newnode127; /typefor (int j = 0; j 127; j+) /对每一种字符的个数进展初始化 countj.num = 0;while (inno != 0) /完毕之前，每
6、输入一个字符，如此对应的数目增1+countinno.num;countinno.data = inno;+no;for (int k = 0; k0)n+;cout countk.data countk.num endl;将初始化的数据用于建立哈夫曼树：voidHuffman:createht()no = 0;htree = newhnode2 * n - 1;/含有n种字符的哈夫曼树需要2*n-1个结点for (int i = 0; in; i+)while (countno.num = 0) /该字符没有出现，跳过，继续找出现过的字符no+;htreei.weight = countno
7、.num; /将count里统计的次数传入哈夫曼树的节点中，作为字符权重htreei.lchild = -1;htreei.rchild = -1;htreei.parent = -1; /将左右孩子结点和父节点都置空htreei.data = countno.data; /将字符传入哈夫曼树的结点no+;int x = -1, y = -1;for (int i = n; i 2 * n - 1; i+)SelectMin(x, y, i); /挑选三者中的权重较小的两个htreex.parent = htreey.parent = i; /令较小的x、y为孩子节点，该两个结点的父节点是ih
8、treei.weight = htreex.weight + htreey.weight;/i结点字符的权重赋为是左右孩子字符权重之和htreei.lchild = x; /左孩子为xhtreei.rchild = y; /右孩子为yhtreei.parent = -1; /父节点置空x = -1;y = -1;注意select函数的编写十分重要，必须成功选出每次权值最小的两个数据才能正确的建立哈夫曼树voidHuffman:SelectMin(int &x, int &y, intk) /选出权值较小的两个字符结点int i = 0;while (i k)while (i k&htreei.
9、parent = -1) /当前结点不具有父结点且满足ik如此进展循环if (x = -1) /左孩子x = i;elseif (y = -1)y = i;elseif (htreex.weight = htreey.weight)if (htreey.weight htreey.weight)if (htreei.weight = htreex.weight)x = x; y = y;elsex = i;i+;i+;Bcreate table建立编码表：利用初始化得到的结果将哈夫曼树进展编码并输出每个字符的编码。1.在程序中设置了一个数组save来存储每个字符的编码。voidHuffman:
10、createhc() /建立哈夫曼编码表hcodetable = newhcoden; /生成编码表for (int i = 0; in; i+)hcodetablei.data = htreei.data;int child = i;int parent = htreei.parent;int k = 0;while (parent != -1)if (child = htreeparent.lchild) /该节点是父节点的左孩子如此编码为0，右孩子如此编码为1hcodetablei.codek = 0;elsehcodetablei.codek = 1;k+;child = parent
11、; /将该节点的父节点进展编码输出parent = htreechild.parent;hcodetablei.codek = 0; /code数组以0结尾Reverse(hcodetablei.code); /逆置输出字符的编码值cout 每个字符的编码为： endl;for (int i = 0; in; i+)cout hcodetablei.data ： hcodetablei.code = 0) /通过t数组将use数组内的数据逆序排序usej = ti;i-;j+;usej = 0;C.Encoding根据编码表对输入的字符串进展编码，并将编码后的字符串进展输出。 voidHuffman:Encoding() /编译输入内容为代码内容用0和1表示cout 编码结果为：;int k = 0;for (int i = 0; ini != 0; i+)int j = 0;while (hcodetablej.data != ini) /编码表的字符等于输入内容的字符时进展下一个while循环j+;int m = 0;while (hcodetablej.codem != 0)/输出该字符的编码savek = hcodetablej.codem;/save数组记录编码数据cout savek endl;k+;m+;
