歡迎您光臨本站 註冊首頁

C++實現哈夫曼樹的方法

←手機掃碼閱讀     kyec555 @ 2020-05-11 , reply:0

序言
對於哈夫曼編碼,個人的淺薄理解就是在壓縮存儲空間用很大用處。
用一個很簡單例子,存儲一篇英文文章時候,可能A出現的概率較大,Z出現的記錄較小,如果正常存儲,可能A與Z存儲使用的空間一樣。但是用哈夫曼編碼方式,A經常出現,所用編碼長度就短。
構造哈夫曼樹,生成哈夫曼編碼
一、定義節點類型
struct Node { char C; long key; Node *Left, *Right,*parent; Node() { Left = Right = NULL; } };
二、定義樹類型(節點數組)
三要素:不定長數組,元素大小,有效元素個數
struct RootA { Node *NodeA; const int Size; int n; RootA(int Size) :Size(Size) { n = 0; NodeA = new Node[Size]; } ~RootA() { delete[]NodeA; } };
三、創建哈夫曼樹
1.將每一個節點都當成一棵樹,初始化數組大小,並進行賦值
RootA RA(4); //1.在RA.NodeA中存入字母和權值 for (RA.n = 0;RA.n < RA.Size;RA.n++) { cout << "字母:"; cin >> RA.NodeA[RA.n].C; cout << "權值:"; cin >> RA.NodeA[RA.n].key; }
2.將樹按權值大小排序
void Sort(RootA *ra) { for (int i = 0;i < ra->n;i++) { bool ESC = false; for (int j = 0;j < ra->n - i - 1;j++) { if (ra->NodeA[j].key > ra->NodeA[j + 1].key) { Node T;T = ra->NodeA[j];ra->NodeA[j] = ra->NodeA[j + 1];ra->NodeA[j + 1] = T; ESC = true; } } if (!ESC) return; } }
3.(1)遍歷數組,將RA.NodeA[0]和RA.Node[1]合併,其餘向前移動,重新排序
(2)將RA.NodeA[0],RA.NodeA[1]分別放在新合併的RA.NodeA[0]的左右子結點中
while (RA.n > 1) { //1.將RA.NodeA[0]和RA.NodeA[1]合併,將其餘向前移動 Node *NewNode0 = new Node; *NewNode0 = RA.NodeA[0]; Node *NewNode1 = new Node; *NewNode1 = RA.NodeA[1]; RA.NodeA[0].C = ' '; RA.NodeA[0].key = RA.NodeA[0].key + RA.NodeA[1].key; RA.NodeA[0].Left = NewNode0; NewNode0->parent = &RA.NodeA[0]; RA.NodeA[0].Right = NewNode1; NewNode1->parent = &RA.NodeA[0]; for (int i = 1;i < RA.n-1;i++) { RA.NodeA[i] = RA.NodeA[i + 1]; } RA.n = RA.n - 1; //2.排序 Sort(&RA); }
4.輸出哈夫曼編碼
遞歸,找到葉子節點,記錄路徑,左記錄0,右記錄1,直到輸出所有葉子節點
void CrateCode(Node *t,string &s) { //1.遍歷節點,遍歷左節點編碼為0,右節點則為1,遞歸,直到輸出所有葉子節 if (t->Left != NULL && t->Right != NULL) { s.push_back('0'); CrateCode(t->Left, s); s.pop_back(); s.push_back('1');CrateCode(t->Right, s); s.pop_back(); } else { cout << "哈夫曼編碼:"; cout << t->C << ":" << s<<endl; } }


[kyec555 ] C++實現哈夫曼樹的方法已經有238次圍觀

http://coctec.com/docs/c/language/show-post-233805.html