用C++实现哈夫曼编码译码

Question

统计字符串长度和各字符频度，编码译码，打印哈夫曼树
没有统计字符长度和频度啊

Answer 1

#include<iostream>
#include<fstream>
#include<string>

using namespace std;

typedef struct HuffmanNode{//结点结构
int weight;
int parent,lchild,rchild;
}*HfmNode;

struct HuffmanTree{//哈弗曼树
HfmNode Node;
char *Info;//存储字符，也可放在结点结构里定义
int LeafNum;//叶结点数量
};

HuffmanTree T;//连接各模块变量
/****************初始化(建立哈夫曼树)函数********************/

void Initialization() //初始化
{
int WeightNum;
int i,j,pos1,pos2,max1,max2; //
int choice;
cout<<endl;
cout<<"***************** 建树方案目录*********************"<<endl;
cout<<"| |"<<endl;
cout<<"| 方案1:输入N个字符和N个权值进行建树 |"<<endl;
cout<<"| 方案2:以文档中字符和并以各字符出现的 |"<<endl;
cout<<"| 频度作为权值进行建树 |"<<endl;
cout<<"***************************************************"<<endl;
lp: cout<<"选择(输入对应方案序号):";cin>>choice;
/********************建树方案1 ************************************/
if(choice==1){

cout<<"输入字符个数:";
cin>>WeightNum;

T.Node=new HuffmanNode[2*WeightNum-1]; //WeightNum权值对应的哈夫曼树中的结点总数为2*WeightNum-1个
T.Info=new char[2*WeightNum-1];//实际只需要申请WeightNum-1；但为了实现要求（5）所以所有结点都由字符域
for(i=0;i<WeightNum;i++)
{
cout<<"请输入第"<<i+1<<"个字符值";

cin.get ();
T.Info[i]=cin.get ();
cout<<"请输入该字符的权值或频度";
cin>>T.Node[i].weight; //输入权值
T.Node[i].parent=-1; //为根结点
T.Node[i].lchild=-1; //无左孩子
T.Node[i].rchild=-1; //无右孩子
}
}
/***********************建树方案2*******************************************************/
else if(choice==2)
{
char ch, *st,*name;
st=new char[128];//128为ASCII码总数
name=new char[20];
cout<<"请输入文档名称:";cin>>name;
cout<<endl;
cout<<"提示：请确认此文件存在或检查文件名是否正确输入!"<<endl;
cout<<endl;
system("pause");
ifstream infile(name);
if(!infile)
{
cout<<"文件打开失败!"<<endl;//为什么字符个数统计与字符归类无法同时进行？？？？
exit(1);
}
i=0;
int k=0;//统计字符种类
while(infile.get (ch))
{

for(int j=0;j<=i;j++)
{
if(st[j]==ch) {break;}

else if(j==i){
st[k]=ch;
++k;
break;
}
}
i++;
}

infile.close();
int *count;
count=new int[k];
for(int m=0;m<k;m++)
count[m]=0;

ifstream infile1(name);
if(!infile1)
{
cout<<"文件打开失败!"<<endl;
exit(1);
}
while(infile1.get (ch))//统计各字符在文档中出现的次数
{

for(int j=0;j<=k;j++)
if(st[j]==ch) count[j]++;
}

infile1.close();
WeightNum=k;

T.Node=new HuffmanNode[2*WeightNum-1];
T.Info=new char[2*WeightNum-1];
for(i=0;i<WeightNum;i++)
{
T.Info[i]=st[i];
T.Node[i].weight=count[i]; //输入权值
T.Node[i].parent=-1; //为根结点
T.Node[i].lchild=-1; //无左孩子
T.Node[i].rchild=-1; //无右孩子
}
delete st;
delete name;
delete count;
}

else {
goto lp;
}
/***************************************************************************/
for(i=WeightNum;i<2*WeightNum-1;i++) //建立哈弗曼树
{
pos1=-1;
pos2=-1; //分别用来存放当前最小值和次小值的所在单元编号
max1=32767; //32767为整型数的最大值
max2=32767; //分别用来存放当前找到的最小值和次小值

for(j=0;j<i;j++) //在跟节点中选出权值最小的两个
if(T.Node[j].parent==-1) //是否为根结点
if(T.Node[j].weight<max1)
{
max2=max1;
max1=T.Node[j].weight;
pos2=pos1; //修改次小值所在单元编号
pos1=j; //修改最小值所在单元编号
}
else
if(T.Node[j].weight<max2) //比原最小值大但比原次小值要小
{
max2=T.Node[j].weight; //存放次小值
pos2=j; //修改次小值所在的单元编号
}
//for
T.Node[pos1].parent=i; //修改根节点位置
T.Node[pos2].parent=i;
T.Node[i].lchild=pos1; //修改儿子节点位置
T.Node[i].rchild=pos2;
T.Node[i].parent=-1; //表示新结点应该是根结点
T.Node[i].weight=T.Node[pos1].weight+T.Node[pos2].weight;
}
T.LeafNum=WeightNum;

ofstream outfile("hfmTree.dat");
if(!outfile)
{
cout<<"打开文件失败!"<<endl;
return;
}
outfile.write((char*)&WeightNum,sizeof(WeightNum)); //写入字符个数
for(i=0;i<WeightNum;i++) //把各字符信息写入文件

outfile.write((char*)&T.Info[i],sizeof(T.Info[i]));

for(i=0;i<2*WeightNum-1;i++) //把个节点内容写入文件

outfile.write((char*)&T.Node[i],sizeof(T.Node[i]));

outfile.close();

cout<<"已建立哈夫曼树!"<<endl;

}
/****************编码函数********************/
void Encoding(){

if(T.Node==NULL) //哈夫曼树不在内存，从文件hfmTree中读入
{
ifstream infile0; //以二进制方式打开hfmTree.dat文件
infile0.open("hfmTree.dat",ios::binary|ios::in);
if(infile0.fail())
{
cout<<"文件打开失败！\n";
return;
}
infile0.read((char*)&T.LeafNum,sizeof(T.LeafNum)); //读取叶子数

T.Info=new char[T.LeafNum];
T.Node=new HuffmanNode[2*T.LeafNum-1];

for(int i=0;i<T.LeafNum;i++) //读取字符信息
infile0.read((char*)&T.Info[i],sizeof(T.Info[i]));

for(i=0;i<2*T.LeafNum-1;i++) //读取结点信息
infile0.read((char*)&T.Node[i],sizeof(T.Node[i]));

infile0.close();
}
char *Tree; //用于存储需编码内容
int i=0,k=0;
cout<<" _________________"<<endl;
cout<<" | 测试数据选择: |"<<endl;
cout<<" | |"<<endl;
cout<<" | A:另输入内容测试|"<<endl;
cout<<" | |"<<endl;
cout<<" | B:用ToBeTran文件|"<<endl;
cout<<" | 内容测试! |"<<endl;
cout<<" |_________________|"<<endl;
cout<<"你的选择(不分大小写):";
char c;
cin>>c;// tag
if(c=='A'||c=='a')
{
string ch;
cout<<"请输入测试数据(输入完毕按两次回车):"<<endl;

cin.ignore();//跳过tag 处输入的字符<--........................*//否则运行结果很意外y因为c也被添加至string中
getline(cin,ch,'\n'); //回车键作为输入结束条件。所以输入结束时按两次回车，
//第一次作为分界符，第二次通知流对象cin已输入一行字符

while(ch[k]!='\0')//统计输入字符个数
k++;

Tree=new char[k+1];
k=0;
while(ch[k]!='\0')//将输入的内容存到Tree中
{
Tree[k]=ch[k];
k++;
}
Tree[k]='\0';

cout<<"需编码内容为:";
cout<<Tree<<endl;

}

else{
ifstream infile1("ToBeTran.txt");
if(!infile1)
{
cout<<"文件打开失败!\n";
return;
}
char ch;
int k=0;
// infile1>>noskipws;
while(infile1.get(ch))
{
k++; //计算ToBeTran中正文长度，以便确定Tree的空间大小
}
infile1.close();
Tree=new char[k+1];
ifstream infile2("ToBeTran.txt");

k=0;
// infile2>>noskipws;
while(infile2.get(ch))
{
Tree[k]=ch; //读取文件内容，并存到Tree中
k++;
}
infile2.close();

Tree[k]='\0';//结束标志

cout<<"需编码内容为:";
cout<<Tree<<endl;
}

ofstream outfile("CodeFile.txt"); //存储编码后的代码,并覆盖原文件
if(T.Node==NULL) //还未建哈夫曼树
{
cout<<"警告+提示：请先建树!\n";
return;
}
char *code;
code=new char[T.LeafNum]; //为所产生编码分配容量为T.LeafNum的存储空间
k=0;
while(Tree[k]!='\0')
{
int j,start=0;
for(i=0;i<T.LeafNum;i++)
if(T.Info[i]==Tree[k]) //求出该文字所在单元的编号
break;
j=i;
while(T.Node[j].parent!=-1) //结点j非树根
{
j=T.Node[j].parent; //非结点j的双亲结点
if(T.Node[j].lchild==i) //是左子树，则生成代码0
code[start++]='0';
else //是右子树，则生成代码1
code[start++]='1';
i=j;
}

int m=start-1;
while(m>=0) //存储哈弗曼编码
{

outfile<<code[m];
m--;
}
k++;

}

outfile.close();
cout<<"已编码！且编码形式内容已存到文件CodeFile.txt中!\n\n";
delete Tree;
delete code;
} //Encoding
/****************译码函数********************/
void Decoding()

