数据结构回顾（八） 基于哈夫曼树的压缩编码实现 （C/C++）
·
构建哈夫曼树的核心思想便是贪心，但在实现细节上却可以有许多种写法。记得当时研究的问题是基于哈夫曼树的文件压缩，在此实现了核心组件，也就是哈夫曼树的构建生成。
以字符编码为例：在此先对字符集进行统计，得到每个字符的权重。而后对每个字符的字符值以及权重进行封装，以此得到相应数据节点（Node）。将这些节点构建成以权重为参考的有序链表，每次从链表上取下两个权重最大的节点进行生成树构建，得到生成树的root节点链接回链表中，当然在将root节点插回到链表后还要保证其有序；相当于维护了一个优先级队列。循环合并节点，最后在队列中只剩下一个节点；便是哈夫曼树的根节点了。自此哈夫曼树的生成完成，关于这个思想如下图所示：（还是近三年前读大二时同学问到的问题，在当天熬夜到12点（12点对于我来说已经是熬夜了）完成的，真的不知道以后还会不会有这样的热血了。一直惦记着这个demo，真的没想到还可以找回来，太值得纪念了。）
哈夫曼树生成后，字符编码生成就是一个简单地节点搜寻过程了，其他的一些细节实现见代码。
#include<iostream>
#include<fstream>
#include<iomanip>
#define Datatype char
using namespace std;
struct Node
{
Node *lchild,*rchild;
Node *parent;
Node *next;
Datatype data;
int weight;
int flag;//记录当前节点为做孩子还是右孩子
};
class Hfm
{
private:
Node **leef_record;//记录各节点 方便哈弗生成编码
string *hfcode;//编码
int nums;//统计字符数(链表结点个数)
int size;//
Node *head;//头结点
public:
Hfm()
{
nums=0;
head=new Node; //头结点预留
head->next =NULL;
}
bool get_data_and_statistic();//从外存得到数据且统计
void show_list();//展示统计结果
bool copy_node();//复制链表到指针数组上
void show_copy_record();//展示复制后的指针数组内容
bool create_hftree();//创建哈弗曼树 辅助
bool c_h_t();//创建哈弗曼树 //在此约定min1 <min2 (min1 min2 节点中权值最小的两个节点)
void swap(Node *p1,Node *p2);//交换两节点值
bool show_hftree_and_get_hfcode();//遍历哈弗曼树得到哈弗编码
};
bool Hfm::show_hftree_and_get_hfcode()//遍历哈弗曼树得到哈弗编码
{
fstream fs;
fs.open ("c:\\hfcode.txt",ios::out );
if(!fs.is_open() )
{
return false;
}
//cout<<"sizez :"<<size<<endl;
Node *p;
cout<<" hafucode(在C盘文件夹下查看 实际哈弗曼编码为以下字符串的逆序以避免前缀码重复问题)"<<endl;
for(int i=0;i<size;i++)
{
p=this->leef_record [i];
cout<<p->data <<" ";
while(p && p->flag !=-1)
{
fs<<p->flag ;
cout<<p->flag ;
p=p->parent ;
}
cout<<endl;
fs<<" ";
}
fs.close ();
}
void Hfm::swap(Node *p1,Node *p2)//交换两节点值
{
Node p;
p=*p1;
*p1=*p2;
*p2=p;
}
bool Hfm::create_hftree()//创建哈弗曼树 辅助
{
if(nums>=2)
{
this->c_h_t ();//在此假设第一个及第二个节点为最小权 在接下函数中进行一个轴参考
}
else
{
cout<<"仅有一类字符!编码为 1 !"<<endl;
return true;
}
}
bool Hfm::c_h_t()//创建哈弗曼树
{
Node *min1, *min2;
//show_list();
nums--;
//cout<<"nums: "<<nums<<endl;
//cout<<"0"<<endl;
Node *p=this->head->next ;
if(nums>=1)
{
int k=0;
while(p) //选取参考轴
{
if(p->flag ==-1)
{
if(k==0)
{
//cout<<"0000"<<endl;
min1=p;
k=1;
}
else
{
//cout<<"11111"<<endl;
min2=p;
break;
}
}
p=p->next ;
}
//cout<<"1"<<endl;
/*if(min1->weight > min2->weight) // 在此约定min1 <min2
{
swap(min1,min2);
}*/
// cout<<"2"<<endl;
if(nums>1)
{
p=this->head->next ;
while(p) // 选取最小且未处理节点 (在以下算法中若无特别说明所谓最小都是以权权值为参考系)
{
if(min1->weight > p->weight && p->flag ==-1)
{
min1=p;
}
p=p->next ;
}
min1->flag =0;//min1作为左孩子
//cout<<"3"<<endl;
p=this->head->next ;
while(p) // 选取次小且未处理节点 (在以下算法中若无特别说明所谓最小都是以权权值为参考系)
{
if(min2->weight >= p->weight && p->flag ==-1)
{
min2=p;
}
p=p->next ;
}
min2->flag =1;//min2作为右孩子
//cout<<"select : min1: "<<min1->data <<" min2: "<<min2->data <<endl;
//cout<<"4"<<endl;
}
}
if(nums>1)
{
//cout<<"5"<<endl;
//错位挂链 + 头插法 +哈弗曼树创建
Node *new_node;
new_node=new Node;
new_node->lchild =min1; //挂上树
new_node->rchild =min2;
new_node->flag=-1;
new_node->weight =min1->weight +min2->weight ; //保存两节点权值之和
//new_node->data ='*';
min1->parent =new_node;//挂上树
min2->parent =new_node;
new_node->next =this->head ->next ;//new_node作为新节点挂入链表中
this->head ->next =new_node;
c_h_t();//递归
}
else
{
//cout<<"6"<<endl;
this->head ->flag =-1;
this->head ->lchild =min1;
this->head->rchild =min2;
//cout<<" min1->flag "<<min1->flag<<endl;
//cout<<" min2->flag "<<min2->flag<<endl;
min1->flag =0;
min2->flag =1;
//cout<<" min1->weight "<<min1->weight<<endl;
//cout<<" min2->weight "<<min2->weight<<endl;
this->head->weight =min1->weight +min2->weight ;
min1->parent =this->head ;//挂上树
min2->parent =this->head ;
head->parent =NULL;
}
return true;
}
void Hfm::show_copy_record()//展示复制后的指针数组内容
{
cout.setf(ios::left );
cout<<" "<<setw(10)<<"data"<<setw(10)<<"weight"<<endl;
for(int i=0;i<this->size ;i++)
{
cout<<" "<<setw(10)<<this->leef_record [i]->data <<setw(10)<<this->leef_record [i]->weight <<endl;
}
}
bool Hfm::copy_node()//复制链表到指针数组上
{
this->leef_record =(Node**)malloc(sizeof(Node*)*this->nums );//开辟空间
int count=0;
Node *p=this->head ->next ;
while(p)//记录节点指针 便于生成哈弗编码
{
this->leef_record [count++]=p;
p=p->next ;
}
return true;
}
void Hfm::show_list()//展示统计结果
{
Node *p;
p=this->head->next ;
cout.setf(ios::left );
cout<<" "<<setw(10)<<"data"<<setw(10)<<"weight"<<setw(10)<<"flag"<<endl;
while(p)
{
cout<<" "<<setw(10)<<p->data <<setw(10)<<p->weight <<setw(10)<<p->flag <<endl;
p=p->next ;
}
cout<<"nums: "<<this->nums <<endl;
}
bool Hfm::get_data_and_statistic ()//从外存得到数据
{
fstream fs;
fs.open ("c:\\hfm.txt",ios::in);
if(!fs.is_open ())
{
return false;
}
else
{
char ch;
Node *p,*p1;
while((ch=fs.get())!=EOF)
{
p1=head->next ;
while(p1)//若在节点中已存在该字符则直接进行自加即可
{
if(p1->data ==ch)
{
p1->weight ++;
break;
}
p1=p1->next ;
}
if(!p1)//若在节点中不存在该字符则创建一个节点且挂链
{
p=new Node;
p->lchild =NULL;
p->rchild =NULL;
p->parent=NULL;
p->flag =-1; //-1表示未处理
p->weight=1;//表该字符当前出现一次
p->data =ch;//赋值
p->next =head->next ;//挂链 头插法
head->next =p;
nums++;//节点数自加
}
}
head->next=p->next;//文件读取错位处理
free(p);
nums--;
this->size =nums;
}
}
int main()
{
Hfm hf;
hf.get_data_and_statistic ();
cout<<"字符统计如下:"<<endl;
hf.show_list ();
hf.copy_node ();
//hf.show_copy_record ();
hf.create_hftree();
hf.show_hftree_and_get_hfcode();
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献7条内容
所有评论(0)