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

1、昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告(201201學(xué)年第一學(xué)期)課程名稱：算法設(shè)計(jì)與分析開(kāi)課實(shí)驗(yàn)室：年月日年級(jí)、專業(yè)、班學(xué)號(hào)姓名成績(jī)實(shí)驗(yàn)項(xiàng)目名稱哈夫曼編碼指導(dǎo)教師教該同學(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á)到匚評(píng)實(shí)驗(yàn)報(bào)告是否規(guī)范：A.規(guī)范口B.基本規(guī)范匚C.不規(guī)范匚實(shí)驗(yàn)過(guò)程是否詳細(xì)記錄：A.詳細(xì)口B.一般匚C.沒(méi)有匚語(yǔ)教師簽名：年月日、上機(jī)目的及內(nèi)容1. 上機(jī)內(nèi)容設(shè)需要編碼的字符集為di,d2,dn，它們出現(xiàn)的頻率為w1,w2,wn,應(yīng)用哈夫曼樹(shù)構(gòu)造最短的不等長(zhǎng)編碼方

2、案。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)與算法：typedefchar*HuffmanCode;/動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼編碼typedefstructunsignedintweight;/用來(lái)存放各個(gè)結(jié)點(diǎn)的權(quán)值unsignedintparent,LChild,RChild;/指向雙親、孩子結(jié)點(diǎn)的指針HTNode,*H

3、uffmanTree;/動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼樹(shù)程序流程圖：三、所用儀器、材料（設(shè)備名稱、型號(hào)、規(guī)格等或使用軟件）1臺(tái)PC及VISUALC+6.0軟件四、實(shí)驗(yàn)方法、步驟（或：程序代碼或操作過(guò)程）程序代碼：#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructunsignedintweight;unsignedintparent,LChild,RChild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組，存儲(chǔ)哈夫曼樹(shù)typedefchar*HuffmanCode;/動(dòng)態(tài)分配

4、數(shù)組，存儲(chǔ)哈夫曼編碼voidSelect(HuffmanTree*ht,intn,int*s1,int*s2)inti,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=

5、0&&i!=(*s1)if(*ht)i.weight<(*ht)min.weight)min=i;*s2=min;/構(gòu)造哈夫曼樹(shù)ht,w存放已知的n個(gè)權(quán)值voidCrtHuffmanTree(HuffmanTree*ht,int*w,intn)intm,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

6、=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)s

7、2.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)的哈夫曼編碼voidCrtHuffmanCode(HuffmanTree*ht,HuffmanCode*hc,intn)char*cd;/定義的存放編碼的空間inta100;inti,start,p,w=0;unsignedintc;hc=(HuffmanCode*)malloc(n+1)*sizeof(char*);cd=(char*)mall

8、oc(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;/起始指針位置在最右邊f(xié)or(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+;elsecd-start='0'ai+;hci=(char*)malloc(n-start)*sizeof(char);/為第i個(gè)編碼分配空間strcpy(hci,&cdstart);

9、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);voidmain()HuffmanTreeHT;HuffmanCodeHC;int*w,i,n,wei;printf("tttt哈夫曼編碼n");printf("請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)：");scanf("%d",&n

10、);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ì)算等）'G;VCDwbughafurnan.exe"請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)；11咱夫昜編碼5

11、123456789分點(diǎn)占皆苦苦M占苦吿苦苦苦小S-口士口士口20162100-0772-19構(gòu)造的哈夫曼樹(shù)為:23<11,12>28<13,15>3&<18,18>43<20,23>k53TG：VCDebughfunnanexe"-F31回所構(gòu)In的哈夫曼樹(shù)甘:7(2,&>13<6,7>1S<7,S>18<9,9>23<11,12>28<13,15>36<18,18>43<20,23)T<28,36>137<43.&4>01019100010B0B8101101110103000111001+療療冃drm帀一I自自！n"藥國(guó)旨3<m自3m曼曼湊日1£室夫哈哈刖哈哈哈JnJQn2帀Idrpldrph-i扁11251&7zJx?t1Ln.I十K1d-LhI*J1*-JIjTjjnj+lajjljnrljTTIJ4n嘆嘆嘆嘆艱嘆嘆嘆嘆後!*F，帀權(quán)路怪長(zhǎng)度WPL為354I'essytocontiriue六、實(shí)驗(yàn)結(jié)果、分析和結(jié)論（誤差分析