北邮信通院数据结构实验报告三哈夫曼编码器

1、数据结构实验报告实验名称：实验二树哈夫曼编/解码器学生：班 级：班序号：学号：日期：2014年12月11日1. 实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化（Init）:能够对输入的任意长度的字符串 s进行统计，统计每 个字符的频度，并建立赫夫曼树2、 建立编码表（CreateTable）:利用已经建好的赫夫曼树进行编码，并将 每个字符的编码输出。3、编码（Encoding）:根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码（Decoding）:禾U用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、 打印（Print）:以直观的方式打印赫夫

2、曼树（选作）6计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。测试数据：I love data Structure, I love Computer。I will try my best to study data Structure.提示：1 、用户界面可以设计为“菜单”方式：能够进行交互。2 、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2. 程序分析2.1存储结构Huffman 树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为 Huffman树，也叫做最优二叉树哈夫虽树示意图left

3、chi Idweightrightchildparentroot孩子双亲表示法JL.weight Ichild child parent2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weight Ichild rchild pare nt2-1-155-1-156-1-167-1-169-1-17701713238165482967-12.2关键算法分析(1)计算出现字符的权值利用ASCII码统计出现字符的次数,再将未出现的字符进行筛选,将出现的字符及頻数存储在数组a中。void Huffma n:l nit()int nNu m256= 0;/int ch = ci

4、n.get();int i=0;while(ch!=r) & (ch!=n)nNu mch+;/stri+ = ch;/ch = cin .get();/记录每一个字符出现的次数统计字符出现的次数记录原始字符串读取下一个字符stri=0;n = 0;for ( i=0;i0)/若 nNumi=0，字符未出现ln = (char)i;an = nNu mi;n+;时间复杂度为0( 1);(2 )创建哈夫曼树：算法过程：Huffman树采用顺序存储-数组；数组的前n个结点存储叶子结点，然后是分支结点，最后是根结点；首先初始化叶子结点元素一循环实现；以循环结构，实现分支结点的合成，合成规则按照huf

5、fman树构成规则进行。关键点：选择最小和次小结点合成。void Huffma n:CreateHTree()HTree = new HNode 2*n-1; /根据权重数组 a0.n-1 初始化 Huffman 树for (i nt j = 0; j n; j+)HTreej.weight = aj;HTreej.LChild = HTreej.RChild = HTreej.pare nt = -1;int x,y;for (int i = n; i 2*n-1; i+) /开始建 Huffman 树SelectMin( HTree, i, x, y);/从1i中选出两个权值最小的结点HT

6、reex.pare nt = HTreey.pare nt = i;HTreei.weight = HTreex.weight+ HTreey.weight;HTreei.LChild = x;HTreei.RChild = y;HTreei.pare nt = -1;2时间复杂度为0(n )void Huffman:SelectMin( HNode *hTree,int n, int & 1, int &i2 ) int i;/找一个比较值的起始值for(i=0; in; i+) /找 i1 if(hTreei.pare nt=_1 )i1=i; break;i+；for( ; ihTree

7、i2.weight) i1 int j=i2;i2=i1; i1 = j; / 开始找最小的两个i+;for( ; in; i+) if(hTreei.pare nt=-1& hTreei.weight hTreei1.weight ) i2=i1;i1 = i; else if( hTreei.pare nt=-1& hTreei.weight hTreei2.weight) i2=i; 时间复杂度为0(n)(3)创建编码表算法过程：从叶子到根自底向上child = pare nt;/迭代首先定义码表存储空间；形成编码的逆序串;循环对n个叶子结点自底向上回溯到根，记下途径的左右关系,将各个叶

8、子结点对应的逆序串反序即可。void Huffma n:CreateCodeTable()HCodeTable = new HCode n; /生成编码表for (int i=0;i n;i+)HCodeTablei.data = li;int child = i;int pare nt = HTreei.pare nt;/孩子结点编号当前结点的父结点编号/左孩子标/右孩子标1int k=0;while(pare nt!=-1)if (child=HTreepare nt. LChild)HCodeTablei.codek = O;elseHCodeTablei.codek = 1k+;par

9、e nt = HTreechild.pare nt;/将编码字符逆置HCodeTablei.codek = 0：Reverse(HCodeTablei.code);时间复杂度为0(n)(4)生成编码串将输入的字符串的每一个字符与编码表比较void Huffman:Encode(char *d)编码，d为编码后的字符串char *s = str;while(*s!=0)for (in t i=0;i n;i+)if (*s = HCodeTablei.data )strcat(d, HCodeTablei.code);break;s+;时间复杂度为0(n)(5)解码：算法过程： 从根到叶子-自顶

10、向下基于huffman树存储数组，从根结点开始，依据输入待解码串s中码字0或1，分别向左或右跟踪至叶子结点，叶子结点对应的字符(见码表)，即为解码得到的字符;*d = HCodeTablepare nt.data;只要s串为结束，重复上述过程void Huffma n:Decode(char* s, char *d)/解码，s为编码串，d为解码后的字符串while(*s!=0)int pare nt = 2*n-2;while (HTreepare nt. LChild!=-1)II/根结点在HTree中的下标如果不是叶子结点if (*s=0)pare nt = HTreepare nt.LC

