#include<iostream>
#include<fstream>
#include<string>
using namespace std;
struct HuffmanNode //树结点类定义
{
int weight; //权值
int parent; //双亲
int lchild,rchild; //左右孩子
};
class HuffmanTree //哈夫曼树类定义
{
private:
struct HuffmanNode *Node; //哈夫曼树中结点的存储结构
char *Info; //用来保存各字符信息的字符数组
int LeafNum; //树中的叶子结点总数
public:
HuffmanTree(); //构造函数
~HuffmanTree(); //析构函数
void Initialization(int WeightNum); //初始化函数
void Encoder(); //编码函数,生成哈夫曼编码
void Decoder(); //译码函数,对二进制串进行译码
void Print(); //输出编码
void TreePrinting(); //输出哈夫曼树
};
HuffmanTree::HuffmanTree() //初始化空树
{
Node=NULL; //将树结点初始化为空
Info=NULL; //将字符数组初始化为空
LeafNum=0; //将叶子数初始化为0
}
HuffmanTree::~HuffmanTree() //析构函数
{
delete[] Node; //释放结点空间
delete[] Info; //释放字符存储空间
}
//初始化函数
void HuffmanTree::Initialization(int WeightNum)
{
int i,j,pos1,pos2,max1,max2;
Node=new HuffmanNode[2*WeightNum-1]; //为哈夫曼树所需的结点申请空间
Info=new char[2*WeightNum-1];
for(i=0;i<WeightNum;i++) //先构造weightnum个点
{
cout<<"请输入第"<<i+1<<"个字符值";
cin>>Info[i];
cout<<"请输入该字符的权值或频度";
cin>>Node[i].weight; //输入权值
Node[i].parent=-1; //为根结点
Node[i].lchild=-1; //无左孩子
Node[i].rchild=-1; //无右孩子
}
//这里构造出weightnum个带权结点
for(i=WeightNum;i<2*WeightNum-1;i++)
{
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; //修改次小值所在的单元编号
}
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;
}
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";
}
//编码函数
void HuffmanTree::Encoder()
{
if(Node==NULL)
{
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in); //以二进制方式打开hfmTree.dat文件
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(int 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++;
}
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<<"需编码内容为:"<<Tree<<endl;
} //if(Choose=='2')
else
{
string tree;
cin.ignore();
cout<<"请输入需要编码的内容(可输入任意长,结束时请按2下回车):\n";
getline(cin,tree,'\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
code[start++]='1'; //是右子树,则生成代码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";
}
//解码函数
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++;
}
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]; //存入文件
}
i++;
}
fop.close();
cout<<"\n译码成功且已存到文件TextFile.dat中!\n\n";
}
//输出编码函数
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)
{
cout<<endl;
i=0;
}
i++;
}
cout<<endl;
fip.close(); //关闭CodeFile.dat文件
fop.close(); //关闭CodePrin.dat文件
}
//输出哈夫曼树
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";
}
}
int main()
{
cout<<"~~~~~~~~~~~~~welcome to Huffman encodrding&decoding system ~~~~~~~~~~~~~~~~~~~~\n\n";
cout<<"You can choose 1--6 options:\n";
cout<<"(1)初始化 \n";
cout<<"(2) 编码\n";
cout<<"(3) 译码\n";
cout<<"(4) 输出编码\n";
cout<<"(5) 输出哈弗曼树\n";
cout<<"(6) Byebye~!\n\n";
HuffmanTree HT;
int weight;
int choice;
int OK=0;
while ( !OK )
{
cout<<"Please input your option (1--6):";
cin>> choice;
switch( choice)
{
case 1:
cout<<"Please input your code lenth"<<endl;
cin>>weight;
HT.Initialization(weight);
break;
case 2:
HT.Encoder();
break;
case 3:
HT.Decoder();
break;
case 4:
HT.Print();break;
case 5:
HT.TreePrinting();break;
case 6:
cout<<"\n***********Thanks for Using!***********\n";
OK=1;
break;
return 0;
}
cout<<"(1)初始化\n";
cout<<"(2)编码\n";
cout<<"(3)译码\n";
cout<<"(4)打印哈弗曼编码\n";
cout<<"(5)打印哈弗曼树\n";
cout<<"(6) Byebye~!\n\n";
}
return 0;
}
C++用哈弗曼编码实现压缩,编码文件比原文件大是怎么回事,怎么能实现压缩,代码如下,求修改
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- threenewbee 2019-01-10 00:24关注
如果你试图压缩的是高熵数据(比如已经被压缩的数据,jpg图片、zip文件等),就会出现编码以后更大的情况。
在商业压缩软件上,避免这个问题的办法就是对高熵数据不压缩处理。解决 无用评论 打赏 举报
悬赏问题
- ¥15 素材场景中光线烘焙后灯光失效
- ¥15 请教一下各位,为什么我这个没有实现模拟点击
- ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
- ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
- ¥20 有关区间dp的问题求解
- ¥15 多电路系统共用电源的串扰问题
- ¥15 slam rangenet++配置
- ¥15 有没有研究水声通信方面的帮我改俩matlab代码
- ¥15 ubuntu子系统密码忘记
- ¥15 保护模式-系统加载-段寄存器