数据结构实验报告huffman编码和解码算法

《数据结构实验报告huffman编码和解码算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、（规格为A4纸或A3纸折叠）佛山科学技术学院（用四号宋体）实验报告（用小二号黑体）课程名称数据结构实验实验项目用Huffman树进行编码和解码算法专业班级—姓名学号—指导教师成绩H期（用小四号宋体）一、目的和要求1、通过本实验，熟悉二叉树、Huffman树的基本概念，掌握二叉树的存储结构及各种算法。2、熟悉用Huffman树进行电文的加密与解密算法。二、实验原理Huffman树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符的频度，能够达到编码电文的最小化。三、实验步骤1.统计电文中字符的出现频率。2.用统计频率建立Hffman树。3.生成前缀码；4.建立huffm

2、an树的解码算法.5.用随机输入的电文完成编码与解码过程。四、源程序#include^include#includc〈string.h>#defineMAX100structHTNode{chara;intweight;intparent,lchild,rchild;}*HT;//动态分配数组存储赫夫曼树char**HC;intn=0,m=0;char*writc（）〃存储输入的电文{char*p,*q;printf（，z请输入电文（结束输入请按enter）：〃）;p=（char*）malloc（MAX*sizeof（char））;//申请存

3、储输入的屯文的空间if（!p）exit（0）;q=p;scanf（〃％c〃，q）;while（*q!二'）{//******录入电文，每录入一个字符同时给电文长度计数器n加一*******n=n+l;if(n>二MAX)//判断己中请的空间是否足够录入，不足则追加空间{p=(char*)realloc(q,(MAX+10)*sizeof(char));if(!p)exit(0);}q++；scanf(〃％c〃，q);}return(p);}voidweight(char*p)//求电文中各字符的概率，并将该概率当作各字符的权值{char*q,*ql,temp;structHTNo

4、de*q2;inti,j,t;ql=q=(char*)malloc(n*sizeof(char));for(;*p!二';p++,ql++)*ql=*p;//将电文存放到ql指向的空间中qi=q;for(i=0;i

5、出现过不同的字符的个数{ql++；if(temp!=*ql){m++；//字符种类计数器加一temp=*ql;}}ql二q；HT=(structHTNodc*)malloc(2*m*sizeof(structHTNode));/*申请赫夫曼树HT的空间，其中0号单元不用*/q2二HT+1;//*****************初女台化赫夫曼树HT*********************for(i=l;i〈二n;)t=0;for(q2-〉a=*ql;*ql二二q2-〉a;ql++)t++；i++；}q2-〉weight二(int)(t*100/n);q2->lchild=0;q2->

6、parent二0;q2->rchild=0;q2++;}for(i=m+l;i<=2*m-l;i++,q2++){q2->lchild=0;q2->parcnt二0;q2->rchild=0;q2-〉weight二0;}free(q);}voidSelect(intt,int*sl,int*s2){/************在HT[1,t]选择parent为0且weight最小的两个结点，其序号分别为si和s2o**********************/inttemp,j;for(j=l;j<=t;j++)if(HT[jJ.parent==0){*sl二j;for(j=j+l;j

7、<=t;j++)if(HT[j].parcnt==0){*s2二j;break;}break;}if(HT[*sl].weight>HT[*s2].weight)temp=*s2;*s2=*sl;*sl二temp;for(;t>0;t-一)if(t!=*sl&&t!=*s2)if(HT[t]・parent==0)if(HT[*sl].weight〈二HT[t].weight&&HT[*s2]・weight>HT[t].weight)*s2二t;elseif