搜索
哈夫曼编码的C语言实现编码原理程序步骤的分析：哈夫曼码是用概率匹配方法进行信源编码。编程时应该注意：1，概率大的符号对应于短码，概率小的对应于长码，充分利用短码；2缩减信源的最后二个码字，总是最后一位不同，保证了哈夫曼码是即时码。程序步骤：（见信息论课本p88页内容）（l）将信号源的符号按照出现概率递减的顺序排列。（2）将两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率（3）重排后的两个概率最小符号重复步骤(2)过程。（4）不断继续上述过程，直到最后两个符号配以0和1为止（5）从最后一级开始向前返回各个信源符号所对应的码元序列，及相应的码字。根据以上规则编码可知：哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，到树根结束，最后得到一个横放的码树，所以编出的码是即时码。哈夫曼编码概率大的符号对应于短码，概率小的符号对应于长码，使平均码长最小。每次对概率最小的两个符号求概率之和形成缩减信源时，构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字不惟一。程序源代码如下;#includestdio.h#includemalloc.h#includeconio.h#includestring.h#includestdlib.h#defineHuffmanTreeHF#defineHuffmanCodeHMCtypedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HF;typedefchar**HMC;typedefstruct{unsignedints1;unsignedints2;}MinCode;voidError(char*message);HMCHuffmanCoding(HFHT,HMCHC,unsignedint*w,unsignedintn);MinCodeSelect(HFHT,unsignedintn);voidError(char*message){fprintf(stderr,Error:%s\n,message);exit(1);}HMCHuffmanCoding(HFHT,HMCHC,unsignedint*w,unsignedintn){unsignedinti,s1=0,s2=0;HFp;char*cd;unsignedintf,c,start,m;MinCodemin;if(n=1)Error(Codetoosmall!);m=2*n-1;HT=(HF)malloc((m+1)*sizeof(HTNode));for(p=HT,i=0;i=n;i++,p++,w++){p-weight=*w;p-parent=0;p-lchild=0;p-rchild=0;}for(;i=m;i++,p++){p-weight=0;p-parent=0;p-lchild=0;p-rchild=0;}for(i=n+1;i=m;i++){min=Select(HT,i-1);s1=min.s1;s2=min.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;}printf(HTList:\n);printf(Number\t\tweight\t\tparent\t\tlchild\t\trchild\n);for(i=1;i=m;i++)printf(%d\t\t%d\t\t%d\t\t%d\t\t%d\n,i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);HC=(HMC)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char*));cd[n-1]='\0';for(i=1;i=n;i++){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char*));strcpy(HC[i],&cd[start]);}free(cd);returnHC;}voidmain(){MinCodeSelect(HFHT,unsignedintn);HFHT=NULL;HuffmanCodeHC=NULL;unsignedint*w=NULL;unsignedinti,n;printf(请输入节点个数n:);scanf(%d,&n);w=(unsignedint*)malloc((n+1)*sizeof(unsignedint*));w[0]=0;printf(请输入权重:\n);for(i=1;i=n;i++){printf(w[%d]=,i);scanf(%d,&w[i]);}HC=HuffmanCoding(HT,HC,w,n);printf(HMC:\n);printf(Number\t\tWeight\t\tCode\n);for(i=1;i=n;i++)printf(%d\t\t%d\t\t%s\n,i,w[i],HC[i]);}MinCodeSelect(HFHT,unsignedintn){unsignedintmin,secmin;unsignedinttemp;unsignedinti,s1,s2,tempi;MinCodecode;s1=1;s2=1;for(i=1;i=n;i++)if(HT[i].parent==0){min=HT[i].weight;s1=i;break;}tempi=i++;for(;i=n;i++)if(HT[i].weightmin&&HT[i].parent==0){min=HT[i].weight;s1=i;}for(i=tempi;i=n;i++)if(HT[i].parent==0&&i!=s1){secmin=HT[i].weight;s2=i;break;}for(i=1;i=n;i++)if(HT[i].weightsecmin&&i!=s1&&HT[i].parent==0){secmin=HT[i].weight;s2=i;}if(s1s2){temp=s1;s1=s2;s2=temp;}code.s1=s1;code.s2=s2;returncode;}运行结果如下：请输入节点个数n:5请输入权重:w[1]=2w[2]=3w[3]=1w[4]=1w[5]=3NumberWeightCode1200231031010410115311Pressanykeytocontinue编程感想及总结：正如事物均具有两面性，哈夫曼编码也具有优点和缺点，比如哈夫曼编码可以取得较好的荣誉压缩效果，使得输出码元概率均匀化。但是由于编码不唯一，硬件实现可能会有一定难度，压缩与还原也相对费时，尤其在概率相同的情况下，编码效率较低。