哈夫曼编码与译码附源码.docx
《哈夫曼编码与译码附源码.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码与译码附源码.docx（33页珍藏版）》请在冰点文库上搜索。
哈夫曼编码与译码附源码
哈夫曼编码与译码（附源码）
建立Huffman树进行编码和译码的设计
郝萌1100300423哈尔滨工业大学计算机科学与技术学院1003104班
摘要：
建立一个简易的系统，对于给定的一篇英文文章，统计字符出
现的概率，并根据概率建立Huffman树，利用Huffman编码
对文章进行编码和译码。
掌握Huffman树的建立与应用，并进
一步熟练掌握程序的设计流程。
关键词：
Huffman树Huffman编码文章译码文件压缩解压缩
1.引言：
给定一篇文章，统计字符出现的概率，根据概率建立哈夫曼树，并进行哈夫曼编码，进而可以利用哈夫曼编码对文章进行编码与译码和文件压缩、解压缩等操作。
2.程序设计流程
（1）文字表述
开始进入功能选择界面，包含五种操作：
1.读取文章并对字符编码，2.哈夫曼编码信息，3.文章编码，4.文章译码，5.文件压缩，6.文件解压缩，7.退出程序。
操作1：
给定一篇文章，统计字符出现的概率，并根据概率建立Huffman树，并利用Huffman树对字符进行Huffman编码。
操作2：
显示Huffman编码信息，包括字符，字符出现的概率，Huffman编码。
操作3：
对文章进行译码，显示译码信息，并保存。
操作4：
对文章进行译码，显示并保存。
操作5：
对文件进行压缩，每7位二进制序列对应一个ASCII码。
操作6：
对文件进行解压缩。
（2）流程图
（3）程序数据要求及功能实现
主界面
1.读取文件并对字符进行编码
2.哈夫曼编码信息
3.文件编码
（1）显示文件编码
（2）保存文件编码
4.文件译码
（1）显示文章编码的译码
（2）保存文章编码的译码
5.文件压缩
6.文件解压缩
附：
程序源代码
/*
*File:
HUFFMANFUNCTION.h
*Author:
Administrator
*
*Createdon2011年12月19日,下午6:
19
*/
#ifndefHUFFMANFUNCTION_H
#defineHUFFMANFUNCTION_H
#include
#include
#include
#include
#definemax1150
#definemax250
#definemax3256
usingnamespacestd;
classHtnote{
public:
charname;//字符名
doubleweight;//权重
intlchild;//左孩子
intrchild;//右孩子
intparent;//父亲
Htnote（）{
weight=0;
lchild=-1;
parent=-1;
rchild=-1;
}
};
className{
public:
intnum;//字符出现的次数
charpname;//字符名
doublelweight;//权值
Name（）{
num=0;
lweight=0;
}
};
classGetName{
public:
charnamef[max2];
intn;//字符的种类
intsum;//字符的总数
Nameletter[max1];//存储字符信息的类的数组
GetName（）{
sum=0;
n=0;
}
voidGetWeight（）//得到字符的权值
{
for（inti=0;iletter[i].lweight=（double）letter[i].num/sum;//出现的次数除总数得到权值
}
}
intReadLetter（）{
ifstreaminput;
cout<<"请输入文件名：
"<cin>>namef;
input.open（namef）;//打开文件
if（input.fail（））{
cout<<"该文件不存在！
"<return0;
}
charch;
ch=input.get（）;
letter[0].pname=ch;
letter[0].num++;
sum++;
while（!
input.eof（））{//读取文件中的所有字符
inttag=0;
ch=input.get（）;
for（inti=0;iif（letter[i].pname==ch）{
letter[i].num++;
sum++;
tag=1;
}
}
if（tag==0）{
n++;
letter[n].pname=ch;
letter[n].num++;
sum++;
}
}
sum--;
input.close（）;
GetWeight（）;//得到字符权值
}
};
classCodeNode//编码类
{
public:
charch;//存储字符
charbits[max1];//存储编码
};
classFunction{
public:
GetNameL;
intfn;//定义哈夫曼数组大小
HtnoteHuffmanT[max3];//哈夫曼数组
CodeNodeCode[max1];//字符编码数组
Function（）{
fn=0;
}
voidCharHuffmanTCoding（）//编码功能实现
{
inti,f,c;
charcd[L.n+1];//暂时存储编码的数组
intstart;//编码读取起始位置
cd[L.n]='\0';
for（i=0;iCode[i].ch=HuffmanT[i].name;//字符信息
start=L.n;//起始位置
c=i;
while（（f=HuffmanT[c].parent）>=0）{
if（HuffmanT[f].lchild==c）//如果为左孩子，为‘0’
{
cd[--start]='0';
}else//如果为右孩子，为‘1’
{
cd[--start]='1';
}
c=f;
}
strcpy（Code[i].bits,&cd[start]）;//将结果存入对应的编码数组中
}
}
voidOutputHuffmanTCode（）{
cout<<"哈夫曼编码：
"<cout<<"——————————————————————"<cout<<"字符\t权值\t\t哈夫曼编码"<for（inti=0;i{
cout<<"——————————————————————"<cout<cout<cout<}
cout<<"——————————————————————"<}
voidInitHT（）//哈夫曼初始化
{
L.ReadLetter（）;
fn=（L.n）*2-1;
for（inti=0;iif（iHuffmanT[i].name=L.letter[i].pname;
HuffmanT[i].weight=L.letter[i].lweight;
}
}
}
voidSelectMin（intm,int&p1,int&p2）//选择最小的两个节点
{
inti,j;
doublem1,m2;
m1=m2=1;
p1=p2=-1;
for（i=0;iif（HuffmanT[i].parent==-1&&HuffmanT[i].weight{
m2=m1;
p2=p1;
m1=HuffmanT[i].weight;
p1=i;
}elseif（HuffmanT[i].parent==-1&&HuffmanT[i].weight{
m2=HuffmanT[i].weight;
p2=i;
}
}
}
voidCreatHT（）//建立哈夫曼树
{
inti,p1,p2;
InitHT（）;
for（i=L.n;iSelectMin（i,p1,p2）;
HuffmanT[p1].parent=HuffmanT[p2].parent=i;
HuffmanT[i].lchild=p1;
HuffmanT[i].rchild=p2;
HuffmanT[i].weight=HuffmanT[p1].weight+HuffmanT[p2].weight;
}
}
intOutArticleCode（）//显示文章编码
{//文章编码操作
ifstreaminput;
input.open（L.namef）;
if（input.fail（））{
cout<<"文件不存在！
"<return0;
}
charch;
cout<<"文章编码如下：
"<while（!
input.eof（））{
ch=input.get（）;
for（inti=0;iif（Code[i].ch==ch）
cout<}
}
cout<input.close（）;
}
intSaveArticleCode（）//保存文章编码
{
ofstreamoutput;
ifstreaminput;
charnamef1[max2];
input.open（L.namef）;
if（input.fail（））{
cout<<"该文件不存在！
"<return0;
}
cout<<"请输入保存文章编码的文件名：
"<cin>>namef1;
output.open（namef1）;
charch;
while（!
input.eof（））{
ch=input.get（）;
for（inti=0;iif（Code[i].ch==ch）{
for（intj=0;joutput.put（Code[i].bits[j]）;
}
}
}
}
input.close（）;
output.close（）;
cout<<"保存完毕！
"<}
intOutTransCode（）{//文章译码操作
ifstreaminput;
charnamef[max2];
cout<<"请输入保存文章编码的文件名：
"<cin>>namef;
input.open（namef）;
if（input.fail（））{
cout<<"该文件不存在！
"<return0;
}
charch;
ch=input.get（）;
intc=2*L.n-2;
while（!
input.eof（））{
if（ch=='0'）//遇0搜索左子树
{
if（HuffmanT[c].lchild>=0）{
c=HuffmanT[c].lchild;
}
if（HuffmanT[c].lchild==-1）//判断是否到叶子
{
cout<c=2*L.n-2;//返回根节点
}
}
if（ch=='1'）//遇1搜索右子树
{
if（HuffmanT[c].rchild>=0）{
c=HuffmanT[c].rchild;
}
if（HuffmanT[c].rchild==-1）//判断是否到叶子
{
cout<c=2*L.n-2;//返回根节点
}
}
ch=input.get（）;
}
cout<input.close（）;
}
intSaveTransCode（）{//保存文章译码
ofstreamoutput;
ifstreaminput;
charnamef[max2];
charnamef1[max2];
cout<<"请输入文章编码所在的文件名：
"<cin>>namef;
input.open（namef）;
if（input.fail（））{
cout<<"该文件不存在！
"<return0;
}
cout<<"请输入保存文章译码的文件名：
"<cin>>namef1;
output.open（namef1）;
charch;
ch=input.get（）;
intc=2*L.n-2;
while（!
input.eof（））{
if（ch=='0'）{
if（HuffmanT[c].lchild>=0）{
c=HuffmanT[c].lchild;
}
if（HuffmanT[c].lchild==-1）{
output.put（HuffmanT[c].name）;
c=2*L.n-2;
}
}
if（ch=='1'）{
if（HuffmanT[c].rchild>=0）{
c=HuffmanT[c].rchild;
}
if（HuffmanT[c].rchild==-1）{
output.put（HuffmanT[c].name）;
c=2*L.n-2;
}
}
ch=input.get（）;
}
input.close（）;
output.close（）;
cout<<"保存完毕！
"<}
intFileCompression（）{//文件压缩功能
CreatHT（）;
CharHuffmanTCoding（）;
//保存编码
ofstreamoutput;
ifstreaminput;
charnamef1[]={"temp.txt"};
input.open（L.namef）;
if（input.fail（））{
cout<<"该文件不存在！
"<return0;
}
output.open（namef1）;
charch;
while（!
input.eof（））{
ch=input.get（）;
for（inti=0;iif（Code[i].ch==ch）{
for（intj=0;joutput.put（Code[i].bits[j]）;
}
}
}
}
input.close（）;
output.close（）;
//压缩文件
ofstreamFile1;
ifstreamFile2;
charnamef2[max2];
cout<<"请输入压缩后的文件名：
"<cin>>namef2;
File1.open（namef2）;
File2.open（namef1）;
if（File2.fail（））{
cout<<"该文件不存在！
"<return0;
}
charsh;
charth;
inti=0;
charj='0';
intcount=0;
while（!
File2.eof（））{
sh=File2.get（）;
if（i<7&&sh!
=EOF）{
count=count+（sh-'0'）*pow（2,i）;
if（sh=='0'）{
j++;
}else{
j='0';
}
i++;
}
if（i==7）{
th=count;
File1.put（th）;
i=0;
count=0;
}
if（sh==EOF）{
th=count;
File1.put（th）;
File1.put（j）;
i=0;
count=0;
}
}
File1.close（）;
File2.close（）;
remove（namef1）;
cout<<"文件压缩完毕！
"<}
intFileDecompression（）{//文件解压缩
//保存编码
fstreamoutput;
fstreaminput;
charnamef2[max2];
charnamef1[]={"temp.txt"};
cout<<"请输入待解压缩的文件名：
"<cin>>namef2;
input.open（namef2,ios:
:
in|ios:
:
binary）;
output.open（namef1,ios:
:
out|ios:
:
binary）;
if（input.fail（））{
cout<<"该文件不存在！
"<return0;
}
charch;
input.read（reinterpret_cast（&ch）,sizeof（ch））;
charsh;
charth=ch;
input.read（reinterpret_cast（&ch）,sizeof（ch））;
intcount;
charnum;
chart='0';
charp='1';
while（!
input.eof（））{
sh=th;
th=ch;
input.read（reinterpret_cast（&ch）,sizeof（ch））;
count=sh;
if（ch!
=EOF）{
for（inti=0;i<7;i++）{
num=count%2+'0';
output.write（reinterpret_cast（&num）,sizeof（num））;
count=count/2;
}
}
if（ch==EOF）{
for（inti=0;i<7;i++）{
num=count%2+'0';
output.write（reinterpret_cast（&num）,sizeof（num））;
count=count/2;
if（count==0）{
break;
}
}
for（inti=0;ioutput.write（reinterpret_cast（&t）,sizeof（t））;
}
}
}
output.close（）;
input.close（）;
//解压文件
fstreamFile1;
fstreamFile2;
charnamef3[max2];
cout<<"请输入解压后的文件名：
"<cin>>namef3;
File2.open（namef1,ios:
:
in|ios:
:
binary）;
File1.open（namef3）;
if（File2.fail（））{
cout<<"该文件不存在！
"<return0;
}
cout<<"解压后的文件内容为：
"<File2.read（reinterpret_cast（&ch）,sizeof（ch））;
intc=2*L.n-2;
while（!
File2.eof（））{
if（ch=='0'）{
if（HuffmanT[c].lchild>=0）{
c=HuffmanT[c].lchild;
}
if（HuffmanT[c].lchild==-1）{
cout<File1.write（reinterpret_cast（&HuffmanT[c].name）,sizeof（HuffmanT[c].name））;
c=2*L.n-2;
}
}
if（ch=='1'）{
if（HuffmanT[c].rchild>=0）{
c=
升级会员 