哈夫曼编译码器课程设计报告完整版.docx
《哈夫曼编译码器课程设计报告完整版.docx》由会员分享，可在线阅读，更多相关《哈夫曼编译码器课程设计报告完整版.docx（34页珍藏版）》请在冰点文库上搜索。
哈夫曼编译码器课程设计报告完整版
哈夫曼编译码器课程设计报告（完整版）
LT
一、设计题目（任选其一）
实验一、哈夫曼编/译码器
二、实验目的
1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；
2深化对算法课程中基本概念、理论和方法的理解；
3巩固构造赫夫曼树的算法；
4设计试验用程序实验赫夫曼树的构造。
三、运行环境（软、硬件环境）
Windowsxpsp3，VisualC++6.0英文版
四、算法设计的思想
（1）初始化赫夫曼树，输入文件tobetrans.txt中各字符及其权值，并保存于hfmtree.txt文件中
（2）编码（Coding）。
对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中
（3）D：
解码（Decoding）。
利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。
（4）P：
打印代码文件（Print）。
将文件codefile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码文件写入文件codeprint中。
（5）T：
打印哈夫曼树（TreePrinting）。
将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。
五、流程图
六、算法设计分析
1.赫夫曼树节点的数据类型定义为：
typedefstruct{//赫夫曼树的结构体
charch;
intweight;//权值
intparent,lchild,rchild;
}HTNode,*HuffmanTree;
2.voidHuffmanCoding（HuffmanTree&,char*,int*,int）;建立赫夫曼树的算法，此函数块调用了Select（）函数。
voidselect（HuffmanTreeHT,intj,int*x,int*y）;从已建好的赫夫曼树中选择parent为0，weight最小的两个结点。
3．利用已建好的哈夫曼树从文件hfmtree.txt中读入，对文件中的正文进行编码，然后将结果存入文件codefile.txt中。
4.coding
编码功能：
对输入字符进行编码
5.Decoding
译码功能：
利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码，结果存入文件textfile.txt中。
6.Print（）打印功能函数：
输出哈夫曼树以及对应的编码。
七、源代码
//////////////////////////////////////////////////////////////////////////////////////////
#include
#include
#include
//定义赫夫曼树结点的结构体
typedefstruct{
charch;//增加一个域，存放该节点的字符
intweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;//指向赫夫曼编码的指针
voidtips（）;//打印操作选择界面
voidHuffmanCoding（HuffmanTree&,char*,int*,int）;//建立赫夫曼树的算法
voidselect（HuffmanTreeHT,intj,int*x,int*y）;//从已建好的赫夫曼树中选择parent为0，weight最小的两个结点
voidInit（）;
voidCoding（）;//编码
voidDecoding（）;//译码
voidPrint_code（）;//打印译码好的代码
voidPrint_tree（）;//打印哈夫曼树
intRead_tree（HuffmanTree&）;//从文件中读入赫夫曼树
voidfind（HuffmanTree&HT,char*code,char*text,inti,intm）;//译码时根据01字符串寻找相应叶子节点的递归算法
voidConvert_tree（unsignedcharT[100][100],ints,int*i,intj）;//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树
HuffmanTreeHT;//全局变量
intn=0;//全局变量，存放赫夫曼树叶子结点的数目
intmain（）
{
charselect;
while
（1）
{
tips（）;
scanf（"%c",&select）;
switch（select）//选择操作，根据不同的序号选择不同的操作
{
case'1':
Init（）;
break;
case'2':
Coding（）;
break;
case'3':
Decoding（）;
break;
case'4':
Print_code（）;
break;
case'5':
Print_tree（）;
break;
case'0':
exit
（1）;
default:
printf（"Inputerror!
\n"）;
}
getchar（）;
}
return0;
}
voidtips（）//操作选择界面
{
printf（"-----------------------------------------------------\n"）;
printf（"--请选择操作--\n"）;
printf（"-----------------------------------------------------\n"）;
printf（"\n"）;
printf（"---------------------1初始化赫夫曼树---------------\n"）;
printf（"---------------------2编码---------------\n"）;
printf（"---------------------3译码---------------\n"）;
printf（"---------------------4打印代码文件---------------\n"）;
printf（"---------------------5打印赫夫曼树---------------\n"）;
printf（"---------------------0退出---------------\n"）;
printf（"-----------------------------------------------------\n"）;
}
//初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中
voidInit（）
{
FILE*fp;
inti,n,w[52];//数组存放字符的权值
charcharacter[52];//存放n个字符
printf（"\n输入字符个数n:
"）;
scanf（"%d",&n）;//输入字符集大小
printf（"输入%d个字符及其对应的权值:
\n",n）;
for（i=0;i{
charb=getchar（）;
scanf（"%c",&character[i]）;
scanf（"%d",&w[i]）;//输入n个字符和对应的权值
}
HuffmanCoding（HT,character,w,n）;//建立赫夫曼树
if（（fp=fopen（"hfmtree.txt","w"））==NULL）
printf（"Openfilehfmtree.txterror!
\n"）;
for（i=1;i<=2*n-1;i++）
{
if（fwrite（&HT[i],sizeof（HTNode）,1,fp）!
=1）//将建立的赫夫曼树存入文件hfmtree.txt中
printf（"Filewriteerror!
\n"）;
}
printf（"\n赫夫曼树建立成功，并已存于文件hfmtree.txt中\n"）;
fclose（fp）;
}
//建立赫夫曼树的算法
voidHuffmanCoding（HuffmanTree&HT,char*character,int*w,intn）
{
intm,i,x,y;
HuffmanTreep;
if（n<=1）return;
m=2*n-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
for（p=HT+1,i=1;i<=n;++i,++p,++character,++w）
{p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}
for（;i<=m;++i,++p）{p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}
for（i=n+1;i<=m;++i）
{
select（HT,i-1,&x,&y）;
HT[x].parent=i;HT[y].parent=i;
HT[i].lchild=x;HT[i].rchild=y;
HT[i].weight=HT[x].weight+HT[y].weight;
}
}
//从HT[1]到HT[j]中选择parent为0，weight最小的两个结点，用x和y返回其序号
voidselect（HuffmanTreeHT,intj,int*x,int*y）
{
inti;
//查找weight最小的结点
for（i=1;i<=j;i++）
if（HT[i].parent==0）
{*x=i;break;}
for（;i<=j;i++）
if（（HT[i].parent==0）&&（HT[i].weight*x=i;
HT[*x].parent=1;
//查找weight次小的结点
for（i=1;i<=j;i++）
if（HT[i].parent==0）
{*y=i;break;}
for（;i<=j;i++）
if（（HT[i].parent==0）&&（i!
=*x）&&（HT[i].weight*y=i;
}
//对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中
voidCoding（）
{
FILE*fp,*fw;
inti,f,c,start;
char*cd;
HuffmanCodeHC;
if（n==0）
n=Read_tree（HT）;//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数
//求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中
{
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;
cd=（char*）malloc（n*sizeof（char））;
cd[n-1]='\0';
for（i=1;i<=n;++i）
{
start=n-1;
for（c=i,f=HT[i].parent;f!
=0;c=f,f=HT[f].parent）
if（HT[f].lchild==c）
cd[--start]='0';
elsecd[--start]='1';
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
strcpy（HC[i],&cd[start]）;
}
free（cd）;
}
if（（fp=fopen（"tobetrans.txt","rb"））==NULL）
printf（"Openfiletobetrans.txterror!
\n"）;
if（（fw=fopen（"codefile.txt","wb+"））==NULL）
printf（"Openfilecodefile.txterror!
\n"）;
chartemp;
fscanf（fp,"%c",&temp）;//从文件读入第一个字符
while（!
feof（fp））
{
for（i=1;i<=n;i++）
if（HT[i].ch==temp）break;//在赫夫曼树中查找字符所在的位置
for（intr=0;HC[i][r]!
='\0';r++）//将字符对应的编码存入文件
fputc（HC[i][r],fw）;
fscanf（fp,"%c",&temp）;//从文件读入下一个字符
}
fclose（fw）;
fclose（fp）;
printf（"\n已将文件hfmtree.txt成功编码,并已存入codefile.txt中！
\n\n"）;
}
//将文件codefile中的代码进行译码，结果存入文件textfile中
voidDecoding（）
{
FILE*fp,*fw;
intm,i;
char*code,*text,*p;
if（n==0）
n=Read_tree（HT）;//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数
if（（fp=fopen（"codefile.txt","rb"））==NULL）
printf（"Openfilecodefile.txterror!
\n"）;
if（（fw=fopen（"textfile.txt","wb+"））==NULL）
printf（"Openfiletextfile.txterror!
\n"）;
code=（char*）malloc（sizeof（char））;
fscanf（fp,"%c",code）;//从文件读入一个字符
for（i=1;!
feof（fp）;i++）
{
code=（char*）realloc（code,（i+1）*sizeof（char））;//增加空间
fscanf（fp,"%c",&code[i]）;//从文件读入下一个字符
}
code[i-1]='\0';
//codefile.txt文件中的字符已全部读入，存放在code数组中
text=（char*）malloc（100*sizeof（char））;
p=text;
m=2*n-1;
if（*code=='0'）
find（HT,code,text,HT[m].lchild,m）;//从根节点的左子树去找
else
find（HT,code,text,HT[m].rchild,m）;//从根节点的右子树去找
for（i=0;p[i]!
='\0';i++）//把译码好的字符存入文件textfile.txt中
fputc（p[i],fw）;
fclose（fp）;
fclose（fw）;
printf（"\n已将codefile.txt文件成功译码，兵已存入textfile.txt文件！
\n\n"）;
}
//将文件codefi1e以紧凑格式显示在终端上,每行50个代码。
同时将此字符形式的编码文件写入文件codeprint中。
voidPrint_code（）
{
FILE*fp,*fw;
chartemp;
inti;
if（（fp=fopen（"codefile.txt","rb"））==NULL）
printf（"Openfilecodefile.txterror!
\n"）;
if（（fw=fopen（"codeprint.txt","wb+"））==NULL）
printf（"Openfilecodeprint.txterror!
\n"）;
printf（"\n文件codefi1e显示如下:
\n"）;
fscanf（fp,"%c",&temp）;//从文件读入一个字符
for（i=1;!
feof（fp）;i++）
{
printf（"%c",temp）;
if（i%50==0）printf（"\n"）;
fputc（temp,fw）;//将该字符存入文件codeprint.txt中
fscanf（fp,"%c",&temp）;//从文件读入一个字符
}
printf（"\n\n已将此字符形式的编码写入文件codeprint.txt中！
\n\n"）;
fclose（fp）;
fclose（fw）;
}
//将已在内存中的哈夫曼树显示在屏幕上，并将此字符形式的哈夫曼树写入文件treeprint中。
voidPrint_tree（）
{
unsignedcharT[100][100];
inti,j,m=0;
FILE*fp;
if（n==0）
n=Read_tree（HT）;//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数
Convert_tree（T,0,&m,2*n-1）;//将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中
if（（fp=fopen（"treeprint.txt","wb+"））==NULL）
printf（"Openfiletreeprint.txterror!
\n"）;
printf（"\n打印已建好的赫夫曼树：
\n"）;
for（i=1;i<=2*n-1;i++）
{
for（j=0;T[i][j]!
=0;j++）
{
if（T[i][j]==''）{printf（""）;fputc（T[i][j],fp）;}
else
{printf（"%d",T[i][j]）;fprintf（fp,"%d\n",T[i][j]）;}
}
printf（"\n"）;
}
fclose（fp）;
printf（"\n已将该字符形式的哈夫曼树写入文件treeprint.txt中！
\n\n"）;
}
//从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数
intRead_tree（HuffmanTree&HT）
{
FILE*fp;
inti,n;
HT=（HuffmanTree）malloc（sizeof（HTNode））;
if（（fp=fopen（"hfmtree.txt","r"））==NULL）
printf（"Openfilehfmtree.txterror!
\n"）;
for（i=1;!
feof（fp）;i++）
{
HT=（HuffmanTree）realloc（HT,（i+1）*sizeof（HTNode））;//增加空间
fread（&HT[i],sizeof（HTNode）,1,fp）;//读入一个节点信息
}
fclose（fp）;
n=（i-1）/2;
returnn;
}
//译码时根据01字符串寻找相应叶子节点的递归算法
voidfind（HuffmanTree&HT,char*code,char*text,inti,intm）
{
if（*code!
='\0'）//若译码未结束
{
code++;
if（HT[i].lchild==0&&HT[i].rchild==0）//若找到叶子节点
{
*text=HT[i].ch;//将叶子节点的字符存入text中
text++;
if（（*code=='0'））
find（HT,code,text,HT[m].lchild,m）;//从根节点的左子树找
else
find（HT,code,text,HT[m].rchild,m）;//从根节点的右子树找
}
else//如果不是叶子节点
if（*code=='0'）
find（HT,code,text,HT[i].lchild,m）;//从该节点的左子树去找
else
find（HT,code,text,HT[i].rchild,m）;//从该节点的右子树去找
}
else
*text='\0';//译码结束
}
//将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来
voidConvert_tree（unsignedcharT[100][100],ints,int*i,intj）
{
intk,l;
l=++（*i）;
for（k=0;kT[l][k]='';
T[l][k]=HT[j].weight;
if（HT[j].lchild）
Convert_tree（T,s+1,i,HT[j].lchild）;
if（HT[j].rchild）
Convert_tree（T,s+1,i,HT[j].rchild）;
T[l][++k]='\0';
}
//////////////////////////////////////////////////////////////////////////////////////////////////
八、运行结果分析
截图说明：
1、运行后界面如图
（1）：
图
（1）
选择要选择的操作序号可以运行各个步骤；
2、初始化赫夫曼树：
输入tobetrans.txt中各元素及其出现频率，如图
（2）
图
（2）
3、编码及译码，如图（3）
图（3）
4、打印编码文件，如图（4）
图（4）
5、打印赫夫曼树，如图（5）
图（5）
6、各步骤所存的文件内容如图（6）
图（6）
九、收获及体会
课程设计是让我们充分利用我们专业课程所学知识的机会，也是我们迈向社会，从事工作前一个必不少的过程。
通过这次课程设计，我深深体会到将知识运用到实践中的重要作用。
我这两天的课程设计，是让我学会脚踏实地迈开这一步，也是为明天能稳健地在社会大潮中奔跑打下坚实的基础。
我的课程设计题目是赫夫曼编译码器。
最初做这个程序的时候，让我觉得完成这次程序设计真的是太难了，然后我查阅了课本，并去图书馆借了资料，在写这个程序的时候也参考了网上的设计流程，写完刚运行时出现了很多问题。
尤其是编码错误，导致内存无法read，通过同组人员的交流请教，逐渐明白过来，然后经过不知道多少次修改才顺利运行。
本次试验也让我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。
通过对各个步骤各个流程的控制，逐渐让我产生了兴趣，在实际编写过程中，和同学们相互讨论让我学到的不仅仅是一些解决问题的方法，更是解决问题的思想。
课程设计本身也是一种相互学习的过程,//////////////////////////////////////////////////////////////
升级会员 