1、#include#include#includeintm,s1,s2;typedefstructunsignedintweight;unsignedintparent,lchild,rchild;HTNode,*HuffmanTree;/動態(tài)分配數(shù)組存儲哈夫曼樹typedefchar*HuffmanCode;/動態(tài)分配數(shù)組存儲哈夫曼編碼表voidSelect(HuffmanTreeHT,intn)inti,j;for(i=1;i=n;i+)if(!HTi.parent)s1=i;break;for(j=i+1;j=n;j+)if(!HTj.parent)s2=j;break;for(i=1;i

2、HTi.weight)&(!HTi.parent)&(s2!=i)s1=i;for(j=1;jHTj.weight)&(!HTj.parent)&(s1!=j)s2=j;voidHuffmanCoding(HuffmanTree&HT,HuffmanCodeHC,int*w,intn)/算法6.13/w存放n個字符的權值(均0)，構造哈夫曼樹HT，/并求出n個字符的哈夫曼編碼HCinti,j;char*cd;intp;intcdlen;if(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0號單元未用for(i=1;

3、i=n;i+)/初始化HTi.weight=wi-1;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i=m;i+)/初始化HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;puts(n哈夫曼樹的構造過程如下所示：);printf(HT初態(tài):n結點weightparentlchildrchild);for(i=1;i=m;i+)printf(n%4d%8d%8d%8d%8d,i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);printf(按任意鍵，

4、繼續(xù).);getchar();for(i=n+1;i=m;i+)/建哈夫曼樹/在HT1.i-1中選擇parent為0且weight最小的兩個結點，/其序號分別為s1和s2。Select(HT,i-1);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;printf(nselect:s1=%ds2=%dn,s1,s2);printf(結點weightparentlchildrchild);for(j=1;j=i;j+)printf(n%4d%8d%8d%8d%8d,

5、j,HTj.weight,HTj.parent,HTj.lchild,HTj.rchild);printf(按任意鍵，繼續(xù).);getchar();/-無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼cd=(char*)malloc(n*sizeof(char);/分配求編碼的工作空間p=m;cdlen=0;for(i=1;i=m;+i)/遍歷哈夫曼樹時用作結點狀態(tài)標志HTi.weight=0;while(p)if(HTp.weight=0)/向左HTp.weight=1;if(HTp.lchild!=0)p=HTp.lchild;cdcdlen+=0;elseif(HTp.rchild=0)/登記葉子結

6、點的字符的編碼HCp=(char*)malloc(cdlen+1)*sizeof(char);cdcdlen=0;strcpy(HCp,cd);/復制編碼(串)elseif(HTp.weight=1)/向右HTp.weight=2;if(HTp.rchild!=0)p=HTp.rchild;cdcdlen+=1;else/HTp.weight=2，退回退到父結點，編碼長度減1HTp.weight=0;p=HTp.parent;-cdlen;/HuffmanCodingintmain()HuffmanTreeHT;HuffmanCode*HC;int*w,n,i;puts(輸入結點數(shù):);scanf(%d,&n);getchar();HC=(HuffmanCode*)malloc(n*sizeof(HuffmanCode);w=(int*)malloc(n*sizeof(int);printf(輸入%d個結點的權值n,n);for(i=0;in;i+)scanf(%d,&wi);getchar(