哈夫曼编码及其应用Word文档下载推荐.docx
《哈夫曼编码及其应用Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码及其应用Word文档下载推荐.docx（20页珍藏版）》请在冰点文库上搜索。
/*INT_MAX等*/
stdio.h>
/*EOF（=^Z或F6）,NULL*/
stdlib.h>
/*atoi（）*/
io.h>
/*eof（）*/
math.h>
/*floor（）,ceil（）,abs（）*/
process.h>
/*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"
）;
\t********************************\t\n"
\t**\t\n"
\t***哈夫曼编译码系统***\t\n"
\t*1.更新哈夫曼编码信息*\t\n"
\t*2.显示哈夫曼树及哈夫曼编码*\t\n"
\t*3.将输入的文本编译为报文*\t\n"
\t*4.将输入的报文编译为文本*\t\n"
\t*5.将已有的文本编译为报文*\t\n"
\t*6.将已有的报文编译为文本*\t\n"
\t*7.退出系统*\t\n"
\t*请输入您的选择选择:
"
scanf（"
%d"
&
t）;
}
4、新建文件/C/C++HeaderFile，选中“添加到工程的复选按钮”，输入文件名“huffmanAlgo.h”，按“确定”按钮，在显示的代码编辑区内输入：
PrintHuffmanTree（HuffmanTreeht,intn）
{
inti,m;
m=2*n-1;
\t哈夫曼树及哈弗曼编码\n\n"
序号字符权值双亲左孩子右孩子\n"
for（i=0;
i<
m;
i++）
{
printf（"
%2d%c%5d"
i,ht[i].ch,ht[i].weight）;
%5d%5d%5d\n"
ht[i].parent,ht[i].lchild,ht[i].rchild）;
}
//输出哈夫曼编码
voidPrintHuffmanCode（HuffmanTreeht,HuffmanCodehc,intn）
inti;
字符\t哈弗曼编码\n"
n;
%c%s\n"
ht->
ch,hc[i]）;
ht++;
\n\n\n\n\n\n\n\n\n"
//将哈夫曼树的初始信息写入文件
voidWriteHuffmanTree（）
FILE*fp;
uintwe;
charch;
请输入你需要的字符和权值，用‘#’结束输入：
\n"
if（（fp=fopen（"
DataFile.data"
"
w"
））==NULL）
\nErroronopen%s!
\a"
exit
（1）;
\n%c"
ch）;
while（ch!
='
#'
）
scanf（"
we）;
fprintf（fp,"
%c"
ch）;
%5d\n"
we）;
ch=getchar（）;
fclose（fp）;
//读哈夫曼树的初始信息
voidReadHuffmanTree（）
inti=0;
count=0;
r"
{
//表示程序非正常退出
while（!
feof（fp））
fscanf（fp,"
c[i]）;
if（c[i]=='
\n'
）continue;
//读到换行符，跳过，读下一行
%5d"
w[i]）;
count++;
i++;
//将内容写入文件
voidWriteDataFile（char*fileName）
num=0;
if（（fp=fopen（fileName,"
fileName）;
num++;
//读文件内容
voidReadDataFile（char*fileName）
if（data[i]=='
data[i]）;
data[i]='
\0'
;
//编码，用已及建好的哈夫曼树，对所输入的文件进行编码形成报文
voidEnCoding（HuffmanCodehc）
inti=0,j;
请输入您需要进行编码的文本，以‘#’结束：
WriteDataFile（"
ToBeTran.data"
ReadDataFile（"
Code.txt"
num;
'
）putchar（'
for（j=0;
j<
count;
j++）
if（data[i]==c[j]）
{
fprintf（fp,"
%s"
hc[j]）;
printf（"
break;
}
putchar（'
//译码，用用已及建好的哈夫曼编码，对所输入的报文进行解译形成文本
voidDeCoding（HuffmanTreeht）
HuffmanTreep;
请输入您需要进行解码的代码，以‘#’结束：
CodeFile.data"
TextFile.txt"
p=&
ht[2*count-1-1];
=num;
）
putchar（'
continue;
}
0'
&
&
p->
lchild!
=-1）p=&
ht[p->
lchild];
elseif（data[i]=='
1'
rchild!
rchild];
else
fprintf（fp,"
p->
printf（"
p=&
if（data[i]!
）i--;
//编码，用已及建好的哈夫曼树，对已有的文件进行编码形成报文
voidAlEnCoding（HuffmanCodehc）
FILE*fp1,*fp2;
if（（fp1=fopen（"
feof（fp1））
data[i]=fgetc（fp1）;
num=i;
fclose（fp1）;
if（（fp2=fopen（"
fprintf（fp2,"
fclose（fp2）;
//译码，用用已及建好的哈夫曼编码，对已有的报文进行解译形成文本
voidAlDeCoding（HuffmanTreeht）
\a\n"
data[i-1]='
fprintf（fp2,"
voidmain（）
HuffmanTreeHT;
HuffmanCodeHC;
Start_Screen（）;
ReadHuffmanTree（）;
//读哈夫曼树原始信息
CreateHuffmanTree（&
HT,count）;
//创建哈夫曼树
HC=HuffmanCoding（HT,count）;
//创建哈夫曼编码
while
（1）
switch（t）
case1:
WriteHuffmanTree（）;
//更新哈夫曼树信息
ReadHuffmanTree（）;
//读哈夫曼树初始化信息
CreateHuffmanTree（&
HC=HuffmanCoding（HT,count）;
break;
case2:
PrintHuffmanTree（HT,count）;
//输出哈夫曼树
PrintHuffmanCode（HT,HC,count）;
//输出哈夫曼编码
exit（0）;
//表示程序正常退出
case3:
EnCoding（HC）;
//编码，对所输入的文本进行编码形成报文
case4:
DeCoding（HT）;
//译码，对所输入的报文进行解译形成文本
case5:
AlEnCoding（HC）;
//编码，对所已有的文本进行编码形成报文
break;
case6:
AlDeCoding（HT）;
//译码，对所已有的报文进行解译形成文本
case7:
exit（0）;
default:
\a'
system（"
cls"
//清屏
Start_Screen（）;
Start_Screen（）;
}
5、新建文件/C++SourceFile，选中“添加到工程的复选按钮”，输入文件名“huffmanUse.cpp”，按“确定”按钮，在显示的代码编辑区内输入：
#include"
pubuse.h"
huffmanDef.h"
huffmanAlgo.h"
HuffmanTreeHT;
HuffmanCodeHC;
intMin（HuffmanTreebt,intm）
inti,temp;
uintk;
i++）//取k等于首个parent为0的权值
if（bt[i].parent==0）
{
k=bt[i].weight;
temp=i;
for（i=i+1;
i++）//逐个与其他权值进行比较，并返回在parent为0下权值最小的序号
if（bt[i].weight<
k&
bt[i].parent==0）
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）
uints1,s2;
inti,num;
num=2*n-1;
*HT=（HuffmanTree）malloc（num*sizeof（HTNode））;
p=*HT;
i++）//由给定的n个权值和字符构造n棵只有一个叶子结点的二叉树；
p->
ch=c[i];
weight=w[i];
parent=0;
lchild=p->
rchild=-1;
//初始化二叉树结点，parent置为0,lchild,rchild均置为-1
p++;
for（i=n;
i++）//构造n-1个空二叉树用于存储新树根结点
ch='
*'
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;
char*hc;
HC=（HuffmanCode）malloc（n*sizeof（char*））;
//动态申请指针存储哈夫曼编码
hc=（char*）malloc（n*sizeof（char））;
//申请哈夫曼编码的工作空间
hc[n-1]='
top=n-1;
t=i;
f=HT[i].parent;
while（f!
=0）
if（HT[f].lchild==t）hc[--top]='
elsehc[--top]='
t=f;
f=HT[t].parent;
HC[i]=（char*）malloc（（n-top）*sizeof（char））;
//为已申请的指针分配一维数组存储哈夫曼编码
strcpy（HC[i],&
hc[t
升级会员 