哈夫曼编码解码实验报告.doc

哈夫曼编码解码实验1. 实验要求掌握二叉树的相关概念掌握构造哈夫曼树，进行哈夫曼编码。对编码内容通过哈夫曼树进行解码。2. 实验内容通过二叉树构造哈夫曼树，并用哈夫曼树对读取的txt文件进行哈夫曼编码。编码完成后通过哈夫曼树进行解码。#include#include#define MAX 100/定义哈夫曼树的存储结构typedef structchar data;int weight;int parent;int lch;int rch;HuffNode;/定义哈夫曼编码的存储结构typedef structchar bitMAX;int start;HuffCode;HuffNode ht2*MAX;HuffCode hcdMAX;int Coun127=0;int n;char s1200000;char text5000;/构造哈夫曼树void HuffmanTree()int i,j,k,left,right,min1,min2;/printf(输入叶子的节点数：);/scanf(%d,&n);printf(字符数量=%dn,n);for(i=1;i=2*n-1;i+)hti.parent=hti.lch=hti.rch=0;j=0;for(i=1;i=n;i+)/*getchar();printf(输入第%d个叶子节点的值：,i);scanf(%c,&hti.data);printf(输入该节点的权值：);scanf(%d,&hti.weight);*/for(;j127;j+)if(Counj!=0)hti.data=j;/printf(%c,hti.data);hti.weight=Counj;/printf(%d,hti.weight);break;j+;printf(n);for(i=1;i=n;i+)printf(%c,hti.data);printf(n);for(i=n+1;i=2*n-1;i+)/在前n个结点中选取权值最小的两个结点构成一颗二叉树min1=min2=10000;/为min1和min2设置一个比所有权值都大的值left=right=0;for(k=1;k=i-1;k+)if(htk.parent=0)/若是根结点 /令min1和min2为最小的两个权值，left和right为权值最小的两个结点位置 if(htk.weightmin1) min2=min1; right=left; min1=htk.weight; left=k; else if (htk.weightmin2) min2=htk.weight; right=k; htleft.parent=i; htright.parent=i; hti.weight=htleft.weight+htright.weight; hti.lch=left; hti.rch =right;/构造哈夫曼编码void HuffmanCode()int i,c,k,f;HuffCode cd;for(i=1;i=n;i+)cd.start=n;c=i;f=hti.parent;while(f!=0)if(htf.lch=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=f;f=htf.parent;hcdi=cd;printf(输出哈夫曼编码：n);for(i=1;i=n;i+)printf(%c:,hti.data);for(k=hcdi.start+1;k=n;k+)printf(%c,hcdi.bitk);printf(n);/对字母进行编码void Code()/将字符与相应的哈夫曼编码进行匹配，输出编码结果int i=0,j,k,h=0;while(texti!=0)for(j=1;j=n;j+)if(texti=htj.data)for(k=hcdj.start+1;k=n;k+)s1h=hcdj.bitk;h+;break;i+;/printf(编码n);/puts(s1);/printf(n);/解码void HuffmanDecode()printf(解码n);int len,i,f;char C;/char SMAXCODE;/scanf(%s,S);/使用gets()直接跳过len=strlen(s1);printf(s1:%dn,len);f=2*n-1;for(i=0;ilen;i+)if(s1i=0)f=htf.lch;if(htf.lch=0&htf.rch=0)C=htf.data;printf(%c,C);f=2*n-1;else if(s1i=1)f=htf.rch;if(htf.lch=0&htf.rch=0)C=htf.data;printf(%c,C);f=2*n-1;printf(n);/统计字母个数及其权值void Count()int i,j,m;n=0;i=0;/printf(请仅输入小写字母n);/例程本省存在一个BUG，只输入一个字母不能进行编码（并未解决）/scanf(%s,s);while(texti!=0)/使用ASCII码表进行统计m=texti;/printf(%dn,m);Counm+;i+;for(j=0;j127;j+)if(Counj!=0)n+;/mark Codevoid main()int l=0;FILE *fp;fp=fopen(text.txt,r);if(fp=NULL)printf(文件打开失败n);while(1);while(!feof(fp)textl = fgetc(fp);l+;printf(输入文本n);printf(%sn,text);fclose(fp);Count();HuffmanTree();HuffmanCode();Code