哈夫曼樹與哈夫曼編碼實驗五

1、實驗四 哈夫曼樹與哈夫曼編碼問題描述已知n個字符在原文中出現(xiàn)的頻率，求它們的哈夫曼編碼?；疽?. 初始化：從鍵盤讀入n個字符，以及它們的權(quán)值，建立Huffman樹。（具體算法可參見教材P147的算法6.12）2. 編碼：根據(jù)建立的Huffman樹，求每個字符的Huffman編碼。對給定的待編碼字符序列進(jìn)行編碼。3、測試數(shù)據(jù)四、程序代碼：#include #include #include int m,s1,s2; typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTre

2、e; /動態(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.parents1 = i;break; for(j = i+1;j <= n;j+ if(!HTj.parents2 = j;break; for(i = 1;i <= n;i+ if(HTs1.weight>HTi.weight&&(!HTi.parent&&(s2!=is1=i;

3、 for(j = 1;j <= n;j+ if(HTs2.weight>HTj.weight&&(!HTj.parent&&(s1!=js2=j; void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int *w, int n / 算法6.13 / w存放n個字符的權(quán)值(均>0，構(gòu)造哈夫曼樹HT， / 并求出n個字符的哈夫曼編碼HC int i, j; char *cd; int p; int cdlen; if (n<=1 return; m=2*n-1; HT=(HuffmanTree

4、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.lchild=0; HTi.rchild=0; puts("n哈夫曼樹的構(gòu)造過程如下所示：" printf("HT初態(tài):n 結(jié)點(diǎn) weight parent lchild rchild" for

5、(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且weight最小的兩個結(jié)點(diǎn)， / 其序號分別為s1和s2。 Select(HT, i-1; HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rc

6、hild = 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(; /

7、-無棧非遞歸遍歷哈夫曼樹，求哈夫曼編碼 cd = (char *malloc(n*sizeof(char; / 分配求編碼的工作空間 p = m; cdlen = 0; for (i=1; i<=m; +i / 遍歷哈夫曼樹時用作結(jié)點(diǎn)狀態(tài)標(biāo)志 HTi.weight = 0; while (p if (HTp.weight=0 / 向左 HTp.weight = 1; if (HTp.lchild != 0 p = HTp.lchild; cdcdlen+ ='0' else if (HTp.rchild = 0 / 登記葉子結(jié)點(diǎn)的字符的編碼 HCp = (char *ma

8、lloc(cdlen+1 * sizeof(char; cdcdlen ='0' strcpy(HCp, cd; / 復(fù)制編碼(串 else if (HTp.weight=1 / 向右 HTp.weight = 2; if (HTp.rchild != 0 p = HTp.rchild; cdcdlen+ ='1' else / HTp.weight=2，退回退到父結(jié)點(diǎn)，編碼長度減1 HTp.weight = 0; p = HTp.parent; -cdlen; / HuffmanCoding void main( HuffmanTree HT;HuffmanCode *HC;int *w,n,i; puts("輸入結(jié)點(diǎn)數(shù):" scanf("%d",&n; HC = (HuffmanCode *malloc(n*sizeof(HuffmanCode; w = (int *malloc(n*sizeof(int; printf("輸入%d個結(jié)點(diǎn)的權(quán)值n",n; for(i = 0;i < n;i+ scanf("%d",&