数据结构课程设计哈夫曼编码译码器.docx
《数据结构课程设计哈夫曼编码译码器.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计哈夫曼编码译码器.docx(22页珍藏版)》请在冰点文库上搜索。
![数据结构课程设计哈夫曼编码译码器.docx](https://file1.bingdoc.com/fileroot1/2023-5/4/9e4c2504-875a-43ff-8a69-5c12b87e0e92/9e4c2504-875a-43ff-8a69-5c12b87e0e921.gif)
数据结构课程设计哈夫曼编码译码器
数据结构课程设计
哈夫曼编码译码器
哈夫曼编码译码器
a)需求分析:
一个完整的系统应具有以下功能:
(l)I:
初始化。
从终端读入字符集大小n,及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmtree中。
(2)C:
编码。
利用已建好的哈夫曼树(如不在内存,则从文件hfmtree中读入),对文件tobetrans中的正文进行编码,然后将结果存入文件codefile中。
(3)D:
编码。
利用已建好的哈夫曼树将文件codefile中的代码进行译码,结果存入文件textfile中。
(4)P:
印代码文件。
将文件codefile以紧凑格式显示在终端上,每行50个代码。
同时将此字符形式的编码文件写入文件codeprint中。
(5)T:
印哈夫曼树。
将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件treeprint中
字符
__
A
B
C
D
E
F
G
H
I
J
K
L
M
频度
186
64
23
22
32
103
21
15
47
57
1
5
32
20
字符
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频度
20
56
19
2
50
51
55
30
10
11
2
21
2
可以根据题目要求把程序划成5个模块,设计成菜单方式,每次执行一个模块后返回菜单。
除了初始化(I)过程外,在每次执行时都经过一次读取磁盘文件数据。
这是为了如果在程序执行后一直没有进行初始化(I)过程,为了能使后面的操作顺利进行,可以通过读取旧的数据来进行工作。
比如:
如果程序的工作需要的字符集和权值数据是固定的,只要在安装程序时进行一次初始(I)化操作就可以了。
在再次运行程序时,不管进行那项操作都可以把需要的数据读入到内存。
b)概要设计
本程序主要用到了三个算法。
(1)哈夫曼编码
在初始化(I)的过程中间,要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。
先将输入的字符和权值存放到一个结构体数组中,建立哈夫曼树,将计算所得的哈夫曼编码存储到另一个结构体数组中。
(2)串的匹配
在编码(D)的过程中间,要对已经编码过的代码译码,可利用循环,将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较,如果相等就回显并存入文件。
(3)二叉树的遍历
在印哈夫曼树(T)的中,因为哈夫曼树也是二叉树,所以就要利用二叉树的先序遍历将哈夫曼树输出
c)详细设计
构造树的方法如下:
初始化:
每个字符就是一个结点,字符的频度就是结点的权;
1、将结点按频度从小到大排序;
2、选取频度最小的 两个结点,以它们为儿子,构造出一个新的结点;
新结点的权值就是 它两个儿子的权值之和;
构造之后,从原来的结点序列里删除刚才选出的那两个结点,但同时将新生成的结点加进去;
3、如果结点序列里只剩下一个结点,表示构造完毕,退出。
否则回到第一步。
编码:
上面已经生成了树,接着就该对该树进行编码了。
可以假定,对某个结点而言,其左孩子在当前阶段的编码为 0,右孩子的编码为 1。
这样就可以通过“树的遍历”的方式来生成 字符——编码 对照表。
来到这里,基本上艰苦的已经完成了,对某个具体的字符串编码和解码就只是简单的“查表——替换”的工作了。
解码:
解码也是个简单的查表--替换过程。
如果利用该种编码发送字符串,则它的“字符——编码”对应表也必须发送过去,不然对方是不知道怎么解码的。
对给出的一串编码,从左向右,将编码组合起来并查表,“一旦”找到有匹配的 字符,则马上将当前的 编码 替换为 对应的字符。
因为该编码是不会出现 “某一个字符的编码 是 另一个字符编码 的前缀” 这种情况的,也就是不会出现类似于“A 00 B 0010” 这样的情况,所以解码出来的字符串是唯一的,而且就是原来进行编码的那一个。
程序如下
#include
#include
#include
usingnamespacestd;
structHuffmanNode//定义哈夫曼树各结点
{
intweight;//存放结点的权值,假设只考虑处理权值为整数的情况
intparent;//记录结点父亲位置,-1表示为根结点,否则表示为非根结点
intlchild,rchild;//分别存放该结点的左、右孩子的所在单元的编号
};
classHuffmanTree//建立哈夫曼树类
{
private:
HuffmanNode*Node;//哈夫曼树中结点的存储结构
char*Info;//用来保存各字符信息
intLeafNum;//树中的叶子结点总数
public:
HuffmanTree();//构造函数
~HuffmanTree();//析构函数
voidInitialization(intWeightNum);//初始化函数:
根据WeightNum个权值建立一棵哈夫曼树
voidEncoder();//编码函数:
利用构造好的哈夫曼树对字符进行编码
voidDecoder();//译码函数:
对二进制串进行译码
voidPrint();//印文件函数:
把已保存好的编码文件显示在屏幕
voidTreePrinting();//印哈夫曼树函数:
将已在内存中的哈夫曼树以直观的方式显示在终端上
};
//程序名:
HuffmanTree.cpp
//程序功能:
实现哈夫曼树类的源文件(并用其来实现编/译码)
//构造函数
//函数功能:
将结点指针初始化为NULL
HuffmanTree:
:
HuffmanTree()
{
Node=NULL;//将树结点初始化为空
Info=NULL;//将字符数组初始化为空
LeafNum=0;//将叶子数初始化为0
}
//析构函数
//函数功能:
将所有结点的空间释放
//函数参数:
无
//参数返回值:
无
HuffmanTree:
:
~HuffmanTree()
{
delete[]Node;//释放结点空间
delete[]Info;//释放字符存储空间
}
//初始化函数
//函数功能:
从终端读入字符集大小n,以及n个字符和n个权值,
//建立哈夫曼树,并将它存放在文件hfmTree中.
//函数参数:
intWeightNum表示代码个数
//参数返回值:
无
voidHuffmanTree:
:
Initialization(intWeightNum)//初始化
{
inti,j,pos1,pos2,max1,max2;
Node=newHuffmanNode[2*WeightNum-1];//WeightNum权值对应的哈夫曼树中的结点总数为2*WeightNum-1个
Info=newchar[2*WeightNum-1];
for(i=0;i{
cout<<"请输入第"<
getchar();//丢弃字符'\t'与'\n'
Info[i]=getchar();//输入一个字符,主要是考虑输入空格而采用这种形式的
getchar();
cout<<"请输入该字符的权值或频度";
cin>>Node[i].weight;//输入权值
Node[i].parent=-1;//为根结点
Node[i].lchild=-1;//无左孩子
Node[i].rchild=-1;//无右孩子
}
for(i=WeightNum;i<2*WeightNum-1;i++)//表示需做WeightNum-1次合并
{
pos1=-1;
pos2=-1;//分别用来存放当前最小值和次小值的所在单元编号
max1=32767;//32767为整型数的最大值
max2=32767;//分别用来存放当前找到的最小值和次小值
for(j=0;j
if(Node[j].parent==-1)//是否为根结点
if(Node[j].weight{
max2=max1;//原最小值变为次小值
max1=Node[j].weight;//存放最小值
pos2=pos1;//修改次小值所在单元编号
pos1=j;//修改最小值所在单元编号
}
else
if(Node[j].weight{
max2=Node[j].weight;//存放次小值
pos2=j;//修改次小值所在的单元编号
}
//for
Node[pos1].parent=i;//修改父亲位置
Node[pos2].parent=i;
Node[i].lchild=pos1;//修改儿子位置
Node[i].rchild=pos2;
Node[i].parent=-1;//表示新结点应该是根结点
Node[i].weight=Node[pos1].weight+Node[pos2].weight;
}//for
LeafNum=WeightNum;
charch;
cout<<"是否要替换原来文件(Y/N):
";
cin>>ch;
if(ch=='y'||ch=='Y')
{
ofstreamfop;//以二进制方式打开hfmTree.dat文件,并当重新运行时覆盖原文件
fop.open("hfmTree.dat",ios:
:
out|ios:
:
binary|ios:
:
trunc);
if(fop.fail())//文件打开失败
cout<<"文件打开失败!
\n";
fop.write((char*)&WeightNum,sizeof(WeightNum));//写入WeightNum
for(i=0;i{
fop.write((char*)&Info[i],sizeof(Info[i]));
flush(cout);
}
for(i=0;i<2*WeightNum-1;i++)//把个节点内容写入文件
{
fop.write((char*)&Node[i],sizeof(Node[i]));
flush(cout);
}
fop.close();//关闭文件
}
cout<<"哈夫曼树已构造完成。
\n";
}//Initialization
//编码函数
//函数功能:
利用已建立好的哈夫曼树(如不在内存,则从文件hfmTree中读入),
//对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile
voidHuffmanTree:
:
Encoder()
{
if(Node==NULL)//哈夫曼树不在内存,从文件hfmTree中读入
{
ifstreamfip;//以二进制方式打开hfmTree.dat文件
fip.open("hfmTree.dat",ios:
:
binary|ios:
:
in);
if(fip.fail())//文件打开失败
{
cout<<"文件打开失败!
\n";
return;//结束本函数
}
fip.read((char*)&LeafNum,sizeof(LeafNum));//读取叶子数
Info=newchar[LeafNum];
Node=newHuffmanNode[2*LeafNum-1];
for(inti=0;ifip.read((char*)&Info[i],sizeof(Info[i]));
for(i=0;i<2*LeafNum-1;i++)//读取结点信息
fip.read((char*)&Node[i],sizeof(Node[i]));
}
char*Tree;//用于存储需编码内容
inti=0,num;
charChoose;//让用户选择读取文件或重新输入需编码内容
cout<<"你要从文件中读取内容
(1),还是重新输入
(2):
";
cin>>Choose;
if(Choose=='1')//读取文件ToBeTran.txt
{
ifstreamfip1("ToBeTran.txt");
if(fip1.fail())//文件不存在
{
cout<<"文件打开失败!
\n";
return;//结束本函数
}
charch;
intk=0;
while(fip1.get(ch))
{
k++;//计算CodeFile中代码长度
}
fip1.close();
Tree=newchar[k+1];
ifstreamfip2("ToBeTran.txt");
k=0;
while(fip2.get(ch))
{
Tree[k]=ch;//读取文件内容,并存到Tree中
k++;
}
fip2.close();
Tree[k]='\0';//结束标志
cout<<"需编码内容为:
";
cout<}//if(Choose=='1')
else//Choose!
='1',重新输入
{
stringtree;//用于输入需编码内容,由于string类对象可以输入任意长度,
//所以先利用这个对象输入,再转存在Tree中
cin.ignore();
cout<<"请输入需要编码的内容(可输入任意长,结束时请按2下回车):
\n";
getline(cin,tree,'\n');//输入任意长字符串,
//getline以回车('\n')作为结束符,第一次按回车表示字符串结束,第二次按回车才开始输出。
while(tree[i]!
='\0')
i++;
num=i;//计算tree长度
i=0;
Tree=newchar[num+1];
while(tree[i]!
='\0')//将tree中的字符转存到Tree中
{
Tree[i]=tree[i];
i++;
}
Tree[i]='\0';//结束标志符
}
ofstreamfop("CodeFile.dat",ios:
:
trunc);//存储编码后的代码,并覆盖原文件
i=0;
intk=0;
char*code;
code=newchar[LeafNum];//为所产生编码分配容量为LeafNum的存储空间
//因为不等长编码中最长的编码一定不会超过要求编码的字符个数
while(Tree[k]!
='\0')//对每一个字符编码
{
intj,start=0;
for(i=0;iif(Info[i]==Tree[k])//求出该文字所在单元的编号
break;
j=i;
while(Node[j].parent!
=-1)//结点j非树根
{
j=Node[j].parent;//非结点j的双亲结点
if(Node[j].lchild==i)//是左子树,则生成代码0
code[start++]='0';
else//是右子树,则生成代码1
code[start++]='1';\
i=j;
}
code[start]='\0';//置串结束符
for(i=0;i{
j=code[i];
code[i]=code[start-i-1];
code[start-i-1]=j;
}
i=0;
while(code[i]!
='\0')//存储代码
{
fop<i++;
}
k++;
}
fop.close();
cout<<"已编码!
且存到文件CodeFile.dat中!
\n\n";
}//Encode
//译码函数
//函数功能:
利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,
//将译码结果存入文件TextFile中.
voidHuffmanTree:
:
Decoder()
{
inti=0,k=0;
intj=LeafNum*2-1-1;//表示从根结点开始往下搜索
char*BitStr;
ifstreamfip1("CodeFile.dat");//利用已建好的哈夫曼树将文件CodeFile中的代码进行译码
if(fip1.fail())//文件打开失败,还未编码
{
cout<<"请先编码!
\n";
return;
}
cout<<"经译码,原内容为:
";
charch;
while(fip1.get(ch))
{
k++;//计算CodeFile中代码长度
}
fip1.close();
BitStr=newchar[k+1];
ifstreamfip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
{
BitStr[k]=ch;//读取文件内容
k++;
}
fip2.close();
BitStr[k]='\0';//结束标志符
if(Node==NULL)//还未建哈夫曼树
{
cout<<"请先编码!
\n";
return;
}
ofstreamfop("TextFile.dat");//将字符形式的编码文件写入文件CodePrin中
while(BitStr[i]!
='\0')
{
if(BitStr[i]=='0')
j=Node[j].lchild;//往左走
else
j=Node[j].rchild;//往右走
if(Node[j].rchild==-1)//到达叶子结点
{
cout<j=LeafNum*2-1-1;//表示重新从根结点开始往下搜索
fop<}//if、
i++;
}//while
fop.close();
cout<<"\n译码成功且已存到文件TextFile.dat中!
\n\n";
}//Decoder
//印文件代码函数
//函数功能:
将文件CodeFile以紧凑格式显示在终端上,
//每行50个代码。
同时将此字符形式的编码文件写入文件CodePrin中。
//函数参数:
无
//参数返回值:
无
voidHuffmanTree:
:
Print()
{
charch;
inti=1;
ifstreamfip("CodeFile.dat");//读取文件
ofstreamfop("CodePrin.dat");//存储文件
if(fip.fail())
{
cout<<"没有文件,请先编码!
\n";
return;
}
while(fip.get(ch))
{
cout<fop<if(i==50)//每行输出50个字符
{
cout<i=0;
}
i++;
}
cout<fip.close();//关闭CodeFile.dat文件
fop.close();//关闭CodePrin.dat文件
}
//显示哈夫曼树函数
//函数功能:
将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上,
//同时将此字符形式的哈夫曼树写入文件TreePrint中。
voidHuffmanTree:
:
TreePrinting()
{
if(Node==NULL)//未建立哈夫曼树
{
cout<<"请先建立哈夫曼树!
\n";
return;
}
ofstreamfop("TreePrint.dat");
cout<<"结点位置(权值)"<<"编码"<<"左孩子"<<"编码"<<"右孩子('^'表示叶子)\n";
fop<<"结点位置(权值)"<<"编码"<<"左孩子"<<"编码"<<"右孩子('^'表示叶子)\n";
inti;
for(i=(2*LeafNum-2);i>LeafNum-1;i--)//输出哈夫曼树
{
cout<
<<fop<
<<}
for(;i>=0;i--)
{
cout<
"<fop<
"<}
}
//程序功能:
主函数源文件
//主函数
intmain()
{
cout<<"欢迎使用哈夫曼码的编/译码系统!
\n";
cout<<"在此系统中可以进行以下操作:
\n";
cout<<"
(1)初始化(I);\n";
cout<<"
(2)编码(E);\n";
cout<<"(3)译码(D);\n";
cout<