Question

急求用数据结构写出的哈夫曼编码/译码器！！！必须要数据结构写出的。谢谢！！！急用！！！大侠帮帮忙！！

哈夫曼编码/译码器
【问题描述】
设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。
【基本要求】
(1) 输入一个待压缩的文本文件名， 统计文本文件中各字符的个数作为权值，生成哈夫曼树；
(2) 将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod），
(3) 输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；
(4) 显示指定的压缩文件和文本文件；
(5) 界面友好，易与操作。采用菜单方式进行选择。

Answer 1

（二） 数据结构描述：
为实现上述程序功能，应以指针存储结点。为此，需要定义一个抽象数据类型。
1. 抽象数据类型定义为：ADT HuffmanTree{
数据对象：D={ai| ai∈CharSet,i=1,2,……,n, n≥0}
数据关系：R={< ai-1, ai > ai-1, ai∈D, ai-1<ai ,i=2，3，……，n}
基本操作P：
HuffmanTree(); 构造函数
~ HuffmanTree(); 析构函数
Initialization(int WeightNum);
操作结果：构造哈夫曼树。
Encoder()
初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。
操作结果：对字符串进行编码
Decoder();
初始条件：哈夫曼树已存在且已编码。
操作结果：对二进制串进行译码
Print()
初始条件：编码文件已存在。
操作结果：把已保存好的编码文件显示在屏幕
2.本程序包含三个模块：
1)主程序模块：
void main(){
初始化；
do{
接受命令；
处理命令；
}while(“命令”=”退出”)
}
2)、建树模块――实现定义的抽象数据类型
3)、编/译码模块――实现字符串的编/译码
各模块之间的调用关系如下：
主程序模块

建树模块

