数据结构实验-哈夫曼编码_随笔

数据结构实验-哈夫曼编码
#include

#include

#include

#include

using namespace std;

class Node		//创建Node结点 

{

public:

	//构造函数：

	Node(char c,int count,Node *l=NULL,Node *r=NULL)		//默认子树为空 

	//当我们构建哈夫曼编码才进行设置子节点 

	:m_c(c),m_count(count),left(l),right(r)

	{} 

	

	bool operator <(const Node& node)const

	//重载'<' 在实现优先队列的时候 count 出现次数小的优先 

	{

		return m_count>node.m_count;

	}

	char m_c;			//存放字符 

	int m_count;		//字符出现的次数 依照此来排序 

	Node *left;

	Node *right;

};

void init(int nodenum,priority_queue&q)

{

	//现在开始初始化nodenum个结点

	char ch;

	int frequent;

	for(int i=0;i>ch;

	cin>>frequent;

	Node newnode(ch,frequent);		///创建结点 左右结点初始化为空  

	q.push(newnode);		//放进队列  结点值最小的优先 

	} 

}

void makehuffman(priority_queue&q)

{

	while(q.size()!=1)		//每次需要将两个结点来创建 

	{

		//创建树 每次取出来frequent最小的两个结点

		//然后创建他们的父节点放进queue中去

		Node *left=new Node(q.top());		//拷贝赋值 

		q.pop();  //最小的出队

		Node *right=new Node(q.top());

		q.pop();

		Node father('#',left->m_count+right->m_count,left,right);

		q.push(father); 

	}

}

void huffmancode(Node *root,string &curstr,map& fins)

{

	string now=curstr;		//存储用于回溯

	 if(root->left==NULL||root->right==NULL)		//到达叶子节点了就return掉 

	 return ;

	//左子树

	curstr+="0"; 

	if(root->left->left!=NULL)

	{

		//下一个结点不是叶子结点

		huffmancode(root->left,curstr,fins); 

	}else {

		//左节点是叶子结点

		//放进fins哈希表中

		fins[root->left->m_c]=curstr;

		huffmancode(root->left,curstr,fins); 

	}

	//回溯 

	curstr=now;

	curstr+="1";

	if(root->right->right!=NULL)

	{

		//下一个结点不是叶子结点

		huffmancode(root->right,curstr,fins); 

	}else {

		//左节点是叶子结点

		//放进fins哈希表中

		fins[root->right->m_c]=curstr;

		huffmancode(root->right,curstr,fins); 

	}	

}

void print(map& fins)

{

	//打印哈夫曼编码

	map::iterator it=fins.begin();

	for(it=fins.begin();it!=fins.end();it++)

	{

		cout<first<<":"<second<q;		//直接用优先队列取最小值 

	cout<<"请输入总的需要编码的字符个数 TuT :n";

	int nodenum;

	cin>>nodenum;

	init(nodenum,q);		//传引用过去 

	makehuffman(q);			//创建好树了 

	//下面实现编码

	//需要从根节点回溯搜索构建字符创 遇到叶子结点就退出

	//用map存储

	Node root=q.top();

	string curstr="";

	mapfins;		//创建哈希进行存储

	huffmancode(&root,curstr,fins); 	//传地址进去

	print(fins); 

}
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5658778.html
数据结构实验-哈夫曼编码

发表评论

评论列表（0条）
