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]，北京：
清华大学出版社
升级会员 