主题:哈夫曼树编码问题-急急急,求教高高手
下面这程序运行时会出现问题,希望有人帮帮忙
#ifndef HUFFMANCODING_H
#define HUFFMANCODING_H
#include<iostream>
#include<fstream>
#include<string>
#include<iomanip>
using namespace std;
class HfmNode{
public:
HfmNode()
{
left = right = NULL;
d[10] = '\0';
}
char c;//输入的字符
int data;//对应节点的权植
char d[10];//对应节点的编码
HfmNode *left, *right;
};
class HuffManCoding{
public:
HuffManCoding();//初始化
void setHuffNode();
void CreatHuffman();
void PrintHfmTree(HfmNode *);//输出哈夫曼树
void CodingNode( HfmNode *,int lenth );//对哈夫曼树的叶结点进行编码
//void CreatFileToBeTran();//输入正文并保存在文件ToBeTran以进行编码
void CodeFileToBeTran();//对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中,并输出结果,将文件CodeFile以紧凑格式先是在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
void DecodingFile();//利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中,并输出结果。
private:
HfmNode *root;
HfmNode **node;//指向对象指针节点数组
int size;//对象指针节点数组大小
};
#endif
HuffManCoding::HuffManCoding()
{
setHuffNode();
}
void HuffManCoding::setHuffNode()
{
int i,j;
int n;
//HfmNode **N;
cout << "输入进行编码的字符个数 ";
cin >> n;
size = n;
node = new HfmNode *[n];
for( i = 0; i < n; i++ )
node[i] = new HfmNode;
for( j = 0; j < n; j++ )
{
cout << "输入第" << j + 1 << "字符: " ;
cin >> node[j]->c;
cout << "权值为: ";
cin >> node[j]->data ;
}
root = NULL;
}
//建立哈夫曼树并调用函数进行输出和编码
void HuffManCoding::CreatHuffman()
{
HfmNode *q;
int i,j;
for( i = 0; i < size; i++ )
{
int k1 = -1;//用k1表示森林中具有最小权值的树根结点的下标
int k2;//用k2表示森林中具有次最小权值的树根结点的下标
for( j = 0; j < size; j++ )
{
if( node[j] != NULL && k1 == -1 )
{
k1 = j;
continue;
}
if( node[j] != NULL )
{
k2 = j;
break;
}
}
for( j = k2; j < size; j++ )
{
if( node[j] != NULL )
{
if( node[j]->data < node[k1]->data )
{
k2 = k1;
k1 = j;
}
else if( node[j]->data < node[k2]->data )
k2 = j;
}
}
q = new HfmNode;
q->data = node[k1]->data + node[k2]->data;
q->left = node[k1];
q->right = node[k2];
}
root = q;
cout << "建立的哈夫曼树为" << endl;
PrintHfmTree(q);
CodingNode(q,0);
}
//输出哈夫曼树
void HuffManCoding::PrintHfmTree(HfmNode *r)
{
if( r != NULL )
{
cout << r->c;
if( r->left != NULL || r->right != NULL )
{
cout << "(";
PrintHfmTree( r->left );
if( r->right != NULL )
cout << ", ";
PrintHfmTree( r->right );
cout << ") ";
}
}
}
//对哈夫曼树的结点进行编码
void HuffManCoding::CodingNode(HfmNode *r,int len)
{
static int a[10];
static int i = 0;
if( r!= NULL )
{
if( r->left == NULL && r->right == NULL )
node[i++] = r;
int j;
for( j = 0; j < len; j++ )
node[i]->d[j] = a[j];
node[i]->d[len] = '\0';
}
else{
a[len] = 0;
CodingNode( r->left,len+1);
a[len] = 1;
CodingNode( r->right,len+1);
}
}
/*void HuffManCoding::CreatFileToBeTran()//输入正文并保存在文件ToBeTran以进行编码
{
cout << "输入要进行编码的文件" << endl;
char ch;
ofstream InputFile("ToBeTran.dat");
if(!InputFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
while(( ch=cin.get())!= EOF )
{
InputFile.put(ch);
}
InputFile.close();
}
*/
//对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中,
//并输出结果,将文件CodeFile以紧凑格式先是在终端上,每行50个代码。
//同时将此字符形式的编码文件写入文件CodePrint中。
void HuffManCoding::CodeFileToBeTran()
{
ifstream OpenFile("ToBeTran.dat");
if(!OpenFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
ofstream InputFile("CodeFile.dat");
if(!InputFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
char ch;
while( ( ch =OpenFile.get())!= EOF)
{
for( int i = 0; i < size; i++ )
if( node[i]->c == ch )
InputFile << node[i]->d;
}
OpenFile.close();
InputFile.close();
ifstream openFile("CodeFile.dat");
if(!openFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
ofstream inputFile("CodePrint.dat");
if(!inputFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
int i = 0;
while(( ch = openFile.get() != EOF )
{
cout<<ch;
i++;
if( i == 10 )
cout << endl;
inputFile.put(ch);
}
openFile.close();
inputFile.close();
}
//利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中,并输出结果。
void HuffManCoding::DecodingFile()
{
ifstream OpenFile("CodeFile.dat");
if(!OpenFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
ofstream InputFile("TextFile.dat");
if(!InputFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
char ch;
char c[10];
int i = 0;
while((ch = OpenFile.get()) != EOF )
{
c[i++] = ch;
c[i] = '\0';
for( int j = 0; j < size; j++ )
if( strcmp(node[j]->d,c) )
{
cout << node[j]->c << setw(2) << endl;
InputFile << node[j]->c;
i = 0;
}
}
OpenFile.close();
InputFile.close();
}
int main()
{
HuffManCoding h;
h.CreatHuffman();
// h.CreatFileToBeTran();//输入要编码的文件
cout << "编码后的文件代码为" << endl;
h.CodeFileToBeTran();//编码并输出
cout << "译码后的文件为" << endl;
h.DecodingFile();//译码并输出
return 0;
}
#ifndef HUFFMANCODING_H
#define HUFFMANCODING_H
#include<iostream>
#include<fstream>
#include<string>
#include<iomanip>
using namespace std;
class HfmNode{
public:
HfmNode()
{
left = right = NULL;
d[10] = '\0';
}
char c;//输入的字符
int data;//对应节点的权植
char d[10];//对应节点的编码
HfmNode *left, *right;
};
class HuffManCoding{
public:
HuffManCoding();//初始化
void setHuffNode();
void CreatHuffman();
void PrintHfmTree(HfmNode *);//输出哈夫曼树
void CodingNode( HfmNode *,int lenth );//对哈夫曼树的叶结点进行编码
//void CreatFileToBeTran();//输入正文并保存在文件ToBeTran以进行编码
void CodeFileToBeTran();//对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中,并输出结果,将文件CodeFile以紧凑格式先是在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
void DecodingFile();//利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中,并输出结果。
private:
HfmNode *root;
HfmNode **node;//指向对象指针节点数组
int size;//对象指针节点数组大小
};
#endif
HuffManCoding::HuffManCoding()
{
setHuffNode();
}
void HuffManCoding::setHuffNode()
{
int i,j;
int n;
//HfmNode **N;
cout << "输入进行编码的字符个数 ";
cin >> n;
size = n;
node = new HfmNode *[n];
for( i = 0; i < n; i++ )
node[i] = new HfmNode;
for( j = 0; j < n; j++ )
{
cout << "输入第" << j + 1 << "字符: " ;
cin >> node[j]->c;
cout << "权值为: ";
cin >> node[j]->data ;
}
root = NULL;
}
//建立哈夫曼树并调用函数进行输出和编码
void HuffManCoding::CreatHuffman()
{
HfmNode *q;
int i,j;
for( i = 0; i < size; i++ )
{
int k1 = -1;//用k1表示森林中具有最小权值的树根结点的下标
int k2;//用k2表示森林中具有次最小权值的树根结点的下标
for( j = 0; j < size; j++ )
{
if( node[j] != NULL && k1 == -1 )
{
k1 = j;
continue;
}
if( node[j] != NULL )
{
k2 = j;
break;
}
}
for( j = k2; j < size; j++ )
{
if( node[j] != NULL )
{
if( node[j]->data < node[k1]->data )
{
k2 = k1;
k1 = j;
}
else if( node[j]->data < node[k2]->data )
k2 = j;
}
}
q = new HfmNode;
q->data = node[k1]->data + node[k2]->data;
q->left = node[k1];
q->right = node[k2];
}
root = q;
cout << "建立的哈夫曼树为" << endl;
PrintHfmTree(q);
CodingNode(q,0);
}
//输出哈夫曼树
void HuffManCoding::PrintHfmTree(HfmNode *r)
{
if( r != NULL )
{
cout << r->c;
if( r->left != NULL || r->right != NULL )
{
cout << "(";
PrintHfmTree( r->left );
if( r->right != NULL )
cout << ", ";
PrintHfmTree( r->right );
cout << ") ";
}
}
}
//对哈夫曼树的结点进行编码
void HuffManCoding::CodingNode(HfmNode *r,int len)
{
static int a[10];
static int i = 0;
if( r!= NULL )
{
if( r->left == NULL && r->right == NULL )
node[i++] = r;
int j;
for( j = 0; j < len; j++ )
node[i]->d[j] = a[j];
node[i]->d[len] = '\0';
}
else{
a[len] = 0;
CodingNode( r->left,len+1);
a[len] = 1;
CodingNode( r->right,len+1);
}
}
/*void HuffManCoding::CreatFileToBeTran()//输入正文并保存在文件ToBeTran以进行编码
{
cout << "输入要进行编码的文件" << endl;
char ch;
ofstream InputFile("ToBeTran.dat");
if(!InputFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
while(( ch=cin.get())!= EOF )
{
InputFile.put(ch);
}
InputFile.close();
}
*/
//对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中,
//并输出结果,将文件CodeFile以紧凑格式先是在终端上,每行50个代码。
//同时将此字符形式的编码文件写入文件CodePrint中。
void HuffManCoding::CodeFileToBeTran()
{
ifstream OpenFile("ToBeTran.dat");
if(!OpenFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
ofstream InputFile("CodeFile.dat");
if(!InputFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
char ch;
while( ( ch =OpenFile.get())!= EOF)
{
for( int i = 0; i < size; i++ )
if( node[i]->c == ch )
InputFile << node[i]->d;
}
OpenFile.close();
InputFile.close();
ifstream openFile("CodeFile.dat");
if(!openFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
ofstream inputFile("CodePrint.dat");
if(!inputFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
int i = 0;
while(( ch = openFile.get() != EOF )
{
cout<<ch;
i++;
if( i == 10 )
cout << endl;
inputFile.put(ch);
}
openFile.close();
inputFile.close();
}
//利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中,并输出结果。
void HuffManCoding::DecodingFile()
{
ifstream OpenFile("CodeFile.dat");
if(!OpenFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
ofstream InputFile("TextFile.dat");
if(!InputFile)
{
cout<< "文件流打开错误" << endl;
exit(1);
}
char ch;
char c[10];
int i = 0;
while((ch = OpenFile.get()) != EOF )
{
c[i++] = ch;
c[i] = '\0';
for( int j = 0; j < size; j++ )
if( strcmp(node[j]->d,c) )
{
cout << node[j]->c << setw(2) << endl;
InputFile << node[j]->c;
i = 0;
}
}
OpenFile.close();
InputFile.close();
}
int main()
{
HuffManCoding h;
h.CreatHuffman();
// h.CreatFileToBeTran();//输入要编码的文件
cout << "编码后的文件代码为" << endl;
h.CodeFileToBeTran();//编码并输出
cout << "译码后的文件为" << endl;
h.DecodingFile();//译码并输出
return 0;
}