哈夫曼编码与译码报告

1、用哈夫曼树对字符串进行编码译码一、设计思想程序要求：利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。将得到的一串字串译成0、1编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解码。实现方法：输入一串字符，要求字符的区间为大写的26个英文字母， 将获得的串字符用计算权值的函数（jsquanzhi()）进行字符统计，统计出现的字符种数以及每种字符出现的次数， 将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC，利用HT（节点）权值的大小建立哈夫曼树，首先用选择函数select（）函数选择两个权值最小的字符作为叶子节点，创建一个新的节

2、点作为这两个叶节点的父节点，被选中的节点给他的HTi.parent赋值是他下次不再被选中，父节点的权值为，子节点的权值之和。然后将该将父节点放入筛选区中，再进行选择（被选过的不再被使用），直到所有的节点都被使用，这样一个哈夫曼树就被建立了。根据每个字符在哈夫曼书中的位置来编译每个字符的0、1密文代码，从叶节点判断该叶节点是其父节点的左右字左字为0，右子为1，在判断父节点是上级父节点的左右子直至根节点，将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins数组。重新一个一个字符的读取输入的字符串，按照字符出现的顺序将它转为0、1代码并存到一个txt文件夹中去。解码时从文件夹中，一个一

3、个字符的读出那串0、1代码赋给一个临时字符串cd，用该字符串与每个字符的HCi.bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。二、算法流程图 说明：将的的字符串进行字符种类级每种字符出现频率的统计i+;图1计算字符权值及字符种类算法是j+;strj=i+64; quanj=quantempi;结束i<27?quantempi=0?k=getstri-64;quantempk+( quantemp为int型数组开始值都为0)i+;i=1,

4、j=0判断getstri是否为26个大写字母开始获得输入的字符串getstr，i=0。i+;否否是否是说明：利用选择排序，选择节点权值最小的两个节点，构建一个子树，将该树的根节点再放入选择区，重复该操作，直至用完所有节点完成哈夫曼数的搭建。图2 构建哈夫曼树算法选择权值最小的两个节点将下标赋给s1,s2.HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;i+结束是·i=num+1i<=2*num-1?HTi.weight=quanii=1;(num

5、为字符的种类)开始将所有的几点的父节点和子节点权值赋成0i<=num否是否说明：利用每个字符在哈夫曼树中的位子，得到每个字符的0、1密文编码。再将字符串按字符密文进行编译，然后存入文件夹中。图3 利用哈夫曼树加密算法否否是HTc.parent>0cd-start=(HTp.lchild=c)?'0':'1' c= HTc.parent;i+start=num; c=i开始i=0;cdnum='0'将stri的值依次赋给HCi.chi<=num;strcpy(HCi.bits,&cdstart); HCi.len=num-

6、start;i+结束否打开codefile.txt文件,获得字符串str指针，i=0；HCi.ch=*str?i<=num;将HCi.bitsj存进文件是否是否是说明：从文件夹中读出密文，和HCi.bis中的密文进行比较译出字符，存入临时数组。待译码结束后，输出字符串。strk=HCj.ch;cjs=1;k+;strk='0'break;j+strcmp(HCj.bits,cd)=0j<=numi+结束开始(i<num)&&(cjs=0)&&(!feof(fp)打开文件夹codefile.txt, cjs=0, i=0!feof

7、(fp)图4 解密算法cdi=''cdi+1='0'cdi=fgetc(fp);j=1;三、源代码/ hafuman.cpp : 定义控制台应用程序的入口点。/#include "stdafx.h"#include "stdlib.h"#include "string.h"#include "stdio.h"#define n 100/叶节点的个数小等于n#define m 2*n-1/总结点的个数为m=2*n-1int num;/定义一个全局变量用于存放字符种类个数typedef

8、struct/结构体用于存放树节点包括节点的父节点、左子、右子以及权值 int weight;int parent,lchild,rchild;HTNode;typedef HTNode HafumanTreem+1;/重命名HTNodetypedef struct/结构体由于存放每个字符的密文和长度char ch;char bits10;int len;CodeNode;typedef CodeNode HafumanCoden+1;/重命名CodeNodeint _tmain(int argc, _TCHAR* argv)int quan27;/声明一个数组用以存放26字符的权值char

9、getstr300,str27;/声明两个字符串数组一个用于存输入一个由于存放输入中含有的字符char *s;/声明一个char型指针用于指向字符HafumanTree HT;/声明m+1个树节点HafumanCode HC;/声明n+1个codeint jisuanquan(char *s,int quan,char str);/声明需要调用的函数void gjhafumantree(HafumanTree HT,HafumanCode HC,int quan,char str);void Hafumanencode(HafumanTree HT,HafumanCode HC);void c

10、oding(HafumanCode HC,char *str);char *decode(HafumanCode HC);printf("请输入要加密的字符串：n");gets(getstr);/获得输入的字符串num=jisuanquan(getstr,quan,str);/统计字符串中含有字符种类个数/printf("%dn",num);gjhafumantree(HT,HC,quan,str);/根据字符权值构建哈夫曼树Hafumanencode(HT,HC);/根据哈夫曼树确定每个字符的codecoding(HC,getstr);/将字符串译码存

11、入文件夹s=decode(HC);/将暗文解码printf("解密为：n");printf("%sn",s);system("pause");return 0;/函数int jisuanquan(char *s,int quan,char str)/计算字符串中字符权值char *p; int i,j,k,quantemp27; for(i=1;i<27;i+)/将所有字符的权值赋成0 quantempi=0; for(p=s;*p!='0'p+)/判断字符串是否结束 if(*p>='A'&

12、amp;&*p<='Z')/判断字符是否为26字母k=*p-64;/看是26个字符中的哪个字符quantempk+;/字符权值加1 j=0; for(i=1,j=0;i<27;i+)if(quantempi!=0)j+;/用于统计字符种类个数strj=i+64;/str按字母表顺序存储出现过的字符quanj=quantempi; return j;void select(HafumanTree HT,int k,int *s1,int*s2)/选择权值最小的两个int i,j; int min1=9999;/声明一个int类型的数值min1，赋个较大的输给它

13、 for(i=1;i<=k;i+)/选择权值最小的一个节点（且该节点无父节点） if(HTi.weight<min1)&&(HTi.parent=0) j=i;min1=HTi.weight; *s1=j; min1=9999; for(i=1;i<=k;i+) if(HTi.weight<min1)&&(HTi.parent=0)&&(i!=*s1)/选择权值最小的一个节点（且该节点无父节点） j=i;min1=HTi.weight; *s2=j;void gjhafumantree(HafumanTree HT,Haf

14、umanCode HC,int quan,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;i<=num;i+)/将num个字符的权值赋给num叶节点 HTi.weight=quani; for(i=1;i<=num;i+)/将num个字符赋给codenode HCi.ch=stri; i=1; while(i<=num) printf("=%c=%d=n"

15、,HCi.ch,quani);i+;/输出每个字符的及其权值 for(i=num+1;i<=2*num-1;i+) select(HT,i-1,&s1,&s2);/选择两个权值最小的叶节点HTs1.parent=i;HTs2.parent=i;/两个节点指向同一父节点 HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/父节点的权值为子节点相加（父节点继续放入选择区） void Hafumanencode(HafumanTree HT,HafumanCode HC)int c,p,i;char c

16、dn;/临时数组用于记录字符在哈夫曼树的位置int start;cdnum='0'/给cd赋个结束符for(i=1;i<=num;i+)start=num; c=i; while(p=HTc.parent)>0)/根据节点是其父节点的左右子来记录它的位置 cd-start=(HTp.lchild=c)?'0':'1' c=p;/将父节点转为子节点 strcpy(HCi.bits,&cdstart);/将得到的0、1字串存入结构体HC printf("%c:%sn",HCi.ch,HCi.bits); HCi

