huffman.cpp

该源码实现了从文件中读取字符串

/***************************************************/
/*    项目名称:霍夫曼编码算法     */
                                  
/***************************************************/
#include <iostream.h>
#include <vector>
#include <string>
#include <stdlib.h>

using namespace std;


//存储霍夫曼树节点的数据结构
typedef struct treenode
{
    char data;                    //存储要编码的字符
    int weight;                   //存储要编码的字符的权重
    struct treenode* parent;    //父节点
    struct treenode* lchild;    //左子树
    struct treenode* rchild;    //右子树
}TreeNode;

//存储霍夫曼码表单元的数据结构
typedef struct nodecode
{
	char node;     //存储要编码的字符
	string huffmancode;//存储相应字符的霍夫曼码
}Nodecode;

//定义全局变量
 static int N;  //记录文件中出现的字符总数
 static nodecode s[30];//计算出的霍夫曼码表
 static int index=0; 
/*******************************************************************/
/*函数功能:获得字符cc在文件中出现的次重,以此作为权重
/******************************************************************/
int GetCount(FILE* fp,char cc)
{
    int i=1;
    while(!feof(fp))
    {
        if(cc==fgetc(fp))
            i++;
    }
    rewind(fp);
    return i;
}
/******************************************************************************/
//函数功能:判断vector中是否已存在指定字符为cc的treenode
/******************************************************************************/
int IsExit(vector<TreeNode*> vec,char cc)
{
    for(int i=0;i<vec.size();i++)
    {
        if(cc==vec[i]->data)
            return 1;
    }
    return 0;
}
/******************************************************************************/
//函数功能:从vector中选择权重最小的两个节点lnode,
//         rnode,并将其从vector中移除
/******************************************************************************/
vector<TreeNode*> Select(vector<TreeNode*> vec,TreeNode** lnode,TreeNode** rnode)
{
    int temp=vec[0]->weight;
    vector<TreeNode*>::iterator iter=vec.begin();
    vector<TreeNode*>::iterator it=vec.begin();
    if(vec.size()==1)
        return vec;
    while(iter!=vec.end())
    {
        if(temp>=iter[0]->weight)
        {
            *lnode=iter[0];
            it=iter;
            temp=iter[0]->weight;
        }
        iter++;
    }
    vec.erase(it);//将取出的第一个节点从vector中删掉
    temp=vec[0]->weight;
    it=iter=vec.begin();
    while(iter!=vec.end())
    {
        if(temp>=iter[0]->weight)
        {
            *rnode=iter[0];
            it=iter;
            temp=iter[0]->weight;
        }
        iter++;
    }

    vec.erase(it);//将取出的第二个节点从vector中删掉

    return vec;
}
/******************************************************************************/
//函数功能:判断vector中是否只含有一个父节点为NULL的节点
//         则将此节点作为霍夫曼树的根节点返回
/******************************************************************************/
TreeNode* Top(vector<TreeNode*> vec)
{
    int flag=0;
    TreeNode* node;
    for(int i=0;i<vec.size();i++)
    {
        if(vec[i]->parent==NULL)
        {
            flag++;
            node=vec[i];
        }
    }
    if(flag>1)
        return NULL;
    return node;
}
/******************************************************************************/
//函数功能：输出文件的霍夫曼编码结果
/******************************************************************************/
string output(FILE *fp)
{
	char cc;
	int i,j;
	string ss;
	ss="";
	cout<<"the encode result is :";
	while(!feof(fp))
	{
		cc=fgetc(fp);
	
		if(cc==EOF)
			break;
	
		for(i=0;i<N;i++)
		{
			if(cc==s[i].node)
			{   
				for(j=0;j<s[i].huffmancode.size();j++)
					cout<<s[i].huffmancode[j];
				ss=ss+s[i].huffmancode;
			
			}
			
		}
	}
	cout<<endl;
	return ss;
}
/******************************************************************************/
//函数功能:对霍夫曼编码后数据解码，恢复源文件
/******************************************************************************/
void decode(string encode)
{
	int i=0;
	string ss;
	ss="";
	cout<<"the decode result is :";
	while(i<encode.size())
	{
	
		ss=ss+encode[i];
		for(int j=0;j<N;j++)
		{
			if(ss==s[j].huffmancode)
			{
				cout<<s[j].node;
				ss="";
				continue;
			}
		}
		i=i+1;

	}

}
/******************************************************************************/
//函数功能:初始化vector,将文件中的字符及其权重
//                  不重复的写入treenode,并将其压入vector
/******************************************************************************/
vector<TreeNode*> InitList(FILE *fp)
{
    
    int i=0,k=0,flag=0,len=0;
    char cc;
    TreeNode* node;
    vector<TreeNode*> vec;

    while(!feof(fp))
    {
	
        cc=fgetc(fp);
		if (cc==EOF)
			break;
        //若数据重复则跳过此次循环
        if(IsExit(vec,cc))
        {
            continue;
        }
		else
		{
        //将本次循环取出的字符作为TreeNode的data,并计算其权重,将TreeNode
        //的左子树和右字树以及父节点初始化为NULL,其压入vector
        node=(TreeNode*)malloc(sizeof(TreeNode));
        node->data=cc;
        node->weight=GetCount(fp,node->data);
		cout<<"the data is : "<<node->data;
		cout<<" the frequency is : "<<node->weight<<endl;
        node->lchild=node->rchild=node->parent=NULL;
        vec.push_back(node);
  
		}
		
	}
   rewind(fp);//将文件指针重定向到文件头

    return vec;

}
/******************************************************************************/
//函数功能:构造霍夫曼树
/******************************************************************************/
TreeNode* CreateTree(vector<TreeNode*> vec)
{
    TreeNode* root;        //霍夫曼树的根节点
    TreeNode* lchild;    //霍夫曼树的左子树
    TreeNode* rchild;    //霍夫曼树的右子树
    TreeNode* tree;
    tree=(TreeNode*)malloc(sizeof(TreeNode));
    int i=0;
    while(1)
    {
        lchild=rchild=(TreeNode*)malloc(sizeof(TreeNode));
        //从vector中选择权重最小的两个节点
        vec=Select(vec,&lchild,&rchild);
        //新建一个TreeNode节点
        TreeNode* node=(TreeNode*)malloc(sizeof(TreeNode));
        //将取出的节点作为TreeNode节点的的左子树和右子树
        node->parent=NULL;
        node->lchild=lchild;
        node->rchild=rchild;
        //新节点的权重为其左子树和右子树的权重之和
        node->weight=lchild->weight+rchild->weight;
        lchild->parent=rchild->parent=node;    
        //将新建的节点压入vector
        vec.push_back(node);

        
        if((root=Top(vec))!=NULL)
            break;
    }
    return root;

}
/******************************************************************************/
//函数功能:递归遍历某一支树,对某一字符进行编码
/******************************************************************************/
string Trace(TreeNode* Node,string& cc)
{
    if(Node->parent)
    {
        if(Node->parent->lchild==Node)
        {
            cc="1"+cc;
		//	strcpy("1",cc);
        }
        if(Node->parent->rchild==Node)
        {
		//	strcpy("0",cc);
            cc="0"+cc;
        }
        cc=Trace(Node->parent,cc);
    }
    return cc;
}
/******************************************************************************/
//函数功能:对霍夫曼树的节点进行访问
/******************************************************************************/
void Visit(TreeNode* Node)
{
   string cc;
   char ss;
   int i;
   int len;
	cc="";
	Trace(Node,cc);	
    if(Node->lchild==NULL&&Node->rchild==NULL)
    {
	   s[index].node=Node->data;
	   s[index].huffmancode=s[index].huffmancode + cc;	   
	  cout<<"the character is: "<<Node->data;
		len=cc.size();
		cout<<"; the encoding is "; 
		for(i=0;i<len;i++)
		{
			ss=cc[i];
			cout<<ss;
		}
		index=index+1;
		cout<<endl;
    }

	
}
/******************************************************************************/
//函数功能:对霍夫曼树进行中序遍历
/******************************************************************************/
/*void Inorder(TreeNode* top, void (*Visit)(TreeNode* Node))
{
    if(top)
    {
        Inorder(top->lchild,Visit);
        Visit(top);
        Inorder(top->rchild,Visit);
    }
}*/
void Inorder(TreeNode* top)
{
    if(top)
    {
        Inorder(top->lchild);
        Visit(top);
        Inorder(top->rchild);
    }
}
/******************************************************************************/
//主函数
/******************************************************************************/

int main(int argc,char* argv[])
{
   
    vector<TreeNode*> vec;	
	string encode;
    FILE* fp;
    TreeNode* top=(TreeNode*)malloc(sizeof(TreeNode));

    fp=fopen("D:\\test.txt","r");
	if(fp==NULL) 
	{ 
		printf("\nerror on open test.dat!");
		exit(1);
	} 
    vec=InitList(fp);
    N=vec.size();//确定文件中出现的字符数	

    vector<TreeNode*>::iterator iter=vec.begin();
    top=CreateTree(vec);
    
    Inorder(top); 
	encode=output(fp);//霍夫曼编码输出结果

    decode(encode);//对霍夫曼码解码后源文件输出
	
    
    return 0;
}