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

1、實(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è)程序，在用戶輸入結(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 <s

2、tdlib.h>typedef structchar data;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char * * HuffmanCode;void Select(HuffmanTree &HT,int n,int m)HuffmanTree p=HT;int tmp;for(int j=n+1;j<=m;j+)int tag1,tag2,s1,s2;tag1=tag2=32767;for(int x=1;x<=j-1;x+) if(px.parent=0&&

3、px.weight<tag1) tag1=px.weight;s1=x; for(int y=1;y<=j-1;y+) if(py.parent=0&&y!=s1&&py.weight<tag2) tag2=py.weight;s2=y;s1if(s1>s2) / 將選出的兩個(gè)節(jié)點(diǎn)中的序號(hào)較小的始終賦給 tmp=s1; s1=s2; s2=tmp; ps1.parent=j;ps2.parent=j; pj.lchild=s1; pj.rchild=s2;pj.weight=ps1.weight+ps2.weight; void Huff

4、manCoding(HuffmanTree &HT,int n,char *w1,int*w2) int m=2*n-1; if(n<=1) return; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); HuffmanTree p=HT;for(int i=1;i<=n;i+) pi.data=w1i-1;pi.weight=w2i; pi.parent=pi.lchild=pi.rchild=0; for(;i<=m;i+) pi.weight=pi.parent=pi.lchild=pi.rchild=0; Select(

5、HT,n,m);ofstream outfile; / 生成 hfmTree 文件 outfile.open("hfmTree.txt",ios:out);for (i=1;i<=m;i+)outfile<<HTi.weight<<"t"<<HTi.parent<<"t"<<HTi.lchild <<"t"<<HTi.rchild<<"t"<<endl;outfile.close()

6、;cout<<" 初始化結(jié)果已保存在 hfmTree文件中 n"void ToBeTree() / 將正文寫(xiě)入文件 ToBeTree 中 ofstream outfile; outfile.open("ToBeTree.txt",ios:out); outfile<<"THIS PROGRAM IS MYFAVORITE" outfile.close();void Encoding(HuffmanTree &HT,int n)/ 編碼HuffmanCode HC;HC=(HuffmanCode)mall

7、oc(n+1)*sizeof(char *); char *cd;cd=(char *)malloc(n*sizeof(char); cdn-1='0'for(int k=1;k<=n;k+) int start=n-1;for(int c=k,f=HTk.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1'HCk=(char *)malloc(n-start)*sizeof(char); strcpy(HCk,&cdstart);

8、cout<<" 輸出哈夫曼編碼 :"<<endl;for(int h=1;h<=n;h+) / 輸出編碼 cout<<HTh.data<<":" cout<<HCh; cout<<" "if (h%8=0) cout<<endl;cout<<endl<<" 輸出正文編碼 :"<<endl; ToBeTree();/ 讀取 TOBETREE 文件里的正文，并進(jìn)行編碼 fstream infil

9、e;infile.open("ToBeTree.txt",ios:in);char s80; while(!infile.eof() infile.getline(s,sizeof(s); infile.close();fstream outfile;outfile.open("CodeFile.txt",ios:out);int count=0;for (h=0;sh!='0'h+) for(k=1;k<=n;k+)if (sh=HTk.data) cout<<HCk; cout<<" "

10、;count+; outfile<<HCk;break;if (count%9=0) cout<<endl; / 每輸出 7 個(gè)換行 outfile.close();cout<<"n 編碼結(jié)果已保存在文件 CodeFile中 ." cout<<endl;void Decoding(HuffmanTree &HT,int n) / 譯碼int f=2*n-1;fstream infile;infile.open("CodeFile.txt",ios:in);char s1000; while(!inf

11、ile.eof() infile.getline(s,sizeof(s); infile.close(); int i=0;int j=0; fstream outfile; outfile.open("TextFile.txt",ios:out);while(si!='0') f=2*n-1;while(HTf.lchild!=0)/ 以f對(duì)應(yīng)的節(jié)點(diǎn)的左孩子的值 =0 作為結(jié)束 if (sj='0') f=HTf.lchild; else f=HTf.rchild;j+; i=j; cout<<HTf.data; outfile

12、<<HTf.data; outfile.close(); cout<<"n 譯碼結(jié)果已保存在文件 TextFile 中." cout<<endl;void Print()/ 印代碼文件 int count=0; fstream infile;infile.open("CodeFile.txt",ios:in);char s1000; while(!infile.eof() infile.getline(s,sizeof(s);for(int i=0;si!='0'i+) cout<<si;

13、count+;if (count%50=0) cout<<endl; / 在終端上每行顯示 50 個(gè)代碼 infile.close();cout<<endl;char menu() / 菜單函數(shù) cout<<" 功能菜單如下 :"<<endl;cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl;cout<<"cout<<"cout<<" cout<<

14、;" cout<<"I:初始化 (Initialization)"<<endl;E:編碼 (Encoding)"<<endl;D:譯碼 (Decoding)"<<endl;P:印代碼文件 (Print)"<<endl;Q:退出 (Exit)"<<endl;cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl; cout<<" 請(qǐng)輸入

15、功能字符 :"char ch; cin>>ch;return ch;void main() int n;int Array100; char cArray100; HuffmanTree HT;cout<<" 輸入 n 個(gè)字符:"cin.getline(cArray,100); n=strlen(cArray);cout<<" 一共"<<n<<" 個(gè)字符 .n"cout<<" 依次輸入各個(gè)字符的權(quán)值 :"<<endl; f

16、or (int i=1;i<=n;i+)cin>>Arrayi;int tag;char x=menu();while(1) switch (x)case 'I':HuffmanCoding(HT,n,cArray,Array);break;case 'E':Encoding(HT,n);break;case 'D':Decoding(HT,n);break;case 'P':Print();break;case 'Q':tag=0;cout<<"結(jié)束 "<&

17、lt;endl;break; default:cout<<" 你輸入錯(cuò)誤 !"<<endl;if(tag=0) break;cout<<"y(繼續(xù)) or n(退出)"<<endl;char ch;cin>>ch;if (ch='y') cout<<" 請(qǐng)輸入功能字符 :"char c;cin>>c;x=c;else exit(1);測(cè)試數(shù)據(jù)： 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹(shù)， 并實(shí)現(xiàn) 以下報(bào)文的譯碼和編碼 :"THIS PROGRAM IS MY FAVORITE ".字符 空格A BCDEFGH IJ KLM頻度18664 13 223210321154757 15 32 20字符NO PQRSTU VW XYZ頻度5763 15 148518023818 116 1四 .測(cè)試結(jié)果 ：如圖一所示五.實(shí)驗(yàn)體會(huì)通過(guò)本次實(shí)驗(yàn)，尤其在自己對(duì)程序的調(diào)試過(guò)程中，