17、.len=num-start;/求每个字符0、1编码长度void coding(HafumanCode HC,char *str)/根据哈夫曼树确定每个字符的0、1代码codeint i,j;FILE *fp;/声明一个文件夹指针fp=fopen("codefile.txt","w");/打开文件夹codefileprintf("密文为：n");while(*str)/字符串未结束时for(i=1;i<=num;i+)if(HCi.ch=*str)/判断字符是否在Codenode中存在for(j=0;j<HCi.len;j

18、+)/将codenode中该字符的1、0代码存入文件夹 fputc(HCi.bitsj,fp);printf("%s",HCi.bits);break; str+;/字符后移printf("n");fclose(fp);char *decode(HafumanCode HC)FILE *fp;char tempstr9999;char *p;static char cdn+1;/char型数组用于存放从文件夹中读取的1、0代码int i,j,k=0,jsjs;fp=fopen("codefile.txt","r")

19、;while(!feof(fp)/当文件夹读取没有结束jsjs=0;/判读一个字符是否译码结束for(i=0;(i<num)&&(jsjs=0)&&(!feof(fp);i+)/当一个字符未译完并且文件未读取结束 cdi=' 'cdi+1='0'/让cd赋成空格cdi=fgetc(fp);/读取文件夹中的一个字符for(j=1;j<=num;j+) if(strcmp(HCj.bits,cd)=0)/看cd的字符串是否等于Codenode中的某个密文tempstrk=HCj.ch;jsjs=1;printf("

20、;=%s=",HCj.bits);k+;break;/将译出的字符赋给临时字符串tempstr,标记一个字符译码结束jsjs赋1，跳出循环tempstrk='0'/赋给临时字符串一个结束标志p=tempstr;/char型指针指向临时字符串return p;四、运行结果图5 哈夫曼编码与译码运行结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l 当我写完程序，输入一段字符串让程序进行译码和解码是出现了一个问题，译出的结果不是想要的结果，但结果又有一定规律，就是结果中的字符都在明文中出现过，可是字符数量明显比明文中的要少很多。首先我认

21、为为题可能出现在我将明文加密后的存储阶段，于是我在程序将0、1代码存入codeflie.txt文件前，先将临时存储字符串数组内容输出，结果发现没有问题，于是我又在，译码阶段将从codeflie.txt读出的内容逐字输出发现结果和存入的一样。输入和输出都一样。问题不是出现在存储上，于是我想到问题可能出现在，我将0、1编码转成明文的时。于是我认真的看了看我的decode函数，添加了些辅助输出，发现有写编码不是原先的一个字符的译文，有的是两个字符的译文译成了一个字符。于是我又输进一段字符将暗文带入函数计算，发现问题出在但一出一个字符后，我的一个循环并没有终止，而是继续向cd数组中添加，1和0；直至cd的长度超过num时才结束，而下次调用该循环式，前面会有几个1、0没有被编译。所以导致了以上的错误，于是我在函数中声明了一个变量jsjs（计算结束），用它在译完一个字符是让函数跳出循环。于是问题得到了解决。l 第二个问题再之前就出现了只不过他和前一个问题没有多大的联系，就是在输出明文结果是字符串的结尾变成了: 烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫。一开始我认为他和第一个问题是一个问题，是存储或者译码出错了，但是但第一个问题解决后他依然存在。于是我才确定