哈夫曼编码与译码.docx

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

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

3、出现的顺序将它转为 0、1 代码并存到一个 txt 文件夹中去。解码时从文件夹中，一个一个字符的读出那串 0、1 代码赋给一个临时字符串 cd ，用该字符串与每个字符的 HCi.bins 密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组 tempstr 中，清空临时字符串继续读取 0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。- 1 -用哈夫曼树对字符串进行编码译码二、算法流程图开始获得输入的字符串 getstr ， i=0 。判断 getstri 是否 i+; 为 26 个大写字母 否是k=getstri-64;quantempk+(

4、 quantemp 为 int 型数组开始值都为 0)i+;i=1,j=0否i27?是结束 是 quantempi=i+;0?否j+;strj=i+64;quanj=quantempi;图 1 计算字符权值及字符种类算法说明 : 将的的字符串进行字符种类级每种字符出现频率的统计- 2 -用哈夫曼树对字符串进行编码译码开始将所有的几点的父节点和子节点权值赋成 0i=1;(num 为字符的种类 )HTi.weight=quani i=num是 否i=num+1否i=2*num-1?是结束 ? 选择权值最小的两个节点将下标赋给 s1,s2.HTs1.parent=i;HTs2.parent=i;HT

5、i.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;i+图 2 构建哈夫曼树算法说明 : 利用选择排序，选择节点权值最小的两个节点，构建一个子树，将该树的根节点再放入选择区，重复该操作，直至用完所有节点完成哈夫曼数的搭建。- 3 -用哈夫曼树对字符串进行编码译码开始将 stri 的值依次赋给 HCi.ch i=0;cdnum=0;i0 否 &cdstart); 是HCi.len=num-start; cd-start=(HTp.lchild=c)?0:1;c= HTc.parent; 打开 codefile.txt 文件 ,

6、 获得字符串 str 指针， i=0;否i=num;是结束否 否HCi.ch=*str? i+是将 HCi.bitsj 存进文件图 3 利用哈夫曼树加密算法说明 : 利用每个字符在哈夫曼树中的位子，得到每个字符的 0、1 密文编码。再将字符串按字符密文进行编译，然后存入文件夹中。- 4 -用哈夫曼树对字符串进行编码译码开始cjs=0, i=0 打开文件夹 codefile.txt,!feof(fp)结束(inum)&(cjs=0)&(!feof(fp)cdi=;cdi+1=0;cdi=fgetc(fp);j=1;j=num i+j+strcmp(HCj.bits,cd)=0strk=HCj.c

7、h;cjs=1;k+;strk=0;break;图 4 解密算法说明 : 从文件夹中读出密文，和 HCi.bis 中的密文进行比较译出字符，存入临时数组。待译码结束后，输出字符串。- 5 -用哈夫曼树对字符串进行编码译码三、源代码/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-1 int num; / 定义一个全局变量用于存放字符种类个

8、数typedef 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; /声明一个数组

9、用以存放26 字符的权值char 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(Ha

10、fumanTree HT,HafumanCode HC); voidcoding(HafumanCode HC,char *str); char *decode(HafumanCode HC); - 6 -用哈夫曼树对字符串进行编码译码printf( 请输入要加密的字符串 :n);gets(getstr); / 获得输入的字符串 num=jisuanquan(getstr,quan,str); /统计字符串中含有字符种类个数/printf(%dn,num);gjhafumantree(HT,HC,quan,str); /根据字符权值构建哈夫曼树Hafumanencode(HT,HC); /根据

11、哈夫曼树确定每个字符的codecoding(HC,getstr); /将字符串译码存入文件夹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=A&*p=Z) /判断字符是否为26 字母k=*p-64; / 看是 26个字符中的哪个字符quantempk+; / 字符权值加 1j=0;for(i=1,j=0;i2

12、7;i+)if(quantempi!=0)j+; / 用于统计字符种类个数strj=i+64; /str 按字母表顺序存储出现过的字符quanj=quantempi;return j;- 7 -用哈夫曼树对字符串进行编码译码void select(HafumanTree HT,int k,int *s1,int*s2) / 选择权值最小的两个 int i,j;int min1=9999; / 声明一个 int 类型的数值 min1，赋个较大的输给它for(i=1;i=k;i+) / 选择权值最小的一个节点 ( 且该节点无父节点 )if(HTi.weightmin1)&(HTi.parent=0

13、)j=i;min1=HTi.weight;*s1=j;min1=9999;for(i=1;i=k;i+)if(HTi.weightmin1)&(HTi.parent=0)&(i!=*s1)/选择权值最小的一个节点 ( 且该节点无父节点 ) j=i;min1=HTi.weight;*s2=j;void gjhafumantree(HafumanTree HT,HafumanCode HC,int quan,charstr) / 构建哈夫曼树 int i,s1,s2;for(i=1;i2*num-1;i+) / 将所有的节点赋空HTi.lchild=0;HTi.rchild=0;HTi.paren

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

15、ld=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/父节点的权值为子节点相加 ( 父节点继续放入选择区 )- 8 -用哈夫曼树对字符串进行编码译码void Hafumanencode(HafumanTree HT,HafumanCode HC)int c,p,i;char cdn; / 临时数组用于记录字符在哈夫曼树的位置 int start;cdnum=0; / 给 cd 赋个结束符for(i=1;i0) / 根据节点是其父节点的左右子来记录它的位置cd-start=(HTp.lchild=c)?0:1;c=p; / 将父节点转为子

