哈夫曼编码算法实现完整版(共8页).doc
《哈夫曼编码算法实现完整版(共8页).doc》由会员分享,可在线阅读,更多相关《哈夫曼编码算法实现完整版(共8页).doc(8页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上实验三 树的应用一.实验题目:树的应用哈夫曼编码二.实验内容:利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。要求:从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各个字符进行哈夫曼编码,最后打印输出字符及对应的哈夫曼编码。三、程序源代码:#include #include #include #include typedef struct char data; int weight; int parent,lchil
2、d,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.weighttag1) tag1=px.weight;s1=x; for(int y=1;y=j-1;y+) if(py.parent=0&y!=s
3、1&py.weights2) /将选出的两个节点中的序号较小的始终赋给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 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(in
4、t 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+)outfileHTi.weighttHTi.parenttHTi.lchild tHTi.rchildtendl; outfile.clo
5、se(); cout初始化结果已保存在hfmTree文件中n;void ToBeTree() /将正文写入文件ToBeTree中ofstream outfile;outfile.open(ToBeTree.txt,ios:out);outfileTHIS PROGRAM IS MYFAVORITE;outfile.close();void Encoding(HuffmanTree &HT,int n) /编码 HuffmanCode HC; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); char *cd; cd=(char *)malloc(n*siz
6、eof(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+) /输出编码 coutHTh.data:; coutHCh; cout ; if (h%8=0) c
7、outendl; coutendl输出正文编码: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=HT
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼 编码 算法 实现 完整版
限制150内