11、hild;elsepare nt = HTreepare nt.RChild;s+; d+;时间复杂度为0(n)2.3其他(1)哈夫曼树的输出是以凹入表示法来实现的，具体算法如下：void Huffma n:Pri nt( in t i, i nt m)if (HTreei.LChild = -1)coutsetfill( )setw(m+1)lisetfill(-)setw(10-m)n：elsecoutsetfill()setw(m+1)HTreei.weightsetfill(-)setw(10-m)n：Prin t(HTreei.LChild,m+1);Prin t(HTreei.RC

12、hild,m+1);函数(2)统计字符頻数时，利用字符的ASCII码进行计数统计，调用了 cin.get()3.程序运行程序框图：开始输入要编码的字符串1F统计字符頻数1F生成哈夫关曼树1创建编码表1生成编码串1f解码结束程序源代码:#in elude #i nclude using n amespace std; struct HNodeint weight;/结点权值int parent;/双亲指针int LChild;/左孩子指针int RChild ;/右孩子指针;struct HCodechar data;char code100;class Huffma nprivate:树编码表

13、输入的原始字符串:节点对应的字符 记录每个出现的字符的个数HNode* HTree;/Huffma nHCode* HCodeTable;/Huffmanchar str1024;/char l256;/Iint a256;/public:叶子节点数int n;/void In it();/void CreateHTree();void CreateCodeTable();void Prin tTable();void En code(char *d);void Decode(char *s, char *d); void Prin t(i nt i,i nt m);/void SelectM

14、i n( HNode *hTree,i nt n,出最小的两个权值void Reverse(char* s);void Compare(char*d); Huffma n();void Huffma n:l nit()int nNu m256= 0;int ch = cin .get();int i=0;while(ch!=r) & (ch!=n) nNu mch+; stri+ = ch; ch = cin .get();stri=0;n = 0;for ( i=0;i0)ln = (char)i; an = nNu mi; n+;void Huffma n:CreateHTree()HTr

15、ee = new HNode 2* n-1; /Huffman 树for (i nt j = 0; j n; j+)/初始化/创建huffman树创建编码表编码解码打印Huffman树找逆序比较压缩大小析构int & 1, int &i2);/记录每一个字符出现的次数统计字符出现的次数 记录原始字符串 读取下一个字符若nNumi=0，字符未出现根据权重数组a0.n-1 初始化HTreej.weight = aj;HTreej.LChild = HTreej.RChild = HTreej.pare nt = -1;int x,y;for (int i = n; i 2*n-1; i+) /开始

16、建 Huffman 树SelectMin( HTree, i, x, y);/从1i中选出两个权值最小的结点HTreex.pare nt = HTreey.pare nt = i;HTreei.weight = HTreex.weight+ HTreey.weight;HTreei.LChild = x;HTreei.RChild = y;HTreei.pare nt = -1;void Huffman:SelectMin( HNode *hTree,int n, int & 1, int &i2 )int i;/找一个比较值的起始值for(i=0; in; i+) /找 i1 if(hTre

17、ei.pare nt=_1 )i1=i; break; i+;for( ; ihTreei2.weight) /i1指向最小的 int j=i2;i2=i1; i1 = j; /开始找最小的两个i+;for( ; in; i+) if(hTreei.pare nt=-1& hTreei.weight hTreei1.weight ) i2=i1;i1 = i; else if( hTreei.pare nt=-1& hTreei.weight hTreei2.weight) i2=i; void Huffma n:Pri nt( in t i, i nt m)生成编码表/孩子结点编号/当前结点

18、的父结点编号/左孩子标 0:0;:1 ;/右孩子标1/迭代/将编码字符逆置if (HTreei.LChild = -1)coutsetfill()setw(m+1)lisetfill(-)setw(10-m)n： elsecoutsetfill()setw(m+1)HTreei.weightsetfill(-)setw(10-m)n;Prin t(HTreei.LChild,m+1);Prin t(HTreei.RChild,m+1);void Huffma n:CreateCodeTable()HCodeTable = new HCode n; / for (i nt i=0;i n ;i+

19、) HCodeTablei.data = li;int child = i;int pare nt = HTreei.pare nt; int k=0;while(pare nt!=-1)if (child=HTreepare nt.LChild) HCodeTablei.codek elseHCodeTablei.codekk+;child = pare nt;pare nt = HTreechild.pare nt;HCodeTablei.codek = 0; Reverse(HCodeTablei.code);void Huffma n:Pri ntTable() for (i nt i

20、=0;i n ;i+)coutHCodeTablei.datatHCodeTablei.codee ndl; char *s = str;void Huffman:Encode(char *d)编码，d为编码后的字符串while(*s!=O)for (int i=0;i n;i+)if (*s = HCodeTablei.data )strcat(d, HCodeTablei.code); break;s+;解码，s为编码串，d根结点在HTree中的下如果不是叶子结点void Huffma n:Decode(char* s, char *d)/为解码后的字符串while(*s!=0)in t

21、pare nt = 2*n-2;/标while (HTreepare nt.L Child!=-1)/if (*s=0)pare nt = HTreepare nt.LChild; elsepare nt = HTreepare nt.RChild; s+;*d = HCodeTablepare nt.data;d+;void Huffma n:Reverse(char* s)/换序char ch;int len = strle n( s);for (int i=0;ilen/2;i+)ch = si;si = sle n-i-1;sle n-i-1 = ch; void Huffma n:C

22、ompare(char*d)比较压缩大小cout编码前：strlen(str)*8bitendl; cout编码后：strlen(d)bitendl;Huffma n: Huffma n()/析构函数delete HTree;delete HCodeTable;void mai n()Huffman HFCode;char d1024=0;char s1024=0;cout请输入要编码的字符串：;HFCode.I nit();HFCode.CreateHTree();HFCode.CreateCodeTable();HFCode.E ncode(d);HFCode.Decode(d,s);int m;cout欢迎使用n1.打印哈夫曼树n2.打印哈夫曼编码表n3.打印编码n4.打印解码n5.压缩比endl;while(1)cinm;switch(m)case 1:HFCode.Pri nt(2*HFCode. n-2,1);break;case 2:HFCode .Prin tTable();break;case 3:cout编