数据结构哈夫曼树实验报告

数据结构哈夫曼树实验 北京邮电大学信息与通信学院 2009级数据结构实验报告 实验名称: 实验3——哈夫曼树 学生姓名: 陈家斌 班 级: 2009211121 班内序号: 16 学 号: 09210619 日 期: 2010年12月3日 1(实验要求 【实验目的】 通过选择下面两个题目之一进行实现，掌握如下: , 掌握二叉树基本操作的实现方法 , 了解赫夫曼树的思想和相关概念 , 学习使用二叉树解决实际问题的能力 【题目】 利用二叉树结构实现赫夫曼编/解码器。 【基本要求】 1、初始化(Init):能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码(CreateTable):利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding):根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding):利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print):以直观的方式打印赫夫曼树(选作) 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 【测试数据】 I love data Structure, I love Computer。I will try my best to study data Structure. 第1页 北京邮电大学信息与通信工程学院 提示: 1、用户界面可以为“菜单”方式:能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。 【代码要求】 1、必须要有异常处理，比如删除空链表时需要抛出异常; 2、保持良好的编程的风格: , 代码段与段之间要有空行和缩近 , 标识符名称应该与其代表的意义一致 , 函数名之前应该添加注释说明该函数的功能 , 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出 2. 程序分析 【算法实现】 程序第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并把 树的信息保存起来，以便解压时创建同样的哈夫曼树进行解压;第二遍，根据第一遍扫描得 到的哈夫曼树进行编码，并把编码后的码字存储。 哈弗曼树的c++描述如下: class Huffman { public: HNode*HTree; //哈夫曼树 HCode*HCodeTable; //哈弗曼编码表 void CreateHTree(int a[],int n);//创建哈夫曼树 void CreateTable(char b[],int n);//创建编码表 void Encoding (char*s,int n);//编码 void Decoding (char*s,char*d,int n);//解码 void DestroyTree(int n); }; 【存储算法】 对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树 void Huffman::CreateHTree(int a[],int n) { HTree=new HNode [2*n-1]; 第2页 北京邮电大学信息与通信工程学院 for(int i=0;i=HTree[x].weight) { if(HTree[jjj].weight<_min) { _min=HTree[jjj].weight; y=jjj; } 第3页 北京邮电大学信息与通信工程学院 } } } bb[k]=y; k++; HTree[x].parent=HTree[y].parent=n; HTree[n].weight=HTree[x].weight+HTree[y].weight; HTree[n].lchild=x; HTree[n].rchild=y; HTree[n].parent=-1; for(int ii=n+1;ii<2*n-1;ii++) //开始创建哈夫曼树， { min=1000; for(int jj=0;jj=HTree[y].weight )// may wrong { if(HTree[jj].weight=HTree[x].weight) { if(HTree[jjj].weight<_min) { _min=HTree[jjj].weight; y=jjj; } } } } bb[k]=y; k++; HTree[x].parent=HTree[y].parent=ii; HTree[ii].weight=HTree[x].weight+HTree[y].weight; HTree[ii].lchild=x; HTree[ii].rchild=y; HTree[ii].parent=-1; } } 2.1 存储结构 哈夫曼树是一棵正则二叉树。根据二叉树的性质，一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，我们可以用一个静态三叉链表来存储哈夫曼树。 weight LChild RChild parent 0 2 -1 -1 -1 1 3 -1 -1 -1 2 6 -1 -1 -1 3 9 -1 -1 -1 4 -1 -1 -1 5 -1 -1 -1 【初始化哈夫曼树】 weight LChild RChild parent 0 2 -1 -1 4 1 3 -1 -1 4 第5页 北京邮电大学信息与通信工程学院 2 6 -1 -1 5 3 9 -1 -1 6 4 5 0 1 5 5 11 4 2 6 【创建好的哈夫曼树】 2.2 关键算法分析 【编码】 采用自下向上的方式生成编码表，由于每一个字符对应一个哈夫曼树的叶子结点，因此，创建编码表从叶子结点开始，若该节点是其父节点的左分支则编码1;然后将该结点的父结点当成叶子节点来分析，直到根结点为止，一个字符编码结束。 生成编码表的C++描述如下: void Huffman::CreateTable(char b[],int n) { HCodeTable=new HCode [n]; for (int i=0;i