{

int i=0,k=0;
int j=T.LeafNum*2-1-1; //从根结点开始往下搜索
char* str;
char ch;
ifstream infile1("CodeFile.txt"); //利用已建好的哈夫曼树将文件CodeFile中的代码进行译码
if(!infile1)
{
cout<<"请先编码!\n";
return;
}
cout<<"经译码,原内容为:";

while(infile1.get(ch))
{
k++; //计算CodeFile中代码长度
}
infile1.close();

str=new char[k+1];

ifstream infile2("CodeFile.txt");
k=0;

while(infile2.get(ch))
{
str[k]=ch; //读取文件内容
k++;
}
infile2.close();
str[k]='\0'; //结束标志符
if(T.Node==NULL) //还未建哈夫曼树
{
cout<<"请先编码!\n";
return;
}
ofstream outfile("TextFile.txt"); //将字符形式的编码文件写入文件Textfile中
while(str[i]!='\0')
{
if(str[i]=='0')
j=T.Node[j].lchild; //往左走
else
j=T.Node[j].rchild; //往右走
if(T.Node[j].rchild==-1) //到达叶子结点
{
cout<<T.Info[j]; //输出叶子结点对应的字符

outfile.put(T.Info[j]);
j=T.LeafNum*2-1-1; //存入文件
}
i++;
}
outfile.close();
delete str;

cout<<"\n译码成功且其内容已存到文件TextFile.txt中！\n\n";
}//Decoding
/****************印代码函数********************/

