霍夫曼编码的思路就是按照字符出现的概率(或权重)来构造一颗霍夫曼二叉树,然后通过遍历二叉树的节点对霍夫曼树进行编码,道理貌似不是很难.程序也写好了,不过在写好之后才发现这个算法其实还可以改进,在构建霍夫曼树的时候,我将所有出现过的字符全都压入vector,然后对其进行遍历将其中权重最小的两个字符读出然后,将其的父节点设为一空霍夫曼节点,并将此父节点的权重高为两 个字节点的权重之和,然后将此父节点压入vector,这个过程中我已经把两个取出的子节点从vector中删除,最后霍夫曼树构建完成的时候vector中只有一个节点,那就是霍夫曼树的根节点.这样在遍历的时候会影响效率,因为要从叶子节点开始遍历,而取得叶子节点需要先正向遍历一遍霍夫曼树,这样就带来了额外的开销.改进的方法是取出权重最小的两个节点后并不从vector中删除,而是将其父节点由NULL设为其它 节点,这样循环构造霍夫曼条件的结束条件就是vector中的父节点不空的节点只有一个,此节点也即霍夫曼树的根节点.在遍历的时候通过遍历vector就可以得到各叶子节点.这样就算完成了,算法我也懒得改进了,就先这样吧,还是我思维不够敏捷啊.
/***************************************************/
/* 项目名称:霍夫曼编码算法 */
/* 测试平台:Linux,gcc4.1.2 */
/* 程序员:通信工程2005级,李文鹏 */
/***************************************************/
#include <iostream.h>
#include <vector>
#include <string>
using namespace std;
//存储霍夫曼树节点的数据结构
typedef struct treenode
{
char data; //存储要编码的字符
int weight; //存储要编码的字符的权重
struct treenode* parent; //父节点
struct treenode* lchild; //左子树
struct treenode* rchild; //右子树
}TreeNode;
/*******************************************************************/
/*函数功能:获得字符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;
}
/******************************************************************************/
//函数功能:初始化vector,将文件中的字符及其权重
// 不重复的写入treenode,并将其压入vector
/******************************************************************************/
vector<TreeNode*> InitList(FILE *fp)
{
int i=0,flag=0;
char cc;
TreeNode* node;
vector<TreeNode*> vec;
while(!feof(fp))
{
cc=fgetc(fp);
//若数据重复则跳过此次循环
if(IsExit(vec,cc))
{
continue;
}
//将本次循环取出的字符作为TreeNode的data,并计算其权重,将TreeNode
//的左子树和右字树以及父节点初始化为NULL,其压入vector
node=(TreeNode*)malloc(sizeof(TreeNode));
node->data=cc;
node->weight=GetCount(fp,node->data);
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; //霍夫曼树的右子树
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;
}
if(Node->parent->rchild==Node)
{
cc="0"+cc;
}
cc=Trace(Node->parent,cc);
}
return cc;
}
/******************************************************************************/
//函数功能:对霍夫曼树的节点进行访问
/******************************************************************************/
void Visit(TreeNode* Node)
{
string cc("");
if(Node->lchild==NULL&&Node->rchild==NULL)
{
cout<<"the encoding of charactor '"<<Node->data<<"' is "<<Trace(Node,cc)<<endl;
}
}
/******************************************************************************/
//函数功能:对霍夫曼树进行中序遍历
/******************************************************************************/
void Inorder(TreeNode* top,void (*Visit)(TreeNode* Node))
{
if(top)
{
Inorder(top->lchild,Visit);
Visit(top);
Inorder(top->rchild,Visit);
}
}
int main(int argc,char* argv[])
{
if(argc!=3)
{
cout<<"Usage:"<<argv[0]<<" <input file> <output file>"<<endl;
return -1;
}
vector<TreeNode*> vec;
FILE* fp;
TreeNode* top=(TreeNode*)malloc(sizeof(TreeNode));
fp=fopen(argv[1],"r");
vec=InitList(fp);
vector<TreeNode*>::iterator iter=vec.begin();
top=CreateTree(vec);
Inorder(top,Visit);
return 0;
}
| |
