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

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

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

2、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。实用文档2.程序分析2.1存储结构Huffman树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffm

3、an树，也叫做最优二叉树。weightlchildrchildparent实用文档2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weightlchildrchildparent2-1-155-1-156-1-167-1-169-1-177017实用文档13238165482967-12.2关键算法分析（1）计算出现字符的权值利用ASCII码统计出现字符的次数，再将未出现的字符进行筛选，将出现的字符及頻数存储在数组a[]中。voidHuffman::Init(){intnNum[256]={0};//记录每一个字符出现的次数intch

4、=cin.get();inti=0;while((ch!='r')&&(ch!='')){nNum[ch]++;//统计字符出现的次数str[i++]=ch;//记录原始字符串ch=cin.get();//读取下一个字符}str[i]='';n=0;实用文档for(i=0;i<256;i++){if(nNum[i]>0)//若nNum[i]==0，字符未出现{l[n]=(char)i;a[n]=nNum[i];n++;}}}时间复杂度为O（1）；（2）创建哈夫曼树：算法过程：Huffman树采用顺序存储---数组；数组的前n个结点存储叶子结点，然

5、后是分支结点，最后是根结点；首先初始化叶子结点元素—循环实现；以循环结构，实现分支结点的合成，合成规则按照huffman树构成规则进行。关键点：选择最小和次小结点合成。voidHuffman::CreateHTree(){HTree=newHNode[2*n-1];//根据权重数组a[0..n-1]初始化Huffman树for(intj=0;j

6、-1;i++)//开始建Huffman树{SelectMin(HTree,i,x,y);//从1~i中选出两个权值最小的结点HTree[x].parent=HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;}}时间复杂度为O(n2)voidHuffman::SelectMin(HNode*hTree,intn,int&i1,int&i2){inti;//找一个比较值的

7、起始值for(i=0;ihTree[i2].weight)//i1指向最小的{intj=i2;i2=i1;i1=j;}//开始找最小的两个i++;for(;i

8、=i1;i1=i;}elseif(hTree[i].parent=