哈夫曼编码步骤

哈夫曼编码步骤：一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。/*-------------------------------------------------------------------------*Name:哈夫曼编码源代码。*Date:2011.04.16*Author:JeffreyHill+Jezze(解码部分)*在Win-TC下测试通过*实现过程：着先通过HuffmanTree()函数构造哈夫曼树，然后在主函数main()中*自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在*父结点左侧，则置码为0,若在右侧,则置码为1。最后输出生成的编码。*------------------------------------------------------------------------*/#includestdio.h#includestdlib.h#defineMAXBIT100#defineMAXVALUE10000#defineMAXLEAF30#defineMAXNODEMAXLEAF*2-1typedefstruct{intbit[MAXBIT];intstart;}HCodeType;/*编码结构体*/typedefstruct{intweight;intparent;intlchild;intrchild;intvalue;}HNodeType;/*结点结构体*//*构造一颗哈夫曼树*/voidHuffmanTree(HNodeTypeHuffNode[MAXNODE],intn){/*i、j：循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/inti,j,m1,m2,x1,x2;/*初始化存放哈夫曼树数组HuffNode[]中的结点*/for(i=0;i2*n-1;i++){HuffNode[i].weight=0;//权值HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].value=i;//实际值，可根据情况替换为字母}/*endfor*//*输入n个叶子结点的权值*/for(i=0;in;i++){printf(Pleaseinputweightofleafnode%d:\n,i);scanf(%d,&HuffNode[i].weight);}/*endfor*//*循环构造Huffman树*/for(i=0;in-1;i++){m1=m2=MAXVALUE;/*m1、m2中存放两个无父结点且结点权值最小的两个结点*/x1=x2=0;/*找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树*/for(j=0;jn+i;j++){if(HuffNode[j].weightm1&&HuffNode[j].parent==-1){m2=m1;x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].weightm2&&HuffNode[j].parent==-1){m2=HuffNode[j].weight;x2=j;}}/*endfor*//*设置找到的两个子结点x1、x2的父结点信息*/HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;printf(x1.weightandx2.weightinround%d:%d,%d\n,i+1,HuffNode[x1].weight,HuffNode[x2].weight);/*用于测试*/printf(\n);}/*endfor*//*for(i=0;in+2;i++){printf(Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n,HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);}*///测试}/*endHuffmanTree*///解码voiddecodeing(charstring[],HNodeTypeBuf[],intNum){inti,tmp=0,code[1024];intm=2*Num-1;char*nump;charnum[1024]for(i=0;istrlen(string);i++){if(string[i]=='0')num[i]=0;elsenum[i]=1;}i=0;nump=&num[0];while(nump(&num[strlen(string)])){tmp=m-1;while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1)){if(*nump==0){tmp=Buf[tmp].lchild;}elsetmp=Buf[tmp].rchild;nump++;}printf(%d,Buf[tmp].value);}}intmain(void){HNodeTypeHuffNode[MAXNODE];/*定义一个结点结构体数组*/HCodeTypeHuffCode[MAXLEAF],cd;/*定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/inti,j,c,p,n;charpp[100];printf(Pleaseinputn:\n);scanf(%d,&n);HuffmanTree(HuffNode,n);for(i=0;in;i++){cd.start=n-1;c=i;p=HuffNode[c].parent;while(p!=-1)/*父结点存在*/{if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;/*求编码的低一位*/c=p;p=HuffNode[c].parent;/*设置下一循环条件*}/*endwhile*//*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/for(j=cd.start+1;jn;j++){HuffCode[i].bit[j]=cd.bit[j];}HuffCode[i].start=cd.start;}/*endfor*//*输出已保存好的所有存在编码的哈夫曼编码*/for(i=0;in;i++){printf(%d'sHuffmancodeis:,i);for(j=HuffCode[i].start+1;jn;j++){printf(%d,HuffCode[i].bit[j]);}printf(start:%d,HuffCode[i].start);printf(\n);}/*for(i=0;in;i++){for(j=0;jn;j++){printf(%d,HuffCode[i].bit[j]);}printf(\n);}*/printf(Decoding?PleaseEntercode:\n);scanf(%s,&pp);decodeing(pp,HuffNode,n);getch();return0;}解码#includestring.h#includestdio.h#defineMAXVALUE1000/*定义最大权值*/#defineMAXLEAF30/*定义哈夫曼树叶结点个数*/#defineMAXNODEMAXLEAF*2-1#defineMAXBIT30/*定义哈夫曼编码的最大长度*/typedefstruct{intbit[MAXBIT];intstart;}HCODETYPE;typedefstruct{intweight;intparent;intlchild;intrchild;}HNODETYPE;char*getcode1(char*s1,char*s2,char*s3)/*首先去掉电文中的空格*/{chartemp[128]=,*p,*q;p=s1;while((q=strstr(p,s2))!=NULL){*q='\0';strcat(temp,p);strcat(temp,s3);p=q+strlen(s2);}strcat(temp,p);strcpy(s1,temp);returns1;}/*再去掉重复出现的字符（即压缩电文），提取哈夫曼树叶结点*/char*getcode(char*s1){chars2[26],s5[26];chartemp[200]=,*p,*q,*r,*s3=;intm,e,n=0;m=strlen(s1);while(m0){p=s1;s2[0]=s1[0];s2[1]='\0';r=s2;e=0;while((q=strstr(p,r))!=NULL){*q='\0';strcat(temp,p);strcat(temp,s3);p=q+strlen(s2);e++;}m-=e;strcat(temp,p);strcpy(s1,temp);s5[n]=s2[0];n++;strcpy(temp,);}s5[n]='\0';strcpy(s1,s5);printf(压缩后的电文（即叶结点）:%s\n,s1);returns1;}HNODETYPEhuffmantree(char*s2,chars3[]){HNODETYPEhuffnode[MAXNODE];HCODETYPEhuffcode[MAXLEAF],cd;intsum,i,j,n1,n2,x1,x2,p,k,c;chars1[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};chars5[MAXLEAF];intww[26]={0},n=0;strcpy(s5,s2);sum=strlen(s2);for(i=0;i26;i++)/*统计所有字符出现的频度*/for(j=0;jsum;j++)if(s2[j]==s1[i])ww[i]++;n=strlen(s3);for(i=0;i2*n-1;i++){huffnode[i].weight=0;huffnode[i].parent=-1;huffnode[i].lchild=-1;huffnode[i].rchild=-1;}for(i=0;in;i++)/*分配给各叶结点权值*/for(j=0;j26;j++)if(s3[i]==s1[j])huffnode[i].weight=ww[j];for(i=0;in-1;i++)/*构造哈夫曼树*/{n1=n2=MAXVALUE;x1=x2=0;for(j=0;jn+i;j++){if(huffnode[j].parent==-1&&huffnode[j].weig