哈夫曼huffman编译码器课程设计.docx
《哈夫曼huffman编译码器课程设计.docx》由会员分享，可在线阅读，更多相关《哈夫曼huffman编译码器课程设计.docx（20页珍藏版）》请在冰点文库上搜索。
哈夫曼huffman编译码器课程设计
兰州商学院陇桥学院
工学系课程设计报告
设计题目：
哈夫曼（huffman）编译码器
系别：
专业（方向）：
年级、班：
学生姓名：
学生学号：
指导教师：
年月日
哈夫曼（huffman）编译码器
1、编译码器开发的背景
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
二、系统的分析与设计
（一）系统功能要求
一个完整的系统应具有以下功能：
1）I：
初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
2）E：
编码（Encoding）。
利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
3）D：
译码（Decoding）。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
4）P：
印代码文件（Print）。
将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。
5）T：
印哈夫曼树（TreePrinting）。
将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
（二）系统模块结构设计
通过对系统功能的分析，哈夫曼（huffman）编译码器功能如图
（1）所示。
哈夫曼（huffman）编译码器
图
（1）哈夫曼（huffman）编译码器功能图
通过上图的功能分析，把整个系统分为四个模块：
1.初始化模块，该模块主要实现：
输入二叉树的结点数，以及要加密的句子，建立哈夫曼树。
2.输出二叉树模块，该运算模块主要实现：
将输入的字符串中每个字符出现的次数当作权值，建立二叉树，将二叉树的parent,weight,lchild,rchild输出。
3.译码模块，该操作主要实现：
对编码后的代码进行译码，然后输出。
4.输出模块，该操作主要进行表头的输出。
图２ 流程图
三、系统的设计与实现
（一）main（）
输出1.输出二叉树操作2.进行输出二叉树操作3.退出编译码操作系统，并让用户选择所进行的操作，对其调用。
该模块的具体代码如下所示：
voidmain（）
{
inti,n,s=1;
hnodetypehuffnode[maxnode];
while（s）
{
shuchu（）;
scanf（"%d",&i）;
switch（i）
{
case1:
{
haffmantree（huffnode,&n）;
break;
}
case2:
{
haffmancode（）;
break;
}
case3:
s=0;
break;
}
}
}
分析：
首先输出一个主菜单，方便用户进行操作，用switch语句调用函数使用户对其进行选择要执行的操作（1.输出二叉树操作，2.进行编译码操作，3.退出程序）。
（二）运算
该模块的具体代码如下所示：
1.权值运算quanzhi（）
分析：
此函数用于对一串字符进行求权值运算，利用循环将一串字符中每个字符的个数设定为权值。
voidquanzhi（intt[maxleaf],chars[maxleaf],intn）//求权值函数，将句子中的字符出现的个数当作权值
{
inti,j,h;
for（i=0;i{
for（j=0;jif（s[i]==s[j]）
h++;
t[i]=h;
}
}
2.印二叉树函数huffmantree（）
voidhaffmantree（hnodetypehuffnode[maxnode],int*m）
{
inti,j,n,k;
intm1,m2,x1,x2;
chars[maxleaf],t[maxleaf];
printf（"输入叶子结点个数：
"）;
scanf（"%d",&n）;
for（i=0;i<2*n-1;i++）//数组huffnode[]初始化
{
huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
}
printf（"输入要编译的句子的\n"）;
for（i=0;iprintf（"第%d个结点",i+1）;
scanf（"%d",&huffnode[i].weight）;
getchar（）;
}
printf（"印二叉树：
\n"）;
for（i=0;i{
quanzhi（t,s,n）;
k=huffnode[i].weight;
}
for（i=0;i{//构造哈夫曼树
m1=m2=maxvalue;
x1=x2=0;
for（j=0;j{//选取最小和次小两个权值
if（huffnode[j].parent==-1&&huffnode[j].weight{
m2=m1;
x2=x1;
m1=huffnode[j].weight;
x1=j;
}
else
if（huffnode[j].parent==-1&&huffnode[j].weight{
m2=huffnode[j].weight;
x2=j;
}
}//将找出的两棵子树合并为一颗子树
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for（i=0;i<2*n-1;i++）
{
printf（"%4d",k）;
printf（"%4d",huffnode[i].lchild）;
printf（"%4d",huffnode[i].rchild）;
printf（"%4d\n",huffnode[i].parent）;
}
*m=n;
}
3.编译码运算huffmancode（）
voidhaffmancode（）
{
hnodetypehuffnode[maxnode];
hcodetypehuffcode[maxleaf],cd;
inti,j,c,p,n=0;
haffmantree（huffnode,&n）;
for（i=0;i{
cd.start=n-1;
c=i;
p=huffnode[c].parent;
while（p!
=-1）
{
if（huffnode[p].lchild==c）
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
for（j=cd.start+1;jhuffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
for（i=0;i{
printf（"第%d个译码为：
",i+1）;
for（j=huffcode[i].start+1;jprintf（"%4d",huffcode[i].bit[j]）;
printf（"\n"）;
}
}
4.输出运算shuchu（）
voidshuchu（）
{
printf（"********************************************************************************\n"）;
printf（"***|**哈夫曼树的编译码**|***\n"）;
printf（"***|**1.输出二叉树操作**|***\n"）;
printf（"***|**2.进行编译码操作**|***\n"）;
printf（"***|**3.退出编译码操作系统**|***\n"）;
printf（"********************************************************************************\n"）;
printf（"请选择要进行的操作:
"）;
}
四、系统测试
（一）测试主函数main（）函数
该测试主要进行对主函数调用以及输出的测试，测试的结果：
（二）测试印二叉树函数
测试选择1，选择1操作首先输入叶子节点数，然后输入要编译的句子，分别输入第n+1个节点，然后系统会将输入字符的个数当作权值进行编译输出二叉树，测试结果为：
（3）测试译码运算函数
测试选择2，输入要选择的操作2，然后按要求依次输入需要的值，系统会根据输入的数据进行译码操作，最后输出译码。
输出结果为：
（4）测试退出函数
测试选择3进行退出，测试结果为:
五、总结
系统功能：
系统完成了将一段字符串进行哈夫曼加密，用户将自己的选择输入程序，然后按照程序的提示进行输入，系统将根据输入进行编码、译码操作，然后印出编译的二叉树，以及每个字符的译码。
不足：
系统没有将印哈夫曼树操作完成，系统没有将字符的权值根据大小将左孩子设为最小权值，将次小权值设为右孩子，导致加密有许多种，哈夫曼树也创建了许多种，输出的译码不唯一。
收获：
通过一学期数据结构的学习，我发现数据结构比较难，没有完整的自己独立完成一个程序。
但也学到了许多东西，学会了以前不会的函数调用，在编程时，有许多小问题还是不能够及时的发现，老是被一点小问题卡住导致程序不执行或输出死循环，一些程序的指针还不太熟悉。
通过这次程序设计，我发现了许多自己的不足，对一些算法还不能熟练运用，不能将所学的运用到程序中，一些语句还是不太懂；同时，也有一些收获，对函数调用能够熟练运用，也明白了结构体的作用，掌握了最优二叉树的建立和原理，对哈夫曼树有了更深一步的了解。
六、附件（代码、部分图表）
/*哈弗曼树*/
#include
#definemaxvalue1000//定义最大权值
#definemaxleaf50//定义哈夫曼树中叶子结点个数
#definemaxnodemaxleaf*2-1//定义哈夫曼树中结点个数整数常量maxnode
#definemaxbit100//定义哈夫曼树的最大长度整数常量
typedefstruct//定义结构体
{
intweight;
intparent;
intlchild;
intrchild;
}hnodetype;
typedefstruct
{
intbit[maxbit];
intstart;
}hcodetype;
//求权值函数
voidquanzhi（intt[maxleaf],chars[maxleaf],intn）//求权值函数，将句子中的字符出现的个数当作权值
{
inti,j,h;
for（i=0;i{
for（j=0;jif（s[i]==s[j]）
h++;
t[i]=h;
}
}
//印二叉树函数
voidhaffmantree（hnodetypehuffnode[maxnode],int*m）
{
inti,j,n,k;
intm1,m2,x1,x2;
chars[maxleaf],t[maxleaf];
printf（"输入叶子结点个数：
"）;
scanf（"%d",&n）;
for（i=0;i<2*n-1;i++）//数组huffnode[]初始化
{
huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
}
printf（"输入要编译的句子的\n"）;
for（i=0;iprintf（"第%d个结点",i+1）;
scanf（"%d",&huffnode[i].weight）;
getchar（）;
}
printf（"印二叉树：
\n"）;
for（i=0;i{
quanzhi（t,s,n）;
k=huffnode[i].weight;
}
for（i=0;i{//构造哈夫曼树
m1=m2=maxvalue;
x1=x2=0;
for（j=0;j{//选取最小和次小两个权值
if（huffnode[j].parent==-1&&huffnode[j].weight{
m2=m1;
x2=x1;
m1=huffnode[j].weight;
x1=j;
}
else
if（huffnode[j].parent==-1&&huffnode[j].weight{
m2=huffnode[j].weight;
x2=j;
}
}//将找出的两棵子树合并为一颗子树
huffnode[x1].parent=n+i;
huffnode[x2].parent=n+i;
huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
huffnode[n+i].lchild=x1;
huffnode[n+i].rchild=x2;
}
for（i=0;i<2*n-1;i++）
{
printf（"%4d",k）;
printf（"%4d",huffnode[i].lchild）;
printf（"%4d",huffnode[i].rchild）;
printf（"%4d\n",huffnode[i].parent）;
}
*m=n;
}
//编译码函数
voidhaffmancode（）
{
hnodetypehuffnode[maxnode];
hcodetypehuffcode[maxleaf],cd;
inti,j,c,p,n=0;
haffmantree（huffnode,&n）;
for（i=0;i{
cd.start=n-1;
c=i;
p=huffnode[c].parent;
while（p!
=-1）
{
if（huffnode[p].lchild==c）
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
c=p;
p=huffnode[c].parent;
}
for（j=cd.start+1;jhuffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
}
for（i=0;i{
printf（"第%d个译码为：
",i+1）;
for（j=huffcode[i].start+1;jprintf（"%4d",huffcode[i].bit[j]）;
printf（"\n"）;
}
}
//输出主菜单函数
voidshuchu（）
{
printf（"********************************************************************************\n"）;
printf（"***|**哈夫曼树的编译码**|***\n"）;
printf（"***|**1.输出二叉树操作**|***\n"）;
printf（"***|**2.进行编译码操作**|***\n"）;
printf（"***|**3.退出编译码操作系统**|***\n"）;
printf（"********************************************************************************\n"）;
printf（"请选择要进行的操作:
"）;
}
//主函数
voidmain（）
{
inti,n,s=1;
hnodetypehuffnode[maxnode];
while（s）
{
shuchu（）;
scanf（"%d",&i）;
switch（i）
{
case1:
{
haffmantree（huffnode,&n）;
break;
}
case2:
{
haffmancode（）;
break;
}
case3:
s=0;
break;
}
}
}
升级会员 