歡迎來到Linux教程網
設為首頁 加入收藏
Linux教程網
Linux教程網
Linux教程網
Linux教程網 >> Linux編程 >> Linux編程 >> C++使用優先隊列來構建huffman樹[哈夫曼樹]

C++使用優先隊列來構建huffman樹[哈夫曼樹]

日期：2017/3/1 10:35:59   编辑：Linux編程
  1. #include <iostream>
  2. #include <queue>
  3. #include <string.h>
  4. #include <vector>
  5. #include <algorithm>
  6. using namespace std;
  8. char Table[26];
  10. struct Node
  11. {
  12. int freq;
  13. char val;
  14. Node * left;
  15. Node * right;
  16. Node():left(NULL), right(NULL) , freq(0) , val('0'){}
  17. };
  19. class Cmp
  20. {
  21. public:
  22. bool operator() (const Node * a, const Node * b) const
  23. {
  24. return a->freq > b->freq; // 從小到大 ，freq 小的 優先級別高
  25. }
  26. };
  28. priority_queue<Node* , vector<Node*> , Cmp> myQueue;
  30. void BuildTree()
  31. {
  32. for (int i = 0; i < 26; ++ i)
  33. {
  34. if (Table[i] > 0)
  35. {
  36. Node * node = new Node();
  37. node->freq = Table[i];
  38. node->val =(char) (i + 'A');
  39. myQueue.push(node);
  40. }
  41. }
  43. while (myQueue.size() > 1)
  44. {
  45. Node * f = myQueue.top();
  46. myQueue.pop();
  47. Node * s = myQueue.top();
  48. myQueue.pop();
  49. Node * tmp = new Node();
  50. tmp->freq = f->freq + s->freq;
  51. tmp->left = f;
  52. tmp->right = s;
  53. myQueue.push(tmp);
  54. }
  55. //cout << myQueue.top()->freq<<endl;
  56. }
  58. struct PrintNode
  59. {
  60. int freq;
  61. char val;
  62. string code;
  63. };
  65. vector<PrintNode> vpn;
  66. bool cmp(const PrintNode & a , const PrintNode & b)
  67. {
  68. return a.freq > b.freq;
  69. }
  71. void Print( Node * node , string res)
  72. {
  73. if (node == NULL)
  74. {
  75. return;
  76. }
  77. if (node->val != '0')
  78. {
  79. PrintNode pn;
  80. pn.val = node->val;
  81. pn.freq = node->freq;
  82. pn.code = res;
  83. vpn.push_back(pn);
  84. //cout <<node->val <<" | " << node->freq <<" | "<< res <<endl;
  85. return ;
  86. }
  87. Print(node->left , res + "0");
  88. Print(node->right, res + "1");
  89. delete node->left;
  90. delete node->right;
  91. }
  93. int main()
  94. {
  95. int N;
  96. memset(Table , 0 , sizeof(Table));
  97. cin >> N;
  98. for (int i = 0; i < N; ++i)
  99. {
  100. char ch ;
  101. cin >> ch;
  102. if (ch >= 'A' && ch <= 'Z')
  103. {
  104. ++Table[ch - 'A'];
  105. }
  106. }
  107. BuildTree();
  108. Node * root = myQueue.top();
  109. myQueue.pop();
  110. Print(root , "");
  112. sort(vpn.begin() , vpn.end() , cmp);
  114. for (int i = 0; i < vpn.size(); ++i)
  115. {
  116. cout <<vpn[i].val << " "<<vpn[i].freq <<" " << vpn[i].code<<endl;
  117. }
  118. return 0;
  119. }
具體的構成算法不再這裡討論了，

Linux編程

Java Filter的執行順序

OpenGL設置窗口居中顯示方法

HTML5應用——簡易播放器

C++拾遺--模板元編程

Android開發返回拍攝的圖片

u-boot2010.03 移植篇(一)-----建立編譯目標

Android關於Bitmap內存溢出的一點想法

matlab-膚色檢測

Linux教程網

Linux使用vim進行多文件查找和替換的方法

　　vim是Linux系統下常用的文本編輯，通過使用多種shell命令能

Kylin 2.0 服務器版安裝vsftpd-2.0.4

uC/OS-II源碼分析

簡談ubuntu之DIY發行版

Linux網管123---第10章.升級Linux及其他應用軟體-3.保持

Ubuntu 編譯 /usr/bin/ld: cannot find 問題解決

Linux作PPP接入服務器(2)

Linux下MySQL整個數據庫的備份與還原

在線設置你的 VMware Player 虛擬機

相关文章
Linux編程SHELL編程PERL編程
文章推荐
热点聚焦

Linux HID 驅動開發(2) USB HID Report 描述及usage 概念

jQuery屬性過濾選擇器的使用

Android Handler消息傳遞機制

Makefile入門教程

Java對象序列化

Android Animations之LayoutAnimationController的使用方法

C++容器總結

C++之拷貝構造函數

嵌入式學習之ARM中斷

C鏈表和文件操作實戰--圖書管理系統

Copyright © Linux教程網 All Rights Reserved