哈夫曼编码C++实现（优先队列）（map映射）
哈夫曼编码C++实现（优先队列）（map映射）
哈夫曼树
哈夫曼树是带权路径最短的最优二叉树，即权值越小的结点里根节点越远反之则越近。
借助优先队列，初始时，将所有的结点压入优先队列，权值越小优先级越高，每次取两个优先级最小的结点，将其作为新节点左右孩子节点，再将新节点压入优先队列，再次选取两个权值最小的结点，直到优先队列中只剩下一个结点，此节点作为根节点，哈夫曼树建立完成。
void HuffmanTree::createHuffmanTree(vector<pair<int, string> >& v) {priority_queue<Node*, vector<Node*>, Compare> Q;for (int i = 0; i < v.size(); i++) {Q.push(new Node(v[i].second, v[i].first, NULL, NULL));}Node *left, *right;while (true) {left = Q.top();Q.pop();right = Q.top();Q.pop();if (Q.empty()) {root = new Node("", left->frequency + right->frequency, left, right);break;}Q.push(new Node("", left->frequency + right->frequency, left, right));}
}
哈夫曼编码
规定左子树编码’0’，右子树编码’1’，递归地进行编码，遇到叶子节点则在map建立<编码,值>映射，
void HuffmanTree::huffmanEncode(Node *p) {if (!p) {return;}if (!p->leftChild && !p->rightChild) {string temp(s, codeCount);huffmanCode[temp] = p->data;} else {s[codeCount++] = '0';huffmanEncode(p->leftChild);codeCount--;s[codeCount++] = '1';huffmanEncode(p->rightChild);codeCount--;}
}
哈夫曼解码
根据哈夫曼树的构造，不定长编码，任一编码一定不其他任意编码的前缀码，假定输入编码均为合法，遍历编码序列，对于每个子编码序列，在map中查看编码是否存在，若存在则输出并将子序列清空，继续遍历，直到遍历编码序列结束。
void HuffmanTree::huffmanDecode(string code) {string tmp;for (int i = 0; i < code.length(); i++) {tmp += code[i];if (huffmanCode.find(tmp) != huffmanCode.end()) {cout << huffmanCode[tmp] << " ";tmp.clear();}}
}
实现代码
/*
author : eclipse
email : eclipsecs@qq.com
time : Sat Jun 13 11:50:26 2020
*/
#include<bits/stdc++.h>
using namespace std;struct Node {int frequency;string data;Node* leftChild;Node* rightChild;Node(string dataVal, int frequnceyValue, Node* left, Node* right): data(dataVal), frequency(frequnceyValue), leftChild(left), rightChild(right) {}
};struct Compare {bool operator() (Node* &x, Node* &y) {return x->frequency > y->frequency;}
};class HuffmanTree {
private:static const int MAX_CAPACITY = 1024;map<string, string> huffmanCode;int codeCount;char s[MAX_CAPACITY];Node *root;void createHuffmanTree(vector<pair<int, string> >& v);void huffmanEncode(Node *p);
public:void huffmanDecode(string code);HuffmanTree(vector<pair<int, string> > v);
};HuffmanTree::HuffmanTree(vector<pair<int, string> > v) {codeCount = 0;createHuffmanTree(v);huffmanEncode(root);
}void HuffmanTree::huffmanEncode(Node *p) {if (!p) {return;}if (!p->leftChild && !p->rightChild) {string temp(s, codeCount);huffmanCode[temp] = p->data;} else {s[codeCount++] = '0';huffmanEncode(p->leftChild);codeCount--;s[codeCount++] = '1';huffmanEncode(p->rightChild);codeCount--;}
}void HuffmanTree::huffmanDecode(string code) {string tmp;for (int i = 0; i < code.length(); i++) {tmp += code[i];if (huffmanCode.find(tmp) != huffmanCode.end()) {cout << huffmanCode[tmp] << " ";tmp.clear();}}
}void HuffmanTree::createHuffmanTree(vector<pair<int, string> >& v) {priority_queue<Node*, vector<Node*>, Compare> Q;for (int i = 0; i < v.size(); i++) {Q.push(new Node(v[i].second, v[i].first, NULL, NULL));}Node *left, *right;while (true) {left = Q.top();Q.pop();right = Q.top();Q.pop();if (Q.empty()) {root = new Node("", left->frequency + right->frequency, left, right);break;}Q.push(new Node("", left->frequency + right->frequency, left, right));}
}int main(int argc, char const *argv[])
{freopen("test33.txt", "r", stdin);int value;vector<pair<int, string> > v;while (scanf("%d", &value) && value != -1) {string s;cin >> s;v.push_back(make_pair(value, s));}HuffmanTree *huffmanTree = new HuffmanTree(v);string code;cin >> code;huffmanTree->huffmanDecode(code);return 0;
}输入数据
876 Huffman
616 tree
427 create
583 successfully
929 !
-1
010011011110
输出数据
Huffman tree create successfully !
最后
- 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！
哈夫曼编码C++实现（优先队列）（map映射）
哈夫曼编码C++实现（优先队列）（map映射）
哈夫曼树
哈夫曼树是带权路径最短的最优二叉树，即权值越小的结点里根节点越远反之则越近。
借助优先队列，初始时，将所有的结点压入优先队列，权值越小优先级越高，每次取两个优先级最小的结点，将其作为新节点左右孩子节点，再将新节点压入优先队列，再次选取两个权值最小的结点，直到优先队列中只剩下一个结点，此节点作为根节点，哈夫曼树建立完成。
void HuffmanTree::createHuffmanTree(vector<pair<int, string> >& v) {priority_queue<Node*, vector<Node*>, Compare> Q;for (int i = 0; i < v.size(); i++) {Q.push(new Node(v[i].second, v[i].first, NULL, NULL));}Node *left, *right;while (true) {left = Q.top();Q.pop();right = Q.top();Q.pop();if (Q.empty()) {root = new Node("", left->frequency + right->frequency, left, right);break;}Q.push(new Node("", left->frequency + right->frequency, left, right));}
}
哈夫曼编码
规定左子树编码’0’，右子树编码’1’，递归地进行编码，遇到叶子节点则在map建立<编码,值>映射，
void HuffmanTree::huffmanEncode(Node *p) {if (!p) {return;}if (!p->leftChild && !p->rightChild) {string temp(s, codeCount);huffmanCode[temp] = p->data;} else {s[codeCount++] = '0';huffmanEncode(p->leftChild);codeCount--;s[codeCount++] = '1';huffmanEncode(p->rightChild);codeCount--;}
}
哈夫曼解码
根据哈夫曼树的构造，不定长编码，任一编码一定不其他任意编码的前缀码，假定输入编码均为合法，遍历编码序列，对于每个子编码序列，在map中查看编码是否存在，若存在则输出并将子序列清空，继续遍历，直到遍历编码序列结束。
void HuffmanTree::huffmanDecode(string code) {string tmp;for (int i = 0; i < code.length(); i++) {tmp += code[i];if (huffmanCode.find(tmp) != huffmanCode.end()) {cout << huffmanCode[tmp] << " ";tmp.clear();}}
}
实现代码
/*
author : eclipse
email : eclipsecs@qq.com
time : Sat Jun 13 11:50:26 2020
*/
#include<bits/stdc++.h>
using namespace std;struct Node {int frequency;string data;Node* leftChild;Node* rightChild;Node(string dataVal, int frequnceyValue, Node* left, Node* right): data(dataVal), frequency(frequnceyValue), leftChild(left), rightChild(right) {}
};struct Compare {bool operator() (Node* &x, Node* &y) {return x->frequency > y->frequency;}
};class HuffmanTree {
private:static const int MAX_CAPACITY = 1024;map<string, string> huffmanCode;int codeCount;char s[MAX_CAPACITY];Node *root;void createHuffmanTree(vector<pair<int, string> >& v);void huffmanEncode(Node *p);
public:void huffmanDecode(string code);HuffmanTree(vector<pair<int, string> > v);
};HuffmanTree::HuffmanTree(vector<pair<int, string> > v) {codeCount = 0;createHuffmanTree(v);huffmanEncode(root);
}void HuffmanTree::huffmanEncode(Node *p) {if (!p) {return;}if (!p->leftChild && !p->rightChild) {string temp(s, codeCount);huffmanCode[temp] = p->data;} else {s[codeCount++] = '0';huffmanEncode(p->leftChild);codeCount--;s[codeCount++] = '1';huffmanEncode(p->rightChild);codeCount--;}
}void HuffmanTree::huffmanDecode(string code) {string tmp;for (int i = 0; i < code.length(); i++) {tmp += code[i];if (huffmanCode.find(tmp) != huffmanCode.end()) {cout << huffmanCode[tmp] << " ";tmp.clear();}}
}void HuffmanTree::createHuffmanTree(vector<pair<int, string> >& v) {priority_queue<Node*, vector<Node*>, Compare> Q;for (int i = 0; i < v.size(); i++) {Q.push(new Node(v[i].second, v[i].first, NULL, NULL));}Node *left, *right;while (true) {left = Q.top();Q.pop();right = Q.top();Q.pop();if (Q.empty()) {root = new Node("", left->frequency + right->frequency, left, right);break;}Q.push(new Node("", left->frequency + right->frequency, left, right));}
}int main(int argc, char const *argv[])
{freopen("test33.txt", "r", stdin);int value;vector<pair<int, string> > v;while (scanf("%d", &value) && value != -1) {string s;cin >> s;v.push_back(make_pair(value, s));}HuffmanTree *huffmanTree = new HuffmanTree(v);string code;cin >> code;huffmanTree->huffmanDecode(code);return 0;
}输入数据
876 Huffman
616 tree
427 create
583 successfully
929 !
-1
010011011110
输出数据
Huffman tree create successfully !
最后
- 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！
发布评论