哈夫曼编码算法实现完整版

1、精选文档实验三 树的应用一.实验题目：树的应用哈夫曼编码二.实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。三、程序源代码:#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&&a

3、mp;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; if(s1>s2) /将选出的两个节点中的序号较小的始终赋给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 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; Selec

5、t(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<<"初始化结果已保存在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+

7、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文件里的正文，并进行编码 fstream infile; i

9、nfile.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<<" &q

10、uot; count+; outfile<<HCk; break; if (count%9=0) cout<<endl; /每输出7个换行 outfile.close(); cout<<"n编码结果已保存在文件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(

11、!infile.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对应的节点的左孩子的值=0作为结束 if (sj='0') f=HTf.lchild;else f=HTf.rchild;j+; i=j; cout<<HTf.data; outfi

12、le<<HTf.data; outfile.close();cout<<"n译码结果已保存在文件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;c

13、ount+;if (count%50=0) cout<<endl; /在终端上每行显示50个代码 infile.close();cout<<endl;char menu() /菜单函数 cout<<"功能菜单如下:"<<endl; cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl; cout<<" I:初始化(Initialization) "<<endl; cout<&l

14、t;" 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<<"依次输入各个字符的权值:"<<endl; for

16、(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<<"结束"

17、<<endl;break; default:cout<<"你输入错误!"<<endl; if(tag=0) break; cout<<"y(继续) or n(退出)"<<endl; char ch; cin>>ch; if (ch='y') cout<<"请输入功能字符:" char c; cin>>c; x=c; else exit(1); 测试数据： 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的译码和编码:"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 四.测试结果：如