實 驗 報 告一、 實驗目的1. 掌握哈夫曼樹的基本概念及所用的存儲結(jié)構(gòu)。2. 掌握哈夫曼樹的建立算法。3. 掌握哈夫曼樹的應用（哈夫曼樹的編碼和譯碼）。二、 實驗內(nèi)容給定權(quán)值5、29、7、8、14、23、3、11，建立哈夫曼樹，輸出哈夫曼編碼。對上述給定的哈夫曼樹及得到的哈夫曼編碼，試輸入一串二進制編碼，輸出它的哈夫曼譯碼。三、 實驗與算法分析建立哈夫曼樹，將哈夫曼樹的機構(gòu)定義為一個結(jié)構(gòu)型的一維數(shù)組每個元素含有四項：權(quán)值、雙親、左孩子、右孩子。給定的權(quán)值可以從鍵盤輸入，要輸出所建立的哈夫曼樹，只要輸出表示哈夫曼樹的一維數(shù)組中的全部元素即可。要實現(xiàn)哈夫曼編碼，只要在所建立的哈夫曼樹上進行二進制編碼：往左走，編碼為0，往右走編碼為1，然后將從根結(jié)點到樹葉中的所有0,1排列起來，則得到該樹葉的哈夫曼編碼。哈夫曼編碼可以用一個結(jié)構(gòu)型的一維數(shù)組保存，每個元素包含：編碼，編碼的開始位置，編碼所對應的字符三項。哈夫曼譯碼，就是將輸入的譯碼還原成對應的字符。抽象的算法描述：將建立哈夫曼樹、實現(xiàn)哈夫曼編碼、哈夫曼譯碼都定義成子函數(shù)的的形式，然后在主函數(shù)中調(diào)用它們。哈夫曼樹的構(gòu)造：假設(shè)有n個權(quán)值，則構(gòu)造出的有n個葉子結(jié)點。n個權(quán)值分別設(shè)為w1,w2,wn，則哈夫曼樹的構(gòu)造規(guī)則為：（1）將w1,w2,wn看成是有n棵樹的森林（每棵樹僅有一個結(jié)點）；（2）在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左右子樹，且新樹的根結(jié)點權(quán)值為其左右子樹的根結(jié)點的權(quán)值之；（3）從森林中刪除選取的兩棵樹，并將新樹加入森林。（4）重復（2）、（3）步，直到森林中只剩一棵樹為止，該樹即為我們所求得的哈夫曼樹。四、 可執(zhí)行程序及注釋實驗代碼#include<iostream.h>#include<iomanip.h>const int n=8; /maxn表示葉子數(shù)目const int m=2*n-1; /m為森林中樹的棵數(shù)struct tree /哈夫曼樹中的一個結(jié)點float weight; /權(quán)值int parent; /雙親int lch,rch; /左孩子、右孩子;struct codetype /哈弗曼編碼int bitsn+1; /哈弗曼編碼int start; /編碼的存放位置char ch; /所對應的字符;tree hftreem+1;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;i<=n;i+)cin>>hftreei.weight; /輸入權(quán)值for(i=n+1;i<=m;i+) /進行次合并p1=p2=0; /p1,p2分別指向兩個權(quán)值最小的值的位置s1=s2=32767; /s1,s2代表兩個最小權(quán)值for(j=1;j<=i-1;j+) /選兩個最小值if(hftreej.parent=0) /該權(quán)值還沒有選中if(hftreej.weight<s1)s2=s1;s1=hftreej.weight;p2=p1;p1=j;else if(hftreej.weight<s2)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;int c,p;for(int i=1;i<=n;i+)cd.start=n+1;cd.ch=96+i; /第一個樹葉對應字母a，其余依此類推c=i;p=hftreei.parent;while(p!=0)cd.start-;if(hftreep.lch=c)cd.bitscd.start=0;elsecd.bitscd.start=1;c=p;p=hftreep.parent;codei=cd;for(i=1;i<=n;i+)cout<<"字符"<<codei.ch<<"的權(quán)值為："<<hftreei.weight<<setw(5)<<"編碼為："for(int j=codei.start;j<=n;j+)cout<<codei.bitsj<<" "cout<<endl;void trancode() /哈弗曼譯碼int i=m;char b;cout<<"請輸入一串二進制編碼（0、1以外的數(shù)結(jié)束）"<<endl;cin>>b;while(b=0)|(b=1)if(b=0)i=hftreei.lch;elsei=hftreei.rch;if(hftreei.lch=0)cout<<codei.ch;i=m;cin>>b;void main()creathuffmantree(); /建立哈夫曼樹huffcode(); /實現(xiàn)哈弗曼編碼trancode(); /進行哈弗曼譯碼cout<<endl;五、 實驗小結(jié)