數(shù)據(jù)結(jié)構哈夫曼樹C++實現(xiàn).doc
《數(shù)據(jù)結(jié)構哈夫曼樹C++實現(xiàn).doc》由會員分享,可在線閱讀,更多相關《數(shù)據(jù)結(jié)構哈夫曼樹C++實現(xiàn).doc(4頁珍藏版)》請在裝配圖網(wǎng)上搜索。
實 驗 報 告一、 實驗目的1. 掌握哈夫曼樹的基本概念及所用的存儲結(jié)構。2. 掌握哈夫曼樹的建立算法。3. 掌握哈夫曼樹的應用(哈夫曼樹的編碼和譯碼)。二、 實驗內(nèi)容給定權值5、29、7、8、14、23、3、11,建立哈夫曼樹,輸出哈夫曼編碼。對上述給定的哈夫曼樹及得到的哈夫曼編碼,試輸入一串二進制編碼,輸出它的哈夫曼譯碼。三、 實驗與算法分析建立哈夫曼樹,將哈夫曼樹的機構定義為一個結(jié)構型的一維數(shù)組每個元素含有四項:權值、雙親、左孩子、右孩子。給定的權值可以從鍵盤輸入,要輸出所建立的哈夫曼樹,只要輸出表示哈夫曼樹的一維數(shù)組中的全部元素即可。要實現(xiàn)哈夫曼編碼,只要在所建立的哈夫曼樹上進行二進制編碼:往左走,編碼為0,往右走編碼為1,然后將從根結(jié)點到樹葉中的所有0,1排列起來,則得到該樹葉的哈夫曼編碼。哈夫曼編碼可以用一個結(jié)構型的一維數(shù)組保存,每個元素包含:編碼,編碼的開始位置,編碼所對應的字符三項。哈夫曼譯碼,就是將輸入的譯碼還原成對應的字符。抽象的算法描述:將建立哈夫曼樹、實現(xiàn)哈夫曼編碼、哈夫曼譯碼都定義成子函數(shù)的的形式,然后在主函數(shù)中調(diào)用它們。哈夫曼樹的構造:假設有n個權值,則構造出的有n個葉子結(jié)點。n個權值分別設為w1,w2,wn,則哈夫曼樹的構造規(guī)則為:(1)將w1,w2,wn看成是有n棵樹的森林(每棵樹僅有一個結(jié)點);(2)在森林中選出兩個根結(jié)點的權值最小的樹合并,作為一棵新樹的左右子樹,且新樹的根結(jié)點權值為其左右子樹的根結(jié)點的權值之;(3)從森林中刪除選取的兩棵樹,并將新樹加入森林。(4)重復(2)、(3)步,直到森林中只剩一棵樹為止,該樹即為我們所求得的哈夫曼樹。四、 可執(zhí)行程序及注釋實驗代碼#include#includeconst int n=8; /maxn表示葉子數(shù)目const int m=2*n-1; /m為森林中樹的棵數(shù)struct tree /哈夫曼樹中的一個結(jié)點float weight; /權值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個權值endl;for(i=1;ihftreei.weight; /輸入權值for(i=n+1;i=m;i+) /進行次合并p1=p2=0; /p1,p2分別指向兩個權值最小的值的位置s1=s2=32767; /s1,s2代表兩個最小權值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;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的權值為: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ù)結(jié)束)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;五、 實驗小結(jié)- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞:
- 數(shù)據(jù)結(jié)構 哈夫曼樹 C+ 實現(xiàn)
裝配圖網(wǎng)所有資源均是用戶自行上傳分享,僅供網(wǎng)友學習交流,未經(jīng)上傳用戶書面授權,請勿作他用。
相關資源
更多
正為您匹配相似的精品文檔
相關搜索
鏈接地址:http://www.szxfmmzy.com/p-6635512.html