void Print1(){
char ch;
ifstream infile("Codefile.txt");//
if(!infile)
{
cout<<"未进行编码"<<endl;
return;
}
ofstream outfile("CodePrin.txt");//
if(!outfile)
{
cout<<"打开失败!"<<endl;
return;
}
int i=0;
int j=T.LeafNum*2-1-1;
while(infile.get(ch))
{
cout<<ch;
i++;
if(i==50)
{i=0;
cout<<endl;
}
if(ch=='0')
j=T.Node[j].lchild; //往左走
else
j=T.Node[j].rchild; //往右走
if(T.Node[j].rchild==-1) //到达叶子结点
{
//输出叶子结点对应的字符
outfile.put(T.Info[j]); //存入文件

j=T.LeafNum*2-1-1;
}
}
cout<<endl;
infile.close();
outfile.close();
cout<<"相应的字符形式的编码文件已写入CodePrin.txt中!"<<endl;
}//Print()
/****************印哈夫曼树函数********************/
void Tree_Printing(){
if(T.Node==NULL) //未建立哈夫曼树
{
cout<<"请先建立哈夫曼树！\n";
return;
}
cout<<"所建立的哈夫曼树的凹入表形式为："<<endl;
ofstream fop("TreePrint.txt");
cout<<"位置:权值(字符) "<<"左孩子位置(权值) "<<"右孩子位置(权值)\n";
fop<<"位置:权值(字符) "<<"左孩子位置 (权值) "<<"右孩子位置(权值)\n";
int i;
for(i=0;i<T.LeafNum;i++)
{
cout<<i<<":"<<T.Node[i].weight<<"("<<T.Info[i]<<") \n";
fop<<i<<":"<<T.Node[i].weight<<"("<<T.Info[i]<<") \n";
}
for(i=T.LeafNum;i<(2*T.LeafNum-1);i++) //输出哈夫曼树
{
cout<<i<<":"<<T.Node[i].weight<<"(#)"<<"-------"
<<T.Node[i].lchild<<"("<<T.Node[T.Node[i].lchild].weight<<")"<<"------"
<<T.Node[i].rchild<<"("<<T.Node[T.Node[i].rchild].weight<<")"<<endl;

fop<<i<<":"<<T.Node[i].weight<<"(#)"<<"------"
<<T.Node[i].lchild<<"("<<T.Node[T.Node[i].lchild].weight<<")"<<"------"
<<T.Node[i].rchild<<"("<<T.Node[T.Node[i].rchild].weight<<")"<<endl;
}

}
/*

/****************哈夫曼编码表:********************/
void Print(){
cout<<"哈夫曼编码表:"<<endl;

char *code;
code=new char[T.LeafNum];
int i=0;

while(i<T.LeafNum)
{
cout<<T.Info [i]<<":";
int j,start=0;
int k;
k=i;
j=k;
while(T.Node[j].parent!=-1) //结点j非树根
{
j=T.Node[j].parent; //非结点j的双亲结点
if(T.Node[j].lchild==k) //是左子树，则生成代码0
code[start++]='0';
else //是右子树，则生成代码1
code[start++]='1';
k=j;
}
for(int n=start-1;n>=0;n--)
cout<<code[n];

i++;
cout<<endl;
}

delete code;
}
/****************操作界面函数************************************************************/
void Screen_display(){
char ch;
do{
cout<<"*******************************************************************************"<<endl;
cout<<" 哈夫曼编码/译码系统"<<endl;
cout<<endl;
cout<<" 操作指令目录"<<endl;
cout<<endl;
cout<<" I:初始化(建立哈夫曼树) E:编码 D:译码 P:印代码 T:印哈夫曼树 Q:退出系统"<<endl;
cout<<endl;
cout<<"版本:V1.0"<<endl;
cout<<"*******************************************************************************"<<endl;
cout<<endl;

cout<<"输入相应操作的指令(不分大小写):"<<endl;
cin>>ch;
switch(ch)
{
case'I':
case'i':cout<<" 现在进行'初始化'操作:"<<endl;Initialization();break;
case'E':
case'e':cout<<" 现在进行'编码'操作: "<<endl;Encoding();break;
case'D':
case'd':cout<<" 现在进行'译码'操作: "<<endl;Decoding();break;
case'P':
case'p':cout<<" 现在进行'印代码'操作: "<<endl;Print1();break;
case't':
case'T':{Tree_Printing();cout<<endl;Print();break;}
case'Q':
case'q':cout<<"谢谢使用!"<<endl;exit(1);break;
}
}while(1);
}
/****************主函数********************/
void main(){
Screen_display();
}

