用赫夫曼樹(shù)進(jìn)行字符串的編碼

1、華北水利水電大學(xué) 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)三 樹(shù)的應(yīng)用一、 實(shí)驗(yàn)題目：樹(shù)的應(yīng)用哈夫曼編碼二、 實(shí)驗(yàn)內(nèi)容：利用哈夫曼編碼進(jìn)行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r(shí)間，降低傳輸成本。根據(jù)哈夫曼編碼的原理，編寫(xiě)一個(gè)程序，在用戶輸入結(jié)點(diǎn)權(quán)值的基礎(chǔ)上求哈夫曼編碼。從鍵盤輸入若干字符及每個(gè)字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結(jié)點(diǎn)的權(quán)值，建立哈夫曼樹(shù)，求出各字符的哈夫曼編碼。要求：1 輸出存放哈夫曼樹(shù)的數(shù)組HT的初態(tài)和終態(tài)；2 輸出每個(gè)字符的哈夫曼編碼；3 輸入由上述若干字符組成的字符串，對(duì)電文進(jìn)行編碼并輸出；三、 程序源代碼：#include #include #include #define N

2、8#define M 4typedef structchar data;char *code;unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù)typedef char *HuffmanCode; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼編碼表void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *data,int *w,int n,char *str/存放n個(gè)字符的權(quán)值(均>0，構(gòu)造赫夫曼樹(shù)HT，并求出n

3、各字符的赫夫曼編碼HCif(n<=1 return;int m=2*n-1; /總節(jié)點(diǎn)數(shù)HT=(HuffmanTreemalloc(m+1*sizeof(HTNode;/0號(hào)單元未用HuffmanTree p;int i,j;printf("n"printf("-n"printf("存放哈夫曼樹(shù)的數(shù)組HT的初態(tài):n"printf("葉子節(jié)點(diǎn)以及它的雙親節(jié)點(diǎn)，權(quán)值，左孩子，右孩子分別為:n"for(p=HT+1,i=1;i<=n;+i,+p,+data,+wp->data=*data;p->p

4、arent=p->lchild=p->rchild=0;p->weight=*w;p->code=(char *malloc(n*sizeof(char; printf("%c %2d %2d %2d %2dn",p->data,p->parent,p->weight,p->lchild,p->rchild;for(;i<=m;+p,+ip->parent=p->lchild=p->rchild=p->weight=0;p->data=NULL;p->code=(char *ma

5、lloc(n*sizeof(char; printf(" %2d %2d %2d %2dn",p->parent,p->weight,p->lchild,p->rchild;for(i=n+1;i<=m;+i/建赫夫曼樹(shù)/在HT1-i-1選擇parent為0且weight最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)分別為s1和s2unsigned int m1=32767;unsigned int m2=32767;/m1,m2為最小和次小權(quán)值int s1=0;int s2=0;/s1,s2為最小和次小節(jié)點(diǎn)的序號(hào)for(int k=1;k<=i-1;k+if(

6、HTk.parent=0&&(HTk.weight m2=m1;s2=s1;m1=HTk.weight;s1=k;else if(HTk.parent=0&&(HTk.weight m2=HTk.weight;s2=k;HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;printf("n"printf("-n"printf("存放哈夫曼樹(shù)的數(shù)組HT的終態(tài):n"printf(

7、"葉子節(jié)點(diǎn)以及它的雙親節(jié)點(diǎn)，權(quán)值，左孩子，右孩子分別為:n"for(p=HT+1,i=1;i<=n;+p,+iprintf("%c %2d %2d %2d %2dn",p->data,p->parent,p->weight,p->lchild,p->rchild;for(;i<=m;+p,+iprintf(" %2d %2d %2d %2dn",p->parent,p->weight,p->lchild,p->rchild;/-從葉子到根逆向求每個(gè)字符的赫夫曼編碼-HC

8、=(HuffmanCodemalloc(n+1*sizeof(char *;/分配n個(gè)字符編碼的頭指針向量char *cd;cd=(char *malloc(n*sizeof(char; /分配求編碼的工作空間cdn-1='0' /編碼結(jié)束符int start;unsigned int f,c;printf("n"printf("-n"printf("每個(gè)字符的哈夫曼編碼:n"for(p=HT+1,i=1;i<=n;+i,+p /逐個(gè)字符求赫夫曼編碼start=n-1;/編碼結(jié)束符位置for(c=i,f=HTi.

9、parent;f!=0;c=f,f=HTf.parent/從葉子到根逆向求編碼if(HTf.lchild=c cd-start='0'else cd-start='1'HCi=(char *malloc(n-start*sizeof(char; /為第i個(gè)字符編碼分配空間char *R=&cdstart;strcpy(HCi,&cdstart;strcpy(p->code,R;printf("%c ",p->data;printf("%s",HCi;printf("n"pri

10、ntf("輸出字符串的赫夫曼編碼:n"for(i=0;i for(p=HT+1,j=0;j if(stri=p->dataprintf("%s",p->code;free(cd;/釋放工作空間int main(char dataN,strM;int pN,i;for(i=0;i printf("輸入第%d個(gè)字符及頻率：n",i+1;scanf("%c",&datai;scanf("%d",&pi;getchar(;printf("輸入字符串：n"for(i=0;i scanf("%c",&stri;HuffmanTree HT;HuffmanCode HC;HuffmanCoding(HT,HC,data,p,N,str;printf("n"return 0;四、 測(cè)試結(jié)果：五、小結(jié)（包括收獲、心得體會(huì)、存在的問(wèn)題及解決問(wèn)題的方法、建議等）注：內(nèi)容一律使用宋體五號(hào)字，單倍行間距本次實(shí)驗(yàn)中第三個(gè)問(wèn)題沒(méi)做出來(lái)，我本來(lái)想出了一種方法，但是總是出錯(cuò)，我的方法是在結(jié)構(gòu)體中加一個(gè)編碼域，