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

《北邮信通院数据结构实验报告三哈夫曼编码器》由会员分享，可在线阅读，更多相关《北邮信通院数据结构实验报告三哈夫曼编码器（20页珍藏版）》请在装配图网上搜索。

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 parent2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weight lchild rchild parent2-1-155-1-156-1-167-1-169-1-17701713238165482967-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

5、 Huffman:CreateHTree()HTree = 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;HTr

6、eei.weight = HTreex.weight+ HTreey.weight;HTreei.LChild = 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;

7、 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; 时间复杂度为O(n)(3)创建编码表算法过程：从叶子到根-自底向上 首先定义码表存储空间； 循环对n个叶子结点自底向上回溯到根，记下途径的左右关系，形成编码的逆序串； 将各个叶子结点对应的逆序串反序即可。 void Huffman:CreateCodeTabl

8、e() HCodeTable = new HCoden; /生成编码表for (int i=0;in;i+)HCodeTablei.data = li; int child = i;/孩子结点编号 int parent = HTreei.parent; /当前结点的父结点编号 int k=0; while(parent!=-1) if (child=HTreeparent.LChild) /左孩子标0 HCodeTablei.codek = 0; else HCodeTablei.codek = 1 ; /右孩子标1 k+; child = parent;/迭代 parent = HTreec

9、hild.parent;HCodeTablei.codek = 0;Reverse(HCodeTablei.code); /将编码字符逆置 时间复杂度为O(n)(4)生成编码串将输入的字符串的每一个字符与编码表比较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+;时间复杂度为O(n)（5）解码:算法过程： 从根到叶子-自顶向下 基于huffm

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

11、ld;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)lisetfill(-)setw(10-m)n;elsecoutsetfill( )setw(m+1)HTreei.weightsetfill(-)setw(10-m)n;Print(HTreei.LChild,m+1);Print(HTreei.RChild,m+1);（2）

12、统计字符頻数时，利用字符的ASCII码进行计数统计，调用了cin.get()函数开始3. 程序运行程序框图：输入要编码的字符串统计字符頻数生成哈夫曼树创建编码表生成编码串解码结束程序源代码：#include #include using namespace std;struct HNode int weight; /结点权值 int parent; /双亲指针int LChild; /左孩子指针int RChild ; /右孩子指针; struct HCode char data;char code100; ;class Huffmanprivate: HNode* HTree; /Huffm

13、an树 HCode* HCodeTable; /Huffman编码表char str1024; /输入的原始字符串char l256; /叶子节点对应的字符int a256; /记录每个出现的字符的个数public: int n; /叶子节点数void Init(); /初始化 void CreateHTree(); /创建huffman树 void CreateCodeTable(); /创建编码表void PrintTable(); void Encode(char *d); /编码void Decode(char *s, char *d); /解码void Print(int i,int

14、 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; /记录每一个字符出现的次数int ch = cin.get(); int i=0; while(ch!=r) & (ch!=n)nNumch+; /统计字符出现的次数stri+ = ch; /记录原始字符串ch = cin.g

15、et(); /读取下一个字符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 = HTreej.RChild = HTreej.parent = -1; int x,y; for (int i = n; i 2*n-1; i+) /开始

16、建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; /找一个比较值的起始值 for(i=0; in; i+) /找i1 if(hTree

17、i.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.LChild

18、= -1)coutsetfill( )setw(m+1)lisetfill(-)setw(10-m)n;elsecoutsetfill( )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

19、 = HTreei.parent; /当前结点的父结点编号 int k=0; while(parent!=-1) if (child=HTreeparent.LChild) /左孩子标0 HCodeTablei.codek = 0; else HCodeTablei.codek = 1 ; /右孩子标1 k+; child = parent;/迭代 parent = HTreechild.parent;HCodeTablei.codek = 0;Reverse(HCodeTablei.code); /将编码字符逆置 void Huffman:PrintTable()for (int i=0;i

20、n;i+)coutHCodeTablei.datatHCodeTablei.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

21、中的下标 while (HTreeparent.LChild!=-1) /如果不是叶子结点if (*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)/比较

22、压缩大小cout编码前：strlen(str)*8bitendl;cout编码后：strlen(d)bitendl;Huffman: 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.打印哈夫

23、曼树n2.打印哈夫曼编码表n3.打印编码n4.打印解码n5.压缩比m;switch(m)case 1:HFCode.Print(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()函数进行统计。最后由于有一些字符没有出现过，所以还需要进行筛选。在输出哈夫曼树时 ，采用了

24、凹入函数法进行输出，更加直观。创建编码表时 ，开始是自下到上的进行遍历，所以最后还需要进行逆序，形成最终的编码表。创建编码树的时候，没有正确运用指针的传递，结果出现了很多问题，各种内存访问错误，最后经过细细地从头到尾检查，发现了是在形式参数的地方出现了错误，在获取两个最小权值的结点的时候应该用引用，改过来之后错误没有了。打印赫夫曼树是最难的部分，一开始没有找到合适的办法，出现了很多问题，最后采用凹入表示打印的方法，从最右边的结点开始一行一行的打印，最后问题也能解决了。调试时，出现的问题是在进行编码时循环出现了错误，导致运行后编码变少，通过修改问题得以解决。通过哈夫曼编码的程序设计，更加深入的学习了哈夫曼树编码的思想，了解了不等长编码的思想，同时也通过实践明白了编码器的原理，在编码过程中，面对出现的问题，也学习了字符串的相关函数的运用，更加了解树的存储结构，受益匪浅。