《数据结构课程设计》赫夫曼编码实验报告.docx
《《数据结构课程设计》赫夫曼编码实验报告.docx》由会员分享，可在线阅读，更多相关《《数据结构课程设计》赫夫曼编码实验报告.docx（19页珍藏版）》请在冰点文库上搜索。
《数据结构课程设计》赫夫曼编码实验报告
一、概述
本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生产的代码串进行译码，输出电文字符串。
在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
二、系统分析
赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。
树中从根到每个叶子都有一条路径，对路径上的各分支约定：
指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。
通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。
电报通信是传递文字的二进制码形式的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。
假设每种字符在电文中出现的次数为Wi,编码长度为Li，电文中有n种字符，则电文编码总长为∑WiLi。
若将此对应到二叉树上，Wi为叶节点的权，Li为根节点到叶节点的路径长度。
那么，∑WiLi恰好为二叉树上带权路径长度。
因此，设计电文总长最短的二进制前缀编码，就是以n种子符出现的频率作权，构造一刻赫夫曼树，此构造过程成为赫夫曼编码。
根据设计要求和分析，要实现设计，必须实现以下方面的功能：
（1）赫夫曼树的建立；
（2）赫夫曼编码的生成；
（3）编码文件的译码；
三、概要设计
程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。
voidmain（）
voidHufffmanEncoding（HuffmanTreeHT,HuffmanCodeHC）//编码部分
char*decode（HuffmanCodeHc）//译码
voidChuffmanTree（HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]）//生成Huffman树
voidselect（HufmanTreeHT,intk,int&s1,int&s2）//找寻parent为0,权最小的两个节点
其流程图如下：
四、详细设计
4.1赫夫曼树的建立
由赫夫曼算法的定义可知，初始森林中共有n棵只含根节点的二叉树。
算法的第二步是：
将当前森林中的两颗根节点的二叉树，合并成一颗新的二叉树；每合并一次，森林中就减少一棵树，产生一个新节点。
显然要进行n-1次合并，所以共产生n-1个新节点，它们都是具有两个孩子分支结点。
由此可知，最新求得的赫夫曼树中一共有2n-1个结点，其中n个结点是初始森林的n个孤立结点。
并且赫夫曼树中没有度数为1的分支结点。
我们可用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。
因此，赫夫曼树的存储结构描述为：
#definen100
#definem2*n-1
typedefstruct{
intweight;
intlchild,rchild,parent;
}HTNode;T
typedefHTNodeHuffmanTree[m+1];
4.1.1选择选择parent为0且权值最小的两个根结点的算法
voidselect（HuffmanTreeT,intk,int*s1,int*s2）
{//在HT[1……k]中选择parent为0且权值最小的两个根结点，其序号分别为S1和S2
inti,j;
intmin1=100;
for（i=1;i<=k;i++）//查找s1
if（T[i].weight{
j=i;min1=T[i].weight;
}
*s1=j;
min1=32767;
for（i=1;i<=k;i++）//查找s2,不和s1相同
if（T[i].weight=（*s1））
{
j=i;
min1=T[i].weight;
}
*s2=j;
}
4.1.2统计字符串中字符的种类以及各类字符的个数
假设电子文件字符串全是大写字母，那么该算法的实现思想是：
先定义一个含有26个元素的临时整型数组，用来存储各种字母出现的次数。
应为大写字母的ASCII码与整数1~26个元素之间相差64，因此在算法中使用字母减去64作为统计数组的下标对号入座，无须循环判断来实现，从而提高了效率；另外，要求出电文字符串中有多少种字符，并保存这些字符以供编码时使用。
统计和保存都比较容易，用一个循环来判断先前统计好的各类字符个数的数组元素是否为零，若不为零，则将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组元素中。
具体实现如下：
intjsq（char*s,intcnt[],charstr[]）
{
//统计各字符串中各种字母的个数以及字符的种类
char*p;
inti,j,k;
inttemp[27];
for（i=1;i<=26;i++）
temp[i]=0;
for（p=s;*p!
='\0';p++）
{//统计各种字符个数
if（*p>='A'&&*p<='Z'）{
k=*p-64;
temp[k]++;
}
}
j=0;
for（i=1,j=0;i<=26;i++）//统计有多少种字符
if（temp[i]!
=0）{
j++;
str[j]=i+64;//将对应的数组送到数组中
cnt[j]=temp[i];//存入对应数组的权值
}
returnj;
}
4.1.3构造赫夫曼树
voidChuffmanTree（HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]）
{//构造赫夫曼树HT
inti,s1,s2;
for（i=1;i<=2*num-1;i++）//初始化HT，左右孩子，双亲，权值都为0
{HT[i].lchild=0;HT[i].rchild=0;
HT[i].parent=0;HT[i].weight=0;
}
for（i=1;i<=num;i++）//输入num个叶节点的权值
HT[i].weight=cnt[i];
for（i=num+1;i<=2*num-1;i++）//从numd后面开始新建结点存放新生成的父节点
{
select（HT,i-1,&s1,&s2）;//在HT[1……i-1]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2
HT[s1].parent=i;HT[s2].parent=i;//将s1和s2的parent赋值
HT[i].lchild=s1;HT[i].rchild=s2;//新结点的左右孩子
HT[i].weight=HT[s1].weight+HT[s2].weight;//新结点的权值
}
for（i=0;i<=num;i++）//输入字符集中的字符
HC[i].ch=str[i];
i=1;
while（i<=num）
printf（"字符%c,次数为:
%d\n",HC[i].ch,cnt[i++]）;
}
4.2赫夫曼编码
要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下：
typedefstruct{
charch;
charbits[n+1];
intstart;
}CodeNode;
typedefCodeNodeHuffmanCode[n];
4.2.1赫夫曼编码算法
voidHuffmanEncoding（HuffmanTreeHT,HuffmanCodeHC）
{//根据赫夫曼树HT求赫夫曼编码表ＨＣ
intc,p,i;
charcd[n];
intstart;cd[num]='\0';
for（i=1;i<=num;i++）
{
start=num;
c=i;
while（（p=HT[c].parent）>0）//直至上诉到ht[c]是树根为止
{//若HT[c]是HT[p]的孩子，则生成0；否则生成代码1
cd[--start]=（HT[p].lchild==c）?
'0':
'1':
c=p;
}//endofwhile
strcpy（HC[i].bits,&cd[start]）;
HC[i].len=num-start;
}
}
4.2.2建立正文的编码文件
建立编码文件的基本思想是：
将要编码的字符串中的字符逐一与预先生成赫夫曼树时保保存的字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有字符处理完毕为止。
具体算法如下：
viodcoding（huffmanCodeHC,char*str）
{
inti,j;
FILE*fp;
fp=fopen（“codefile.tex”,”w”）;
while（*str）{//对电文中字符逐一生成编码并写入文件
for（i=1;i<=num;i++）
if（HC[i].ch==*str）{
for（j=0;j<=HC[i].len;j++）f
putc（HC[i].bits[j],fp）;
break;
}str++;
}
fclose（fp）;
}
4.3代码文件的译码
译码的基本思想是:
读文件中编码，并与生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。
Char*decode（HuffmanCodeHC）
{//代码文件codefile.tex译码
FILE*fp;charstr[254];
char*p;
staticcharcd[n+1]
inti,j,k=0,cjs;
fp=fopen（“codefile.tex”,”r”）;
while（!
feof（fp））
{cjs=0;
for（i=0;i<=num&&cjs==0&&!
feof（fp）;i++）
{
cd[i]=‘’；
cd[i+1]='\0';
cd[i]=fgetc（fp）;
for（j=1;j<=num;j++）
if（strcmp（HC[i].bits,cd）==0）
{
str[k]=HC[j].ch;k++;
cjs=1;break;
}
}
str[k]='\0';
;p=str;
returnp;
}
五、运行与测试
运行结果为
六、总结与心得
本次编写过程中出现了较多的问题，比如开始对赫夫曼树的理解不是很清楚，导致在编写过程中某些代码错误而没能及时修改，在最后进行修改时遇到了较多的麻烦。
但是经过这次对赫夫曼树的学习后，我了解到赫夫曼编码（HuffmanCoding）是一种编码方式，以赫夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据的无损耗压缩。
总之受益匪浅。
参考文献
【1】《数据结构》严蔚敏.清华大学出版社.
【2】《数据结构课程设计》苏仕华.极械工业出版社.
【3】《程序设计》谭浩强.清华大学出版社.
附录
#include
#include
#definen100//叶子结点数
#definem2*n-1//赫夫曼树种的结点总数
typedefstruct{
charch;
charbits[9];//存放编码位串
intlen;//编码长度
}CodeNode;
typedefCodeNodeHuffmanCode[n+1];
typedefstruct{
intweight;//权值
intlchild,rchild,parent;//左右孩子及双亲指针
}HTNode;//树中的结点类型
typedefHTNodeHuffmanTree[m+1];//0号单元不可用
intnum;//字母类型的个数
voidselect（HuffmanTreeT,intk,int*s1,int*s2）
{//在HT[1……k]中选择parent为0且权值最小的两个根结点，其序号分别为S1和S2
inti,j;
intmin1=100;
for（i=1;i<=k;i++）//查找s1
if（T[i].weight{
j=i;min1=T[i].weight;
}
*s1=j;
min1=32767;
for（i=1;i<=k;i++）//查找s2,不和s1相同
if（T[i].weight=（*s1））
{
j=i;
min1=T[i].weight;
}
*s2=j;
}
intjsq（char*s,intcnt[],charstr[]）
{
//统计各字符串中各种字母的个数以及字符的种类
char*p;
inti,j,k;
inttemp[27];
for（i=1;i<=26;i++）
temp[i]=0;
for（p=s;*p!
='\0';p++）
{//统计各种字符个数
if（*p>='A'&&*p<='Z'）{
k=*p-64;
temp[k]++;
}
}
j=0;
for（i=1,j=0;i<=26;i++）//统计有多少种字符
if（temp[i]!
=0）{
j++;
str[j]=i+64;//将对应的数组送到数组中
cnt[j]=temp[i];//存入对应数组的权值
}
returnj;
}
voidChuffmanTree（HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]）
{//构造赫夫曼树HT
inti,s1,s2;
for（i=1;i<=2*num-1;i++）//初始化HT，左右孩子，双亲，权值都为0
{HT[i].lchild=0;HT[i].rchild=0;
HT[i].parent=0;HT[i].weight=0;
}
for（i=1;i<=num;i++）//输入num个叶节点的权值
HT[i].weight=cnt[i];
for（i=num+1;i<=2*num-1;i++）//从numd后面开始新建结点存放新生成的父节点
{
select（HT,i-1,&s1,&s2）;//在HT[1……i-1]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2
HT[s1].parent=i;HT[s2].parent=i;//将s1和s2的parent赋值
HT[i].lchild=s1;HT[i].rchild=s2;//新结点的左右孩子
HT[i].weight=HT[s1].weight+HT[s2].weight;//新结点的权值
}
for（i=0;i<=num;i++）//输入字符集中的字符
HC[i].ch=str[i];
i=1;
while（i<=num）
printf（"字符%c,次数为:
%d\n",HC[i].ch,cnt[i++]）;
}
voidHuffmanEncoding（HuffmanTreeHT,HuffmanCodeHC）
{//根据赫夫曼树HT求赫夫曼编码表HC
intc,p,i,j;//c和p分别指示T中孩子和双亲的位置
charcd[n];//临时存放编码串
intstart;//指示编码在cd中的起始位置
cd[num]='\0';//最后一位放上串结束符
for（i=1;i<=num;i++）
{
start=num;//初始位置
c=i;//从叶子节点T[i]开始上溯
while（（p=HT[c].parent）>0）//直至上溯到HT[c]是树根为止
{//若T[c]是T[p]的做孩子，则生成0；否则生成代码1
cd[--start]=（HT[p].lchild==c）?
'0':
'1';//cd数组用来存放每一个字母对应的01编码，
c=p;
}//while结束
strcpy（HC[i].bits,&cd[start]）;//将cd数组中德01代码复制到i结点中
HC[i].len=num-start;
}//for结束
}
voidcoding（HuffmanCodeHC,char*str）
{
inti,j;
FILE*fp;
fp=fopen（"codefile.txt","w"）;
while（*str）{
for（i=1;i<=num;i++）
if（HC[i].ch==*str）{
for（j=0;jfputc（HC[i].bits[j],fp）;
}
break;
}
str++;
}
fclose（fp）;
}
char*decode（HuffmanCodeHC）
{//代码文件coodfile.txt的译码*菡枫*
FILE*fp;
charstr[254];//假设原文本文件不超过254个字符
char*p;
staticcharcd[n+1];
inti,j,k=0,cjs;
fp=fopen（"codefile.txt","r"）;//读文件
while（!
feof（fp））
{cjs=0;
for（i=0;ifeof（fp）;i++）
{
cd[i]='';
cd[i+1]='\0';
cd[i]=fgetc（fp）;
for（j=1;j<=num;j++）
if（strcmp（HC[j].bits,cd）==0）//查找所有的字母的对应的编码，如果有相同的则将该字母放入str中
{
str[k]=HC[j].ch;
k++;
cjs=1;
break;
}
}
}
str[k]='\0';
p=str;
returnp;
}
voidmain（）{
charst[254],*s,str[27];
intcn[27];
HuffmanTreeHT;
HuffmanCodeHC;
printf（"输入需要编码的字符串（假设均为大写字母）:
\n"）;
gets（st）;
num=jsq（st,cn,str）;//统计字符的种类及各类字符出现的频率
ChuffmanTree（HT,HC,cn,str）;//建立赫夫曼树
HuffmanEncoding（HT,HC）;//生成赫夫曼编码
coding（HC,st）;//建立电文赫夫曼编码文件
s=decode（HC）;//读编码文件译码
printf（"译码后的字符串:
\n"）;
printf（"%s\n",s）;
}
升级会员 