《數(shù)據(jù)結(jié)構(gòu)——實驗四哈夫曼樹與哈夫曼編碼(共6頁).doc》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)——實驗四哈夫曼樹與哈夫曼編碼(共6頁).doc（6頁珍藏版）》請在匯文網(wǎng)上搜索。

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

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

3、amp;HT,HuffmanCode &HC,int n)求出哈夫曼編碼hc并輸出哈弗曼編碼4、 實驗結(jié)果圖1-1 輸入哈弗曼樹的權(quán)值圖1-2 顯示哈弗曼樹表與其編碼五、總結(jié)通過做哈弗曼樹實驗讓對最優(yōu)二叉樹這種結(jié)構(gòu)有了更深的了解和應(yīng)用，對我以后的編程產(chǎn)生了比較深遠的影響。六、源程序（帶注釋）#include<iostream>#include<iomanip>#include<stdlib.h>#include<string.h>#include<stdio.h>using namespace std;typedef stru

4、ct int weight; int parent,lchild,rchild;char charr;HTNode,*HuffmanTree;typedef char *HuffmanCode;void Select(HuffmanTree HT,int i,int &s1,int &s2) int j,k=1; while(HTk.parent!=0)k+;s1=k;for(j=1;j<=i;+j)if(HTj.parent=0&&HTj.weight<HTs1.weight)s1=j;k=1;while(HTk.parent!=0|k=s1)k+

5、;s2=k;for(j=1;j<=i;+j)if(HTj.parent=0&&HTj.weight<HTs2.weight&&j!=s1)s2=j;void HuffmanCoding(HuffmanTree &HT,int *w,int n)int m,i,s1,s2;if(n <= 1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc(m + 1) * sizeof(HTNode);for(i = 1;i <= n;+i)HTi.weight = wi;HTi.lchild = 0;

6、HTi.rchild = 0;HTi.parent = 0;for(i = n + 1;i <= m;+i)HTi.weight = 0;HTi.lchild = 0;HTi.rchild = 0;HTi.parent = 0;/構(gòu)建哈弗曼樹 for(i = n + 1;i <= m;+i)Select(HT,i - 1,s1,s2);/選擇parent為0且weight最小的兩個結(jié)點，期序號分別為s1，s2 HTs1.parent = i;HTs2.parent = i;HTi.lchild = s1; HTi.rchild = s2;HTi.weight = HTs1.weig

7、ht + HTs2.weight;cout<<"n哈弗曼樹表如下："<<endl;/打印哈弗曼樹表cout<<" i weight parent lchild rchild"<<endl;HuffmanTree p;for(p=HT+1,i=1;i<=m;i+,p+)cout<<setw(2)<<i<<setw(7)<<p->weight<<setw(6)<<p->parent<<setw(7)<&l

8、t;p->lchild<<setw(8)<<p->rchild<<endl;void Huffmancode(HuffmanTree &HT,HuffmanCode &HC,int n)char *cd;int c,f,start; int i;HC = (HuffmanCode)malloc(n + 1) * sizeof(char *);cd = new charn;cdn - 1 = '0'/編碼結(jié)束標志 for(i = 1;i <= n;+i)start = n - 1;for(c = i,f = H

9、Ti.parent;f != 0;c = f,f =HTf.parent)if(HTf.lchild = c)cd-start = '0'else cd-start = '1'HCi = (char *)malloc(n - start) * sizeof(char);strcpy(HCi,&cdstart);cout << endl; cout<<"哈夫曼編碼如下:"for(i=1;i<=n;+i)/逐個字符求赫夫曼編碼 start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f

10、=HTf.parent)/從葉子到根逆向求編碼if(HTf.lchild=c)cd-start='0'elsecd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);/為第i個字符編碼分配空間strcpy(HCi,&cdstart);/從cd復(fù)制編碼到HC printf("nHT%d 節(jié)點的哈夫曼編碼是: %s 對應(yīng)權(quán)值為：%d",i,HCi,HTi.weight);cout<<endl;free(cd);int main()HuffmanTree HT;HuffmanCod

11、e HC;int *w;char *e;char c;int i,n,m,wei;cout << "-請輸入哈弗曼樹的帶權(quán)數(shù)目-" << endl;cin >> n;w = new intn + 1;e = new charn + 1;for(i = 1;i <= n;i+)cout << "-請輸入第" << i << "個元素的權(quán)值-"cin >> wei;wi = wei;HuffmanCoding(HT,w,n);m = 2 * n - 1;Huffmancode(HT,HC,n);return 0;