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

用哈夫曼树对字符串进行编码译码-1-一、设计思想程序要求：利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。将得到的一串字串译成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代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。用哈夫曼树对字符串进行编码译码-2-二、算法流程图i++;图1计算字符权值及字符种类算法是j++;str[j]=i+64;quan[j]=quantemp[i];结束i27?quantemp[i]=0?k=getstr[i]-64;quantemp[k]++(quantemp为int型数组开始值都为0)i++;i=1,j=0判断getstr[i]是否为26个大写字母开始获得输入的字符串getstr[]，i=0。i++;否否是否是说明：将的的字符串进行字符种类级每种字符出现频率的统计用哈夫曼树对字符串进行编码译码-3-图2构建哈夫曼树算法选择权值最小的两个节点将下标赋给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;i++结束是·i=num+1i=2*num-1?HT[i].weight=quan[i]i=1;(num为字符的种类)开始将所有的几点的父节点和子节点权值赋成0i=num否是否说明：利用选择排序，选择节点权值最小的两个节点，构建一个子树，将该树的根节点再放入选择区，重复该操作，直至用完所有节点完成哈夫曼数的搭建。用哈夫曼树对字符串进行编码译码-4-图3利用哈夫曼树加密算法否否是HT[c].parent0cd[--start]=(HT[p].lchild==c)?'0':'1';c=HT[c].parent;i++start=num;c=i开始i=0;cd[num]='\0';将str[i]的值依次赋给HC[i].chi=num;strcpy(HC[i].bits,&cd[start]);HC[i].len=num-start;i++结束否打开codefile.txt文件,获得字符串str指针，i=0；HC[i].ch=*str?i=num;将HC[i].bits[j]存进文件是否是否是说明：利用每个字符在哈夫曼树中的位子，得到每个字符的0、1密文编码。再将字符串按字符密文进行编译，然后存入文件夹中。用哈夫曼树对字符串进行编码译码-5-cd[i]='';cd[i+1]='\0';cd[i]=fgetc(fp);j=1;str[k]=HC[j].ch;cjs=1;k++;str[k]='\0';break;j++strcmp(HC[j].bits,cd)=0j=numi++结束开始(inum)&&(cjs==0)&&(!feof(fp)打开文件夹codefile.txt,cjs=0,i=0!feof(fp)图4解密算法说明：从文件夹中读出密文，和HC[i].bis中的密文进行比较译出字符，存入临时数组。待译码结束后，输出字符串。用哈夫曼树对字符串进行编码译码-6-三、源代码//hafuman.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includestdlib.h#includestring.h#includestdio.h#definen100//叶节点的个数小等于n#definem2*n-1//总结点的个数为m=2*n-1intnum;//定义一个全局变量用于存放字符种类个数typedefstruct//结构体用于存放树节点包括节点的父节点、左子、右子以及权值{intweight;intparent,lchild,rchild;}HTNode;typedefHTNodeHafumanTree[m+1];//重命名HTNodetypedefstruct//结构体由于存放每个字符的密文和长度{charch;charbits[10];intlen;}CodeNode;typedefCodeNodeHafumanCode[n+1];//重命名CodeNodeint_tmain(intargc,_TCHAR*argv[]){intquan[27];//声明一个数组用以存放26字符的权值chargetstr[300],str[27];//声明两个字符串数组一个用于存输入一个由于存放输入中含有的字符char*s;//声明一个char型指针用于指向字符HafumanTreeHT;//声明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);用哈夫曼树对字符串进行编码译码-7-printf(请输入要加密的字符串：\n);gets(getstr);//获得输入的字符串num=jisuanquan(getstr,quan,str);//统计字符串中含有字符种类个数//printf(%d\n,num);gjhafumantree(HT,HC,quan,str);//根据字符权值构建哈夫曼树Hafumanencode(HT,HC);//根据哈夫曼树确定每个字符的codecoding(HC,getstr);//将字符串译码存入文件夹s=decode(HC);//将暗文解码printf(解密为：\n);printf(%s\n,s);system(pause);return0;}//函数intjisuanquan(char*s,intquan[],charstr[])//计算字符串中字符权值{char*p;inti,j,k,quantemp[27];for(i=1;i27;i++)//将所有字符的权值赋成0{quantemp[i]=0;}for(p=s;*p!='\0';p++)//判断字符串是否结束{if(*p='A'&&*p='Z')//判断字符是否为26字母{k=*p-64;//看是26个字符中的哪个字符quantemp[k]++;//字符权值加1}}j=0;for(i=1,j=0;i27;i++){if(quantemp[i]!=0){j++;//用于统计字符种类个数str[j]=i+64;//str按字母表顺序存储出现过的字符quan[j]=quantemp[i];}}returnj;}用哈夫曼树对字符串进行编码译码-8-voidselect(HafumanTreeHT,intk,int*s1,int*s2)//选择权值最小的两个{inti,j;intmin1=9999;//声明一个int类型的数值min1，赋个较大的输给它for(i=1;i=k;i++)//选择权值最小的一个节点（且该节点无父节点）{if((HT[i].weightmin1)&&(HT[i].parent==0)){j=i;min1=HT[i].weight;}}*s1=j;min1=9999;for(i=1;i=k;i++){if((HT[i].weightmin1)&&(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;i2*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++)//将num个字符的权值赋给num叶节点{HT[i].weight=quan[i];}for(i=1;i=num;i++)//将num个字符赋给codenode{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;//父节点的权值为子节点相加（父节点继续放入选择区）}}用哈夫曼树对字符串进行编码译码-9-voidHafumanencode(HafumanTreeHT,HafumanCodeHC){intc,p,i;charcd[n];//临时数组用于记录字符在哈夫曼树的位置intstart;cd[num]='\0';//给cd赋个结束符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]);//将得到的0、1字串存入结构体HCprintf(%c:%s\n,HC[i].ch,HC[i].bits);HC[i].len=num-start;//求每个字符0、1编码长度}}voidcoding(HafumanCodeHC,char*str)//根据哈夫曼树确定每个字符的0、1代码code{inti,j;FILE*fp;//声明一个文件夹指针fp=fopen(codefile.txt,w);//打开文件夹codefileprintf(密文为：\n);while(*str)//字符串未结束时{for(