实验四 赫夫曼.docx
《实验四 赫夫曼.docx》由会员分享，可在线阅读，更多相关《实验四 赫夫曼.docx（16页珍藏版）》请在冰点文库上搜索。
实验四赫夫曼
目录
1.概述1
1.1问题描述1
2.现状分析1
3.系统分析1
4.1系统功能模块图2
5.1赫夫曼树的存储结构定义3
5.2赫夫曼算法及其实现3
5.3统计字符串中字符的种类以及各类字符的个数3
5.4赫夫曼编译码系统功能模块3
6.主要代码结构4
6.1定义赫夫曼编码类型如下4
6.2赫夫曼编码算法4
6.3建立正文的编码文件5
7.主要代码段分析6
7.1赫夫曼编码的结构定义6
7.2赫夫曼编码算法6
8.运行与测试7
8.1测试数据及结果7
9.总结和心得8
参考文献8
10.附：
源代码9
1.概述
1.1问题描述
利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
这要求在发送端通过一个编码系统对待传输数据预先编码，对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编码系统。
2.现状分析
在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
赫夫曼编码是一种编码方式，以赫夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。
赫夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。
赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。
树中从根到每个叶子都有一条路径，对路径上的各分支约定：
指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。
赫夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串.赫夫曼编码是已被证明的一种有效的熵编码方式,在诸如文本、图像、视频压缩及通信、密码等信息压缩编码标准中被广泛使用。
目前广泛应用的许多其他高效数据压缩算法。
3.系统分析
利用二叉树结构实现赫夫曼编/解码器。
基本要求：
1、初始化：
能够对输入的任意长度的字符串进行统计，统计每个字符的频度，并建立赫夫曼树。
2、建立编码表（CreateTable）：
利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。
3、编码（Encoding）：
根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4、译码（Decoding）：
利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。
4.概要设计
4.1系统功能模块图
赫夫曼编\译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码。
在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。
构造一棵赫夫曼树，规定赫夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为赫夫曼编码。
最简单的二进制编码方式是等长编码。
若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。
赫夫曼树课用于构造使电文的编码总长最短的编码方案。
4.1系统功能模块图
5.详细设计
5.1赫夫曼树的存储结构定义
#definen100//叶子结点数
#definem2*n-1//赫夫曼树中结点总数
typedefstruct{
intweight;//权值
intlchild,rchild,parent;//左右孩子及双亲指针
}HTNode;//树中结点类型
typedefHTNodeHuffmanTree[m+1];//零号单元不用
5.2赫夫曼算法及其实现
①根据给定的n个权值{w1,w2,···wn},构成n棵二叉树的集F={T1,T2,···Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空。
②在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。
③在F中删除这两棵树,同时将新得到的二叉树加入F中。
④重复②和③,直到F只含一棵树为止,这棵树便是赫夫曼树。
5.3统计字符串中字符的种类以及各类字符的个数
该算法的主要实现思想是：
先定义一个含有26个元素的临时整型数组，用来存储各种字母出现的次数。
因为大写字母与小写字母相差64位，所以在算法中我们可以使用字母减去64作为统计数组的下标对号入座。
在统计和保存过程中，我们用一个循环来判断先前统计的各类字符是否为零，若不为零，则将其存入一个数组对应得元素中，同时将其对应的字符也存入另一个数组元素中。
5.4赫夫曼编译码系统功能模块
（1）赫夫曼建树模块:
根据输入的字符和频率,完成赫夫曼树的构造,并根据赫夫曼树求赫夫曼编码。
（2）编码模块:
读取文本文件进行编码,编码结果存入到新文件。
（3）译码模块:
读取编码文件并解码,打开存储编码的文件,根据所读取的编码文件中的每字符,利用赫夫曼树进行解码。
（4）输出模块:
将解码后的每个字母写入到一个新的文件中。
6.主要代码结构
6.1定义赫夫曼编码类型如下
typedefstruct{
charch;//存放编码的字符
charbits[n+1];//存放编码的位置
intstart;//编码起始位置
}CodeNode;
typedefCodeNodeHuffmanCode[n];
6.2赫夫曼编码算法
voidHuffmanEncoding（HuffmanTreeHT,HuffmanCodeHC）
{
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）
{
cd[--start]=（HT[p].lchild==c）?
'0':
'1';
c=p;
}
strcpy（HC[i].bits,&cd[start]）;
HC[i].len=num-start;
}
}
6.3建立正文的编码文件
建立正文的编码文件的基本思想是：
将要编码的字符串中的字符逐一与预先生成赫夫曼树是保存的字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有的字符处理完为止。
具体实现算法如下：
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）;
}
7.主要代码段分析
赫夫曼编码可以用于通信技术，它的定义是树从根结点到每个叶子结点的路径上的各分支进行约定，指向左子树对的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。
7.1赫夫曼编码的结构定义
typedefstruct{
charch;//存放编码的字符
charbits[n+1];//存放编码的位置
intstart;//编码起始位置
}CodeNode;
typedefCodeNodeHuffmanCode[n];
7.2赫夫曼编码算法
voidHuffmanEncoding（HuffmanTreeHT,HuffmanCodeHC）
{//根据赫夫曼树HT求赫夫曼编码HC
intc,p,i;//c和p分别指示HT中孩子和双亲的位置
charcd[n];//临时存放编码串
intstart;//指示编码在cd中起始位置
cd[num]='\0';//最后一位放上结束符
for（i=1;i<=num;i++）
{
start=num;//起始位置
c=i;//从叶子结点HT[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;
}
strcpy（HC[i].bits,&cd[start]）;
HC[i].len=num-start;
}
}
8.运行与测试
8.1测试数据及结果
输入：
NOMANCANDOTWOTHINGSATONCE,得出结果：
9.总结和心得
通过这次课程设计，我们学习了很多在上课没懂的知识，并对求赫夫曼树及赫夫曼编码/译码的算法有了更加深刻的了解。
更巩固了课堂中学习有关于赫夫曼编码的知识.
参考文献
[1]《数据结构课程设计》-----苏仕华等编著
[2]《数据结构（C语言版）》-----严蔚敏吴伟民编著
[3]《C程序设计（第三版）》------谭浩强著
10.附：
源代码
#include
#include
/*
（1）类型及相关变量的定义*/
#definen100//叶子结点数
#definem2*n-1//赫夫曼树中的结点总数
typedefstruct{
charch;
charbits[9];//存放编码位串
intlen;//编码长度
}CodeNode;
typedefCodeNodeHuffmanCode[n+1];
typedefstruct{
intweight;//权值
intlchild,rchild,parent;//左右孩子及双亲指针
}HTNode;//树中的结点类型
typedefHTNodeHuffmanTree[m+1];//0号单元不可用
intnum;//字母类型的个数
/*
（2）建立赫夫曼树的三个函数*/
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++]）;
}
/*（3）生成赫夫曼编码文件的两个函数*/
voidHuffmanEncoding（HuffmanTreeHT,HuffmanCodeHC）
{//根据赫夫曼树HT求赫夫曼编码表HC
intc,p,i;//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;
}//endofwhile
strcpy（HC[i].bits,&cd[start]）;//将cd数组中德01代码复制到i结点中
/*printf（"字符%c:
",HC[i].ch）;
for（j=start;cd[j]!
=0;j++）
printf（"%c",cd[j]）;
printf（"\n"）;*/
HC[i].len=num-start;
}//endoffor
}
voidcoding（HuffmanCodeHC,char*str）
{//对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）;
}
/*（4）电码的译文*/
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"）;//读文件
/*printf（"编码后的文件为：
\n"）;*/
while（!
feof（fp））
{cjs=0;
for（i=0;ifeof（fp）;i++）
{
cd[i]='';
cd[i+1]='\0';
cd[i]=fgetc（fp）;
/*printf（"%c",cd[i]）;//打印出编码后的二进制码*/
for（j=1;j<=num;j++）
if（strcmp（HC[j].bits,cd）==0）//查找所有的字母的对应的编码，如果有相同的则将该字母放入str中
{
str[k]=HC[j].ch;
k++;
cjs=1;
break;
}
}
}
/*printf（"\n"）;*/
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）;//输出译码后字符串
}
升级会员 