數(shù)據(jù)結(jié)構(gòu)——實驗四哈夫曼樹與哈夫曼編碼.doc

《數(shù)據(jù)結(jié)構(gòu)——實驗四哈夫曼樹與哈夫曼編碼.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、軟件學(xué)院哈夫曼樹與哈夫曼編碼實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)姓名：鄭斌學(xué)號：7班級：卓越131實驗四哈夫曼樹與哈夫曼編碼一、實驗?zāi)康?、使學(xué)生熟練掌握哈夫曼樹的生成算法。2、熟練掌握哈夫曼編碼的方法。二、實驗內(nèi)容本次實驗提供3個題目，難度相當，學(xué)生可以根據(jù)自己的情況選做，其中題目一是必做題，其它選作！題目一、哈夫曼樹和哈夫曼編碼[問題描述]　一電文，有若干個不同字符，要求從終端輸入這些不同字符及其出現(xiàn)的頻率，然后對這些字符進行哈夫曼編碼，并輸出。［測試數(shù)據(jù)］利用教材P.148例6－2中的數(shù)據(jù)調(diào)試程序(可自己設(shè)定測試數(shù)據(jù))。[選作內(nèi)容]1、打印出該哈夫曼樹2、若從終端輸入

2、任意一段電文（假設(shè)僅為26個大小寫英文字母）,試編程高效地求出該段電文的哈夫曼編碼。提示：如何快速統(tǒng)計不同字符的出現(xiàn)頻率3、譯碼：將上述1的編碼結(jié)果還原成電文。三、算法設(shè)計1)本程序包含三個模塊1．voidSelect(HuffmanTreeHT,inti,int&s1,int&s2)//選擇函數(shù)2．voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)w存放n個權(quán)值,構(gòu)造哈夫曼樹p,3．VoidHuffmancode(HuffmanTree&HT,HuffmanCode&HC,intn)求出哈夫曼編

3、碼hc并輸出哈弗曼編碼四、實驗結(jié)果圖1-1輸入哈弗曼樹的權(quán)值圖1-2顯示哈弗曼樹表與其編碼五、總結(jié)通過做哈弗曼樹實驗讓對最優(yōu)二叉樹這種結(jié)構(gòu)有了更深的了解和應(yīng)用，對我以后的編程產(chǎn)生了比較深遠的影響。六、源程序（帶注釋）#include#include#include#include#includeusingnamespacestd;typedefstruct{intweight;intparent,lchild,rchild;charcharr;}HTNode,*Huff

4、manTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,inti,int&s1,int&s2){intj,k=1;while(HT[k].parent!=0)k++;s1=k;for(j=1;j<=i;++j)if(HT[j].parent==0&&HT[j].weight

5、

6、k==s1))k++;s2=k;for(j=1;j<=i;++j)if(HT[j].parent==0&&HT[j].weight

7、2].weight&&j!=s1)s2=j;}voidHuffmanCoding(HuffmanTree&HT,int*w,intn){intm,i,s1,s2;if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(i=1;i<=n;++i){HT[i].weight=w[i];HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;}for(i=n+1;i<=m;++i){HT[i].weight=0;HT[i].lchild=0;HT[i

8、].rchild=0;HT[i].parent=0;}//構(gòu)建哈弗曼樹for(i=n+1;i<=m;++i){Select(HT,i-1,s1,s2);//選擇parent為0且weight最小的兩個結(jié)點，期序號分別為s1，s2HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}cout<<"哈弗曼樹表如下："<

9、d"<weight<parent<lchild<rchild<

10、r[n];