哈夫曼实现压缩

2025-12-17 17:49:02

推荐回答（1个）

回答1：

我的作业，哈弗曼树的建立，不过那个字符的频率要自己编的。
//main.cpp
#include"HuffmanTree.h"
#include
#include
//#include

//using namespace std;

int main(){

HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n\n**********************欢迎使用哈夫曼编码/译码系统**********************\n"< cout<<" 您可以进行以下操作:\n";
cout<<" 1 建立哈夫曼树\n";
cout<<" 2 编码(源文已在文件ToBeTran中，或键盘输入)\n";
cout<<" 3 译码(码文已在文件CodeFile中)\n";
cout<<" 4 显示码文\n";
cout<<" 5 显示哈夫曼树\n";
cout<<" 6 退出\n\n";

cout<<" 请选择一个操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感谢使用本系统!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main

//Huffmannode.h
#ifndef _HuffmanNode_
#define _HuffmanNode_
struct HuffmanNode
{
int weight; //存放结点的权值，假设只考虑处理权值为整数的情况
int parent; //-1表示为根结点，否则表示为非根结点
int lchild,rchild; //分别存放该结点的左右孩子的所在单元的编号
};
#endif

//huffmantree.h
#ifndef _HuffmanTree_
#define _HuffmanTree_
#include"HuffmanNode.h"
#include
#include
#include
using namespace std;

class HuffmanTree //哈夫曼树
{
public:
struct HuffmanNode *Node; //Node[]存放哈夫曼树
char *Info; //Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放
int LeafNum; //哈夫曼树的叶子个数，也是源码个数
public:
HuffmanTree();
~HuffmanTree();
void CreateHuffmanTree(); /*在内存中建立哈夫曼树，存放在Node[]中。让用户从两种建立哈夫曼树的方法中选择：
1.从键盘读入源码字符集个数，每个字符，和每个字符的权重，建立哈夫曼树，
并将哈夫曼树写入文件hfmTree中。2.从文件hfmTree中读入哈夫曼树信息，建立哈夫曼树*/
void CreateHuffmanTreeFromKeyboard();
void CreateHuffmanTreeFromFile();
void Encoder(); /*使用建立好的哈夫曼树（如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树），
对文件ToBeTran中的正文进行编码，并将码文写入文件CodeFile中。
ToBeTran的内容可以用记事本等程序编辑产生。*/
void Decoder(); /*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树（如果不在内存，
则从文件hfmTree中读入并建立内存里的哈夫曼树）将码文译码，
得到的源文写入文件TextFile中，并同时输出到屏幕上。*/
void PrintCodeFile(); /*将码文文件CodeFile显示在屏幕上*/
void PrintHuffmanTree(); /*将哈夫曼树以直观的形式（凹入表示法，或广义表，或其他树形表示法）显示在屏幕上，
同时写入文件TreePrintFile中*/
void PrintHuffmanTree_aoru(int T,int layer=1); /*凹入表示法显示哈夫曼树，由PrintHuffmanTree()调用*/
};
#endif

//huffmantree.cpp
#include"HuffmanTree.h"
#include
#include //为使用整型最大值

//#include
using namespace std;

//******************************************************
HuffmanTree::HuffmanTree()
{
LeafNum=0;
Node=NULL;
Info+NULL;

}
//******************************************************
HuffmanTree::~HuffmanTree()
{
delete []Node;
Node=NULL;
delete []Info;
Info=NULL;

}
//******************************************************
void HuffmanTree::CreateHuffmanTree()
{
char Choose;
cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？";
cin>>Choose;
if(Choose=='2') {//键盘输入建立哈夫曼树
CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile();
}
}
//******************************************************
void HuffmanTree::CreateHuffmanTreeFromKeyboard()
{
int Num;
int i,j,pos1,pos2,max1,max2;
cout<<"\n请输入源码字符集个数：";
cin>>Num;
if (Num<=1)
{
cout<<"无法建立少于2个叶子结点的哈夫曼树。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
Info=new char[2*Num-1];
for( i=0;i cout<<"请输入第"< getchar();
Info[i]=getchar(); //源文的字符存入字符数组Info[]
getchar();
cout<<"请输入该字符的权值或频度";
cin>>Node[i].weight; //源文的字符权重存入Node[].weight
Node[i].parent=-1; //为根结点
Node[i].lchild=-1; //无左孩子
Node[i].rchild=-1; //无右孩子
}

for( i=Num;i<2*Num-1;i++) //循环建立哈夫曼树内部结点表示需做Num-1次合并
{
pos1=-1;pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号
max1=32767; max2=32767; //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;
}
}
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=Num;
cout<<"哈夫曼树已成功构造完成。\n";

//把建立好的哈夫曼树写入文件hfmTree.dat
char ch;
cout<<"是否要替换原来的哈夫曼树文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打开文件
if(fop.fail()) {
cout<<"\n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先写入哈夫曼树的叶子结点个数
for( i=0;i fop.write((char*)&Info[i],sizeof(Info[i]));
flush(cout);
}
for( i=0;i<2*Num-1;i++) { //最后写入哈夫曼树的各个结点（存储在Node[]中）
fop.write((char*)&Node[i],sizeof(Node[i]));
flush(cout);
}
fop.close(); //关闭文件
cout<<"\n哈夫曼树已成功写入hfmTree.dat文件。\n";
}

//******************************************************
void HuffmanTree::CreateHuffmanTreeFromFile()
{
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。\n";
fip.close();
return;
}
Info=new char[LeafNum];
Node=new HuffmanNode[2*LeafNum-1];
for( int i=0;i fip.read((char*)&Info[i],sizeof(Info[i]));
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼树已成功构造完成。\n";
}

//******************************************************
void HuffmanTree::Encoder()
{
if(Node==NULL) //内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}//if

char *SourceText; //字符串数组，用于存放源文
//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入
char Choose;
cout<<"你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？";
cin>>Choose;
if(Choose=='1')
{
ifstream fip1("ToBeTran.txt");
if(fip1.fail())
{
cout<<"源文文件打开失败!无法继续执行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次读文件只统计文件中有多少个字符，将字符数存入k
fip1.close();

SourceText=new char[k+1]; //申请存放源文的字符数组空间
ifstream fip2("ToBeTran.txt");//第二次读源文文件，把内容写入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
cout<<"需编码的源文为：";
cout< }
else { //从键盘输入源文
string SourceBuff;
cin.ignore();
cout<<"请输入需要编码的源文(可输入任意长，按回车键结束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}

ofstream fop("CodeFile.dat",ios::trunc); //打开码文存放文件
char *code;
code=new char[LeafNum]; //存放一个源文字符的编码
int k=0;
int i,j,start;
while(SourceText[k]!='\0') //源文串中从第一个字符开始逐个编码
{
start=0;
for(i=0;i if(Info[i]==SourceText[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
code[start++]='1'; //是右子树，则生成代码1
i=j;
}
code[start]='\0'; //置串结束符
for(i=0;i {
j=code[i];
code[i]=code[start-1-i];
code[start-1-i]=j;
}
i=0; //将源文的当前字符的对应编码写入码文文件
while(code[i]!='\0')
{
fop< i++;
}
k++; //源文串中的字符后移一个

}
fop.close();
cout<<"已完成编码，码文已写入文件CodeFile.dat中。\n\n";
}

//******************************************************
void HuffmanTree::Decoder()
{

//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1)
{
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}

//将码文从文件CodeFile.dat中读入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail())
{
cout<<"没有码文，无法译码。\n";
return;
}

char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch))
{
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';

cout<<"经译码得到的源文为：";
ofstream fop("TextFile.dat");

int j=(LeafNum-1)*2; //j指向哈夫曼树的根

int i=0; //码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子
while(CodeStr[i]!='\0') //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符
{
if(CodeStr[i]=='0')
j=Node[j].lchild; //往左走
else
j=Node[j].rchild; //往右走
if(Node[j].rchild==-1) //到达叶子结点
{
cout< j=LeafNum*2-1-1; //表示重新从根结点开始往下搜索
}
i++;
}
fop.close();
cout<<"\n译码成功且已存到文件TextFile.dat中。\n\n";
}
//******************************************************
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"没有码文文件，无法显示码文文件内容。\n";
return;
}
while(fip.get(ch))
{
cout< fop< if(i==50)
{
cout< fop< i=0;
}
i++;
}
cout< fop< fip.close();
fop.close();
}
//******************************************************
void HuffmanTree::PrintHuffmanTree()
{
//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}

ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
//******************************************************
void HuffmanTree::PrintHuffmanTree_aoru(int T,int layer)//凹入表示法
{
if(Node[T].lchild!=-1)
PrintHuffmanTree_aoru(Node[T].lchild,layer+1);//左子树
for(int i=1;i<=layer;i++)// 根
cout<<'\0'<<'\0'<<'\0';
cout< if(Node[T].rchild!=-1)
PrintHuffmanTree_aoru(Node[T].rchild,layer+1); // 右子树

}