16、节点strcpy(HCi.bits,&cdstart); /将得到的0、1字串存入结构体HCprintf(%c:%sn,HCi.ch,HCi.bits);HCi.len=num-start; /求每个字符0、1 编码长度void coding(HafumanCode HC,char *str) / 根据哈夫曼树确定每个字符的0、1 代码code int i,j;FILE *fp; /声明一个文件夹指针fp=fopen(codefile.txt,w); /打开文件夹codefile printf(密文为 :n);while(*str) / 字符串未结束时for(i=1;i=num;i+)if(H

17、Ci.ch=*str) /判断字符是否在Codenode中存在for(j=0;jHCi.len;j+) /将 codenode 中该字符的1、 0 代码存入文件夹fputc(HCi.bitsj,fp);printf(%s,HCi.bits);break;str+; /printf(n);fclose(fp);字符后移- 9 -用哈夫曼树对字符串进行编码译码char *decode(HafumanCode HC)FILE *fp;char tempstr9999;char *p;static char cdn+1; /char 型数组用于存放从文件夹中读取的 1、0 代码int i,j,k=0,

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

19、s);k+;break;/将译出的字符赋给临时字符串 tempstr, 标记一个字符译码结束 jsjs 赋1，跳出循环tempstrk=0; / 赋给临时字符串一个结束标志 p=tempstr; /char 型指针指向临时字符串return p;-10-用哈夫曼树对字符串进行编码译码四、运行结果图 5 哈夫曼编码与译码运行结果图-11-用哈夫曼树对字符串进行编码译码五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列 :,当我写完程序，输入一段字符串让程序进行译码和解码是出现了一个问题，译出的结果不是想要的结果，但结果又有一定规律，就是结果中的字符都在明文中出现过，可是

20、字符数量明显比明文中的要少很多。首先我认为为题可能出现在我将明文加密后的存储阶段，于是我在程序将 0、 1代码存入 codeflie.txt 文件前，先将临时存储字符串数组内容输出，结果发现没有问题，于是我又在，译码阶段将从 codeflie.txt 读出的内容逐字输出发现结果和存入的一样。输入和输出都一样。问题不是出现在存储上，于是我想到问题可能出现在，我将 0、1 编码转成明文的时。于是我认真的看了看我的 decode 函数，添加了些辅助输出，发现有写编码不是原先的一个字符的译文，有的是两个字符的译文译成了一个字符。于是我又输进一段字符将暗文带入函数计算，发现问题出在但一出一个字符后，我的

21、一个循环并没有终止，而是继续向cd数组中添加，1 和0;直至cd的长度超过num时才结束，而下次调用该循环式，前面会有几个1、0 没有被编译。所以导致了以上的错误，于是我在函数中声明了一个变量jsjs(计算结束 ) ，用它在译完一个字符是让函数跳出循环。于是问题得到了解决。,第二个问题再之前就出现了只不过他和前一个问题没有多大的联系，就是在输出明文结果是字符串的结尾变成了 : 烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫 。一开始我认为他和第一个问题是一个问题，是存储或者译码出错了，但是但第一个问题解决后他依然存在。于是我才确定这是另外的一个问题。根据以晚的经验出现这种情况的原因就几种，存储出错或者输出

22、形式不对，或者输出的位置不对。而第二种情况可以排除，于是我前后看了看程序中的数组的存储和输出。发现存储形式没有问题，于是我想到了第一个问题解决后输出的结果是在正确解码后面加一串乱码。会不会是输出了一段没有赋值区域内的内容，于是我看了看存储输出内容的临时数组发现我声明时声明的长度为 300，而一般用不了那么多，而我输出是将str 按照字符串形式输出的也就是说，输出结果的前一段时我要的内容而后一段是系统原先的东西，但是也跟着输出了，于是我在 str 中添加了 0结束标志。这样就不会输出我不要的部分了。后来但我输入更长的一段字符串是后没会出现一个字的汉字，于是我又将 str 的长度加长，是它尽可能存

23、储跟唱的字符串。-12-用哈夫曼树对字符串进行编码译码六、心得体会通过对上面程序的编写让我积累了一些编程的经验，比如在你编写代码是首先你应在大脑内先构思好你的程序，并在纸上写下你的思路很实现步骤，而不是急于动手编写。有些事没想好就急于容易出现一些逻辑上的错误，最后实现不了又必须重来。其次是数据类型的处理，不能将字符型数据存其他类型的数据，计算机是不识别的，写程序是要严格规范自己对不同类型数据存储和使用，还有就是当一个数据不再被使用时或下次你要用它来存放其他数值时要记得提前赋空，以免数据出错。还有就是在程序中如果你要重复某些步骤时你可以考虑在主程序外建立一个函数来实现这些步骤，这样在主程序中通过调用这个函数来实现这些步骤，这样可以避免编写同样的代码，并简化你的程序代码。除此之外就是大括号 的一定要对其，不然一旦代码长度变长，会出现一堆的括号，你可能看的眼花缭乱不知道哪个与哪个是一对，最后影响你的代码检查。-13-