《北邮信通院数据结构实验报告三哈夫曼编码器.pdf》由会员分享，可在线阅读，更多相关《北邮信通院数据结构实验报告三哈夫曼编码器.pdf（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、.数据结构实验报告实验名称：实验三 树哈夫曼编/解码器学生：班级：班序号：学号：日期：2014 年 12 月 11 日1实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s 进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。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树，也 叫 做 最 优 二 叉 树
3、。weight lchild rchild parent.2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weight lchild rchild parent 2-1-155-1-156-1-167-1-169-1-177017.13238165482967-12.2 关键算法分析（1）计算出现字符的权值利用 ASCII 码统计出现字符的次数，再将未出现的字符进行筛选，将出现的字符及頻数存储在数组a 中。void Huffman:Init()int nNum256=0;/记录每一个字符出现的次数int ch=cin.get();int i=0;while(ch!=r)&
4、(ch!=n)nNumch+;/统计字符出现的次数stri+=ch;/记录原始字符串ch=cin.get();/读取下一个字符 stri=0;n=0;.for(i=0;i0)/若 nNumi=0，字符未出现 ln=(char)i;an=nNumi;n+;时间复杂度为O（1）；（2）创建哈夫曼树：算法过程：Huffman 树采用顺序存储-数组；数组的前n 个结点存储叶子结点，然后是分支结点，最后是根结点；首先初始化叶子结点元素循环实现；以循环结构，实现分支结点的合成，合成规则按照huffman 树构成规则进行。关键点：选择最小和次小结点合成。void Huffman:CreateHTree()H
5、Tree=new HNode 2*n-1;/根据权重数组a0.n-1 初始化 Huffman 树for(int j=0;j n;j+).HTreej.weight=aj;HTreej.LChild=HTreej.RChild=HTreej.parent=-1;int x,y;for(int i=n;i 2*n-1;i+)/开始建 Huffman 树 SelectMin(HTree,i,x,y);/从 1i 中选出两个权值最小的结点HTreex.parent=HTreey.parent=i;HTreei.weight=HTreex.weight+HTreey.weight;HTreei.LChi
6、ld=x;HTreei.RChild=y;HTreei.parent=-1;时间复杂度为O(n2)void Huffman:SelectMin(HNode*hTree,int n,int&i1,int&i2)int i;/找一个比较值的起始值 for(i=0;in;i+)/找 i1 if(hTreei.parent=-1).i1=i;break;i+;for(;ihTreei2.weight)/i1指向最小的 int j=i2;i2=i1;i1=j;/开始找最小的两个 i+;for(;in;i+)if(hTreei.parent=-1&hTreei.weight hTreei1.weight)
7、i2=i1;i1=i;else if(hTreei.parent=-1&hTreei.weight hTreei2.weight)i2=i;时间复杂度为O(n)(3)创建编码表.算法过程：从叶子到根-自底向上首先定义码表存储空间；循环对 n 个叶子结点自底向上回溯到根，记下途径的左右关系，形成编码的逆序串；将各个叶子结点对应的逆序串反序即可。void Huffman:CreateCodeTable()HCodeTable=new HCoden;/生成编码表for(int i=0;in;i+)HCodeTablei.data=li;int child=i;/孩子结点编号 int parent=H
8、Treei.parent;/当前结点的父结点编号 int k=0;while(parent!=-1)if(child=HTreeparent.LChild)/左孩子标 0HCodeTablei.codek=0;else HCodeTablei.codek=1;/右孩子标 1k+;child=parent;/迭代parent=HTreechild.parent;.HCodeTablei.codek=0;Reverse(HCodeTablei.code);/将编码字符逆置 时间复杂度为O(n)(4)生成编码串将输入的字符串的每一个字符与编码表比较void Huffman:Encode(char*d
9、)/编码，d 为编码后的字符串 char*s=str;while(*s!=0)for(int i=0;in;i+)if(*s=HCodeTablei.data)strcat(d,HCodeTablei.code);break;s+;.时间复杂度为O(n)（5）解码:算法过程：从根到叶子-自顶向下基于 huffman 树存储数组，从根结点开始，依据输入待解码串s 中码字 0 或 1，分别向左或右跟踪至叶子结点，叶子结点对应的字符（见码表），即为解码得到的字符；只要 s 串为结束，重复上述过程void Huffman:Decode(char*s,char*d)/解码，s 为编码串，d 为解码后的字
10、符串 while(*s!=0)int parent=2*n-2;/根结点在HTree 中的下标while(HTreeparent.LChild!=-1)/如果不是叶子结点 if(*s=0)parent=HTreeparent.LChild;else parent=HTreeparent.RChild;s+;*d=HCodeTableparent.data;d+;.时间复杂度为O（n）2.3 其他（1）哈夫曼树的输出是以凹入表示法来实现的，具体算法如下：void Huffman:Print(int i,int m)if(HTreei.LChild=-1)coutsetfill()setw(m+1
11、)lisetfill(-)setw(10-m)n;else coutsetfill()setw(m+1)HTreei.weightsetfill(-)setw(10-m)n;Print(HTreei.LChild,m+1);Print(HTreei.RChild,m+1);（2）统计字符頻数时，利用字符的ASCII 码进行计数统计，调用了cin.get()函数3.程序运行程序框图：开始输入要编码的字符串统计字符頻数生成哈夫曼树.程序源代码：#include#include using namespace std;struct HNode int weight;/结点权值int parent;/
12、双亲指针int LChild;/左孩子指针int RChild;/右孩子指针;struct HCode char data;char code100;class Huffman private:HNode*HTree;/Huffman树HCode*HCodeTable;/Huffman编码表char str1024;/输入的原始字符串char l256;/叶子节点对应的字符int a256;/记录每个出现的字符的个数public:int n;/叶子节点数创建编码表生成编码串解码结束.void Init();/初始化 void CreateHTree();/创建 huffman 树 void C
13、reateCodeTable();/创建编码表void PrintTable();void Encode(char*d);/编码void Decode(char*s,char*d);/解码void Print(int i,int m);/打印 Huffman 树 void SelectMin(HNode*hTree,int n,int&i1,int&i2);/找出最小的两个权值void Reverse(char*s);/逆序void Compare(char*d);/比较压缩大小 Huffman();/析构;void Huffman:Init()int nNum256=0;/记录每一个字符出现
14、的次数int ch=cin.get();int i=0;while(ch!=r)&(ch!=n)nNumch+;/统计字符出现的次数stri+=ch;/记录原始字符串ch=cin.get();/读取下一个字符 stri=0;n=0;for(i=0;i0)/若 nNumi=0，字符未出现 ln=(char)i;an=nNumi;n+;void Huffman:CreateHTree()HTree=new HNode 2*n-1;/根 据 权 重 数 组a0.n-1 初 始 化Huffman 树for(int j=0;j n;j+).HTreej.weight=aj;HTreej.LChild=H
15、Treej.RChild=HTreej.parent=-1;int x,y;for(int i=n;i 2*n-1;i+)/开始建 Huffman 树 SelectMin(HTree,i,x,y);/从 1i 中选出两个权值最小的结点HTreex.parent=HTreey.parent=i;HTreei.weight=HTreex.weight+HTreey.weight;HTreei.LChild=x;HTreei.RChild=y;HTreei.parent=-1;void Huffman:SelectMin(HNode*hTree,int n,int&i1,int&i2)int i;/
16、找一个比较值的起始值 for(i=0;in;i+)/找 i1 if(hTreei.parent=-1)i1=i;break;i+;for(;ihTreei2.weight)/i1指向最小的 int j=i2;i2=i1;i1=j;/开始找最小的两个 i+;for(;in;i+)if(hTreei.parent=-1&hTreei.weight hTreei1.weight)i2=i1;i1=i;else if(hTreei.parent=-1&hTreei.weight hTreei2.weight)i2=i;void Huffman:Print(int i,int m).if(HTreei.
17、LChild=-1)coutsetfill()setw(m+1)lisetfill(-)setw(10-m)n;else coutsetfill()setw(m+1)HTreei.weightsetfill(-)setw(10-m)n;Print(HTreei.LChild,m+1);Print(HTreei.RChild,m+1);void Huffman:CreateCodeTable()HCodeTable=new HCoden;/生成编码表for(int i=0;in;i+)HCodeTablei.data=li;int child=i;/孩子结点编号int parent=HTreei
18、.parent;/当前结点的父结点编号int k=0;while(parent!=-1)if(child=HTreeparent.LChild)/左孩子标 0HCodeTablei.codek=0;else HCodeTablei.codek=1;/右孩子标 1k+;child=parent;/迭代parent=HTreechild.parent;HCodeTablei.codek=0;Reverse(HCodeTablei.code);/将编码字符逆置 void Huffman:PrintTable()for(int i=0;in;i+)coutHCodeTablei.datatHCodeT
19、ablei.codeendl;void Huffman:Encode(char*d)/编码，d 为编码后的字符串 char*s=str;.while(*s!=0)for(int i=0;in;i+)if(*s=HCodeTablei.data)strcat(d,HCodeTablei.code);break;s+;void Huffman:Decode(char*s,char*d)/解码，s 为编码串，d为解码后的字符串 while(*s!=0)int parent=2*n-2;/根结点在HTree 中的下标while(HTreeparent.LChild!=-1)/如果不是叶子结点 if(*
20、s=0)parent=HTreeparent.LChild;else parent=HTreeparent.RChild;s+;*d=HCodeTableparent.data;d+;void Huffman:Reverse(char*s)/换序 char ch;int len=strlen(s);for(int i=0;ilen/2;i+)ch=si;si=slen-i-1;slen-i-1=ch;void Huffman:Compare(char*d)/比较压缩大小.cout 编码前：strlen(str)*8bitendl;cout 编码后：strlen(d)bitendl;Huffma
21、n:Huffman()/析构函数 delete HTree;delete HCodeTable;void main()Huffman HFCode;char d1024=0;char s1024=0;cout 请输入要编码的字符串：;HFCode.Init();HFCode.CreateHTree();HFCode.CreateCodeTable();HFCode.Encode(d);HFCode.Decode(d,s);int m;cout 欢迎使用n1.打印哈夫曼树n2.打印哈夫曼编码表n3.打印编码 n4.打印解码 n5.压缩比 m;switch(m)case 1:HFCode.Prin
22、t(2*HFCode.n-2,1);break;case 2:HFCode.PrintTable();break;.case 3:cout编码结果：dendl;break;case 4:cout解码结果：sendl;break;case 5:HFCode.Compare(d);运行结果：.4.总结在编程时，最开始在字符统计时出现了空格无法统计的问题，后来用cin.get()函数进行统计。最后由于有一些字符没有出现过，所以还需要进行筛选。在输出哈夫曼树时，采用了凹入函数法进行输出，更加直观。创建编码表时，开始是自下到上的进行遍历，所以最后还需要进行逆序，形成最终的编码表。创建编码树的时候，没有正
23、确运用指针的传递，结果出现了很多问题，各种存访问错误，最后经过细细地从头到尾检查，发现了是在形式参数的地方出现了错误，在获取两个最小权值的结点的时候应该用引用，改过来之后错误没有了。打印赫夫曼树是最难的部分，一开始没有找到合适的办法，出现了很多问题，最后采用凹入表示打印的方法，从最右边的结点开始一行一行的打印，最后问题也能解决了。调试时，出现的问题是在进行编码时循环出现了错误，导致运行后编码变少，通过修改问题得以解决。通过哈夫曼编码的程序设计，更加深入的学习了哈夫曼树编码的思想，了解了不等长编码的思想，同时也通过实践明白了编码器的原理，在编码过程中，面对出现的问题，也学习了字符串的相关函数的运用，更加了解树的存储结构，受益匪浅。