哈夫曼编码与译码报告要点

---、设计思想程序要求：利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。将得到的一串字串译成0、1编码后存到一个文件夹中，然后再从这个文件夹中读出这串编码进行解码。实现方法：输入一串字符，要求字符的区间为大写的26个英文字母，将获得的串字符用计算权值的函数（jsquanzhi（））进行字符统计，统计出现的字符种数以及每种字符出现的次数，将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC，利用HT（节点）权值的大小建立哈夫曼树，首先用选择函数select（）函数选择两个权值最小的字符作为叶子节点，创建一个新的节点作为这两个叶节点的父节点，被选中的节点给他的HT[i].parent赋值是他下次不再被选中，父节点的权值为，子节点的权值之和。然后将该将父节点放入筛选区中，再进行选择（被选过的不再被使用），直到所有的节点都被使用，这样一个哈夫曼树就被建立了。根据每个字符在哈夫曼书中的位置来编译每个字符的0、1密文代码，从叶节点判断该叶节点是其父节点的左右字左字为‘0’，右子为‘1’，在判断父节点是上级父节点的左右子直至根节点，将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins口数组。重新一个一个字符的读取输入的字符串，按照字符出现的顺序将它转为0、1代码并存到一个txt文件夹中去。解码时从文件夹中，一个一个字符的读出那串0、1代码赋给一个临时字符串cd口，用该字符串与每个字符的HC[i].bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr口中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。二、算法流程图图1计算字符权值及字符种类算法说明：将的的字符串进行字符种类级每种字符出现频率的统计图2构建哈夫曼树算法说明：利用选择排序，选择节点权值最小的两个节点，构建一个子树，将该树的根节点再放入选择区，重复该操作，直至用完所有节点完成哈夫曼数的搭建。

图3利用哈夫曼树加密算法说明：利用每个字符在哈夫曼树中的位子，得到每个字符的0、1密文编码。再将字符串按字符密文进行编译，然后存入文件夹中。图4解密算法说明：从文件夹中读出密文，和HC[i].bis中的密文进行比较译出字符，存入临时数组。待译码结束后，输出字符串。#definen100#definen100#definem2*n-1intnum;〃重命名HTNode//结构体由于存放每个字符的密文和长度〃重命名CodeNode//声明一个数组用以存放26字符的权值型指针用于指向字符三、源代码//hafuman.cpp:定义控制台应用程序的入口点。//#include"stdafx.h"#include"stdlib.h"#include"string.h"#include"stdio.h"〃叶节点的个数小等于n〃总结点的个数为m=2*n-1//定义一个全局变量用于存放字符种类个数//结构体用于存放树节点包括节点的父节点、左子、右子以及权值//结构体用于存放树节点包括节点的父节点、左子、右子以及权值{intweight;intparent,lchild,rchild;}HTNode;typedefHTNodeHafumanTree[m+1];typedefstruct{charch;charbits[10];intlen;}CodeNode;typedefCodeNodeHafumanCode[n+1];int_tmain(intargc,_TCHAR*argv[]){intquan[27];chargetstr[300],str[27];//声明两个字符串数组一个用于存输入一个由于存放输入中含有的字符char*s;//声明一个charHafumanTreeHT;//声明m+1个树节点HafumanCodeHC;//声明n+1个codeintjisuanquan(char*s,intquan[],charstr[]);//声明需要调用的函数voidgjhafumantree(HafumanTreeHT,HafumanCodeHC,intquan[],charstr[]);voidHafumanencode(HafumanTreeHT,HafumanCodeHC);voidcoding(HafumanCodeHC,char*str);char*decode(HafumanCodeHC);printf("请输入要加密的字符串:\n");gets(getstr);num=jisuanquan(getstr,quan,str);//printf("%d\n",num);gjhafumantree(HT,HC,quan,str);Hafumanencode(HT,HC);coding(HC,getstr);s=decode(HC);printf("解密为:\n");printf("%s\n",s);system("pause");return0;}

//获得输入的字符串//统计字符串中含有字符种类个数//根据字符权值构建哈夫曼树〃根据哈夫曼树确定每个字符的code//将字符串译码存入文件夹//将暗文解码//函数intjisuanquan(char*s,intquan[],charstr[]){char*p;inti,j,k,quantemp[27];for(i=1;i<27;i++){quantemp[i]=0;}for(p=s;*p!='\0';p++){if(*p>='A'&&*p<='Z'){k=*p-64;quantemp[k]++;}}j=0;for(i=1,j=0;i<27;i++){if(quantemp[i]!=0){j++;str[j]=i+64;quan[j]=quantemp[i];}}returnj;}//计算字符串中字符权值//将所有字符的权值赋成0//判断字符串是否结束//判断字符是否为26字母//看是26个字符中的哪个字符//字符权值加1//用于统计字符种类个数//str按字母表顺序存储出现过的字符////将所有的节点赋空//将num个字符的权值赋给num叶节点//将num个字符赋给codenode//输出每个字符的及其权值//选择两个权值最小的叶节点//两个节点指向同一父节点voidselect(HafumanTreeHT,intk,int*s1,int*s2)//选择权值最小的两个{inti,j;intmin1=9999;〃声明一个int类型的数值mini,赋个较大的输给它for(i=1;i<=k;i++)//选择权值最小的一个节点(且该节点无父节点){if((HT[i].weight<min1)&&(HT[i].parent==0)){j=i;min1=HT[i].weight;}}*s1=j;min1=9999;for(i=1;i<=k;i++){if((HT[i].weight<min1)&&(HT[i].parent==0)&&(i!=*s1))//选择权值最小的一个节点(且该节点无父节点){j=i;min1=HT[i].weight;}}*s2=j;}voidgjhafumantree(HafumanTreeHT,HafumanCodeHC,intquan[],charstr[])//构建哈夫曼树{inti,s1,s2;for(i=1;i<2*num-1;i++){HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;HT[i].weight=0;}for(i=1;i<=num;i++){HT[i].weight=quan[i];}for(i=1;i<=num;i++){HC[i].ch=str[i];}i=1;while(i<=num){printf("===%c===%d===\n",HC[i].ch,quan[i]);i++;}for(i=num+1;i<=2*num-1;i++){select(HT,i-1,&s1,&s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//父节点的权值为子节点相加（父节点继续放入选择区）

