實(shí)驗(yàn)四哈夫曼編碼的貪心算法設(shè)計(jì)

1、實(shí)驗(yàn)四 哈夫曼編碼的貪心算法設(shè)計(jì)（4學(xué)時(shí)）實(shí)驗(yàn)?zāi)康? 根據(jù)算法設(shè)計(jì)需要,掌握哈夫曼編碼的二叉樹(shù)結(jié)構(gòu)表示方法;. 編程實(shí)現(xiàn)哈夫曼編譯碼器;. 掌握貪心算法的一般設(shè)計(jì)方法。實(shí)驗(yàn)?zāi)康暮鸵螅?）了解前綴編碼的概念，理解數(shù)據(jù)壓縮的基本方法；（2）掌握最優(yōu)子結(jié)構(gòu)性質(zhì)的證明方法；（3）掌握貪心法的設(shè)計(jì)思想并能熟練運(yùn)用（4）證明哈夫曼樹(shù)滿足最優(yōu)子結(jié)構(gòu)性質(zhì)；（5）設(shè)計(jì)貪心算法求解哈夫曼編碼方案；（6）設(shè)計(jì)測(cè)試數(shù)據(jù)，寫(xiě)出程序文檔。 實(shí)驗(yàn)內(nèi)容設(shè)需要編碼的字符集為d1, d2, , dn，它們出現(xiàn)的頻率為 w1, w2, , wn，應(yīng)用哈夫曼樹(shù)構(gòu)造最短的不等長(zhǎng)編碼方案。 核心源代碼#include <stdi

2、o.h>#include <stdlib.h>#include <string.h>typedef struct unsigned int weight; /用來(lái)存放各個(gè)結(jié)點(diǎn)的權(quán)值 unsigned int parent,LChild,RChild; /指向雙親、孩子結(jié)點(diǎn)的指針 HTNode, *HuffmanTree; /動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼樹(shù)typedef char *HuffmanCode; /動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼編碼/選擇兩個(gè)parent為0，且weight最小的結(jié)點(diǎn)s1和s2void Select(HuffmanTree *ht,int n,in

3、t *s1,int *s2) int i,min; for(i=1; i<=n; i+) if(*ht)i.parent=0) min=i; break; for(i=1; i<=n; i+) if(*ht)i.parent=0) if(*ht)i.weight<(*ht)min.weight) min=i; *s1=min; for(i=1; i<=n; i+) if(*ht)i.parent=0 && i!=(*s1) min=i; break; for(i=1; i<=n; i+) if(*ht)i.parent=0 && i

4、!=(*s1) if(*ht)i.weight<(*ht)min.weight) min=i; *s2=min;/構(gòu)造哈夫曼樹(shù)ht,w存放已知的n個(gè)權(quán)值void CrtHuffmanTree(HuffmanTree *ht,int *w,int n) int m,i,s1,s2; m=2*n-1; /總共的結(jié)點(diǎn)數(shù) *ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(i=1; i<=n; i+) /1-n號(hào)存放葉子結(jié)點(diǎn)，初始化 (*ht)i.weight=wi; (*ht)i.LChild=0; (*ht)i.parent=0; (*ht

5、)i.RChild=0; for(i=n+1; i<=m; i+) /非葉子結(jié)點(diǎn)的初始化 (*ht)i.weight=0; (*ht)i.LChild=0; (*ht)i.parent=0; (*ht)i.RChild=0; printf("n哈夫曼樹(shù)為: n"); for(i=n+1; i<=m; i+) /創(chuàng)建非葉子結(jié)點(diǎn)，建哈夫曼樹(shù) /在(*ht)1(*ht)i-1的范圍內(nèi)選擇兩個(gè)parent為0且weight最小的結(jié)點(diǎn)，其序號(hào)分別賦值給s1、s2 Select(ht,i-1,&s1,&s2); (*ht)s1.parent=i; (*ht)

6、s2.parent=i; (*ht)i.LChild=s1; (*ht)i.RChild=s2; (*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight; printf("%d (%d, %d)n",(*ht)i.weight,(*ht)s1.weight,(*ht)s2.weight); printf("n"); /從葉子結(jié)點(diǎn)到根，逆向求每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼編碼void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) char *cd; /定義的存放編碼

7、的空間 int a100; int i,start,p,w=0; unsigned int c; hc=(HuffmanCode *)malloc(n+1)*sizeof(char *); /分配n個(gè)編碼的頭指針 cd=(char *)malloc(n*sizeof(char); /分配求當(dāng)前編碼的工作空間 cdn-1='0' /從右向左逐位存放編碼，首先存放編碼結(jié)束符 for(i=1; i<=n; i+) /求n個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼編碼 ai=0; start=n-1; /起始指針位置在最右邊 for(c=i,p=(*ht)i.parent; p!=0; c=p,p=

8、(*ht)p.parent) /從葉子到根結(jié)點(diǎn)求編碼 if( (*ht)p.LChild=c)cd-start='1' /左分支標(biāo)1ai+; else cd-start='0' /右分支標(biāo)0ai+; hci=(char *)malloc(n-start)*sizeof(char); /為第i個(gè)編碼分配空間 strcpy(hci,&cdstart); /將cd復(fù)制編碼到hc free(cd); for(i=1; i<=n; i+) printf(" 權(quán)值為%d的哈夫曼編碼為：%sn",(*ht)i.weight,hci); for

9、(i=1; i<=n; i+) w+=(*ht)i.weight*ai; printf(" 帶權(quán)路徑為：%dn",w);void main() HuffmanTree HT; HuffmanCode HC; int *w,i,n,wei; printf("*哈夫曼編碼*n" ); printf("請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)：" ); scanf("%d",&n); w=(int *)malloc(n+1)*sizeof(int); printf("n輸入這%d個(gè)元素的權(quán)值:n",n); for(i=1; i<=n; i+) printf("%d: ",i); fflush(stdin); scanf("%d",&wei); wi=wei; CrtHuffmanTree(&HT,w,n); CrtHuffmanCode(&HT,&HC,n);實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)體會(huì)哈夫曼編碼算法：每次將集合中兩個(gè)權(quán)值最