1、 專業(yè)：計算機(jī)科學(xué)與技術(shù) 班級：計算機(jī)09-1 姓名： * 學(xué)號： 20 指導(dǎo)老師：陳* 評分：實(shí)驗(yàn)四 哈夫曼樹的建立及應(yīng)用一、 實(shí)驗(yàn)?zāi)康?、 掌握哈夫曼樹的基本概念及所有的存儲結(jié)構(gòu)。2、 掌握哈夫曼樹的建立算法。3、 掌握哈夫曼樹的應(yīng)用（哈夫曼編碼和譯碼）。二、 實(shí)習(xí)內(nèi)容1、 給定權(quán)值5，29，7，8，14，23，3，11，建立哈夫曼樹，輸出哈夫曼編碼。2、對上述給定的哈夫曼樹及得到的哈夫曼編碼，試輸入一串二進(jìn)制編碼，輸出它的哈夫曼譯碼。三、算法描述將建立哈夫曼樹、實(shí)現(xiàn)哈夫曼編碼、哈夫曼譯碼都定義成子函數(shù)的形式，然后在主函數(shù)中調(diào)用它們。建立哈夫曼樹時，將哈夫曼樹的結(jié)構(gòu)定義為一個結(jié)構(gòu)型的一維數(shù)

2、組，每個元素含有四項(xiàng)：權(quán)值，雙親，左孩子，右孩子。給定的權(quán)值可以從鍵盤輸入，要輸出所建立的哈夫曼樹，只要輸出表示哈夫曼樹的一維數(shù)組中的全部元素即可。要實(shí)現(xiàn)哈夫曼編碼，只要在所建立的哈夫曼樹上進(jìn)行二進(jìn)制編碼：往左走，編碼為0，往右走，編碼為1，然后將從根結(jié)點(diǎn)到樹葉中的所有0、1排列起來，則得到該樹葉的哈夫曼編碼。哈夫曼編碼可以用一個結(jié)構(gòu)型的一維數(shù)組保存，每個元素包含：編碼、編碼的開始位置、編碼所對應(yīng)的字符三項(xiàng)。程序清單：#include#includeconst int n=8;const int m=2*n-1;struct treefloat weight; int parent; int

3、lch,rch;struct codetypeint bitsn+1; int start; char ch;tree hftreem+1;struct codetype coden+1;void creathuffmantree()int i,j,p1,p2; float s1,s2; for(i=1;i=m;i+) hftreei.parent=0; hftreei.lch=0; hftreei.rch=0; hftreei.weight=0; cout輸入n個權(quán)值endl; for(i=1;ihftreei.weight; for(i=n+1;i=m;i+) p1=p2=0; s1=s2

4、=32767; for(j=1;j=i-1;j+) if(hftreej.parent=0) if(hftreej.weights1) s2=s1; s1=hftreej.weight; p2=p1; p1=j; else if(hftreej.weights2) s2=hftreej.weight;p2=j; hftreep1.parent=i; hftreep2.parent=i; hftreei.lch=p1; hftreei.rch=p2; hftreei.weight=hftreep1.weight+hftreep2.weight;void huffcode()codetype cd

5、; int c,p; for(int i=1;i=n;i+) cd.start=n+1; cd.ch=96+i; c=i; p=hftreei.parent; while(p!=0) cd.start-; if(hftreep.lch=c)cd.bitscd.start=0; else cd.bitscd.start=1; c=p; p=hftreep.parent; codei=cd; for(i=1;i=n;i+) cout字符codei.ch的權(quán)值為：hftreei.weightsetw(5)編碼為：; for(int j=codei.start;j=n;j+) coutcodei.bitsj ; coutendl;void trancode()int i=m;char b; coutb; while(b=0)|(b=1) if(b=0)i=hftreei.lch; else i=hftreei.rch; if(hftreei.lch=0) coutb;void main()creathuffmantree(); huffcode(); trancode();運(yùn)行結(jié)果：結(jié)果分析（心得體會）：上網(wǎng)找了相