哈夫曼編碼算法實現(xiàn)完整版

1、實驗三樹的應用.實驗題目：樹的應用一一哈夫曼編碼二. 實驗內容：利用哈夫曼編碼進行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r間，降低傳輸本錢。 根據(jù)哈夫曼編碼的原理，編寫一個程序，在用戶輸入結點權值的根底上求哈夫曼編碼。要求：從鍵盤輸入假設干字符及每個字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結點的權值，建立 哈夫曼樹，然后對各個字符進行哈夫曼編碼，最后打印輸出字符及對應的哈夫曼編碼。I l.kV.-a/ 打 | .三、程序源代碼：#i nclude#in clude#i ncludevstri ng.h#in cludetypedefstructchardata;in tweight;in t

2、pare nt,lchild,rchild;HTNode,*Huffma nTree;typedefchar*Huffma nCode;voidSelect(Huffma nTree&H T,i ntn ,i ntm)Huffma nTreep二HT;in ttmp;for(i ntj二n+1;j=m;j+)in ttag1,tag2,s1,s2;tag仁tag2=32767;for(i ntx=1;x二j-1;x+)if(px.pare nt=0&px.weighttag1)tag1=px.weight;s1=x;for(i nty=1;y二j-1;y+)if(py.pare nt=0&y

3、!=s1 &py.weights2) 將選出的兩個節(jié)點中的序號較小的始終賦給tmp二s1;s1=s2;s2二tmp;ps1.pare nt二j;ps2.pare nt二j;pj.lchild=s1;pj.rchild=s2;pj.weight二ps1.weight+ps2.weight;voidHuffma nCodi ng(Huffma nTree&H T,i ntn ,char*w1,i nt*w2)in tm=2* n-1;if(n=1)return;HT=(Huffma nTree)malloc(m+1)*sizeof(HTNode);Huffma nTreep二HT;for(i nt

4、i=1;i 二n ;i+) pi.data=w1i-1;pi.weight=w2i;pi.pare nt=pi.lchild二pi.rchild=O; for(;i=m;i+)pi.weight=pi.pare nt=pi.lchild二pi.rchild=O;Select(HT ,n ,m);ofstreamoutfile;/ 生成 hfmTree 文件 outfile.ope n( hfmTree.txt,ios:out);for(i=1;i=m;i+)outfilevHTi.weightvvtvvHTi.pare ntvvtvHTi.lchild vvtvHTi.rchildvvtvve

5、 ndl;outfile.close();coutvv初始化結果已保存在hfmTree文件中n;voidToBeTree() /將正文寫入文件ToBeTree中ofstreamoutfile;outfile.ope n(ToBeTree.txt,ios:out); outfileTHISPROGRAMISM YFAVORITE; outfile.close();voidE ncodi ng(Hufma nTree&H T,i ntn)編碼Huffma nCodeHC;HC=(Huffma nCode)malloc( n+1)*sizeof(char*); char*cd;cd=(char*)m

6、alloc( n*sizeof(char);cd n-1=0：for(i ntk=1;k 二n ;k+)in tstart 二n -1;for(i ntc二k,f=HTk.pare nt;f!=O;c=f,f=HTf.pare nt) if(HTf.lchild=c)cd-start=O： elsecd-start=1;HCk=(char*)malloc( n-start)*sizeof(char); strcpy(HCk,&cdstart);cout輸出哈夫曼編碼:endl;for(in th=1;h=n;h+)/ 輸出編碼coutHTh.data:; coutHCh;coutvv;if(h

7、%8=0)coute ndl;coutendlvv輸出正文編碼:endl;ToBeTree();/讀取TOBETREE文件里的正文，并進行編碼fstreami nfile;in file.ope n(ToBeTree.txt,ios:i n);chars80;while(!i nfile.eof()in file.getli ne(s,sizeof(s);in file.close();fstreamoutfile;outfile.ope n(CodeFile.txt,ios:out);in tco un t=0;for(h=0;sh!=0;h+)for(k=1;k=n ;k+) if(sh=

8、HTk.data)coutHCk;coutvv;coun t+;outfileHCk;break;if(count%9=0)coutendl;/每輸出 7 個換行outfile.close();coutn編碼結果已保存在文件CodeFile中.;coute ndl;voidDecodi ng(Huffma nTree&H T,i ntn) 譯碼in tf=2* n-1;fstreami nfile;in file.ope n(CodeFile.txt,ios:i n);chars1000;while(!i nfile.eof()i nfile.getli ne(s,sizeof(s);in f

9、ile.close();in ti=0;in tj=0;fstreamoutfile;outfile.ope n(TextFile.txt,ios:out);while(si!=0)f=2* n-1;while(HTf.lchild!=O)以f對應的節(jié)點的左孩子的值 =0作為結束if(sj=0)f=HTf.lchild;elsef=HTf.rchild;j+;i=j;coutHTf.data;outfileHTf.data;outfile.close();coutn譯碼結果已保存在文件TextFile中.;coute ndl;voidPri nt()/印代碼文件in tco un t=0;fs

10、treami nfile;in file.ope n(CodeFile.txt,ios:i n);chars1000;while(!i nfile.eof()i nfile.getli ne(s,sizeof(s);for(i nti=0;si!二0;i+)coutsi;coun t+;if(count%50=0)coutendl;在終端上每行顯示50個代碼in file.close();coute ndl;charmenu() /菜單函數(shù)cout功能菜單如下:endl;cout*“e ndl;coutI:初始化(Initialization)endl; . | J； f coutE:編碼(E

11、ncoding)endl;coutD:譯碼(Decoding)endl; * IcoutP:印代碼文件(Print)endl;coutQ:退出(Exit)endl;cout*“ ch;returnch;voidmai n()intn;in tArray100; charcArray100;Huffma nTreeHT;coutvv輸入n個字符:;ci n.getli ne(cArray,100);n=strle n( cArray);cout 一共n個字符.n;coutvv依次輸入各個字符的權值:endl;for(i nti=1;i Arrayi;in ttag;charx二me nu();w

12、hile(1)switch(x)caseT:Huffma nCodi ng(HT ,n ,cArray,Array);break;caseE:E ncodi ng(HT ,n );break;caseD:Decodi ng(HT, n);break;caseP:Pri nt();break;caseQ:tag=0;cout結束e ndl;break;default:cout你輸入錯誤!endl;if(tag=0)break;couty(繼續(xù))orn(退出) ch;if(ch=y)coutvv請輸入功能字符:;charc;cin c;x=c;elseexit(1);測試數(shù)據(jù)：用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的譯碼和編碼:THISPROGRAMISMYFAVORITE字符空格 ABCDEFGHIJKLM頻度 0字符 NOPQRSTUVWXYZ頻度 1四. 測試結果：如圖所示五. 實驗體會通過本次實驗，尤其在自己對程序的調試過程中，感覺對樹的存儲結構，終結狀態(tài)，還有編碼，譯 碼的過程都有了比較清晰的認識。在做本次實驗時，