哈夫曼编码编译器.docx
《哈夫曼编码编译器.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码编译器.docx（17页珍藏版）》请在冰点文库上搜索。
哈夫曼编码编译器
一、课题：
哈夫曼编码编译器
设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件
（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件（.txt）。
二、功能
（1）输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；
（2）将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）
（3）输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码。
三、程序结构
程序流程图
文字说明
Main函数：
Coding（）编码函数
TransCode（）译码函数
Coding（）编码函数：
clearscreen（）清屏函数
Open（）打开源码文件
SearchStr（）查找字符串中不同的字符及其出现的次数
CreatHFMTree（）用每个字符出现的次数作为叶子节点的权值建立哈夫曼树
HFMCode（）利用哈夫曼树对每个叶子节点进行编码，存入编码表中
TotalCoding（）利用编码表对字符串进行最终编码
Save（）保存最终的哈夫曼编码
TransCode（）译码函数：
clearscreen（）清屏函数
Open（）打开编码文件
DeCoding（）;//将编码进行解码存入字符串数组中
Save（）;//保存译码后的字符串
四、算法说明
1.执行界面
可供三个选择
（1）编码
（2）译码
（3）退出
执行
（1）选择
需要输入要编译的文件名
需要输出编码保存文件名
选择
（1）执行完毕
执行
（2）选项
输入要译码的编码文件名并输入保存的文件名
选择
（2）执行完毕
执行（0）则退出该程序
五、报告总结
该程序主要采用了哈夫曼编码译码方法，对txt文件进行编译压缩，同时也能对编码后的文件进行解码，程序结构清晰，主干分两大部分：
编码部分与解码部分，各部分通过调用函数合理清晰的实现其功能。
程序中运用了一些文件的C语言基本操作，例如打开文件open（）、保存文件save（）函数，但程序上对文件类型的处理还有一些缺点，不能实现文件类型的自动保存，需要输入文件名字和类型。
通过这次课程设计，不仅提高了自己的编程能力，还让我知道自己在编程方面的缺点，我以后会更加努力扩大自己的知识面提高自己的编程能力。
#include
#include
#include
#defineM10000//定义字符串最大长度
#defineN128//定义叶子节点个数
typedefstructnode//定义哈夫曼树节点结构体
{
intweight;
structnode*LChild,*RChild,*Parent;//分别指向该节点的左孩子，右孩子，和双亲节点
structnode*next;//指向建立的哈夫曼树的下一个节点
}HFMNode,*HFMTree;
typedefstruct//定义哈夫曼编码的结构体
{
charch;//存储对应的字符
charcode[N+1];//存储对应字符的编码
intstart;//存储编码的起始位置
}CodeNode;
intn;//存储真正叶子节点个数
voidclearscreen（）
{
system（"cls"）;
}
voidOpen（chars[]）//打开存放字符或编码的文件，将其存入字符串数组中
{
charname[10];
FILE*fp;
inti=0;
printf（"请输入要打开的文件名：
"）;
gets（name）;//要打开的文件名
if（（fp=fopen（name,"rt"））==NULL）
{
printf（"打开失败！
\n"）;//若打开失败，则直接退出
exit
（1）;
}
s[i++]=fgetc（fp）;
while（s[i-1]!
=EOF）
s[i++]=fgetc（fp）;
s[i]='\0';//存取字符串结束
fclose（fp）;
}
voidSave（chars[]）//保存字符或编码到文件中
{
charname[10];
FILE*fp;
printf（"请输入要保存的文件名：
"）;
gets（name）;
if（（fp=fopen（name,"wt"））==NULL）
{
printf（"存储失败！
"）;
exit
（1）;
}
fputs（s,fp）;
printf（"\n保存成功，文件名为:
%s。
\n",name）;
printf（"\n按回车键继续..."）;
getchar（）;
fclose（fp）;
}
voidSearchStr（chars[],charstr[],intcount[]）
{
//查找字符串中字符的个数和每个字符出现的次数
inti,j,k=0;
for（i=0;icount[i]=0;
for（i=0;s[i];i++）
{
for（j=0;jif（str[j]==s[i]）
{
count[j]++;
break;
}
if（j==k）//在str[]中无该字符，将其存入最后一个单元
{
str[k]=s[i];
count[k++]++;
}
}
str[k]='\0';//将字符串结尾置\0
n=k;//将实际的字符个数作为叶子节点个数存入n
}
voidSelectMin（HFMTreeHT,intk,HFMTree*HT1,HFMTree*HT2）
{
//查找哈夫曼链表中两个权值最小的节点
inti,min;
HFMTreep;
min=32767;
for（i=0,p=HT;inext）
if（p->weightParent==0）
{
min=p->weight;
*HT1=p;
}
min=32767;
for（i=0,p=HT;inext）
if（p->weightParent==0&&p!
=*HT1）//令第二个最小的节点不等于第一个节点
{
min=p->weight;
*HT2=p;
}
}
voidCreatHFMTree（HFMTree*HT,intcount[]）
{
//创建哈夫曼树
inti;
HFMTreep,HT1,HT2;//HT1，HT2分别存放权值最小和次小的节点的位置
p=*HT=（HFMTree）malloc（sizeof（HFMNode））;
p->next=p->LChild=p->RChild=p->Parent=NULL;//初始化哈夫曼链表且有2n-1个节点
for（i=1;i<2*n-1;i++）
{
p->next=（HFMTree）malloc（sizeof（HFMNode））;
p=p->next;
p->next=p->LChild=p->RChild=p->Parent=NULL;
}
for（i=0,p=*HT;i{//存入哈夫曼链表的前n个单元中
p->weight=count[i];
p=p->next;
}
for（i=n;i<2*n-1;i++）//将后n-1个节点赋权值，建树
{
SelectMin（*HT,i,&HT1,&HT2）;//每次从前i个节点中选取权值最小的两个节点
HT1->Parent=HT2->Parent=p;
p->LChild=HT1;
p->RChild=HT2;
p->weight=HT1->weight+HT2->weight;//将两个节点的权值相加存入最后一个节点中
p=p->next;//p指向下一个没有存储权值的节点
}
}
voidHFMCode（HFMTreeHT,CodeNodeHC[],charstr[]）
{
//从每个叶子节点开始，利用哈夫曼树对每个字符进行编码，最终建立一个哈夫曼表
inti;
HFMTreeq,p=HT;
for（i=0;i{
HC[i].ch=str[i];
HC[i].code[n-1]='\0';//初始化编码的最后一位
}
for（i=0;i{
HC[i].start=n-1;
for（q=p;q->Parent;q=q->Parent）//判断q所指向的节点，左孩子置0，右孩子置1
if（q==q->Parent->LChild）
HC[i].code[--HC[i].start]='0';
elseHC[i].code[--HC[i].start]='1';
p=p->next;//判断下一个叶子节点
}
}
voidTotalCoding（chars[],CodeNodeHC[],charcode[]）
{
//利用哈夫曼编码表对整个字符串进行编码
inti,j;
code[0]='\0';//编码数组初始化
for（i=0;s[i];i++）//将每个字符在哈夫曼编码表中对应的编码存入存放总编码的数组中
for（j=0;jif（s[i]==HC[j].ch）
strcpy（code+strlen（code）,HC[j].code+HC[j].start）;
}
voidDeCoding（charcode[],HFMTreeHT,charstr[],chars[]）
{
//对哈夫曼编码进行解码，放入字符串s中
inti,j,k=0;
HFMTreeroot,p,q;
for（root=HT;root->Parent;root=root->Parent）;//用root指向哈夫曼树的根结点
for（i=0,p=root;code[i];i++）//从根结点开始按编码顺序访问树
{
if（code[i]=='0'）
p=p->LChild;
elsep=p->RChild;
if（p->LChild==NULL&&p->RChild==NULL）//到根节点时将该节点对应的字符输出
{
for（j=0,q=HT;q!
=p;q=q->next,j++）;
s[k++]=str[j];
p=root;//回溯到根结点
}
}
s[k]='\0';//解码完毕，在字符串最后一个单元存入'\0'
}
voidCoding（chars[],charstr[],charcode[],intcount[],HFMTree*HT,CodeNodeHC[]）
{
clearscreen（）;
printf（"\n打开存放字符串的文件...\n\n"）;
Open（s）;//打开源码文件
SearchStr（s,str,count）;//查找字符串中不同的字符及其出现的次数
CreatHFMTree（HT,count）;//用每个字符出现的次数作为叶子节点的权值建立哈夫曼树
HFMCode（*HT,HC,str）;//利用哈夫曼树对每个叶子节点进行编码，存入编码表中
TotalCoding（s,HC,code）;//利用编码表对字符串进行最终编码
printf（"\n读入的字符串为:
\n"）;
puts（s）;
printf（"\n最终的哈夫曼编码是:
\n"）;
puts（code）;
printf（"\n保存编码,"）;
Save（code）;//保存最终的哈夫曼编码
}
voidTransCode（charcode[],charstr[],charss[],HFMTree*HT,CodeNodeHC[]）
{
clearscreen（）;
printf（"\n打开编码的文件...\n\n"）;
Open（code）;//打开编码文件
DeCoding（code,*HT,str,ss）;//将编码进行解码存入字符串数组ss[]中
printf（"\n得到的最终字符串为:
\n"）;
puts（ss）;
printf（"\n保存译码，"）;
Save（ss）;//保存译码后的字符串
}
intmain（）
{
//主函数
chars[M],ss[M];//定义字符串数组，s[]存放将要编码的字符串，ss[]存解码后的字符串
charstr[N];//存放输入的字符串中n个不同的字符
intcount[N];//存放n个不同字符对应的在原字符串中出现的次数
charcode[M];//存放最终编码完成后的编码
charchoice;
HFMTreeHT;//定义一个哈夫曼树的链表
CodeNodeHC[N];//定义一个哈夫曼编码表的数组，存放每个字符对应的哈夫曼编码
do
{
clearscreen（）;
printf（"\n\n"）;
printf（"************哈夫曼树************\n"）;
printf（"****\n"）;
printf（"**1.编码。
**\n"）;
printf（"**2.译码。
**\n"）;
printf（"**0.退出。
**\n"）;
printf（"****\n"）;
printf（"****\n"）;
printf（"****\n"）;
printf（"**请输入相应操作的序号（0-2）**\n"）;
printf（"********************************\n"）;
scanf（"%c",&choice）;
getchar（）;
switch（choice）
{
case'1':
Coding（s,str,code,count,&HT,HC）;break;//对字符串进行编码
case'2':
TransCode（code,str,ss,&HT,HC）;break;//对编码进行解码
case'0':
break;
default:
printf（"输入错误！
请重新输入！
\n"）;
}
}while（choice!
='0'）;
}
升级会员 