voidHafumanencode(HafumanTreeHT,HafumanCodeHC){intc,p,i;charcd[n];intstart;charcd[n];intstart;cd[num]='\0';for(i=1;i<=num;i++){start=num;c=i;while((p=HT[c].parent)>0){cd[--start]=(HT[p].lchild==c)?'0':'1';c=p;}strcpy(HC[i].bits,&cd[start]);printf("%c:%s\n",HC[i].ch,HC[i].bits);HC[i].len=num-start;}}//临时数组用于记录字符在哈夫曼树的位置〃给cd赋个结束符//根据节点是其父节点的左右子来记录它的位置//将父节点转为子节点〃将得到的0、1字串存入结构体HC//求每个字符0、1编码长度voidcoding(HafumanCodeHC,char*str){inti,j;FILE*fp;fp=fopen("codefile.txt","w");printfvoidcoding(HafumanCodeHC,char*str){inti,j;FILE*fp;fp=fopen("codefile.txt","w");printf("密文为:\n");while(*str){for(i=1;i<=num;i++){if(HC[i].ch==*str){for(j=0;j<HC[i].len;j++){fputc(HC[i].bits[j],fp);}printf("%s",HC[i].bits);break;〃根据哈夫曼树确定每个字符的0、1代码code//声明一个文件夹指针〃打开文件夹codefile//字符串未结束时〃判断字符是否在Codenode中存在〃将codenode中该字符的1、0代码存入文件夹}}str++;//字符后移}printf("\n");fclose(fp);}char*decode(HafumanCodeHC){FILE*fp;chartempstr[9999];char*p;staticcharcd[n+1];char*decode(HafumanCodeHC){FILE*fp;chartempstr[9999];char*p;staticcharcd[n+1];inti,j,k=0,jsjs;fp=fopen("codefile.txt","r");//char型数组用于存放从文件夹中读取的1、0代码while(!feof(fp)){jsjs=0;for(i=0;(i<num)&&(jsjs==0)&&(!feof(fp));i++){cd[i]='';cd[i+1]='\0';cd[i]=fgetc(fp);//当文件夹读取没有结束//判读一个字符是否译码结束//当一个字符未译完并且文件未读取结束〃让cd口赋成空格//读取文件夹中的一个字符for(j=1;j<=num;j++){if(strcmp(HC[j].bits,cd)==0)〃看cd口的字符串是否等于Codenode中的某个密文{tempstr[k]=HC[j].ch;jsjs=1;printf("=%s=",HC[j].bits);k++;break;}〃将译出的字符赋给临时字符串tempstr口，标记一个字符译码结束jsjs赋1,跳出循环}}}tempstr[k]='\0';//赋给临时字符串一个结束标志p=tempstr;//char型指针指向临时字符串returnp;}四、运行结果>HI:\Users\Sen\documerts\visualstudio2010\Projects\hafuman\Debug\hafuman.eMe情输入要加密的字符串：JKDSFHGKJDHGKFJDHFKJHKDJSHBKJDFKJHKDJSHFKJDHKJHKJDSFHGEURVUBCZ输入密密文氐其权宿：C：101000D：100E：101001F：010G：10111H：110J:lllK：00R：101010s：0111U：1010ilU：101100V：101101密文为：11100100011101011010111001111001101011100010111100110010001111100010011101111100110100111100010001111100010011101111100100011110011000111110001111000111010110101111010011011001010101011011010110110110100001100解密为：JKDSFHGKJDHGKFJDHFKJHKDJSHBKJDFKJHKDJSHFKJDHKJHKJDSFHGEHRYUBCZ请按任意键继续...・图5哈夫曼编码与译码运行结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：当我写完程序，输入一段字符串让程序进行译码和解码是出现了一个问题，译出的结果不是想要的结果，但结果又有一定规律，就是结果中的字符都在明文中出现过，可是字符数量明显比明文中的要少很多。首先我认为为题可能出现在我将明文加密后的存储阶段，于是我在程序将0、1代码存入codeflie.txt文件前，先将临时存储字符串数组内容输出，结果发现没有问题，于是我又在，译码阶段将从codeflie.txt读出的内容逐字输出发现结果和存入的一样。输入和输出都一样。问题不是出现在存储上，于是我想到问题可能出现在，我将0、1编码转成明文的时。于是我认真的看了看我的decode函数，添加了些辅助输出，发现有写编码不是原先的一个字符的译文，有的是两个字符的译文译成了一个字符。于是我又输进一段字符将暗文带入函数计算，发现问题出在但一出一个字符后，我的一个循环并没有终止，而是继续向cd口数组中添加，1和0；直至cd口的长度超过num时才结束，而下次调用该循环式，前面会有几个1、0没有被编译。所以导致了以上的错误，于是我在函数中声明了一个变量jsjs（计算结束），用它在译完一个字符是让函数跳出循环。于是问题得到了解决。第二个问题再之前就出现了只不过他和前一个问题没有多大的联系，就是在输出明文结果是字符串的结尾变成了:烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫…………。一开始我认为他和第一个问题是一个问题，是存储或者译码出错了，但是但第一个问题解决后他依然存在。于是我才确定这是另外的一个问题。根据以晚的经验出现这种情况的原因就几种，存储