哈夫曼编码及其应用.docx
《哈夫曼编码及其应用.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码及其应用.docx（20页珍藏版）》请在冰点文库上搜索。
哈夫曼编码及其应用
学生姓名：
班级：
学号：
课程：
算法与数据结构
一、实验题目：
哈夫曼编码及其应用
二、实验地点：
三、实验目的：
.
1）理解哈夫曼树的特征及其应用；
2）在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫曼树进行编码和译码；
3）通过该实验，对二叉树的构建、遍历等以及哈夫曼编码的应用有更深层次的理解。
四、实验内容：
1）初始化（Initialzation）。
从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree；
2）编码（EnCoding）。
用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中；
3）译码（Decoding）。
利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中；
4）输出（Output）。
输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt；
要求：
所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.data、ToBeTran.data和CodeFile.data三个文件，以保证系统的通用性。
五、实验环境（使用的软硬件）：
VisualC++
六、实验步骤及操作：
1、进入Visualc++环境，新建工程/Win32ConsoleApplication，新建一个名为“哈夫曼树的应用”的工程；
2、新建文件/C/C++HeaderFile，选中“添加到工程的复选按钮”，输入文件名“pubuse.h”，按“确定”按钮，在显示的代码编辑区内输入：
#include
#include
#include/*malloc（）等*/
#include/*INT_MAX等*/
#include/*EOF（=^Z或F6）,NULL*/
#include/*atoi（）*/
#include/*eof（）*/
#include/*floor（）,ceil（）,abs（）*/
#include/*exit（）*/
/*函数结果状态代码*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/
typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码，如OK等*/
typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/
3、新建文件/C/C++HeaderFile，选中“添加到工程的复选按钮”，输入文件名“huffmanDef.h”，按“确定”按钮，在显示的代码编辑区内输入：
#defineuintunsignedint
#defineMAXSIZE150
#defineMAXSIZE2500
intt,count,num;//采用全局变量定义count存储字符个数，num存储从文件读取内容的个数
uintw[MAXSIZE1];
charc[MAXSIZE1],data[MAXSIZE2];//采用全局变量定义的数组用于存储从文件读取的内容
typedefchar**HuffmanCode;//动态分配数组存储哈夫曼树编码表
voidStart_Screen（）
{
printf（"\n\n\n"）;
printf（"\t********************************\t\n"）;
printf（"\t**\t\n"）;
printf（"\t***哈夫曼编译码系统***\t\n"）;
printf（"\t**\t\n"）;
printf（"\t**\t\n"）;
printf（"\t*1.更新哈夫曼编码信息*\t\n"）;
printf（"\t**\t\n"）;
printf（"\t*2.显示哈夫曼树及哈夫曼编码*\t\n"）;
printf（"\t**\t\n"）;
printf（"\t*3.将输入的文本编译为报文*\t\n"）;
printf（"\t**\t\n"）;
printf（"\t*4.将输入的报文编译为文本*\t\n"）;
printf（"\t**\t\n"）;
printf（"\t*5.将已有的文本编译为报文*\t\n"）;
printf（"\t**\t\n"）;
printf（"\t*6.将已有的报文编译为文本*\t\n"）;
printf（"\t**\t\n"）;
printf（"\t*7.退出系统*\t\n"）;
printf（"\t**\t\n"）;
printf（"\t********************************\t\n"）;
printf（"\t*请输入您的选择选择:
"）;scanf（"%d",&t）;
}
4、新建文件/C/C++HeaderFile，选中“添加到工程的复选按钮”，输入文件名“huffmanAlgo.h”，按“确定”按钮，在显示的代码编辑区内输入：
PrintHuffmanTree（HuffmanTreeht,intn）
{
inti,m;
m=2*n-1;
printf（"\t哈夫曼树及哈弗曼编码\n\n"）;
printf（"序号字符权值双亲左孩子右孩子\n"）;
for（i=0;i{
printf（"%2d%c%5d",i,ht[i].ch,ht[i].weight）;
printf（"%5d%5d%5d\n",ht[i].parent,ht[i].lchild,ht[i].rchild）;
}
}
//输出哈夫曼编码
voidPrintHuffmanCode（HuffmanTreeht,HuffmanCodehc,intn）
{
inti;
printf（"字符\t哈弗曼编码\n"）;
for（i=0;i{
printf（"%c%s\n",ht->ch,hc[i]）;
ht++;
}
printf（"\n\n\n\n\n\n\n\n\n"）;
}
//将哈夫曼树的初始信息写入文件
voidWriteHuffmanTree（）
{
FILE*fp;
uintwe;
charch;
printf（"请输入你需要的字符和权值，用‘#’结束输入：
\n"）;
if（（fp=fopen（"DataFile.data","w"））==NULL）
{
printf（"\nErroronopen%s!
\a","DataFile.data"）;
exit
（1）;
}
scanf（"\n%c",&ch）;
while（ch!
='#'）
{
scanf（"%d",&we）;
fprintf（fp,"%c",ch）;
fprintf（fp,"%5d\n",we）;
ch=getchar（）;
}
fclose（fp）;
}
//读哈夫曼树的初始信息
voidReadHuffmanTree（）
{
FILE*fp;
inti=0;
count=0;
if（（fp=fopen（"DataFile.data","r"））==NULL）
{
printf（"\nErroronopen%s!
\a","DataFile.data"）;
exit
（1）;//表示程序非正常退出
}
while（!
feof（fp））
{
fscanf（fp,"%c",&c[i]）;
if（c[i]=='\n'）continue;//读到换行符，跳过，读下一行
fscanf（fp,"%5d",&w[i]）;
count++;
i++;
}
fclose（fp）;
}
//将内容写入文件
voidWriteDataFile（char*fileName）
{
FILE*fp;
charch;
num=0;
if（（fp=fopen（fileName,"w"））==NULL）
{
printf（"\nErroronopen%s!
\a",fileName）;
exit
（1）;
}
scanf（"\n%c",&ch）;
while（ch!
='#'）
{
fprintf（fp,"%c",ch）;
num++;
ch=getchar（）;
}
fclose（fp）;
}
//读文件内容
voidReadDataFile（char*fileName）
{
FILE*fp;
inti=0;
if（（fp=fopen（fileName,"r"））==NULL）
{
printf（"\nErroronopen%s!
\a",fileName）;
exit
（1）;
}
while（!
feof（fp））
{
if（data[i]=='\n'）continue;
fscanf（fp,"%c",&data[i]）;
i++;
}
data[i]='\0';
fclose（fp）;
}
//编码，用已及建好的哈夫曼树，对所输入的文件进行编码形成报文
voidEnCoding（HuffmanCodehc）
{
FILE*fp;
inti=0,j;
printf（"请输入您需要进行编码的文本，以‘#’结束：
\n"）;
WriteDataFile（"ToBeTran.data"）;
ReadDataFile（"ToBeTran.data"）;
if（（fp=fopen（"Code.txt","w"））==NULL）
{
printf（"\nErroronopen%s!
\a","Code.txt"）;
exit
（1）;
}
for（i=0;i{
if（data[i]==''）putchar（''）;
for（j=0;jif（data[i]==c[j]）
{
fprintf（fp,"%s",hc[j]）;
printf（"%s",hc[j]）;
break;
}
}
fclose（fp）;
putchar（'\n'）;
}
//译码，用用已及建好的哈夫曼编码，对所输入的报文进行解译形成文本
voidDeCoding（HuffmanTreeht）
{
FILE*fp;
HuffmanTreep;
inti=0;
printf（"请输入您需要进行解码的代码，以‘#’结束：
\n"）;
WriteDataFile（"CodeFile.data"）;
ReadDataFile（"CodeFile.data"）;
if（（fp=fopen（"TextFile.txt","w"））==NULL）
{
printf（"\nErroronopen%s!
\a","TextFile.txt"）;
exit
（1）;
}
p=&ht[2*count-1-1];
for（i=0;i<=num;i++）
{
if（data[i]==''）
{
putchar（''）;
continue;
}
if（data[i]=='0'&&p->lchild!
=-1）p=&ht[p->lchild];
elseif（data[i]=='1'&&p->rchild!
=-1）p=&ht[p->rchild];
else
{
fprintf（fp,"%c",p->ch）;
printf（"%c",p->ch）;
p=&ht[2*count-1-1];
if（data[i]!
='\0'）i--;
}
}
fclose（fp）;
putchar（'\n'）;
}
//编码，用已及建好的哈夫曼树，对已有的文件进行编码形成报文
voidAlEnCoding（HuffmanCodehc）
{
FILE*fp1,*fp2;
inti=0,j;
if（（fp1=fopen（"ToBeTran.data","r"））==NULL）
{
printf（"\nErroronopen%s!
\a","ToBeTran.data"）;
exit
（1）;
}
while（!
feof（fp1））
{
data[i]=fgetc（fp1）;
i++;
}
num=i;
fclose（fp1）;
if（（fp2=fopen（"Code.txt","w"））==NULL）
{
printf（"\nErroronopen%s!
\a","Code.txt"）;
exit
（1）;
}
for（i=0;i{
if（data[i]==''）putchar（''）;
for（j=0;jif（data[i]==c[j]）
{
fprintf（fp2,"%s",hc[j]）;
printf（"%s",hc[j]）;
break;
}
}
fclose（fp2）;
putchar（'\n'）;
}
//译码，用用已及建好的哈夫曼编码，对已有的报文进行解译形成文本
voidAlDeCoding（HuffmanTreeht）
{
FILE*fp1,*fp2;
HuffmanTreep;
inti=0;
if（（fp1=fopen（"CodeFile.data","r"））==NULL）
{
printf（"\nErroronopen%s!
\a\n","CodeFile.data"）;
exit
（1）;
}
while（!
feof（fp1））
{
data[i]=fgetc（fp1）;
i++;
}
num=i;
data[i-1]='\0';
fclose（fp1）;
if（（fp2=fopen（"TextFile.txt","w"））==NULL）
{
printf（"\nErroronopen%s!
\a\n","TextFile.txt"）;
exit
（1）;
}
p=&ht[2*count-1-1];
for（i=0;i{
if（data[i]==''）
{
putchar（''）;
continue;
}
if（data[i]=='0'&&p->lchild!
=-1）p=&ht[p->lchild];
elseif（data[i]=='1'&&p->rchild!
=-1）p=&ht[p->rchild];
else
{
fprintf（fp2,"%c",p->ch）;
printf（"%c",p->ch）;
p=&ht[2*count-1-1];
if（data[i]!
='\0'）i--;
}
}
fclose（fp2）;
putchar（'\n'）;
}
voidmain（）
{
HuffmanTreeHT;
HuffmanCodeHC;
inti=0;
Start_Screen（）;
ReadHuffmanTree（）;//读哈夫曼树原始信息
CreateHuffmanTree（&HT,count）;//创建哈夫曼树
HC=HuffmanCoding（HT,count）;//创建哈夫曼编码
while
（1）
{
switch（t）
{
case1:
WriteHuffmanTree（）;//更新哈夫曼树信息
ReadHuffmanTree（）;//读哈夫曼树初始化信息
CreateHuffmanTree（&HT,count）;//创建哈夫曼树
HC=HuffmanCoding（HT,count）;//创建哈夫曼编码
break;
case2:
PrintHuffmanTree（HT,count）;//输出哈夫曼树
PrintHuffmanCode（HT,HC,count）;//输出哈夫曼编码
exit（0）;//表示程序正常退出
break;
case3:
EnCoding（HC）;//编码，对所输入的文本进行编码形成报文
break;
case4:
DeCoding（HT）;//译码，对所输入的报文进行解译形成文本
break;
case5:
AlEnCoding（HC）;//编码，对所已有的文本进行编码形成报文
break;
case6:
AlDeCoding（HT）;//译码，对所已有的报文进行解译形成文本
break;
case7:
exit（0）;
break;
default:
putchar（'\a'）;
system（"cls"）;//清屏
Start_Screen（）;
}
Start_Screen（）;
}
}
5、新建文件/C++SourceFile，选中“添加到工程的复选按钮”，输入文件名“huffmanUse.cpp”，按“确定”按钮，在显示的代码编辑区内输入：
#include"pubuse.h"
#include"huffmanDef.h"
#include"huffmanAlgo.h"
voidmain（）
{
HuffmanTreeHT;
HuffmanCodeHC;
intMin（HuffmanTreebt,intm）
{
inti,temp;
uintk;
for（i=0;iif（bt[i].parent==0）
{
k=bt[i].weight;
temp=i;
break;
}
for（i=i+1;iif（bt[i].weight{
k=bt[i].weight;
temp=i;
}
bt[temp].parent=1;
returntemp;
}
//在HT[0~i]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
voidSelect（HuffmanTreeht,intm,uint*s1,uint*s2）
{
（*s1）=Min（ht,m）;
（*s2）=Min（ht,m）;
}
//构造哈夫曼树
voidCreateHuffmanTree（HuffmanTree*HT,intn）
{
HuffmanTreep;
uints1,s2;
inti,num;
num=2*n-1;
*HT=（HuffmanTree）malloc（num*sizeof（HTNode））;
p=*HT;
for（i=0;i{
p->ch=c[i];
p->weight=w[i];
p->parent=0;
p->lchild=p->rchild=-1;//初始化二叉树结点，parent置为0,lchild,rchild均置为-1
p++;
}
for（i=n;i{
p->ch='*';
p->parent=0;
p->lchild=p->rchild=-1;
p++;
}
for（i=n;i{
Select（*HT,i,&s1,&s2）;
（*HT）[s1].parent=（*HT）[s2].parent=i;
（*HT）[i].lchild=s1;
（*HT）[i].rchild=s2;
（*HT）[i].weight=（*HT）[s1].weight+（*HT）[s2].weight;
}
}
//从叶子节点到根节点逆向求哈弗曼编码
HuffmanCodeHuffmanCoding（HuffmanTreeHT,intn）
{
inti,f,top;
uintt;
HuffmanCodeHC;
char*hc;
HC=（HuffmanCode）malloc（n*sizeof（char*））;//动态申请指针存储哈夫曼编码
hc=（char*）malloc（n*sizeof（char））;//申请哈夫曼编码的工作空间
hc[n-1]='\0';
for（i=0;i{
top=n-1;
t=i;
f=HT[i].parent;
while（f!
=0）
{
if（HT[f].lchild==t）hc[--top]='0';
elsehc[--top]='1';
t=f;
f=HT[t].parent;
}
HC[i]=（char*）malloc（（n-top）*sizeof（char））;//为已申请的指针分配一维数组存储哈夫曼编码
strcpy（HC[i],&hc[t
升级会员 