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

第5-頁(yè)共7頁(yè)實(shí)驗(yàn)三樹(shù)的應(yīng)用一.實(shí)驗(yàn)題目：樹(shù)的應(yīng)用——哈夫曼編碼二.實(shí)驗(yàn)內(nèi)容：利用哈夫曼編碼進(jìn)行通信可以大大提高信道的利用率，縮短信息傳輸?shù)臅r(shí)間，降低傳輸成本。根據(jù)哈夫曼編碼的原理，編寫(xiě)一個(gè)程序，在用戶(hù)輸入結(jié)點(diǎn)權(quán)值的基礎(chǔ)上求哈夫曼編碼。要求：從鍵盤(pán)輸入若干字符及每個(gè)字符出現(xiàn)的頻率，將字符出現(xiàn)的頻率作為結(jié)點(diǎn)的權(quán)值，建立哈夫曼樹(shù)，然后對(duì)各個(gè)字符進(jìn)行哈夫曼編碼，最后打印輸出字符及對(duì)應(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)//將選出的兩個(gè)節(jié)點(diǎn)中的序號(hào)較小的始終賦給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()//將正文寫(xiě)入文件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<<"請(qǐng)輸入功能字符:"; charc; cin>>c;x=c;}elseexit(1);}}測(cè)試數(shù)據(jù)：用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的譯碼和編碼:"THISPROGRAMISMYFAVORITE".字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161四.測(cè)試結(jié)果：如圖一所示五.實(shí)驗(yàn)體會(huì)通過(guò)本次實(shí)驗(yàn)，尤其在自己對(duì)程序的調(diào)試過(guò)程中，感覺(jué)對(duì)樹(shù)的存儲(chǔ)結(jié)構(gòu)，終結(jié)狀態(tài)，還有編碼，譯碼的過(guò)程都有了比較清晰的認(rèn)識(shí)。在做本次實(shí)驗(yàn)時(shí)，其他的都沒(méi)什么問(wèn)題，以前很少進(jìn)行文件操作，剛開(kāi)始有點(diǎn)手生，但是在實(shí)驗(yàn)作完后，文件操作已經(jīng)用的比較熟練了。最近幾次實(shí)驗(yàn)，感到自己對(duì)本題實(shí)驗(yàn)的運(yùn)行機(jī)理和過(guò)程掌握的最為透徹。收獲不小