《數(shù)據(jù)結構哈夫曼樹C++實現(xiàn)》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構哈夫曼樹C++實現(xiàn)（5頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、實驗報告一、 實驗目的1. 掌握哈夫曼樹的基本概念及所用的存儲結構。2. 掌握哈夫曼樹的建立算法。3. 掌握哈夫曼樹的應用（哈夫曼樹的編碼和譯碼） 。二、 實驗內容給定權值 5、 29、 7、 8、 14、 23、 3、 11，建立哈夫曼樹，輸出哈夫曼編碼。對上述給定的哈夫曼樹及得到的哈夫曼編碼， 試輸入一串二進制編碼， 輸出它的 哈夫曼譯碼。 三、 實驗與算法分析建立哈夫曼樹， 將哈夫曼樹的機構定義為一個結構型的一維數(shù)組每個元素含有四項：權值、雙親、左孩子、右孩子。給定的權值可以從鍵盤輸入，要輸出所建立的哈夫曼樹，只要輸出表示哈夫曼樹的一維數(shù)組中的全部元素即可。要實現(xiàn)哈夫曼編碼，只要在所建立

2、的哈夫曼樹上進行二進制編碼：往左走，編碼為0，往右走編碼為1，然后將從根結點到樹葉中的所有0,1 排列起來，則得到該樹葉的哈夫曼編碼。 哈夫曼編碼可以用一個結構型的一維數(shù)組保存， 每個元素包含：編碼，編碼的開始位置，編碼所對應的字符三項。哈夫曼譯碼，就是將輸入的譯碼還原成對應的字符。抽象的算法描述： 將建立哈夫曼樹、 實現(xiàn)哈夫曼編碼、 哈夫曼譯碼都定義成子函數(shù)的的形式， 然后在主函數(shù)中調用它們。 哈夫曼樹的構造： 假設有 n 個權值，則構造出的有n個葉子結點。n個權值分別設為w1,w2,wn,則哈夫曼樹的構造規(guī)則為：（1）將w1,w2,wn看成是有n棵樹的森林（每棵樹僅有一個結點） ； （ 2

3、）在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左右子樹， 且新樹的根結點權值為其左右子樹的根結點的權值之； （ 3） 從森林中刪除選取的兩棵樹，并將新樹加入森林。（ 4）重復（2） 、 （ 3）步，直到森林中只剩一棵樹為止，該樹即為我們所求得的哈夫曼樹。四、 可執(zhí)行程序及注釋實驗代碼#include#includeconst int n=8; /maxn 表示葉子數(shù)目const int m=2*n-1; /m 為森林中樹的棵數(shù)struct tree/哈夫曼樹中的一個結點float weight; / 權值 int parent; /雙親 int lch,rch; /左孩子、右孩子;

4、 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個權值endl;for(i=1;ihftreei.weight;/輸入權值p1=p2=0;s

5、1=s2=32767;for(j=1;j=i-1;j+)for(i=n+1;i=m;i+)/進行次合并/p1,p2 分別指向兩個權值最小的值的位置/s1,s2代表兩個最小權值/選兩個最小值 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;

6、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+)(co

7、ut字 符codei.ch 的 權 值 為hftreei.weightsetw(5)編碼為：;for(int j=codei.start;j=n;j+)coutcodei.bitsj;coutendl;void trancode()/哈弗曼譯碼(int i=m;char b;cout請輸入一審二進制編碼(0、1以外的數(shù)結束)b;while(b=0)|(b=1)(if(b=0)i=hftreei.lch;elsei=hftreei.rch;if(hftreei.lch=0)(coutb;void main()creathuffmantree(); 建立哈夫曼樹huffcode();/實現(xiàn)哈弗曼編碼trancode();/進行哈弗曼譯碼coutendl;實驗小結