5306徐吉 哈夫曼编码译码器综合实验报告Word下载.docx
《5306徐吉 哈夫曼编码译码器综合实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《5306徐吉 哈夫曼编码译码器综合实验报告Word下载.docx（16页珍藏版）》请在冰点文库上搜索。
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-'
]++;
c++;
}
else
CS[ch-'
A'
fclose（fp）;
共有%d个字母\n"
c）;
for（i=0;
i<
N;
i++）
if（cs[i]!
=0）
printf（"
字母%c的权值为%d\n"
i+'
cs[i]）;
n++;
HT[n].letter=i+'
;
HT[n].weight=cs[i];
if（CS[i]!
CS[i]）;
HT[n].weight=CS[i];
共有%d个叶子结点\n"
n）;
2．对已有的字母根据其权值进行排序，并显示结果：
HuffmanTreesort（HuffmanTreeHT）
intt=0;
inti,j;
for（i=1;
n+2;
for（j=1;
j<
n-i+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;
}
经排序后各结点的次序如下所示：
\n"
n+1;
%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;
//先赋予最大值
=len;
if（HT[i].weight<
min1&
HT[i].parent==0）
min1=HT[i].weight;
s1=i;
}
inttemp=HT[s1].weight;
//将原值存放起来，然后先赋予最大值，防止s1被重复选择
HT[s1].weight=0x3f3f3f3f;
min2&
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]表示根结点
=m;
++i）//将1~m号单元中的双亲、左孩子，右孩子的下标都初始化为0
{HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
for（i=n+1;
HT[i].weight=0;
创建后新结点所对应的权值分别为：
++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的权值为左右孩子权值之和
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'
=n;
++i）
{
start=n-1;
c=i;
f=HT[i].parent;
while（f!
{
--start;
if（HT[f].lchild==c）
cd[start]='
0'
else
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;
inta;
a=2*n-1;
请输入要编码的文件名\n"
}
ch=fgetc（fp）;
B[0]=ch;
do
B[i]=ch;
i++;
}while（ch!
=EOF）;
经译码后，HFM.cod文件内哈夫曼编码对应的字母是：
while（j<
=i-2）
if（B[j]=='
a=HT[a].lchild;
a=HT[a].rchild;
if（HT[a].lchild==0&
HT[a].rchild==0）
%c"
HT[a].letter）;
FILE*fp;
if（（fp=fopen（"
C:
\\哈夫曼.txt"
"
a"
Failtoopen哈夫曼.txt\n"
fprintf（fp,"
j++;
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]，北京：
升级会员 