5306徐吉 哈夫曼编码译码器综合实验报告.docx
《5306徐吉 哈夫曼编码译码器综合实验报告.docx》由会员分享,可在线阅读,更多相关《5306徐吉 哈夫曼编码译码器综合实验报告.docx(16页珍藏版)》请在冰点文库上搜索。
5306徐吉哈夫曼编码译码器综合实验报告
“数据结构——哈夫曼编码译码器”综合实验报告
学院
软件学院
年级
2013
学号
20135306
姓名
徐吉
报告日期
2014/12/10
成绩
黑龙江大学软件学院
1问题描述及分析
问题描述:
设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(后缀名.cod);反过来,可将一个编码文件还原为一个文本文件(.txt)。
问题分析:
设计该编码器译码器,首先得根据给出的字母,计算各字母的权值,
然后根据权值进行构建哈夫曼树,生成新的结点,遍厉树,左子树添0,右子树添1,生成倒序的哈夫曼编码,使用文件操作存入新的文件,再进行译码操作,将哈夫曼编码存入数组中,然后根据生成树的原理进行译码,每编译成功一个字母时将返回根结点,最后将译码后的数据存入另一个文件中。
该实验主要实验要求如下:
(1)输入一个待压缩的文本文件名,统计文本文件中各字符的个数作为权值,生成哈夫曼树;
(2)将文本文件利用哈夫曼树进行编码,生成编码文件(后缀名cod);
(3)输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码;
(4)显示指定的编码文件和文本文件;
(5)把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算进行真正的数据压缩,并求压缩比。
(此选项选作)
2功能模块及数据结构描述
该程序主要分为两个功能模块:
1.对已有的字母文件进行哈夫曼编码,对每个字母都形成哈夫曼编码。
2.对生成的哈夫曼编码进行译码操作,将译码结果存入新的文本文件。
数据结构描述:
typedefchar**HuffmanCode;//该结构为哈夫曼编码结构
typedefstruct{
charletter;
intweight;
intparent;
intlchild,rchild;
}HTNode,*HuffmanTree;//该结构为生成的哈夫曼树的结构
3主要算法流程描述
1.读取已有文件,并对其内的字母进行统计,计算出每个字母各自对应的权值:
voidjishu(HuffmanTreeHT,intcs[N],intCS[N])
{
intc=0;
inti;
FILE*fp;
charch,filename[20];
printf("请输入文件名\n");
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("此文件不存在");
getchar();
exit(0);
}
while(!
feof(fp))
{
ch=fgetc(fp);
if(ch>='a'&&ch<='z')
{
cs[ch-'a']++;
c++;
}
else
{
CS[ch-'A']++;
c++;
}
}
fclose(fp);
printf("共有%d个字母\n",c);
for(i=0;i{
if(cs[i]!
=0)
{
printf("字母%c的权值为%d\n",i+'a',cs[i]);
n++;
HT[n].letter=i+'a';
HT[n].weight=cs[i];
}
}
for(i=0;i{
if(CS[i]!
=0)
{
printf("字母%c的权值为%d\n",i+'A',CS[i]);
n++;
HT[n].letter=i+'A';
HT[n].weight=CS[i];
}
}
printf("共有%d个叶子结点\n",n);
}
2.对已有的字母根据其权值进行排序,并显示结果:
HuffmanTreesort(HuffmanTreeHT)
{
intt=0;
inti,j;
for(i=1;i{
for(j=1;j{
if(HT[j].weight>HT[j+1].weight)
{
t=HT[j].weight;
HT[j].weight=HT[j+1].weight;
HT[j+1].weight=t;
HT[1000].letter=HT[j].letter;
HT[j].letter=HT[j+1].letter;
HT[j+1].letter=HT[1000].letter;
}
}
}
printf("经排序后各结点的次序如下所示:
\n");
for(i=1;i{
printf("%d%c的权值为%d\n",i,HT[i].letter,HT[i].weight);
}
returnHT;
}
3.构造选择函数,将所有结点中含有最小和次小值的结点选出:
voidSelect(HuffmanTreeHT,intlen,int&s1,int&s2)
{
inti,min1=0x3f3f3f3f,min2=0x3f3f3f3f;//先赋予最大值
for(i=1;i<=len;i++)
{
if(HT[i].weight{
min1=HT[i].weight;
s1=i;
}
}
inttemp=HT[s1].weight;//将原值存放起来,然后先赋予最大值,防止s1被重复选择
HT[s1].weight=0x3f3f3f3f;
for(i=1;i<=len;i++)
{
if(HT[i].weight{
min2=HT[i].weight;
s2=i;
}
}
HT[s1].weight=temp;//恢复原来的值
}
4.构造哈夫曼树,并显示出新的结点的权值;
voidCreatHuffmanTree(HuffmanTreeHT)
{
//构造赫夫曼树HT
intm,i;
ints1;
ints2;
if(n<=1)return;
m=2*n-1;
//0号单元未用,所以需要动态分配m+1个单元,HT[m]表示根结点
for(i=1;i<=m;++i)//将1~m号单元中的双亲、左孩子,右孩子的下标都初始化为0
{HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}
for(i=n+1;i<=m;i++)
{
HT[i].weight=0;
}
printf("创建后新结点所对应的权值分别为:
\n");
for(i=n+1;i<=m;++i)
{//通过n-1次的选择、删除、合并来创建赫夫曼树
Select(HT,i-1,s1,s2);
//在HT[k](1≤k≤i-1)中选择两个其双亲域为0且权值最小的结点,
//并返回它们在HT中的序号s1和s2
HT[s1].parent=i;
HT[s2].parent=i;
//得到新结点i,从森林中删除s1,s2,将s1和s2的双亲域由0改为i
HT[i].lchild=s1;
HT[i].rchild=s2;//s1,s2分别作为i的左右孩子
HT[i].weight=HT[s1].weight+HT[s2].weight;//i的权值为左右孩子权值之和
printf("HT[%d]=%d\n",i,HT[i].weight);
}//for
}
5.生成哈夫曼编码:
voidCreatHuffmanCode(HuffmanTreeHT,HuffmanCode&HC)
{inti,start,c,f;
HC=newchar*[n+1];
char*cd=newchar[n];
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
start=n-1;
c=i;
f=HT[i].parent;
while(f!
=0)
{
--start;
if(HT[f].lchild==c)
cd[start]='0';
else
cd[start]='1';
c=f;
f=HT[f].parent;
}
HC[i]=newchar[n-start];
strcpy(HC[i],&cd[start]);
}
deletecd;
}
6.进行译码操作,并将结果存入新的文本文件:
voidDecode(HuffmanTreeHT,charB[M])
{
inti=1,j=0;
FILE*fp;
charch,filename[20];
inta;
a=2*n-1;
printf("请输入要编码的文件名\n");
scanf("%s",filename);
if((fp=fopen(filename,"r"))==NULL)
{
printf("此文件不存在");
getchar();
exit(0);
}
ch=fgetc(fp);
B[0]=ch;
do
{
ch=fgetc(fp);
B[i]=ch;
i++;
}while(ch!
=EOF);
fclose(fp);
printf("经译码后,HFM.cod文件内哈夫曼编码对应的字母是:
\n");
while(j<=i-2)
{
if(B[j]=='0')
a=HT[a].lchild;
else
a=HT[a].rchild;
if(HT[a].lchild==0&&HT[a].rchild==0)
{
printf("%c",HT[a].letter);
FILE*fp;
if((fp=fopen("C:
\\哈夫曼.txt","a"))==NULL)
{
printf("Failtoopen哈夫曼.txt\n");
exit(0);
}
fprintf(fp,"%c",HT[a].letter);
fclose(fp);a=2*n-1;
}
j++;
}
printf("\n");
}
7.主函数:
main()
{
HTNodeHT[leaf];
HuffmanCodeHC;
intcs[N]={0};
intCS[N]={0};
charB[M];
jishu(HT,cs,CS);
sort(HT);
CreatHuffmanTree(HT);
CreatHuffmanCode(HT,HC);
show(HT,HC);
Write(HC);
Decode(HT,B);
}
4使用说明
1.进入编译环境,根据提示,输入要进行编码的文件:
2.按回车,输出一系列相关信息,各结点对应的权值,根据权值排列的结点次序以及各个字母对应的哈夫曼编码:
3.再根据提示,输入要译码的文件名:
4.按回车输出译码结果:
并存入文本文件:
5实验及总结
本实验主要涉及文本操作及二叉树的遍厉,在实验中主要遇到使用循环时对循环条件进行不准确的计算,从而造成实验错误,还出现了在将译码后的结果存入文本文件时,出现“烫烫烫烫“字符,下标越界,后调整a=2*n-1的位置后得到解决。
本实验还存在一些瑕疵,例如:
此编码译码器只能对52个大小写字母进行编码译码,编码译码范围较小。
需要改进。
6参考文献
教材:
严蔚敏,李冬梅,吴伟民,《数据结构》(C语言版)[M],北京:
人民邮电出版社
参考书:
1、唐策善等,《数据结构—C语言描述》[M],北京:
高等教育出版社
2、严蔚敏,吴伟民,《数据结构》(C语言版)[M],北京:
清华大学出版社
3、严蔚敏,《数据结构习题集与上机指导》[M],北京:
清华大学出版社