哈夫曼編碼源程序解釋

1、哈夫曼編碼一、源程序#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>/* Huffman 樹的存儲結(jié)構(gòu)*/#define n 8/*葉子數(shù)目根據(jù)需要設(shè)定*/#define m 2*n-1/* Huffman 樹中結(jié)點總數(shù) */typedef struct int weight;/*結(jié)點的權(quán)值*/int lchild,rchild,parent;/*左、右孩子及雙親的下標(biāo)*/htnode;typedef htnode huffmantreem+1;/* hu

2、ffmantree是結(jié)構(gòu)數(shù)組類型,其0號單元不用，存儲哈夫曼樹 */typedef structchar ch;/*存儲字符*/ char coden+1;/*存放編碼位串*/codenode;typedef codenode huffmancoden+1;/*huffmancode是結(jié)構(gòu)數(shù)組類型,其0號單元不用,存儲哈夫曼編碼*/void inithuffmantree(huffmantree ht) /*初始化哈夫曼樹函數(shù)inithuffmantree()*/int i; for(i=0;i<=m;i+)hti.weight=0;hti.lchild=hti.rchild=hti.p

3、arent=0;void inputweight(huffmantree ht)/*輸入權(quán)值函數(shù) */int i; for(i=1;i<=n;i+)printf("請輸入第%d個權(quán)值: ",i); scanf("%d",&hti.weight);void selectmin(huffmantree ht, int i, int *p1, int *p2)/* 在ht1.i中選兩個權(quán)值最小的根結(jié)點，其序號為*p1和*p2，*p1中放權(quán)值最小的根結(jié)點的序號，*p2中放權(quán)值次小的根結(jié)點的序號*/int j,min1,min2;/* min1,mi

4、n2分別是最小權(quán)值和次小權(quán)值*/min1=min2=32767;*p1=*p2=0;for(j=1;j<=i;j+)if(htj.parent=0)/* j 為根結(jié)點*/if(htj.weight<min1|min1=32767)if(min1!=32767)min2=min1; *p2=*p1; min1=htj.weight; *p1=j;elseif(htj.weight<min2|min2=32767)min2=htj.weight; *p2=j;void createhuffmantree(huffmantree ht)/*構(gòu)造huffman樹，htm為其根結(jié)點*/

5、int i,p1,p2;inithuffmantree(ht);/* 將ht初始化*/inputweight(ht);/* 輸入葉子權(quán)值至ht 1.n的weight域*/for(i=n+1;i<=m;i+)/* 共進(jìn)行n-1次合并，新結(jié)點依次存于hti中*/selectmin(ht,i-1,&p1,&p2); /*在ht 1. i-1中選擇兩個權(quán)值最小的根結(jié)點，其序號分別為p1和p2*/ htp1.parent=htp2.parent=i; hti.lchild=p1;/* 最小權(quán)值的根結(jié)點是新結(jié)點的左孩子*/ hti.rchild=p2; /* 次小權(quán)值的根結(jié)點是新結(jié)點

6、的右孩子*/ hti.weight=htp1.weight+htp2.weight;void huffmancodes(huffmantree ht,huffmancode hcd) /*根據(jù)huffman樹ht求huffman編碼*/int c,p,i;/* c和p分別指示 ht中孩子和雙親的位置 */char cdn+1;/* 臨時存放編碼*/int start; /* 指示編碼在cd 中的起始位置*/cdn='0'getchar();/* 編碼結(jié)束符*/printf("請輸入字符"); for(i=1;i<=n;i+)/* 依次求葉子ht i的編

7、碼*/ hcdi.ch=getchar();/* 讀入葉子ht i對應(yīng)的字符*/ start=n;/* 編碼起始位置的初值*/ c=i;/* 從葉子ht i開始上溯*/while(p=htc.parent)!=0)/* 直至上溯到ht c是樹根為止*/ cd-start=(htp.lchild=c)?'0':'1' /*若ht c是htp的左孩子，則生成代碼0，否則生成代碼1*/ c=p;/* 繼續(xù)上溯*/strcpy(hcdi.code,&cdstart);/* 復(fù)制編碼位串*/printf("n");for(i=1;i<=n;i+)printf("第%d個字符%c的編碼為%sn",i,hcdi.ch,hcdi.code);void main()huffmantree t;huffmancode h;printf("n請輸入%d個權(quán)值n",n);createhuffmantree(t);/* 構(gòu)造huffman樹*/huffmancodes(t,h);/* 構(gòu)造huffman編碼*/運(yùn)行結(jié)果心得 getch與getchar基本功能相同,差別是getch直接從鍵盤獲取鍵值,不等待用戶按回車,只要用戶按一個