算法導論之--------------Huffman編碼

算法導論之--------------Huffman編碼

學習Huffman編碼最大的收獲是學會了STL中優先隊列的使用以及在使用的時候要注意的問題：在使用自定義數據類型的時候，優先隊列要重載自己的比較操作符。

關於Huffman樹怎麼講解請看算法導論講解，原理真的很簡單，不過要寫出完整的代碼難點就在於優先隊列的使用。不廢話了啊，再次強調，想把原理弄清楚，請看算法導論，樹上的講解比網上什麼垃圾講解不知道清晰多少，一看就懂。-----------------終於可以上代碼了。

//在優先級隊列中存入指針類型的節點
#include
#include
#include
using namespace std;

class Comapre;
class Node
{
public:
	friend Comapre;
	int key;
	char ch;
	Node* left;
	Node* right;
public:
	Node(int num, char c) :key(num), ch(c), left(NULL), right(NULL){}
	//
	//bool lessthan(const Node* node) const
	//{
	//	return key>node->key;
	//}
};
class Comapre
{
public:
	//因為優先級隊列中傳遞的指針，所以不能直接在Node類裡重載比較運算符
	//大家去看看STL中優先級隊列使用與heap之間的關系
	bool operator()(Node*node1, Node*node2)
	{
		//bool flag = node1->lessthan(node2);
		//return flag;
		return node1->key < node1->key;
	}
};
//使用優先級隊列存儲元素，優先級隊列能保證隊列最頂端的是按照鍵值key排列的最小的元素
Node* Huffman(priority_queue, Comapre> que)
{
	//重復將最頂端的兩個元素拿出合並之後再放入隊列中
	while (que.size()>1)
	{
		Node *node = new Node(0, 0);
		node->left = que.top();
		que.pop();

		node->right = que.top();
		que.pop();

		node->key = node->left->key + node->right->key;

		que.push(node);
	}

	return que.top();
}
//利用中序遍歷的方法輸出霍夫曼編碼
//思路是每向左指一個節點s添加0，每向右指一個節點添加1，每迭代完一次要退出s最後一個元素
//用到了string的pop_back函數
void Inorder(Node* node, string s)
{
	if (node == NULL)
	{
		return;
	}
	else
	{
		if (node->left != NULL)
		{
			s += '0';
		}
		Inorder(node->left, s);

		if (node->left == NULL&&node->right == NULL)
		{
			cout << node->ch << "'s code is :";
			
			for (auto i : s)
				cout << i;
			cout << endl;
		}

		s.pop_back();

		if (node->right != NULL)
			s += '1';
		Inorder(node->right, s);
	}
}

//將開辟的空間清空，不然會導致內存洩露
void Delete(Node*node)
{
	if (node == NULL)
	{
		return;
	}
	Delete(node->left);
	Delete(node->right);
	delete node;
}

int main()
{
	string s;
	Node*n[6];
	n[0] = new Node(5, 'f');
	n[1] = new Node(9, 'e');
	n[2] = new Node(16, 'd');
	n[3] = new Node(12, 'c');
	n[4] = new Node(13, 'b');
	n[5] = new Node(45, 'a');

	priority_queue, Comapre>qu;
	int i;
	for (i = 0; i<6; i++)
	{
		qu.push(n[i]);
	}

	Node* R = Huffman(qu);
	Inorder(R, s);
	Delete(R);
	return 0;
}