哈夫曼編碼步驟

1、哈夫曼編碼步驟哈夫曼編碼步驟:構(gòu)成n棵二叉樹的初始集合 F=一、對給定的n個權(quán)值W1,W2,W3,Wi,WnT1,T2,T3,Ti,Tn,其中每棵二叉樹Ti中只有一個權(quán)值為 Wi的根結(jié)點(diǎn)，它的左右子樹均為空（為方便在計算機(jī)上實(shí)現(xiàn)算法，一般還要求以Ti的權(quán)值Wi的升序排列。）二、在F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為新構(gòu)造的二叉樹的左右子樹，新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹的根結(jié)點(diǎn)的權(quán)值之和。三、從F中刪除這兩棵樹，并把這棵新的二叉樹同樣以升序排列加入到集合F中。四、重復(fù)二和三兩步，直到集合F中只有一棵二叉樹為止。/* Name:哈夫曼編碼源代碼。* Date:2011.04.16 * Auth

2、or: JeffreyHill+Jezze（解碼部分）* 在 Win-TC 下測試通過* 實(shí)現(xiàn)過程：著先通過 HuffmanTree（）函數(shù)構(gòu)造哈夫曼樹，然后在主函數(shù) main（）中*自底向上開始（也就是從數(shù)組序號為零的結(jié)點(diǎn)開始）向上層層判斷，若在*父結(jié)點(diǎn)左側(cè)，則置碼為 0,若在右側(cè)，則置碼為1。最后輸出生成的編碼。*/#include <stdio.h>#include<stdlib.h>#define MAXBIT#define MAXVALUE#define MAXLEAF#define MAXNODE typedef struct int bitMAXBIT;i

3、nt start; HCodeType;*/typedef struct int weight;int parent;int lchild;int rchild;int value; HNodeType; 體*/*構(gòu)造一顆哈夫曼樹*/ void1001000030MAXLEAF*2 -1/*編碼結(jié)構(gòu)體/*結(jié)點(diǎn)結(jié)構(gòu)HuffmanTree(HNodeTypeHuffNodeMAXNODE, int n)/* i、j:循環(huán)變量)ml、m2:構(gòu)造哈夫曼樹 不同過程中兩個最小權(quán)值結(jié)點(diǎn)的權(quán)值， x1、x2:構(gòu)造哈夫曼樹不同過程中兩個最小權(quán)值 結(jié)點(diǎn)在數(shù)組中的序號。*/int i, j, ml, m2, x1

