哈夫曼树的建立与编码实验报告.doc

本科学生实验报告项目组长 学号 成 员 专 业 计算机科学与技术 班级 112 实验项目名称建立赫夫曼树并进行赫夫曼编码指导教师及职称 开课学期 2012 至 2013 学年 一 学期上课时间 2012 年 12 月 3 日一、实验设计方案实验名称：哈夫曼树的建立与译码实验时间：2012.12.3小组合作： 是 否小组成员：1、实验目的设计要求对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。本设计必须实现以下几个方面的功能：1） 哈夫曼树的建立2） 哈夫曼编码的生成3） 编码文件的译码2、实验思路（实验内容、数据处理方法及实验步骤等） 实验内容：通过建立哈夫曼树实现哈夫曼编码，其中包括以下三个功能：1） 哈夫曼树的建立2） 哈夫曼编码的生成3） 编码文件的译码 并最终实现哈夫曼编码的设计目标。实验步骤与数据处理方法：1、哈夫曼树的建立由哈夫曼算法的定义可知，初始深林中共有n棵只含有根结点的二叉树。算法 的第二步将当前深林中的两棵根结点权值最小的二叉树，合并成一棵树的二叉树；每合并一次，深林中就减少一棵树，产生一个新结点。显然要进行n-1次的合并，所以共产生n-1个新结点，它们都是具有两个孩子的分支结点，由此可知，最终求得的哈夫曼树中共有2n-1个结点，其中n个叶结点是初始深林的n个孤立结点。并且，哈夫曼树中没有度数为1的分支结点。我们可用一个大小为2n-1的一维数组来存储哈夫曼树中的结点。哈夫曼树的建立主要包括以下三个算法：1.1 选择parent为0且权值最小的两个根节点的算法void select(HuffmanTree HT,int k,int *s1,int *s2) int i,j;int min1=101;for(i=1;i=k;i+)if(Ti.weightmin1 & Ti.parent=0)j=i;min1=Ti.weight;*s1=j;min1=32767;for(i=1;i=k;i+)if(Ti.weightmin1 & Ti.parent=0 & i!=*s1)j=i; min1=Ti.weight;*s2=j; 1.2 统计字符串中字符的种类以及各类字符的个数的算法 int jsq(char *s,int cnt,char str) char *p;int i,j,k;int temp27;for(i=1;i=A & *p=Z)k=*p-64;tempk+;j=0;for(i=1,j=0;i26;i+)if(tempi!=0)j+;strj=i+64;cntj=tempi;return j; 1.3 构造哈夫曼树void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str) int i,s1,s2;for(i=1;i=2*num-1;i+)HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.weight=0; for(i=1;inum;i+) /输入num个叶子结点的权值HTi.weight=cnti; for(i=num+1;i=2*num-1;i+)select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.weight=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight;for(i=0;i=num;i+) /输入字符集中的字符HCi.ch=stri;i=1;while(i=num) printf(字符 %c, 次数为：%dn,HCi.ch,cnti+);哈夫曼树的存储结构：typedef struct int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;2、 哈夫曼编码的生成要求电文的哈夫曼编码，必须先定义哈夫曼编码类型。根据设计要求与实际需要定义的类型如下： typedef struct char ch; char bits9; /存放编码位串 int len; /编码长度 CodeNode; typedef CodeNode HuffmanCoden+1;并且主要包括以下2个步骤： 2.1 哈夫曼编码算法 void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) /根据赫夫曼树HT求赫夫曼编码HCint c,p,i; /c和p分别指示T中孩子和双亲的位置char cdn; /临时存放编码串int start; /指示编码在cd中的起始位置cdnum=0;for(i=1;i0) /直到上溯到HTc是树根为止 /若HTc是HTp的左孩子，生成0；否则生成代码1cd-start=(HTp.lchild=c)?0:1;c=p;strcpy(HCi.bits,&cdstart);HCi.len=num-start; 2.2 建立正文的编码文件 void coding(HuffmanCode HC,char *str) /对str所代表的字符串进行编码，并写入文件int i,j;FILE *fp;fp=fopen(codefile.text,w);while(*str)for(i=1;i=num;i+)if(HCi.ch=*str)for(j=0;jHCi.len;j+)fputc(HCi.bitsj,fp);break;str+;fclose(fp); 建立编码文件的基本思想是：将要编码的字符串中的字符逐一与预先生成哈夫曼树时保存的字符编码对照表进行比较，找到以后，将字符的编码写入代码文件，直至所有的字符处理完为止。3、 代码文件的译码 译码的基本思想是：读文件中的编码，并与原生成的哈夫曼编码表比较，遇到相等时即取出其对应的字符存入一个新串中 char *decode(HuffmanCode HC) /代码文件codefile.txt的译码FILE *fp;char str254;char *p;static char cdn+1;int i,j,k=0,cjs;fp=fopen(codefile.txt,r);while(!feof(fp)cjs=0;for(i=0;inum & cjs=0 & !feof(fp);i+)cdi= ;cdi+1=0;cdi=fgetc(fp);for(j=1;j=num;j+)if(strcmp(HCj.bits,cd)=0)strk=HCj.ch;k+;cjs=1;break;strk=0;p=str;return p; 主函数：void main()char st254,*s,str27;int cn27;HuffmanTree HT;HuffmanCode HC;printf(输入需要编码的大写字母字符串：n);gets(st);printf(nnnnnnn);num=jsq(st,cn,str);ChuffmanTree(HT,HC,cn,str);HuffmanEncoding(HT,HC);coding(HC,st);s=decode(HC); printf(nnnnnnn);printf(译码后的字符串：n);/printf(%sn,s);printf(QWERTYUIOPLKJHGFDSAMNBVCXZPLMOKNIJBnnnnnnn);二、实验结果与分析1、实验目的、实验思路等见实验设计方案2、实验现象、数据及结果3、对实验现象、数据及观察结果的分析与讨论 从实验现象、数据及结果来看：在建立哈夫曼树时应先考虑好树的存储结构，有了存储结构后才能真正开始程序的编写，开始编写后在按着上面的程序思路写起来就简单多了 讨论：在写译码程序时出现很多错误，按着思路写下去总是会出错，译码后只会出现D，但后来经过他人帮忙才修改正确 4、结论 通过写哈夫曼译码的程序让我更一步的理解了哈夫曼树，知道了哈夫曼树的存储结构以及编写程序时需要注意的一些地方，总体来说，虽然这次写的过程中出了很多问题，但还是有很多收获，让我进一步的理解以及学会了哈夫曼树的运用，学会了使用哈夫曼树来需找带权路径最小的树5、实验总结本次实验成败之处及其原因分析本实验的失败：建树的时候出现了很多次的程序终止问题原因：对指针以及哈夫曼树不理解，不能很好的使用本实验的关键环节及改进措施做好本实验需要把握的关键环节 关键环节：1、哈夫曼树的建立 2、最小权值的选择的算法 3、编码后的译码若重做本实验，为实现预期