C++實現(xiàn)哈夫曼樹編碼解碼
本文實例為大家分享了C++實現(xiàn)哈夫曼樹的編碼解碼,供大家參考,具體內(nèi)容如下
代碼:
#pragma once #include<iostream> #include<stack> using namespace std; #define m 20 stack<int> s; /*哈夫曼樹結(jié)點類HuffmanNode聲明*/ template<class T> class HuffmanNode { private: HuffmanNode<T> * left; HuffmanNode<T> * right; T data; int weight; public: HuffmanNode(){} HuffmanNode(const T& item, HuffmanNode<T> * l, HuffmanNode<T> * r):data(item),left(l),right(r){} HuffmanNode<T> * getLeft() { return left; } void setLeft(HuffmanNode<T> * left) { this->left = left; } HuffmanNode<T> * getRight() { return right; } void setRight(HuffmanNode<T> * right) { this->right=right; } T& getData() { return data; } void setData(const T& item) { data = item; } int getWeight() { return weight; } void setWeight(int weight) { this->weight = weight; } }; /*哈夫曼樹類HuffmanTree聲明*/ template<class T> class HuffmanTree { private: HuffmanNode<T> * root; T data[m]; int weight[m]; int count; public: HuffmanTree(HuffmanNode<T> * t=NULL):root(t){} void CreateHuffmanTree();//創(chuàng)建哈夫曼樹 HuffmanNode<T> * getRoot() { return root; } void setRoot(HuffmanNode<T> * t) { root = t; } void inputNodes();//輸入各個結(jié)點的data和weight值 HuffmanNode<T> * deCode(HuffmanNode<T>*t,T item); void showCode(); }; template<class T> inline void HuffmanTree<T>::CreateHuffmanTree() { inputNodes(); HuffmanNode<T> ** H = new HuffmanNode<T>*[count]; HuffmanNode<T> * p1 = NULL, *p2 = NULL, * p,* t; for (int i = 0; i < count; i++) { H[i] = new HuffmanNode<T>(); H[i]->setData(data[i]); H[i]->setWeight(weight[i]); H[i]->setLeft(NULL); H[i]->setRight(NULL); } for (int i = 0; i < count - 1; i++) { p = new HuffmanNode<T>(); p1 = H[i]; p2 = H[i + 1]; p->setLeft(p1); p->setRight(p2); p->setWeight(p1->getWeight() + p2->getWeight()); //將新的結(jié)點插入結(jié)點數(shù)組中的合適位置,并將被合并的兩個結(jié)點刪除 t = p; int j = i + 2; while ( j < count &&H[j]->getWeight() < t->getWeight()) { H[j - 1] = H[j]; j++; } H[j - 1] = t; } root = H[count - 1]; } template<class T> inline void HuffmanTree<T>::inputNodes() { int i = 0; for (int j = 0; j < m; j++) { data[j] = NULL; weight[j] = 0; } while (cin >> data[i] >> weight[i]) { i++; } count = i; } template<class T> inline HuffmanNode<T>* HuffmanTree<T>::deCode( HuffmanNode<T> * t,T item) { HuffmanNode<T> * p, * q; if(t==NULL) return NULL; if (t->getData() == item) return t; if ((p = deCode(t->getLeft(), item))!=NULL) { s.push(0); return p; } else if((q = deCode(t->getRight(), item))!=NULL){ s.push(1); return q ; } } template<class T> inline void HuffmanTree<T>::showCode() { cout << root->getWeight() << endl; cout << (root->getLeft())->getRight()->getData() << endl; for (int i = 0; i < count; i++) { cout << data[i] << "——"; deCode(root, data[i]); while (!s.empty()) { cout << s.top(); s.pop(); } cout << endl; } }
測試程序:
#include<iostream> #include"HuffmanTree.h" using namespace std; int main() { HuffmanTree<char> * tree = new HuffmanTree<char>(); tree->CreateHuffmanTree(); tree->showCode(); system("pause"); return 0; }
測試數(shù)據(jù):
n 1
s 3
t 4
a 10
i 12
p 13
e 15
Ctrl+Z 回車結(jié)束輸入
輸入時權(quán)值由小到大排序…也可以在程序里加一個排序
結(jié)果:
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C++報錯 XX does not name a type;
這篇文章主要給大家介紹了C++報錯 XX does not name a type;field `XX’ has incomplete type解決方案,文中通過代碼示例講解的非常詳細(xì),需要的朋友可以參考下2023-08-08C++面試八股文之如何實現(xiàn)strncpy函數(shù)
strncpy函數(shù),主要用做字符串復(fù)制,將于字符從一個位置復(fù)制到另一個位置,那么如何實現(xiàn)一個strncpy函數(shù),下面小編就來和大家簡單講講吧2023-07-07centos 7 vscode cmake 編譯c++工程的教程詳解
這篇文章給大家介紹了centos 7 使用vscode+cmake配置簡單c++項目的方法,本文通過圖文并茂的形式給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友參考下吧2020-05-05C語言輸出旋轉(zhuǎn)后數(shù)組中的最小數(shù)元素的算法原理與實例
這篇文章主要介紹了C語言輸出旋轉(zhuǎn)后數(shù)組中的最小數(shù)元素的算法原理與實例,數(shù)組旋轉(zhuǎn)就是把開頭的幾個指定的元素放到數(shù)組的末尾,需要的朋友可以參考下2016-03-03