数据结构实验三哈弗曼编码解码实验报告

《数据结构实验三哈弗曼编码解码实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验三——题目二：哈弗曼编码解码学生姓名：武文齐班级：2011211113班内序号：05学号：2011210363日期：2011年12月6日1．实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将

2、编码后的字符串输出。4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符

3、一律不用编码。第11页北京邮电大学信息与通信工程学院2.程序分析2.1代码/////////////////////////////////////////////////////////////////////////////////function.h类函数的声明#include#includeusingnamespacestd;structLNode//链表的节点,用来统计字符频率，并编码{charch;//字符intweight;//权值charcode[20];/

4、/字符编码LNode*next;//指向下一个节点};structTNode//哈弗曼树的节点{intweight;intLchild;intRchild;intParent;};classHaffman//用类来封装，体现C++面向对象的特点{public:Haffman();//构造函数，输入、统计字符，创建哈弗曼树、码表~Haffman();//释放链表空间、哈弗曼树的节点voidCreateTable();//建立码表，并将信息存入链表voidPrintTable();//输出码表voidEncoding

5、();//哈弗曼编码voidDecoding();//对一串数据解码voidComrate();//计算编码的压缩率voidSelectMin(int&x,int&y,intbegin,intend);//选取权值最小的两个数，创建哈弗曼树voidreverse(charch[]);//将码值倒置，用来编码voidcontrol();//对菜单交互等提示操作private:TNode*troot;LNode*lroot;//在统计字符频率是构建链表的根节点voidList(chara[]);//统计字符的权值建立

6、的单链表voidHTree();//哈弗曼树建立intLetter;//共有不同字符总数第11页北京邮电大学信息与通信工程学院charastr[1000];//用户输入的一串字符charbstr[1000];//将字符串的码值保存};/////////////////////////////////////////////////////////////////////////////////function.cpp类函数的实现#include"function.h"Haffman::Haffman()//做初始

7、化工作，统计字符的权值、创建哈弗曼树、建立码表、编码{cout<<"***********************哈夫曼树应用************************";lroot=newLNode;bstr[0]='';lroot->next=NULL;Letter=0;//初始化字符总数为1cout<<"请输入一串字符，以回车键结束"<

8、coding();};Haffman::~Haffman()//释放链表空间、哈弗曼树的节点{deletetroot;LNode*p=lroot;while(p=lroot->next){lroot=p->next;deletep;p=lroot;}deletep;};voidHaffman::SelectMin(int&x,int&y,intbegin,intend)/