欢迎来到天天文库
浏览记录
ID:48870457
大小:306.50 KB
页数:20页
时间:2020-02-03
《北邮信通院大数据结构实验报告材料三哈夫曼编码器.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;j6、-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(;i8、=i1;i1=i;}elseif(hTree[i].parent=
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(;i8、=i1;i1=i;}elseif(hTree[i].parent=
8、=i1;i1=i;}elseif(hTree[i].parent=
此文档下载收益归作者所有