#include<stdio.h> #include<stdlib.h> #include<string.h> #define?OK?1 #define?ERROR?0 typedef?struct{ unsigned?int?weight; unsigned?int?parent,lchild,rchild; }HTNode,*?HuffmanTree;?//動態(tài)分配數(shù)組存儲哈夫曼樹 typedef?char?*?*HuffmanCode;//動態(tài)分配數(shù)組存儲哈夫曼編碼表 void?SelectMin(HuffmanTree?HT,int?nNode,int?&s1,int?&s2){ int?i,j; for(i=1;i<=nNode;i++) ????if(!HT[i].parent){ ????s1=i; ????break; } for(j=i+1;j<=nNode;j++) if(!HT[j].parent){ s2=j; break; } for(i=1;i<=nNode;i++) if((HT[i].weight<HT[s1].weight)&&(!HT[i].parent)&&s2!=i) s1=i; for(i=1;j<=nNode;j++) if((HT[j].weight<HT[s2].weight)&&(!HT[j].parent)&&s1!=j) s2=j; if(HT[s1].weight>HT[s2].weight){ int?temp=s1; s1=s2; s2=temp; } } void?HuffmanCoding(HuffmanTree?&HT,HuffmanCode?&HC,int?*w,int?nNode){ int?i,s1,s2,start,c,f; char?*cd; if(nNode<=1) return; int?m=2*nNode-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=1;i<=nNode;i++) { HT[i].parent=0; HT[i].weight=w[i-1]; HT[i].lchild=0; HT[i].rchild=0; } for(i=nNode+1;i<=m;i++) { HT[i].parent=0; HT[i].weight=0; HT[i].lchild=0; HT[i].rchild=0; } for(i=nNode+1;i<=m;i++){//建立哈夫曼樹 SelectMin(HT,nNode,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; } //-?-?-?-從葉子到根逆向求每個字符的哈夫曼編碼-?-?-?-// HC=(HuffmanCode)malloc((nNode+1)*sizeof(char?*)); cd=(char?*)malloc(nNode*sizeof(char)); cd[nNode-1]='0'; for(i=1;i<=nNode;i++){ start=nNode-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char?*)malloc((nNode-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); }//HuffmanCoding int?main(){ HuffmanTree?HT; HuffmanCode?HC; ????int?i,nNode,*w; char?Code[20]={0}; printf("請輸入結(jié)點個數(shù)："); scanf("%d",&nNode); HC=(HuffmanCode)malloc(nNode*sizeof(HuffmanCode)); w=(int?*)malloc(nNode*sizeof(int)); printf("請輸入各結(jié)點的權(quán)值\n"); for(i=0;i<nNode;i++) scanf("%d",&w[i]); ?HuffmanCoding(HT,HC,w,nNode); ?printf("各點的哈夫曼編碼為：\n"); ?for(i=0;i<=nNode;i++){ ?printf("%3d:%s\n",i,HC[i]); ?} ?return?OK; }