1、實驗三 樹的應(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>

2、 typedef struct char 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&&p

3、x.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; if(s1>s2) /將選出的兩個節(jié)點中的序號較小的始終賦給s1 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 huffmanc

4、oding(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(ht

5、,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() /將正文寫入文件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)malloc(n+1)*s

7、izeof(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); cout

8、<<"輸出哈夫曼編碼:"<<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文件里的正文，并進行編碼 fstream infile; infil

9、e.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個換行 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對應(yīng)的節(jié)點的左孩子的值=0作為結(jié)束 if (sj='0') f=htf.lchild;else f=htf.rchild;j+; i=j; cout<<htf.data; outfile&l

12、t;<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;count

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

14、uot; e:編碼(encoding) "<<endl; cout<<" d:譯碼(decoding) "<<endl; cout<<" p:印代碼文件(print) "<<endl; cout<<" q:退出(exit) "<<endl; cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl; cout<<"請輸入功能

15、字符:"char ch;cin>>ch;return ch;void main() int n; int array100; char carray100; huffmantree ht; cout<<"輸入n個字符:" cin.getline(carray,100); n=strlen(carray); cout<<"一共"<<n<<"個字符.n" cout<<"依次輸入各個字符的權(quán)值:"<<endl; for (int

16、 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、<endl;break; default:cout<<"你輸入錯誤!"<<endl; if(tag=0) break; cout<<"y(繼續(xù)) or n(退出)"<<endl; char ch; cin>>ch; if (ch='y') cout<<"請輸入功能字符:" char c; cin>>c; x=c; else exit(1); 測試數(shù)據(jù)： 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的譯碼和編碼:"this program is my favorite". 字符 空格 a b c d e f g h i j k l m 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 n o p q r s t u v w x y z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 四.測試結(jié)果：如圖一所示五