4、, x2;/*初始化存放哈夫曼樹數(shù)組HuffNode口中的結(jié)點(diǎn)*/for (i=0; i<2*n-1; i+)HuffNodei.weight = 0;/權(quán)值HuffNodei.parent =-1;HuffNodei.lchild =-1;HuffNodei.rchild =-1; HuffNodei.value=i;實(shí)際值，可根據(jù)情況替換為字母 /* end for */*輸入n個葉子結(jié)點(diǎn)的權(quán)值*/for (i=0; i<n; i+)printf ("Please input weight of leaf node %d: n”, i);scanf ("%d

5、”, &HuffNodei.weight); /* end for */*循環(huán)構(gòu)造 Huffman樹*/for (i=0; i<n-1; i+)m1=m2=MAXV ALUE;/* ml、m2中存放兩個無父結(jié)點(diǎn)且結(jié)點(diǎn)權(quán) 值最小的兩個結(jié)點(diǎn)*/x1=x2=0;/*找出所有結(jié)點(diǎn)中權(quán)值最小、無父結(jié)點(diǎn) 的兩個結(jié)點(diǎn)，并合并之為一顆二叉樹*/ for (j=0; j<n+i; j+)if (HuffNodej.weight < m1 &&HuffNodej.parent=-1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j;else if

6、(HuffNodej.weight < m2 &&HuffNodej.parent=-1)m2=HuffNodej.weight;x2=j； /* end for */ /*設(shè)置找到的兩個子結(jié)點(diǎn) x1、x2的 父結(jié)點(diǎn)信息*/HuffNodex1.parent = n+i;HuffNodex2.parent = n+i;HuffNoden+i.weight=HuffNodex1.weight + HuffNodex2.weight;HuffNoden+i.lchild = x1;HuffNoden+i.rchild = x2;printf ("xl.weight

7、and x2.weight in round %d:%d,%dn”,i+1,HuffNodex1.weight, HuffNodex2.weight);/*用于測試*/printf ("n"); /* end for */*for(i=0;i<n+2;i+) printf("Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d'n”,HuffNodei.parent,HuffNod ei.lchild,HuffNodei.rchild,HuffNodei.value, HuffNodei.weight);

8、*/測試/* end HuffmanTree */解碼void decodeing(char string,HNodeType Buf,int Num)int i,tmp=0,code1024;int m=2*Num-1;char *nump;char num1024for(i=0;i<strlen(string);i+)if(stringi='0') numi=0;else numi=1;)i=0;nump=&num0;while(nump<(&numstrlen(string) tmp=m-1;while(Buftmp.lchild!=-1)&a

9、mp;&(Buftmp.rchild!=-1)if(*nump=0)tmp=Buftmp.lchild ;else tmp=Buftmp.rchild;nump+;printf("%d”,Buftmp.value);int main(void)HNodeType HuffNodeMAXNODE;/*定義一個結(jié)點(diǎn)結(jié)構(gòu)體數(shù)組 */ HCodeType HuffCodeMAXLEAF, cd;/*定義一個編碼結(jié)構(gòu)體數(shù)組， 同時定 義一個臨時變量來存放求解編碼時的信息 */ int i, j, c, p, n;char pp100;printf ("Please input

10、 n:n"); scanf ("%d", &n);HuffmanTree (HuffNode, n); for (i=0; i < n; i+) cd.start = n-1;c = i;p = HuffNodec.parent; while (p != -1)/*父結(jié)點(diǎn)存在*/ if (HuffNodep.lchild = c) cd.bitcd.start = 0;else cd.bitcd.start = 1; cd.start-;/*求編碼的低一位*/c=p;p=HuffNodec.parent;/*設(shè)置下一循環(huán)條件* /* end whil

11、e */*保存求出的每個葉結(jié)點(diǎn)的 哈夫曼編碼和編碼的起始位*/for (j=cd.start+1; j<n; j+)HuffCodei.bitj = cd.bitj; HuffCodei.start = cd.start; /* end for */*輸出已保存好的所有存在編碼的哈夫 曼編碼*/for (i=0; i<n; i+)printf ("%d 's Huffman code is: ", i)；for (j=HuffCodei.start+1; j < n; j+)printf ("%d", HuffCodei.bit

12、j);printf(" start:%d",HuffCodei.start);printf ("n");/*for(i=0;i<n;i+)for(j=0;j<n;j+)printf ("%d”, HuffCodei.bitj);printf("n");*/ printf("Decoding?PleaseEntercode:n");scanf("%s”,&pp);decodeing(pp,HuffNode,n); getch();return 0;解碼#include &quo

13、t;string.h"#include "stdio.h"# define MAXVALUE 1000 /* 定義最大權(quán)值*/# define MAXLEAF 30 /*定義哈夫曼樹葉結(jié)點(diǎn)個數(shù)*/# define MAXNODE MAXLEAF*2-1#define MAXBIT 30 /*定義哈夫曼編碼的最大長度*/ typedef struct int bitMAXBIT; int start; HCODETYPE; typedef struct int weight; int parent; int lchild; int rchild; HNODETYPE

14、;char *getcode1(char *s1,char *s2,char *s3) /* 首先去掉電文 中的空格*/ char temp128="",*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); return s1;/*再去掉重復(fù)出現(xiàn)的字符(即壓縮電文)，提取哈夫曼樹葉結(jié)點(diǎn)*/ char * getcode (char *s1) char s226,s5

15、26;char temp200="",*p,*q,*r,*s3="" int m,e,n=0;m=strlen(s1); while(m>0) p=s1; s20=s10; s21='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); s5n=s20; n+; strcpy(temp,"

16、"); s5n尸0' strcpy(s1,s5);printf(" 壓縮后的電文(即葉結(jié)點(diǎn))：%sn",s1); return s1; HNODETYPE huffmantree(char *s2,char s3口) HNODETYPE huffnodeMAXNODE; HCODETYPE huffcodeMAXLEAF,cd;int sum,i,j,n1,n2,x1,x2,p,k,c;char s126='a','b','c','d','e','fVg',&#

17、39;h','i','j',k,T,'m', 'n','o','p','q','r','s','t','u','v','w','x','y','z'char s5MAXLEAF; int ww26=0,n=0; strcpy( s5,s2); sum=strlen(s2);for(i=0;i<26;i+)/*統(tǒng)計所有字符出現(xiàn)的頻

18、度*/for(j=0;j<sum;j+) if(s2j=s1i)wwi+;n=strlen(s3); for (i=0;i<2*n-1;i+) huffnodei.weight=0;huffnodei.parent=-1; huffnodei.lchild=-1; huffnodei.rchild=-1; for(i=0;i<n;i+) for(j=0;j<26;j+) if (s3i=s1j) for (i=0;i<n-1;i+)/*分配給各葉結(jié)點(diǎn)權(quán)值*/huffnodei.weight=wwj;/*構(gòu)造哈夫曼樹*/ n1=n2=MAXVALUE;x1=x2=0

19、;for(j=0;j<n+i;j+) if (huffnodej.parent=-1 n2=n1;x2=x1;n1=huffnodej.weight;x1=j;elseif (huffnodej.parent=-1 n2=huffnodej.weight;huffnodex1.parent=n+i;huffnodex2.parent=n+i;&& huffnodej.weight<n1)&& huffnodej.weight<n2) x2=j;huffnoden+i.weight=huffnodex1.weight+huffnodex2.w e

20、ight;huffnoden+i.lchild=x1;huffnoden+i.rchild=x2;for(i=0;i<n;i+) cd.start=n-1;c=i;p=huffnodec.parent;/*求每個葉結(jié)點(diǎn)的哈夫曼編碼*/while (p!=-1) if (huffnodep.lchild=c) cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=huffnodec.parent;for (j=cd.start+1;j<n;j+) huffcodei.bitj=cd.bitj; huffcodei.start=cd

21、.start;printf("各葉結(jié)點(diǎn)對應(yīng)口夫曼編碼：");/*輸出每個葉結(jié)點(diǎn)的哈夫曼編碼*/for(i=0;i<n;i+) for(j=huffcodei.start+1;j<n;j+) printf("%d",huffcodei.bitj);printf(" ");printf("n電文的全部哈夫曼編碼：");/*輸出電文的全部哈夫曼編碼*/for(k=0;k<sum;k+)for(i=0;i<n;i+) if(s2k=s3i) for(j=huffcodei.start+1;j<

22、n;j+) printf("%d",huffcodei.bitj); printf(" "); printf("n"); main() char s1MAXLEAF,s2MAXLEAF; printf("n 請輸入電文：");gets(s1);strcpy(s2,getcode1(s1," ","");huffmantree(s1,getcode(s2);nclude<string.h>#include<stdlib.h>#include<std

23、io.h>int m,s1,s2;typedef struct unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/ 動態(tài)分配數(shù)組存儲哈夫曼樹typedef char *HuffmanCode; /動態(tài)分配數(shù)組存儲 哈夫曼編碼表void Select(HuffmanTree HT,int n) int i,j;for(i = 1;i <= n;i+)if(!HTi.parent)s1 = i;break;for(j = i+1;j <= n;j+)if(!HTj.parent)s

24、2 = j;break;for(i = 1;i <= n;i+)if(HTs1.weight>HTi.weight)&&(!HTi.parent)&&(s2!=i)s1=i;for(j = 1;j <= n;j+)if(HTs2.weight>HTj.weight)&&(!HTj.parent)&&(s1!=j)s2=j; void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC口，int *w, int n) /算法6.13/ w存放n個字符的權(quán)值(均&

25、gt;0),構(gòu)造哈夫曼樹HT,/并求出n個字符的哈夫曼編碼HCint i, j;char *cd;int p;int cdlen;if (n<=1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0號單元未用for (i=1; 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.l

26、child=0;HTi.rchild=0;puts("n哈夫曼樹的構(gòu)造過程如下所示：");printf("HT 初態(tài):n 結(jié)點(diǎn) weight parent Ichild rchild");for (i=1; i<=m; i+)printf("n%4d%8d%8d%8d%8d”,i,HTi.weight,HTi.parent,HTi.lchild, HTi.rchild);printf("按任意鍵，繼續(xù))getchar();for (i=n+1; i<=m; i+) /建哈夫曼樹/ 在HT1.i-1 中選擇parent為0且

27、weight最小的兩個結(jié)點(diǎn)，/其序號分別為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=%d s2=%dn", s1, s2);printf(" 結(jié)點(diǎn) weight parent lchild rchild");for (j=1; j<=i; j+)printf("n%4d%8d%8d%8d%8d”,j,HTj.weight,HTj.parent,HTj.lchild, HTj.rchild);printf("按任意鍵，繼續(xù))getchar();/無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼cd = (char *)malloc(n*sizeof(char); 分配求