哈夫曼编译码Word文档下载推荐.docx
《哈夫曼编译码Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《哈夫曼编译码Word文档下载推荐.docx（24页珍藏版）》请在冰点文库上搜索。
本实验拟设其中的数据为abbcccdddd.
二、概要设计
1.总体设计
一个完整的系统应具有以下功能：
（1）I：
初始化（Initialization）。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
（2）E：
编码（Encoding）。
利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
（3）D：
译码（Decoding）。
利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
（4）P：
印代码文件（Print）。
将文件CodeFile以紧凑格式显示在终端上，每行50个代码。
同时将此字符形式的编码写入文件CodePrint中。
（5）T：
印哈夫曼树（TreePrinting）。
将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
2.函数划分：
该程序有一个主函数和多个子函数，主函数完成对子函数的调用，各子函数实现相应的功能。
可以定义相应的抽象数据类型。
三、详细设计
1.算法
voidCrtHuffmanTree（HuffmanTree*ht,int*w,ElemTypes*d,intn）
{/*w存放已知的n个权值，构造哈夫曼树ht*/
intm,i;
ints1,s2;
m=2*n-1;
*ht=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
/*0号单元未使用*/
for（i=1;
i<
=n;
i++）
{/*1-n号放叶子结点，初始化*/
（*ht）[i].weight=w[i];
（*ht）[i].data=d[i];
（*ht）[i].LChild=0;
（*ht）[i].parent=0;
（*ht）[i].RChild=0;
}
for（i=n+1;
=m;
i++）
{
（*ht）[i].weight=0;
}/*非叶子结点初始化*/
/*------------初始化完毕！
对应算法步骤1---------*/
i++）/*创建非叶子结点,建哈夫曼树*/
{/*在（*ht）[1]~（*ht）[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/
select（ht,i-1,&
s1,&
s2）;
（*ht）[i].data=NULL;
（*ht）[s1].parent=i;
（*ht）[s2].parent=i;
（*ht）[i].LChild=s1;
（*ht）[i].RChild=s2;
（*ht）[i].weight=（*ht）[s1].weight+（*ht）[s2].weight;
}
}
voidPrint_d（HuffmanTree*HT,intm,charch,intn,FILE*fp,FILE*fps）{//译码，递归调用
charc;
if（!
feof（fp））{//当文件CodeFile未结束
if（ch=='
1'
）{
if（（*HT）[（*HT）[m].RChild].RChild==0）{//当到达叶子节点时
printf（"
%c"
（*HT）[（*HT）[m].RChild].data）;
//输出翻译后的字符
fprintf（fps,"
intm=2*n-1;
c=fgetc（fp）;
Print_d（HT,m,c,n,fp,fps）;
}
else{//未到达叶子结点时，继续从文件CodeFile读入01代码
Print_d（HT,（*HT）[m].RChild,c,n,fp,fps）;
}
0'
）{
if（（*HT）[（*HT）[m].LChild].LChild==0）{//当到达叶子节点时
（*HT）[（*HT）[m].LChild].data）;
else{
Print_d（HT,（*HT）[m].LChild,c,n,fp,fps）;
}
voidPrintTree（HuffmanTreeHT,intm,intnLayer）/*按竖向树状打印的二叉树*/
{
if（m!
=0）{
if（HT==NULL）
return;
PrintTree（HT,HT[m].RChild,nLayer+1）;
for（inti=0;
nLayer;
printf（"
-"
）;
printf（"
%d\n"
HT[m].weight）;
PrintTree（HT,HT[m].LChild,nLayer+1）;
2.主要函数的实现
CrtHuffmanTree（&
HT,w,d,n）;
//构建哈夫曼树。
CrtHuffmanCode（&
HT,&
HC,n,flag）;
//对哈夫曼树编码
//对文件编码
Print_d（&
HT,m,ch,n,fp,fps）;
//译码
PrintTree（HT,m,nLayer）;
//打印
四、调试结果
五、课程设计总结
1、遇难到哪些问题，解决的方法。
一些算法的构成不理解，并且不会自己编写，对哈夫曼译码的算法不会等
2、通过本次课程设计，自己得到了哪些方面的训练和提高（经验和教训）。
多看书，多上网查资料，多向老师同学请教等，重视基本知识的运用，结合实际等
六、附源程序清单
#include<
stdio.h>
stdlib.h>
string.h>
#defineElemTypeschar
typedefchar*HuffmanCode;
/*动态分配数组，存储哈夫曼编码*/
typedefstruct
ElemTypesdata;
unsignedintweight;
/*用来存放各个结点的权值*/
unsignedintparent,LChild,RChild;
/*指向双亲、孩子结点的指针*/
}HTNode,*HuffmanTree;
/*动态分配数组，存储哈夫曼树*/
voidselect（HuffmanTree*ht,intn,int*s1,int*s2）
inti;
intmin;
i<
i++）
if（（*ht）[i].parent==0）
{
min=i;
i=n+1;
if（（*ht）[i].weight<
（*ht）[min].weight）
min=i;
*s1=min;
if（（*ht）[i].parent==0&
&
i!
=（*s1））
*s2=min;
voidCrtHuffmanCode（HuffmanTree*ht,HuffmanCode*hc,intn,intflag）
/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/
char*cd;
unsignedintc;
intstart;
intp;
hc=（HuffmanCode*）malloc（（n+1）*sizeof（char*））;
/*分配n个编码的头指针*/
cd=（char*）malloc（n*sizeof（char））;
/*分配求当前编码的工作空间*/
cd[n-1]='
\0'
;
/*从右向左逐位存放编码，首先存放编码结束符*/
i++）/*求n个叶子结点对应的哈夫曼编码*/
start=n-1;
/*初始化编码起始指针*/
for（c=i,p=（*ht）[i].parent;
p!
=0;
c=p,p=（*ht）[p].parent）/*从叶子到根结点求编码*/
if（（*ht）[p].LChild==c）
cd[--start]='
/*左分支标0*/
else
/*右分支标1*/
hc[i]=（char*）malloc（（n-start）*sizeof（char））;
/*为第i个编码分配空间*/
strcpy（hc[i],&
cd[start]）;
free（cd）;
if（flag==2）{
FILE*fp1;
if（（fp1=fopen（"
e:
\\hfmTree.txt"
"
w"
））==NULL）{//创建文件hfmTree存储字符形式的编码
Fileopenerror!
\n"
exit（0）;
\n将下面的哈夫曼树写入文件hfmTree.txt中.\n"
fprintf（fp1,"
字符\t权值\t编码\n"
for（i=1;
i++）{
%c\t%d\t%s\n"
（*ht）[i].data,（*ht）[i].weight,hc[i]）;
fprintf（fp1,"
//写入文件hfmTree中
\n成功写入!
if（fclose（fp1））{//关闭文件
Cannotclosethefile!
if（flag==1）{//当flag==1时对文件ToBeTran编码
FILE*fp;
FILE*fps;
charch;
inti;
if（（fp=fopen（"
\\ToBeTran.txt"
r"
））==NULL）{//从文件ToBeTran中读取要编码的文章。
exit（0）;
}
if（（fps=fopen（"
\\CodeFile.txt"
））==NULL）{//创建文件CodeFile存储文件ToBeTran的编码
\n对文件ToBeTran.txt的文章进行编码:
while（!
feof（fp））{
ch=fgetc（fp）;
for（i=1;
if（ch!
='
if（ch==（*ht）[i].data）{
fprintf（fps,"
%s"
hc[i]）;
printf（"
}
}
\n代码成功保存到文件CodeFile.txx中.\n\n"
if（fclose（fp））{//关闭文件
if（fclose（fps））{//关闭文件
voidTreePrint（HuffmanTree*ht,intm）{
FILE*fp;
if（（fp=fopen（"
\\TreePrint.txt"
））==NULL）{//同时将此字符形式的哈夫曼树写入文件TreePrint中
exit（0）;
printf（"
将字符形式的哈夫曼树存储到文件TreePrint中.\n"
fprintf（fp,"
编号\t字符\t权值\tparent\tLChild\tRChild\n"
fprintf（fp,"
%d\t%c\t%d\t%d\t%d\t%d\n"
i,（*ht）[i].data,（*ht）[i].weight,（*ht）[i].parent,（*ht）[i].LChild,（*ht）[i].RChild）;
存储成功!
if（fclose（fp））{//关闭文件
voidPutCode（）{
charch;
inti=0;
））==NULL）{//读取01代码输出文件CodeFile.txt中的代码
while（!
ch=fgetc（fp）;
if（ch!
ch）;
i=i+1;
if（i%50==0）
voidmain（）
{
HuffmanTreeHT;
HuffmanCodeHC;
FILE*fp,*fps,*fpss;
int*w;
char*d,str[1000],s[2];
chardata,ch;
inti,n,choice;
//结点个数;
intwei;
//权值;
intm,flag;
intnLayer=0;
***********************************************************\n"
***\t\t\t哈夫曼编译码\t\t\t***\n"
do{
*\t\t输入你要选择的选项（请先选择1）\t\t*\n"
*\t\t\t1.初始化哈夫曼树\t\t*\n"
*\t\t\t2.对文件编码\t\t\t*\n"
*\t\t\t3.对译文
升级会员 