哈夫曼树和哈夫曼编码
2021/5/23 18:29:28
本文主要是介绍哈夫曼树和哈夫曼编码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<bits/stdc++.h> using namespace std; struct node{ int weight; int parent; int left; int right; }; class Huffman{ public: Huffman(int n, const int w[]); void HuffmanCode(int n); void Decode(int m, char *s); ~Huffman(); private: node *root; char **code; int getMin(int n); void select(int n, int &s1, int &s2); }; Huffman:: Huffman(int n, const int w[]) { int m = 2*n-1, i; int s1, s2; if(n <= 1) { cout << "Size error!" << endl; return; } root = new node[m+5]; if(!root) { cout << "Malloc error!" << endl; exit(-1); } // 初始化 node *p = root+1; for (i = 1; i <= n; ++i, ++(p)) { p->weight = w[i]; p->parent = 0; p->right = 0; p->left = 0; } while(i <= m) { p->parent = 0; p++; i++; } for (i = n+1; i <= m; ++i) { select(i-1, s1, s2); root[s1].parent = root[s2].parent = i; root[i].left = s1; root[i].right = s2; root[i].weight = root[s1].weight+root[s2].weight; } } void Huffman:: HuffmanCode(int n) { code = new char*[n+5]; if(!*code) { cout << "Malloc error1" << endl; exit(-1); } char *tmp = new char[n+5]; //char debug[100], dd; if(!tmp) { cout << "Malloc error2"; exit(-1); } tmp[n-1] = 0; int st; for (int i = 1; i <= n; ++i) { st = n-1; for (int j = i, f = root[j].parent; f; j = f, f = root[f].parent) { if(root[f].left == j) tmp[--st] = '0'; else if(root[f].right == j) tmp[--st] = '1'; //dd = tmp[st+1]; // debug //cout << "dd: " << dd << endl; } code[i] = new char[n-st]; //strcpy(debug, tmp+st); //cout << "debug: " << debug << endl; strcpy(code[i], tmp+st); } delete []tmp; for (int i = 1; i <= n; ++i) { cout << "The Huffmancode is " << root[i].weight << " : " << code[i] << endl; } } void Huffman:: Decode(int n, char *s) { int len = strlen(s), pt = 2*n-1; for (int i = 0; i < len; ++i) { if(s[i] == '0') { pt = root[pt].left; if(pt <= n) { cout << root[pt].weight << " "; pt = 2*n-1; } } else if(s[i] == '1') { pt = root[pt].right; if(pt <= n) { cout << root[pt].weight << " "; pt = 2*n-1; } } } cout << endl; } Huffman:: ~Huffman() { delete []root; delete []code; cout << "The Huffmantree has been destroyed." << endl; } int Huffman:: getMin(int n) { int Min = 100; int flag = 0; //用来记录已遍历过的结点 for(int i = 1; i <= n; ++i) { if ((root + i)->weight < Min && (root + i)->parent == 0) { Min = (root + i)->weight; flag = i; } } //给选中的结点置 1, 下次不需要再遍历 (root + flag)->parent = 1; return flag; } void Huffman:: select(int n, int &s1, int &s2) { s1 = getMin(n); s2 = getMin(n); //目的是 s1 的权值要不大于 s2 的权值 if ((root + s1)->weight > (root + s2)->weight) { swap(s1, s2); } } int main() { int n; cin >> n; int w[5]; for (int i = 1; i <= n; ++i) { cin >> w[i]; } Huffman h_test(n, w); h_test.HuffmanCode(n); h_test.Decode(n, "10011"); return 0; }
这篇关于哈夫曼树和哈夫曼编码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南