算法分析與設(shè)計(jì)-實(shí)驗(yàn)二-哈夫曼編碼.doc

昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告（ 201 201 學(xué)年 第 一 學(xué)期 ）課程名稱：算法設(shè)計(jì)與分析 開(kāi)課實(shí)驗(yàn)室： 年 月 日年級(jí)、專業(yè)、班 學(xué)號(hào) 姓名 成績(jī)實(shí)驗(yàn)項(xiàng)目名稱哈夫曼編碼指導(dǎo)教師 教師評(píng)語(yǔ)該同學(xué)是否了解實(shí)驗(yàn)原理：A.了解B.基本了解C.不了解該同學(xué)的實(shí)驗(yàn)?zāi)芰Γ篈.強(qiáng) B.中等 C.差 該同學(xué)的實(shí)驗(yàn)是否達(dá)到要求：A.達(dá)到B.基本達(dá)到C.未達(dá)到實(shí)驗(yàn)報(bào)告是否規(guī)范：A.規(guī)范B.基本規(guī)范C.不規(guī)范實(shí)驗(yàn)過(guò)程是否詳細(xì)記錄：A.詳細(xì)B.一般 C.沒(méi)有 教師簽名： 年 月 日一、上機(jī)目的及內(nèi)容1.上機(jī)內(nèi)容設(shè)需要編碼的字符集為d1, d2, , dn，它們出現(xiàn)的頻率為w1, w2, , wn，應(yīng)用哈夫曼樹(shù)構(gòu)造最短的不等長(zhǎng)編碼方案。2.上機(jī)目的（1）了解前綴編碼的概念，理解數(shù)據(jù)壓縮的基本方法；（2）掌握最優(yōu)子結(jié)構(gòu)性質(zhì)的證明方法；（3）掌握貪心法的設(shè)計(jì)思想并能熟練運(yùn)用。二、實(shí)驗(yàn)原理及基本技術(shù)路線圖（方框原理圖或程序流程圖）（1）證明哈夫曼樹(shù)滿足最優(yōu)子結(jié)構(gòu)性質(zhì)；（2）設(shè)計(jì)貪心算法求解哈夫曼編碼方案；（3）設(shè)計(jì)測(cè)試數(shù)據(jù)，寫(xiě)出程序文檔。數(shù)據(jù)結(jié)構(gòu)與算法:typedef char *HuffmanCode; /動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼編碼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ù)程序流程圖：三、所用儀器、材料（設(shè)備名稱、型號(hào)、規(guī)格等或使用軟件）1臺(tái)PC及VISUAL C+6.0軟件四、實(shí)驗(yàn)方法、步驟（或：程序代碼或操作過(guò)程）程序代碼：#include #include #include typedef struct 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 Select(HuffmanTree *ht,int n,int *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!=(*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)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所構(gòu)造的哈夫曼樹(shù)為: n); for(i=n+1; i=m; i+) /創(chuàng)建非葉子結(jié)點(diǎn)，建哈夫曼樹(shù) Select(ht,i-1,&s1,&s2); (*ht)s1.parent=i; (*ht)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; /定義的存放編碼的空間 int a100; int i,start,p,w=0; unsigned int c; hc=(HuffmanCode *)malloc(n+1)*sizeof(char *); cd=(char *)malloc(n*sizeof(char); cdn-1=0; 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=(*ht)p.parent) /從葉子到根結(jié)點(diǎn)求編碼 if( (*ht)p.LChild=c)cd-start=1; ai+; else cd-start=0; ai+; hci=(char *)malloc(n-start)*sizeof(char); /為第i個(gè)編碼分配空間 strcpy(hci,&cdstart); free(cd); for(i=1; i=n; i+) printf(權(quán)值為%d的哈夫曼編碼為：%sn,(*ht)i.weight,hci); for(i=1; i=n; i+) w+=(*ht)i.weight*ai; printf(n帶權(quán)路徑長(zhǎng)度WPL為：%dnn,w);void main() HuffmanTree HT; HuffmanCode HC; int *w,i,n,wei; printf(tttt哈夫曼編碼n ); printf(請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)： ); scanf(%d,&n); w=(int *)malloc(n+1)*sizeof(int); printf(n請(qǐng)分別輸入這%d個(gè)結(jié)點(diǎn)的權(quán)值:n,n); for(i=1; i=n; i+) printf(結(jié)點(diǎn)%d: ,i); fflush(stdin); scanf(%d,&wei); wi=wei; CrtHuffmanTree(&HT,w,n); CrtHuffmanCode(&HT,&HC,n);五、實(shí)驗(yàn)過(guò)程原始記錄( 測(cè)試數(shù)據(jù)、圖表、計(jì)算等)六、實(shí)驗(yàn)結(jié)果、分析和結(jié)論（誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中，繪制曲線圖時(shí)必須用計(jì)算紙或程序運(yùn)行結(jié)果、改進(jìn)