程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 算法導論之

算法導論之

編輯:關於C++

學習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;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved