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

《北邮信通院数据结构实验报告三哈夫曼编码器》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、t):以直观的方式打印赫夫曼树(选作)6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提不：1、用户界面可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串屮每个字符出现的次数统计频度，对没有出现的数据结构实验报告实验名称：实验三树——哈夫曼编/解码器学生姓名：班级：班内序号：学号：口期：2014年12月11口1.实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(

3、Ink):能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable):利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding):根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding):利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print):以直观的方式打印赫夫曼树(选作)6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComp

4、uter。IwilltrymybesttostudydataStructure.提不：1、用户界面可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串屮每个字符出现的次数统计频度，对没有出现的字符一律不用编码。1.程序分析2.1存储结构Huffman树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树leftchildweightrightchildII，1parentroot孩子双亲表示法霣weightlchildrchildparent2-1-1-15-1-1-16-1-1-17

5、-1-1-19-1-1-1weightlchildrchildparent2-1-155-1-156-1-167-1-169-1-17701713238165482967-12.2关键算法分析(1)计算出现字符的权值利用ASCII码统计出现字符的次数，再将未出现的字符进行筛选，将出现的字符及頻数存储在数组a□中。voidHuffman::Init(){intnNum[256]={0};//记录每一个字符出现的次数intch二cin.get();inti=0;while((ch!=’r’)&&(ch!=’’)){nNum[ch]++;str[i++]二ch

6、;ch=cin.get();//统计字符出现的次数//记录原始字符串//读取下一个字符str[i]=’’；n二0;for(i=0;i<256;i++)if(nNum[i]>0)//若nNum[i]==0,字符未出现{1[n]=(char)i;a[n]=nNum[i];n++;时间复杂度为0(1);(1)创建哈夫曼树：算法过程：Huffman树采用顺序存储数组；数组的前n个结点存储叶子结点，然后是分支结点，最后是根结点；首先初始化叶子结点元素一循环实现；以循环结构，实现分支结点的合成，合成规则按照huffman树构成规则进行关键点：选择最小和次小结点合成。v

7、oidHuffman::CreatellTree(){HTree=newHNode[2*n~l];//根据权重数组a[0..n_l]初始化Huffman树for(intj=0;j

8、=HTree[x].woight+HT