Answer 2

#include<iostream>
#include<string>
using namespace std;
const int max=100;
class huffTree
{
public:
int parent,lchild,rchild,weight;
string flag;
};

void select(huffTree array[],int n,int &a,int &b)
{
int ii;
int r=1500,s=1500;
for(ii=0;ii<n;ii++)
{
if(array[ii].weight<r&&array[ii].parent==-1)
{
r=array[ii].weight;
a=ii;
}

}
for(ii=0;ii<n;ii++)
{
if(array[ii].weight<s&&ii!=a&&array[ii].parent==-1)
{
s=array[ii].weight;
b=ii;
}

}
}

int main()
{
huffTree huff[max];
string str[max];
int array[max];
int length;
int o;
cout<<"请输入字符集大小，按enter结束"<<endl;
cin>>length;
cout<<"请输入"<<length<<"个字符，用空格隔开，按enter结束"<<endl;
for(o=0;o<length;o++)
{
cin>>str[o];
}
cout<<"请输入"<<length<<"个字符对应的权值，用空格隔开，按enter结束"<<endl;
for(o=0;o<length;o++)
{
cin>>array[o];
}

int i,j,k,n=length;
for(i=0;i<2*n-1;i++)
{
huff[i].lchild=-1;
huff[i].parent=-1;
huff[i].rchild=-1;
huff[i].flag=-1;
}
for(j=0;j<n;j++)
{
huff[j].weight=array[j];
}
int min1,min2;
for(k=n;k<2*n-1;k++)
{
select(huff,k,min1,min2);
huff[min1].parent=k;
huff[min2].parent=k;
huff[min1].flag="0";
huff[min2].flag="1";
huff[k].lchild=min1;
huff[k].rchild=min2;
huff[k].weight=huff[min1].weight+huff[min2].weight;
}
string da[max];
huffTree p;
for(i=0;i<n;i++)
{
p=huff[i];
while(1)
{
da[i]=p.flag+da[i];
p=huff[p.parent];
if(p.parent==-1)
break;
}
}
cout<<"编码规则:"<<endl;
for(i=0;i<n;i++)
{
cout<<"字符"<<str[i]<<" 权值 "<<huff[i].weight<<" 编码 "<<da[i]<<endl;
}
cout<<endl;
cout<<"******************"<<endl;
string key,word;
int sc;
while(1)
{
sc=0;
cout<<endl;
cout<<"请选择使用编码还是译码 编码(b) 译码(y) 退出(q) "<<endl;
cin>>key;
if(key=="b")
{
cout<<"请输入要编码的字符"<<endl;
cin>>word;
for(i=0;i<n;i++)
{
if(str[i]==word)
{
cout<<" 字符 "<<word<<" 编码 "<<da[i]<<endl;
sc=1;
break;
}
}
if(sc!=1)
cout<<"错误：不存在这个编码!"<<endl;
}
else if(key=="y")
{
cout<<"请输入编码"<<endl;
cin>>word;
for(i=0;i<n;i++)
{
if(word==da[i])
{
cout<<" 编码 "<<word<<" 译码 "<<str[i]<<endl;
sc=1;
break;
}
}
if(sc!=1)
cout<<"错误：不存在这个译码!"<<endl;
}
else if(key=="q")
break;

}
return 0;
}
这个我写的，不是很好，就是为了交作业本回答被网友采纳