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

实验三 树的应用一. 实验题目 ：树的应用哈夫曼编码二. 实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时 间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权 值的基础上求哈夫曼编码。要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为 结点的权值， 建立哈夫曼树， 然后对各个字符进行哈夫曼编码， 最后打印输出字 符及对应的哈夫曼编码。三、程序源代码 :#include <iostream.h>#include <fstream.h>#include <string.h>#include <stdlib.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&&px.weight<tag1) tag1=px.weight;s1=x;for(int y=1;y<=j-1;y+)第 - 1 - 页 共 7 页 if(py.parent=0&&y!=s1&&py.weight<tag2) tag2=py.weight;s2=y;s1if(s1>s2) / 将选出的两个节点中的序号较小的始终赋给 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 HuffmanCoding(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,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();cout<<"初始化结果已保存在 hfmTree 文件中 n"void ToBeTree() / 将正文写入文件 ToBeTree 中ofstream outfile; outfile.open("ToBeTree.txt",ios:out);outfile<<"THIS PROGRAM IS MYFA VORITE"第 - 2 - 页 共 7 页outfile.close();void Encoding(HuffmanTree &HT,int n) / 编码HuffmanCode HC;HC=(HuffmanCode)malloc(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);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;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<<" "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(!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; outfile<<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;count+;if (count%50=0) cout<<endl; / 在终端上每行显示 50 个 代码infile.close();cout<<endl;char menu() / 菜单函数 cout<<" 功能菜单如下 :"<<endl;cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl;cout<<"I:初始化 (Initialization)"<<endl;cout<<"E:编码 (Encoding)"<<endl;cout<<"D:译码 (Decoding)"<<endl;cout<<"P:印代码文件 (Print)"<<endl;cout<<"Q:退出 (Exit)"<<endl;cout<<"* * * * * * * * * * * * * * * * * * * * *"<<endl; cout<<" 请输入功能字符 :"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 (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<<"结束 "<<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 FAVORI"T. E字符 空格 A B C D E F G H I J K L M频度18664 13 22 32 103 2115 47 57 1 5 32 20字符NO PQ R S TUVW XY Z频度5763 151 48 51 8023818 116 1四 .测试结果 ：如图一所示五.实验体会通过本次实验，尤其在自己对程序的调试过程中，感觉对树的存储结构， 终结状态，还有编码，译码的过程都有了比较清晰的认识。在做本次实验时，其 他的都没什么问题， 以前很少进行文件操作， 刚开始有点手生， 但是在实验作完 后，文件操作已经用的比较熟练了。 最近几次实验， 感到自己对本题实验的运行 机理和过程掌握的最为透彻。 收获不小。在实验过程中， 遇到的一个主要问题是 在 C+ 里面输入单个空格字符的问题。最终通过用 cin.getline （） 来解决， 但是还不是很理想。为了察看方便，把有些文件的内容直接显示在终端上了,没有列出生成的文件里的结果。图一共7 页