编/译码模块
（三） 主要算法流程描述：
// 程序名：HuffmanTree.h
// 程序功能：赫夫曼树类的头文件(并用其来实现编/译码)
#include<iostream>
#include<fstream>
#include<string>
using namespace std;
struct HuffmanNode //定义赫夫曼树各结点
{
int weight; //存放结点的权值，假设只考虑处理权值为整数的情况
int parent; //记录结点父亲位置，-1表示为根结点，否则表示为非根结点
int lchild,rchild; //分别存放该结点的左、右孩子的所在单元的编号
};
class HuffmanTree //建立赫夫曼树类
{
private:
HuffmanNode *Node; //赫夫曼树中结点的存储结构
char *Info; //用来保存各字符信息
int LeafNum; //树中的叶子结点总数
public:
HuffmanTree(); //构造函数
~HuffmanTree(); //析构函数
void Initialization(int WeightNum); //初始化函数：根据WeightNum个权值建立一棵赫夫曼树
void Encoder(); //编码函数：利用构造好的赫夫曼树对字符进行编码
void Decoder(); //译码函数：对二进制串进行译码
void Print(); //输出文件函数：把已保存好的编码文件显示在屏幕
void TreePrinting(); //输出赫夫曼树函数：将已在内存中的赫夫曼树以直观的方式显示在终端上
};
// 程序名：HuffmanTree.cpp
// 程序功能：实现赫夫曼树类的源文件(并用其来实现编/译码)
#include"HuffmanTree.h"
#include<string>
using namespace std;
//////////////////////////////////////////////////////////////////////////////
// 构造函数
// 函数功能：将结点指针初始化为NULL
// 函数参数：无
// 参数返回值：无
HuffmanTree::HuffmanTree()
{
Node=NULL; //将树结点初始化为空
Info=NULL; //将字符数组初始化为空
LeafNum=0; //将叶子数初始化为0
}
//////////////////////////////////////////////////////////////////////////////
// 析构函数
// 函数功能：将所有结点的空间释放
// 函数参数：无
// 参数返回值：无
HuffmanTree::~HuffmanTree()
{
delete[] Node; //释放结点空间
delete[] Info; //释放字符存储空间
}
//////////////////////////////////////////////////////////////////////////////
// 初始化函数
// 函数功能：从终端读入字符集大小n，以及n个字符和n个权值,
// 建立赫夫曼树,并将它存放在文件hfmTree中.
// 函数参数：int WeightNum表示代码个数
// 参数返回值：无
void HuffmanTree::Initialization(int WeightNum) //初始化
{
int i,j,pos1,pos2,max1,max2; //

Node=new HuffmanNode[2*WeightNum-1]; //WeightNum权值对应的赫夫曼树中的结点总数为2*WeightNum-1个
Info=new char[2*WeightNum-1];
for(i=0;i<WeightNum;i++)
{
cout<<"请输入第"<<i+1<<"个字符值";
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<i;j++) //在跟节点中选出权值最小的两个
if(Node[j].parent==-1) //是否为根结点
if(Node[j].weight<max1) //是否比最小值要小
{
max2=max1; //原最小值变为次小值
max1=Node[j].weight; //存放最小值
pos2=pos1; //修改次小值所在单元编号
pos1=j; //修改最小值所在单元编号
}
else
if(Node[j].weight<max2) //比原最小值大但比原次小值要小
{
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;

char ch;
cout<<"是否要替换原来文件(Y/N):";
cin>>ch;
if(ch=='y'||ch=='Y')
{
ofstream fop; //以二进制方式打开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<WeightNum;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中.
// 函数参数：无
// 参数返回值：无
void HuffmanTree::Encoder()
{
if(Node==NULL) //赫夫曼树不在内存，从文件hfmTree中读入
{
ifstream fip; //以二进制方式打开hfmTree.dat文件
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) //文件打开失败
{
cout<<"文件打开失败！\n";
return; //结束本函数
}
fip.read((char*)&LeafNum,sizeof(LeafNum)); //读取叶子数
Info=new char[LeafNum];
Node=new HuffmanNode[2*LeafNum-1];
for(int i=0;i<LeafNum;i++) //读取字符信息
fip.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; //用于存储需编码内容
int i=0,num;
char Choose; //让用户选择读取文件或重新输入需编码内容
cout<<"你要从文件中读取内容(1)，还是重新输入(2):";
cin>>Choose;
if(Choose=='1') //读取文件ToBeTran.txt
{
ifstream fip1("ToBeTran.txt");
if(fip1.fail()) //文件不存在
{
cout<<"文件打开失败!\n";
return; //结束本函数
}
char ch;
int k=0;
while(fip1.get(ch))
{
k++; //计算CodeFile中代码长度
}
fip1.close();

Tree=new char[k+1];
ifstream fip2("ToBeTran.txt");
k=0;
while(fip2.get(ch))
{
Tree[k]=ch; //读取文件内容，并存到Tree中
k++;
}
fip2.close();
Tree[k]='\0'; //结束标志
cout<<"需编码内容为:";
cout<<Tree<<endl;
}//if(Choose=='1')
else //Choose!='1',重新输入
{
string tree; //用于输入需编码内容，由于string类对象可以输入任意长度，
//所以先利用这个对象输入，再转存在Tree中

cin.ignore();
cout<<"请输入需要编码的内容(可输入任意长，结束时请按2下回车):\n";
getline(cin,tree,'\n'); //输入任意长字符串，
//getline以回车('\n')作为结束符，第一次按回车表示字符串结束，第二次按回车才开始输出。
while(tree[i]!='\0')
i++;
num=i; //计算tree长度
i=0;
Tree=new char[num+1];
while(tree[i]!='\0') //将tree中的字符转存到Tree中
{
Tree[i]=tree[i];
i++;
}
Tree[i]='\0'; //结束标志符
}

ofstream fop("CodeFile.dat",ios::trunc); //存储编码后的代码,并覆盖原文件
i=0;
int k=0;
char *code;
code=new char[LeafNum]; //为所产生编码分配容量为LeafNum的存储空间
//因为不等长编码中最长的编码一定不会超过要求编码的字符个数
while(Tree[k]!='\0') //对每一个字符编码
{
int j,start=0;
for(i=0;i<LeafNum;i++)
if(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<start/2;i++) //对二进制序列进行逆置
{
j=code[i];
code[i]=code[start-i-1];
code[start-i-1]=j;
}
i=0;
while(code[i]!='\0') //存储代码
{
fop<<code[i];
i++;
}
k++;
}
fop.close();
cout<<"已编码！且存到文件CodeFile.dat中！\n\n";
} //Encode
//////////////////////////////////////////////////////////////////////////////
// 译码函数
// 函数功能：利用已建好的赫夫曼树,对传输到达的CodeFile中的数据代码进行译码,
// 将译码结果存入文件TextFile中.
// 函数参数：无
// 参数返回值：无
void HuffmanTree::Decoder()
{
int i=0,k=0;
int j=LeafNum*2-1-1; //表示从根结点开始往下搜索
char* BitStr;

ifstream fip1("CodeFile.dat"); //利用已建好的赫夫曼树将文件CodeFile中的代码进行译码
if(fip1.fail()) //文件打开失败，还未编码
{
cout<< "请先编码！\n";
return;
}
cout<<"经译码,原内容为:";
char ch;
while(fip1.get(ch))
{
k++; //计算CodeFile中代码长度
}
fip1.close();

BitStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
{
BitStr[k]=ch; //读取文件内容
k++;
}
fip2.close();
BitStr[k]='\0'; //结束标志符
if(Node==NULL) //还未建赫夫曼树
{
cout<<"请先编码!\n";
return;
}
ofstream fop("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<<Info[j]; //输出叶子结点对应的字符
j=LeafNum*2-1-1; //表示重新从根结点开始往下搜索
fop<<Info[j]; //存入文件
}//if、
i++;
}//while
fop.close();

cout<<"\n译码成功且已存到文件TextFile.dat中！\n\n";
}//Decoder
//////////////////////////////////////////////////////////////////////////////
// 输出文件代码函数
// 函数功能：将文件CodeFile以紧凑格式显示在终端上，
// 每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
// 函数参数：无
// 参数返回值：无
void HuffmanTree::Print()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat"); //读取文件
ofstream fop("CodePrin.dat"); //存储文件
if(fip.fail())
{
cout<<"没有文件，请先编码！\n";
return;
}
while(fip.get(ch))
{
cout<<ch; //读取文件内容
fop<<ch; //存到文件中
if(i==50) //每行输出50个字符
{
cout<<endl;
i=0;
}
i++;
}
cout<<endl;
fip.close(); //关闭CodeFile.dat文件
fop.close(); //关闭CodePrin.dat文件
}
//////////////////////////////////////////////////////////////////////////////
// 输出赫夫曼树函数
// 函数功能：将已在内存中的赫夫曼树以直观的方式(树或凹入表的形式)显示在终端上，
// 同时将此字符形式的赫夫曼树写入文件TreePrint中。
// 函数参数：无
// 参数返回值：无
void HuffmanTree::TreePrinting()
{
if(Node==NULL) //未建立赫夫曼树
{
cout<<"请先建立赫夫曼树！\n";
return;
}
ofstream fop("TreePrint.dat");
cout<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n";
fop<<"结点位置(权值) "<<"编码 "<<"左孩子 "<<"编码"<<"右孩子('^'表示叶子)\n";
int i;
for(i=(2*LeafNum-2);i>LeafNum-1;i--) //输出赫夫曼树
{
cout<<i<<"("<<Node[i].weight<<")"<<"--1--"
<<Node[i].lchild<<"("<<Node[Node[i].lchild].weight<<")"<<"--0--"
<<Node[i].rchild<<"("<<Node[Node[i].rchild].weight<<")"<<endl;
fop<<i<<"("<<Node[i].weight<<")"<<"--1--"
<<Node[i].lchild<<"("<<Node[Node[i].lchild].weight<<")"<<"--0--"
<<Node[i].rchild<<"("<<Node[Node[i].rchild].weight<<")"<<endl;
}
for(;i>=0;i--)
{
cout<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
fop<<i<<":"<<Node[i].weight<<"("<<Info[i]<<")---^\n";
}
}
// 程序名：main.cpp
// 程序功能：主函数源文件
#include"HuffmanTree.h"
#include<string.h>
#include<stdlib.h>
//////////////////////////////////////////////////////////////////////////////
// 主函数
//参数返回值：无
int main()
{
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";
HuffmanTree huftree; //定义赫夫曼树对象
int weight;
char Choose;
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 'P':
case 'p':
huftree.Print();
break;
case 'T':
case 't':
huftree.TreePrinting();
break;
case 'Q':
case 'q':
cout<<"\n ***********感谢使用本系统!***********\n\n";
system(“pause”); //暂停运行
return 0;
}
cout<<"(1) 初始化(I) (2) 编码(E) (3) 译码(D)\n";
cout<<"(4) 输出代码文件(P) (5) 输出赫夫曼树(T) (6) 退出(Q)\n";
}
}
（四） 使用说明及调试：
点击“运行”按钮，屏幕显示
“欢迎使用赫夫曼的编/译码系统
在此系统中可以进行以下操作:\n";
(1) 初始化(I);
(2) 编码(E);
(3) 译码(D);
(4) 输出代码文件(P);
(5) 输出赫夫曼树(T) ;
(6) 退出(Q)
请从清单中选择一个操作(不区分大小写):”
选择初始化“I”
请输入编码长度：26
请输入第1个编码的字符值A
请输入该字符的权值或频度186
请输入第2个编码的字符值B
请输入该字符的权值或频度64
请输入第3个编码的字符值C
请输入该字符的权值或频度13
请输入第4个编码的字符值D
请输入该字符的权值或频度22
请输入第5个编码的字符值E
请输入该字符的权值或频度32
请输入第6个编码的字符值F
请输入该字符的权值或频度103
请输入第7个编码的字符值G
请输入该字符的权值或频度21
请输入第8个编码的字符值H
请输入该字符的权值或频度15
请输入第9个编码的字符值I
请输入该字符的权值或频度47
请输入第10个编码的字符值J
请输入该字符的权值或频度57
请输入第11个编码的字符值K
请输入该字符的权值或频度15
请输入第12个编码的字符值L
请输入该字符的权值或频度32
请输入第13个编码的字符值M
请输入该字符的权值或频度20
请输入第14个编码的字符值N
请输入该字符的权值或频度57
请输入第15个编码的字符值O
请输入该字符的权值或频度63
请输入第16个编码的字符值P
请输入该字符的权值或频度15
请输入第17个编码的字符值Q
请输入该字符的权值或频度1
请输入第18个编码的字符值R
请输入该字符的权值或频度48
请输入第19个编码的字符值S
请输入该字符的权值或频度51
请输入第20个编码的字符值T
请输入该字符的权值或频度80
请输入第21个编码的字符值U
请输入该字符的权值或频度23
请输入第22个编码的字符值V
请输入该字符的权值或频度8
请输入第23个编码的字符值W
请输入该字符的权值或频度18
请输入第24个编码的字符值X
请输入该字符的权值或频度1
请输入第25个编码的字符值Y
请输入该字符的权值或频度16
请输入第26个编码的字符值Z
请输入该字符的权值或频度1
是否要替换原来文件（Y/N）:Y
赫夫曼树已构造完成。
(1) 初始化(I) (2) 编码(E) (3) 译码(D)
(4) 输出代码文件(P) (5) 输出赫夫曼树(T) (6) 退出(Q)
请从清单中选择一个操作（不区分大小写）:E
你要从文件中读取内容（1），还是重新输入（2）:2
请输入需要编码的内容（可输入任意长，结束时请按2下回车）:
ILOVECHINA
已编码！且存到文件CodeFile.dat中！
(1) 初始化(I) (2) 编码(E) (3) 译码(D)
(4) 输出代码文件(P) (5) 输出赫夫曼树(T) (6) 退出(Q)
请从清单中选择一个操作（不区分大小写）:D
经译码，原内容为：ILOVECHINA
译码成功且存到文件TextFile.dat中！
(1) 初始化(I) (2) 编码(E) (3) 译码(D)
(4) 输出代码文件(P) (5) 输出赫夫曼树(T) (6) 退出(Q)
请从清单中选择一个操作（不区分大小写）:P
000010111100100011011011000011110000000000111111
(1) 初始化(I) (2) 编码(E) (3) 译码(D)
(4) 输出代码文件(P) (5) 输出赫夫曼树(T) (6) 退出(Q)
请从清单中选择一个操作（不区分大小写）:T
结点位置(权值) 编码 左孩子 编码右孩子('^'表示叶子)
50(1009)--1--48(410)--0--49(599)
49(599)--1--46(252)--0--47(347)
48(410)--1--44(193)--0--45(217)
47(347)--1--43(161)--0--0(186)
46(252)--1--41(124)--0--42(128)
45(217)--1--5(103)--0--40(114)
44(193)--1--38(94)--0--39(99)
43(161)--1--19(80)--0--37(81)
42(128)--1--1(64)--0--36(64)
41(124)--1--35(61)--0--14(63)
40(114)--1--9(57)--0--13(57)
39(99)--1--17(48)--0--18(51)
38(94)--1--8(47)--0--34(47)
37(81)--1--32(38)--0--33(43)
36(64)--1--4(32)--0--11(32)
35(61)--1--30(30)--0--31(31)
34(47)--1--20(23)--0--29(24)
33(43)--1--6(21)--0--3(22)
32(38)--1--22(18)--0--12(20)
31(31)--1--15(15)--0--24(16)
30(30)--1--7(15)--0--10(15)
29(24)--1--28(11)--0--2(13)
28(11)--1--27(3)--0--21(8)
27(3)--1--25(1)--0--26(2)
26(2)--1--16(1)--0--23(1)
25:1(Z)---^
24:16(Y)---^
23:1(X)---^
22:18(W)---^
21:8(V)---^
20:23(U)---^
19:80(T)---^
18:51(S)---^
17:48(R)---^
16:1(Q)---^
15:15(P)---^
14:63(O)---^
13:57(N)---^
12:20(M)---^
11:32(L)---^
10:15(K)---^
9:57(J)---^
8:47(I)---^
7:15(H)---^
6:21(G)---^
5:103(F)---^
4:32(E)---^
3:22(D)---^
2:13(C)---^
1:64(B)---^
0:186(A)---^
(1) 初始化(I) (2) 编码(E) (3) 译码(D)
(4) 输出代码文件(P) (5) 输出赫夫曼树(T) (6) 退出(Q)
请从清单中选择一个操作（不区分大小写）:Q
***********感谢使用本系统!***********
请按任意键继续. . .
（五） 特色及改进设想；
1、由于二维指针和string类，还有文件操作的推敲不足，使程序调试时费时不少。还有对单个空格字符的输入，也花了一些时间，不过最终能实现单个空格的输入，还是值得的。
2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性，特别是文件操作方面，如果可能的话，可以把文件读入、读出分别写成一个函数（就是把文件名作为参数），然后就可以直接调用了。
3、本程序模块划分比较合理，且利用指针和string类对象实现字符串的操作，操作方便。
4、算法的时空分析
在此程序中，存储字符串都用了指针，先动态申请空间，然后再存，这样就有效的利用了空间，不过为了实现任意长字符串的输入，引入了string类，先定义string对象，再输入。最后转存到字符指针里，这样就浪费了一些空间。
而对于哈夫曼树算法本身，由于这里只是一个静态的，所以当进行网络传输时，可能会显得效率比较低。
5、本实验采用数据抽象的程序设计方法，将程序分为3个模块，使得设计时思路清晰，实现时调试可以顺利完成，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。

（六） 综合设计过程，做出总结；
1、通过实验更好的掌握了赫夫曼树，并对赫夫曼树有了深一步的了解
2、掌握了用getchar可以输入单个空格
4、更进一步掌握有关类的操作
5、由于算法推敲不足，使程序调试时费时不少
6、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性
7、更熟悉了文件的操作
8、更好的掌握了对程序的调试，并从中感受到调试的巨大的力量，特别是当程序不能实现预想结果时

Answer 2

....同学，你哪个大学的啊，我的刚找过网上的交了作业，我海事的