《数据结构实验三哈弗曼编码解码实验报告》由会员分享，可在线阅读，更多相关《数据结构实验三哈弗曼编码解码实验报告（12页珍藏版）》请在金锄头文库上搜索。
1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验三题目二：哈弗曼编码解码 学生姓名： 武文齐班 级： 2011211113班内序号： 05学 号： 2011210363日 期： 2011年12月6日1实验要求 利用二叉树结构实现赫夫曼编/解码器。基本要求：1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、 译码(Decoding)：利用已经
2、建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、 打印(Print)：以直观的方式打印赫夫曼树（选作）6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2. 程序分析2.1代码/function.h 类函数的声明#include #inc
3、lude using namespace std;struct LNode/链表的节点,用来统计字符频率，并编码char ch;/字符int weight;/权值char code20;/字符编码LNode* next;/指向下一个节点;struct TNode/哈弗曼树的节点 int weight;int Lchild;int Rchild;int Parent;class Haffman/用类来封装，体现C+面向对象的特点public: Haffman();/构造函数，输入、统计字符，创建哈弗曼树、码表Haffman();/释放链表空间、哈弗曼树的节点void CreateTable();
4、/建立码表，并将信息存入链表void PrintTable();/输出码表void Encoding();/哈弗曼编码void Decoding();/对一串数据解码void Comrate();/计算编码的压缩率void SelectMin(int &x,int &y,int begin,int end);/选取权值最小的两个数，创建哈弗曼树void reverse(char ch);/将码值倒置，用来编码void control();/对菜单交互等提示操作private:TNode* troot;LNode* lroot;/在统计字符频率是构建链表的根节点void List(char a)
5、;/统计字符的权值建立的单链表void HTree();/哈弗曼树建立int Letter;/共有不同字符总数char astr1000;/用户输入的一串字符char bstr1000;/将字符串的码值保存;/function.cpp 类函数的实现#include function.hHaffman:Haffman()/做初始化工作，统计字符的权值、创建哈弗曼树、建立码表、编码coutnext=NULL;Letter=0;/初始化字符总数为1cout请输入一串字符，以回车键结束next)lroot=p-next;delete p;p=lroot;delete p;void Haffman:Se
6、lectMin(int &x,int &y,int begin,int end)/选择两个最小的int t1,b,t2;/分别表示临时最小值、对应角标、从b开始比较t1=trootbegin.weight,b=t2=begin;for (;bend;b+)if (trootb.weightt1&trootb.Parent=-1)t1=trootb.weight;t2=b;x=t2;trootx.Parent=100;/临时为该最小的双亲赋值，防止再次被找出if(t2!=begin)/判断最小是否是第一个b=begin;elseb=begin;while (troot+b.Parent!=-1)
7、;t1=trootb.weight;t2=b;for (;bend;b+)if (trootb.weightnext)/建立叶子节点trooti.weight=p-weight;trooti.Parent=-1;trooti.Lchild=-1;trooti.Rchild=-1;i+;for (int i=Letter;i2*Letter-1;i+)trooti.Parent=-1;int x,y,begin=0;/是两个最小值的角标for (int j=Letter;jch!=ai)/查找链表中没有该字符或者找到该字符p=p-next;if (!p)/如果没有该字符，创建节点。p=new L
8、Node;p-ch=ai;p-weight=1;p-next=lroot-next;lroot-next=p;Letter+;else p-weight+;i+;p=lroot-next;void Haffman:reverse(char ch)/将字符串倒置for (int i=0;inext)j=i,k=0;while (trootj.Parent!=-1)if (troottrootj.Parent.Lchild=j)p-codek+=0;elsep-codek+=1;j=trootj.Parent;p-codek=0;reverse(p-code);i+;void Haffman:PrintTable()/打印码表和编码结果LNode* p=lroot;coutnext)coutchtweighttcodeendl;cout原字符编码结果为：bstrendl;cout*n;void Haffman:Encoding()int k=0;/输入字符串的脚标LNode* p;while(astrk!=0)
