哈夫曼編譯碼器實驗報告

1、精品文檔實驗五 哈夫曼編/譯碼器學(xué)院: 工學(xué)院 系: 計算機系 專業(yè): 計算機科學(xué)與技術(shù) 年級: 2009姓名: 學(xué)號: 完成實驗時間: 2011-5-19一 需求分析1.問題描述用huffman編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。是為著這樣的信息收發(fā)站寫一個huffman編/譯碼系統(tǒng)。2.基本要求該系統(tǒng)應(yīng)具有以下功能：（1） i：初始化（initialization）。從終端讀入字符集大小n

2、,以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存進文件hfmtree中。（2） e：編碼（encoding）。利用建好的哈夫曼樹（如不在內(nèi)存中，則從文件hfmtree中讀入），對文件tobetran中的正文進行編碼，然后將結(jié)果存入文件codefile中。（3） d：譯碼(decoding)。(利用已經(jīng)建好的哈夫曼樹將文件codefile中的代碼進行譯碼，結(jié)果存入文件textfile中。（4） p：印代碼文件(print)。將文件codefile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件codeprin中。（5） t：印哈夫曼樹(tree printing)。將已

3、在內(nèi)存中的哈夫曼樹以直觀的方式（凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件treeprin中。3.測試數(shù)據(jù)（1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計哈夫曼編碼。（2）用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“this promgram is my favorite”。字符abcdefghijklm頻度1866413223210321154757153220字符nopqrstuvwxyz頻度576315148

4、5180238181161二概要設(shè)計本程序的數(shù)據(jù)類型定義為typedef struct unsigned int weight; unsigned int parent,lchild,rchild; htnode,*huffmantree;typedef char* huffmancode;所實現(xiàn)的功能函數(shù)如下void inithuffmantree();/選擇初始化哈夫曼樹的方式int openfileinit();/通過打開的data.txt文件初始化哈夫曼樹 該文件是為了測試數(shù)據(jù)2 包涵26個字符int inputinit();/通過手動輸入字符初始化哈夫曼樹int huffmancod

5、ing(int *w); /初始化哈夫曼數(shù)，按照哈夫曼規(guī)則建立二叉樹。此函數(shù)塊調(diào)用了select（）函數(shù)。void select(int j,int &s1,int &s2); /選擇parent為0，且weight最小的兩個節(jié)點 序號為s1，s2void encoding();/選擇哈夫曼編碼方式void openfileenco();/通過打開文件encode.txt的方式進行編碼void inputenco();/通過手動輸入的方式進行編碼void decode();/選擇譯碼方式void openfiledeco();/通過打開文件codefile.txt的方式進行譯碼void inp

6、utdeco();/通過手動輸入的方式進行譯碼void dispht( huffmantree noderoot, int level ); /以縮進方式輸出哈夫曼樹直觀圖主函數(shù)主函數(shù)主要設(shè)計的是一個分支語句，讓用戶挑選所實現(xiàn)的功能。如圖所示：inithuffmantree();初始化哈夫曼樹huffmancoding()構(gòu)造哈夫曼樹編碼調(diào)用encoding()譯碼調(diào)用decode（）dispht()打印哈夫曼樹select（）供huffmancoding()調(diào)用三詳細設(shè)計#include#include#includeusing namespace std;ofstream outstuf;

7、typedef struct unsigned int weight;值得下載 unsigned int parent,lchild,rchild; htnode,*huffmantree;typedef char* huffmancode; huffmantree ht=null;int n=0;huffmancode hc=null;char *ch=null;void inithuffmantree();int openfileinit();int inputinit();int huffmancoding(int *w);void select(int j,int &s1,int &s

8、2);void encoding();void openfileenco();void inputenco();void decode();void openfiledeco();void inputdeco();void dispht( huffmantree noderoot, int level );void inithuffmantree() /選擇初始化哈夫曼樹 int sel=0; for(;) coutt*endl; coutt* 字符集及權(quán)值來源ttttt*endl; coutt*t1.使用權(quán)值文件data.txt進行編碼ttt*endl; coutt*t2.自行輸入字符集及權(quán)

9、值tttt*endl; coutt*t3.返回上層ttttt*endl; coutt*endl; cout請輸入您的選擇endlsel; if(sel=3) break; switch(sel) case 1:openfileinit();break; case 2:inputinit();break; default:cout對不起，您輸入的數(shù)據(jù)有誤！請重新輸入。endl; ; int openfileinit() /通過打開的data.txt文件初始化哈夫曼樹 該文件是為了測試數(shù)據(jù)2 包涵26個字符 int *w=(int*)malloc(28*sizeof(int); ch=(char*

10、)malloc(28*sizeof(char); n=27; ifstream infile(data.txt,ios:in); if(!infile) cerropen error!endl; exit(1); cout 權(quán)值文件中的信息（#代表空格）endlchi; infilewi; coutendl; infile.close(); cout 字符:; for(i=1;i10;i+) coutchit; cout 權(quán)值:; for(i=1;i10;i+) coutwit; cout 字符:; for(i=10;i19;i+) coutchit; cout 權(quán)值:; for(i=10;i

11、19;i+) coutwit; cout 字符:; for(i=19;i28;i+) coutchit; cout 權(quán)值:; for(i=19;i28;i+) coutwit; coutendl; n=27; huffmancoding(w); cout 各字符編碼如下：endl; for(i=1;i=27;i+) cout chit; couthciendl; ; outstuf.open(code.txt,ios:out); for(i=1;i=27;i+) outstufchi;outstufhci; /將各個字符的編碼寫入文件code.txtoutstuf.close(); retur

12、n 0; int inputinit() /通過手動輸入字符初始化哈夫曼樹 coutn; int *w=(int *)malloc(n+1)*sizeof(int); if(!w) couterror;return 0; ch=(char *)malloc(n+1)*sizeof(char); if(!ch) couterror;return 0; cout 請輸入各字符t; for(int i=1;ichi; cout 請輸入各權(quán)值t; for(i=1;iwi; /outstuf.close(); outstuf.open(hfmtree.txt,ios:out); for(i=1;i=n;

13、i+)outstufchi; outstufwi; /將各個字符的權(quán)值寫入文件hfmtree.txt coutendl; huffmancoding(w); cout 各字符編碼如下：; for(i=1;i=n;i+) cout chit; couthci; ; outstuf.close(); outstuf.open(code.txt,ios:out); for(i=1;i=n;i+)outstufchi; outstufhci;/將各個字符的編碼寫入文件code.txt coutendl;outstuf.close(); return 0;int huffmancoding(int *w

14、) /哈夫曼編碼 if(n=1) return 1; int m=2*n-1; ht=(huffmantree)malloc(m+1)*sizeof(htnode); if(!ht) couterror;return 0; for(int i=1; i=n; +i) hti.weight=wi; hti.parent=hti.lchild=hti.rchild=0; for(;i=m; +i) hti.weight=hti.parent=hti.lchild=hti.rchild=0; int s1=0; int s2=0; for(i=n+1;i=m; +i) select(i-1, s1,

15、 s2); hts1.parent=i; hts2.parent=i; hti.lchild=s1; hti.rchild=s2; hti.weight=hts1.weight+ hts2.weight; hc=(huffmancode)malloc(n+1)*sizeof(char*); char *cd=(char*) malloc(n*sizeof(char); if(!cd) couterror;return 0; cdn-1=0; int start; for(i=1;i=n;+i) start=n-1; for(int c=i,unsigned int f=hti.parent;f

16、!=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); free(cd); return 0;void select(int j,int &s1,int &s2) /選擇parent為0，且weight最小的兩個節(jié)點 序號為s1，s2 for(int h=1;h=j;h+) if(hth.parent=0) s1=h;break; h+; for(;hhts2.weight) m=s1;s1

17、=s2;s2=m; h+; for(;hhth.weight&hth.parent=0) s1=h; for(m=1;mhtm.weight&m!=s1&htm.parent=0) s2=m;void encoding() /選擇哈夫曼編碼方式 int sel=0; for(;) if(!ht) cout對不起，哈夫曼樹不存在！請先建立哈夫曼樹。endl; break; coutt*endl; coutt* 要編碼的文件來源ttttt*endl; coutt*t1.使用已有文件encode.txt進行編碼tt*endl; coutt*t2.自行輸入文件進行編碼tttt*endl; coutt*

18、t3.返回上層ttttt*endl; coutt*endl; cout請輸入您的選擇endlsel; if(sel=3) break; switch(sel) case 1:openfileenco();break; case 2:inputenco();break; default:cout對不起，您輸入的數(shù)據(jù)有誤！請重新輸入。endl; void openfileenco() /通過打開文件encode.txt的方式進行編碼 cout encode.txt文件內(nèi)容如下（#代表空格）：endl; ifstream infile(encode.txt,ios:in); if(!infile)

19、cerropen error!filei; coutfilei; coutfilei; infile.close(); coutendl; int m=i; cout 編碼結(jié)果是：endl; /outstuf.close(); outstuf.open(codefile.txt,ios:out); for(i=1;im-1;i+) for(int j=1;j=n;j+)if(filei=chj) couthcj; outstufhcj;break;/將編碼結(jié)果寫入 codefile.txt if(j=(n+1) coutendl此處編碼出現(xiàn)錯誤，含有不可編碼的字符！endl; break; c

20、outendl; outstuf.close();void inputenco() /通過手動輸入的方式進行編碼 cout 請輸入您要編碼的文章（以$作為文章結(jié)尾）endl; char *file=(char *)malloc(200*sizeof(char); for(int i=1;ifilei; if(filei=$) break; if(i=200) file=(char *)realloc(file,(200+80)*sizeof(char); for(;ifilei; if(filei=$) break; int m=i; cout 編碼結(jié)果是：endl; /outstuf.clo

21、se(); outstuf.open(codefile.txt,ios:out); for(i=1;im;i+) for(int j=1;j=n;j+)if(filei=chj) couthcj;outstufhcj; break;/將編碼結(jié)果寫入 codefile.txt if(j=(n+1) coutendl此處編碼出現(xiàn)錯誤，含有不可編碼的字符！endl; break; coutendl; outstuf.close(); void decode() /選擇譯碼方式 int sel=0; for(;) if(!ht) cout對不起，哈夫曼樹不存在！請先建立哈夫曼樹。endl; break

22、; coutt*endl; coutt* 要譯碼的文件來源ttttt*endl; coutt*t1.使用已有文件codefile.txt進行譯碼tt*endl; coutt*t2.自行輸入文件進行譯碼tttt*endl; coutt*t3.返回上層ttttt*endl; coutt*endl; cout請輸入您的選擇endlsel; if(sel=3) break; switch(sel) case 1:openfiledeco();break; case 2:inputdeco();break; default:cout對不起，您輸入的數(shù)據(jù)有誤！請重新輸入。endl; void inputd

23、eco() /通過手動輸入的方式進行譯碼 int m=2*n-1; char *password=(char *)malloc(200*sizeof(char); cout 請輸入要譯碼的文件(以$結(jié)束）endl; for(int i=1;ipasswordi; if(i=200) password=(char *)realloc(password,(200+80)*sizeof(char); for(;ipasswordi; cout譯碼結(jié)果為（#代表空格）endl; /outstuf.close(); outstuf.open(textfile.txt,ios:out); for(i=1;

24、passwordi!=$;) char record20; for(int j=0,q=i;passwordq!=$;j+,q+) if(passwordq=0) recordj=0;m=htm.lchild; else recordj=1;m=htm.rchild; if(htm.rchild=0) recordj+1=0;break; if(htm.rchild!=0) coutendl譯碼在此處出現(xiàn)錯誤！此處不可譯碼！endl; break; for(int p=1;p=n;p+) if(!strcmp(record,hcp) outstufchp; coutchp;break; i=i

25、+strlen(record); m=2*n-1; coutendl; outstuf.close();void openfiledeco() /通過打開文件codefile.txt的方式進行譯碼 int m=2*n-1; cout codefile.txt文件內(nèi)容如下：endl; ifstream infile(codefile.txt,ios:in); if(!infile) cerropen error!passwordi; coutpasswordi; coutpasswordi; infile.close(); password+i=$; coutendl; cout譯碼結(jié)果為（#代

26、表空格）endl; /outstuf.close(); outstuf.open(textfile.txt,ios:out); for(i=1;passwordi!=$;) char record20; for(int j=0,q=i;passwordq!=$;j+,q+) if(passwordq=0) recordj=0;m=htm.lchild; else recordj=1;m=htm.rchild; if(htm.rchild=0) recordj+1=0;break; if(htm.rchild!=0) coutendl譯碼在此處出現(xiàn)錯誤！此處不可譯碼！endl; break; f

27、or(int p=1;p=n;p+) if(!strcmp(record,hcp) outstufchp;coutchp;break; i=i+strlen(record); m=2*n-1; coutrchild) dispht(ht+noderoot-rchild,level+1); for(int i=0;ilevel;i+) if(ilevel-1)cout ;outstuf ;else cout-;outstuf-; coutweightendl; outstufweightlchild!=0 ) dispht(ht+noderoot-lchild,level+1); int main() int sel=0; cout歡迎使用哈夫曼編碼/譯碼器-endl; for(;) coutt*endl; coutt*t1.構(gòu)建哈夫曼樹ttttt*endl; coutt*t2.輸出哈夫曼樹ttttt*endl; coutt*t3.編碼tttttt*endl; coutt*t4.譯碼tttttt*endl; coutt*t5.退出tttttt*endl; coutt*endl; co