数据结构课程设计+哈夫曼编码译码器.docx
《数据结构课程设计+哈夫曼编码译码器.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计+哈夫曼编码译码器.docx（16页珍藏版）》请在冰点文库上搜索。
哈夫曼编码译码器
哈夫曼编码译码器
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#includeusingnamespacestd;
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
// 程序功能：
实现哈夫曼树类的源文件（并用其来实现编/译码）
// 构造函数
// 函数功能：
将结点指针初始化为NULLHuffmanTree:
:
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<<"请输入第"<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;jif（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;
}//forLeafNum=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））; //写入WeightNumfor（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;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） //是左子树，则生成代码0code[start++]='0';
else //是右子树，则生成代码1code[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<}
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++;
}//whilefop.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++;
}
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<<<<<}
for（;i>=0;i--）
{
cout<"<fop<"<}
}
// 程序功能：
主函数源文件
// 主函数
intmain（）
{
cout<<" 欢迎使用哈夫曼码的编/译码系统!
\n";
cout<<"在此系统中可以进行以下操作:
\n";cout<<"
（1）初始化（I）;\n";
cout<<"
（2）编码（E）;\n";
cout<<"（3）译码（D）;\n";
cout<<"（4）代码文件（P）;\n";
cout<<"（5）印哈夫曼树（T）\n";
cout<<"（6）退出（Q）\n\n";
HuffmanTreehuftree; //定义哈夫曼树对象intweight;
charChoose;
while
（1）
{
cout<<"请从清单中选择一个操作（不区分大小写）:
";cin>>Choose;
switch（Choose）
{
case'I':
case'i':
cout<<"请输入编码长度：
";cin>>weight;
huftree.Initialization（weight）; //初始化哈夫曼树break;
case'E':
case'e':
huftree.Encoder（）;break;
case'D':
case'd':
huftree.Decoder（）;break;
case'
升级会员 