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

第5-頁共7頁實驗三樹的應(yīng)用一.實驗題目：樹的應(yīng)用——哈夫曼編碼二.實驗內(nèi)容：利用哈夫曼編碼進行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r間，降低傳輸成本。根據(jù)哈夫曼編碼的原理，編寫一個程序，在用戶輸入結(jié)點權(quán)值的基礎(chǔ)上求哈夫曼編碼。要求：從鍵盤輸入若干字符及每個字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結(jié)點的權(quán)值，建立哈夫曼樹，然后對各個字符進行哈夫曼編碼，最后打印輸出字符及對應(yīng)的哈夫曼編碼。三、程序源代碼:#include<iostream.h>#include<fstream.h>#include<string.h>#include<stdlib.h>typedefstruct{chardata;intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTree&HT,intn,intm){HuffmanTreep=HT;inttmp;for(intj=n+1;j<=m;j++){inttag1,tag2,s1,s2;tag1=tag2=32767; for(intx=1;x<=j-1;x++) {if(p[x].parent==0&&p[x].weight<tag1) {tag1=p[x].weight;s1=x;} }for(inty=1;y<=j-1;y++) {if(p[y].parent==0&&y!=s1&&p[y].weight<tag2) {tag2=p[y].weight;s2=y;} } if(s1>s2)//將選出的兩個節(jié)點中的序號較小的始終賦給s1 {tmp=s1;s1=s2;s2=tmp;}p[s1].parent=j; p[s2].parent=j; p[j].lchild=s1; p[j].rchild=s2; p[j].weight=p[s1].weight+p[s2].weight;}}voidHuffmanCoding(HuffmanTree&HT,intn,char*w1,int*w2){intm=2*n-1;if(n<=1)return;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));HuffmanTreep=HT;for(inti=1;i<=n;i++){p[i].data=w1[i-1]; p[i].weight=w2[i];p[i].parent=p[i].lchild=p[i].rchild=0;}for(;i<=m;i++){p[i].weight=p[i].parent=p[i].lchild=p[i].rchild=0;}Select(HT,n,m);ofstreamoutfile;//生成hfmTree文件outfile.open("hfmTree.txt",ios::out);for(i=1;i<=m;i++){outfile<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<"\t"<<endl;}outfile.close();cout<<"初始化結(jié)果已保存在hfmTree文件中\(zhòng)n";}voidToBeTree()//將正文寫入文件ToBeTree中{ ofstreamoutfile; outfile.open("ToBeTree.txt",ios::out); outfile<<"THISPROGRAMISMYFAVORITE"; outfile.close();}voidEncoding(HuffmanTree&HT,intn)//編碼{HuffmanCodeHC;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));char*cd;cd=(char*)malloc(n*sizeof(char));}if(tag==0)break;cout<<"y(繼續(xù))orn(退出)"<<endl;charch;cin>>ch;if(ch=='y'){cout<<"請輸入功能字符:"; charc; cin>>c;x=c;}elseexit(1);}}測試數(shù)據(jù)：用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的譯碼和編碼:"THISPROGRAMISMYFAVORITE".字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161四.測試結(jié)果：如圖一所示五.實驗體會通過本次實驗，尤其在自己對程序的調(diào)試過程中，感覺對樹的存儲結(jié)構(gòu)，終結(jié)狀態(tài)，還有編碼，譯碼的過程都有了比較清晰的認識。在做本次實驗時，其他的都沒什么問題，以前很少進行文件操作，剛開始有點手生，但是在實驗作完后，文件操作已經(jīng)用的比較熟練了。最近幾次實驗，感到自己對本題實驗的運行機理和過程掌握的最為透徹。收獲不小