数据结构实验三哈夫曼编码.pdf

《数据结构实验三哈夫曼编码.pdf》由会员分享，可在线阅读，更多相关《数据结构实验三哈夫曼编码.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告实验名称：实验 3哈夫曼树学生姓名：XXX班级：班内序号：学号：日期： 2012 年 12 月 1 日1实验要求【实验目的】通过选择下面两个题目之一进行实现，掌握如下内容：掌握二叉树基本操作的实现方法了解赫夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力【题目】利用二叉树结构实现赫夫曼编/解码器。【基本要求】1、 初始化(Init)：能够对输入的任意长度的字符串 s 进行统计，统计每个字符的频度，并建立赫夫曼树2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、 编码(Encoding)：根据编码表对输入的字符串进行编码

2、，并将编码后的字符串输出。4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、 打印(Print)：以直观的方式打印赫夫曼树（选作）6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。【测试数据】 I love data Structure, I love Computer。I will try my best to study dataStructure.提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。【代码要求】1、必须要

3、有异常处理，比如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空行和缩近标识符名称应该与其代表的意义一致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能3、递归程序注意调用的过程，防止栈溢出2. 程序分析2.1 存储结构用二叉树的结构建立哈夫曼树，每个节点的结构是struct HNodeint weight;int lchild;int rchild;int parent;weightlchildrchildparent哈夫曼树结点结构哈夫曼树结点结构哈夫曼树的特点： 只有度为 2 的结点和叶子结点， 所以具有 n 个叶子结点的哈夫曼树的结点总数为 2n-1顺

4、序存储结构： 设置一个的 Tree2*n-1数组2.2 关键算法分析程序第一遍统计原数据中各字符出现的频率， 利用得到的频率值创建哈夫曼树， 并把树的信息保存起来，以便解压时创建同样的哈夫曼树进行解压； 第二遍，根据第一遍扫描得到的哈夫曼树进行编码，并把编码后的码字存储。哈弗曼树的 c+描述如下：class Huffmanpublic:void selectmin(int &x,int &y,int a);void CreateHTree(int a,int n);void CreateTable(char code,int n);void encode(char string,char co

5、de);void decoding(char*s,char*d,int n);void print(int length);HNode * HTree;HCode * HCodeTable;private:【存储算法】对输入的任意长度的字符串s 进行统计，统计每个字符的频度，并建立赫夫曼树void Huffman:CreateHTree(int a,int n)HTree=new HNode2*n-1;for(int i=0;in;i+)int x,y;for(int i=n;i2*n-1;i+)selectmin(x,y,i);HTreex.parent=HTreey.parent=i;HT

6、reei.weight=HTreex.weight+HTreey.weight;HTreei.lchild=x;HTreei.rchild=y;HTreei.parent=-1;HTreei.weight=ai;HTreei.lchild=-1;HTreei.rchild=-1;HTreei.parent=-1;哈夫曼树是一棵正则二叉树。根据二叉树的性质，一棵有n 个叶子的哈夫曼树共有 2n-1 个结点，可以用一个大小为 2n-1 的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，我们可以用一个静态三叉链表来存储哈夫曼树。012345012345【编码】voi

7、d Huffman:CreateTable(char code,int n)HCodeTable=new HCoden;for(int i=0;in;i+)HCodeTablei.data=codei;int child=i;int parent=HTreei.parent;int k=0;while(parent!=-1)HCodeTablei.codek=0;char *b=new chark;for(int j=0;jk;j+)bj=HCodeTablei.codek-1-j;if(child=HTreeparent.lchild)elsek+;child=parent;parent=H

8、Treechild.parent;HCodeTablei.codek=1;HCodeTablei.codek=0;weight2369weight2369511LChild-1-1-1-1-1-1LChild-1-1-1-104RChild-1-1-1-1-1-1RChild-1-1-1-112parent-1-1-1-1-1-1parent445656【初始化哈夫曼树】【创建好的哈夫曼树】bk=0;for(int m=0;m=k;m+)coutendl;HCodeTablei.codem=bm;【解码】void Huffman:decoding(char*s,char*d,int n)cou

9、t解a码?过y后的?字?符?串?为a：oendl;while(*s!=0)coutendl;int parent=2*n-1-1;while(HTreeparent.lchild!=-1)*d=HCodeTableparent.data;cout*d;d+;if(*s=0)elses+;parent=HTreeparent.rchild;parent=HTreeparent.lchild;2.3 其他增加菜单选项，可以重新开始程序或退出程序3.程序运行结果1.程序流程图开始输入字符串算出每个字符权值并分别存储权值和字符建哈夫曼树编码打印输入编码打印字符是是否重新运行否结束2.运行结果3.总结本次实验难度比较大，还好课本给出了大部分关键语句。 和老师 PPT 中的算法相比，这个算法还是略显稚嫩，有待改进的地方还有很多。