哈夫曼編碼_貪心算法.doc

淮海工學(xué)院計(jì)算機(jī)工程學(xué)院實(shí)驗(yàn)報(bào)告書(shū)課程名： 算法分析與設(shè)計(jì) 題 目： 實(shí)驗(yàn)3 貪心算法 哈夫曼編碼 班 級(jí)： 軟件102班 學(xué) 號(hào)： 11003215 姓 名： 鹿 迅 評(píng)語(yǔ)：成績(jī)： 指導(dǎo)教師： 批閱時(shí)間： 年 月 日 算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告 - 4 -實(shí)驗(yàn)3 貪心算法實(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)編碼方案。 實(shí)驗(yàn)環(huán)境 Turbo C 或VC+實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)，必做實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)與算法struct huffmandouble weight; /用來(lái)存放各個(gè)結(jié)點(diǎn)的權(quán)值int lchild,rchild,parent; /指向雙親、孩子結(jié)點(diǎn)的指針;核心源代碼#include#include using namespace std;struct huffmandouble weight;int lchild,rchild,parent;static int i1=0,i2=0;int Select(huffman huff,int i)int min=11000;int min1;for(int k=0;ki;k+)if(huffk.weightmin&huffk.parent=-1)min=huffk.weight; min1=k;huffmin1.parent=1;return min1;void HuffmanTree(huffman huff,int weight,int n)for(int i=0;i2*n-1;i+)huffi.lchild=-1;huffi.parent=-1;huffi.rchild=-1;for(int l=0;ln;l+)huffl.weight=weightl;for(int k=n;k2*n-1;k+)int i1=Select(huff,k);int i2=Select(huff,k);huffi1.parent=k;huffi2.parent=k;huffk.weight=huffi1.weight+huffi2.weight;huffk.lchild=i1;huffk.rchild=i2;void huffmancode(huffman huff,int n) string s;int j;for(int i=0;in;i+)s=;j=i;while(huffj.parent!=-1)if(huffhuffj.parent.lchild=j)s=s+0;else s=s+1;j=huffj.parent;couti+1=0;j-) coutsj; coutendl;void main() huffman huff20;int n,w20;coutn;coutinput the weight:;for(int i=0;iwi; HuffmanTree(huff,w,n); huffmancode(huff,n);實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)體會(huì)哈夫曼編碼算法：每次將集合中兩個(gè)權(quán)值最小的二叉樹(shù)合并成一棵新二叉樹(shù)，n-1次合并后，成為最終的一棵哈夫曼樹(shù)。這既是貪心法的思想：從某一個(gè)最初狀態(tài)出發(fā)，根據(jù)當(dāng)前的局部最優(yōu)策略，以滿足約束方程