用c++写哈夫曼树及编码的函数代码构造哈夫曼树计算WPL。函数接口定义:void CreateHTree;void CreateHCode;
![用c++写哈夫曼树及编码的函数代码构造哈夫曼树计算WPL。函数接口定义:void CreateHTree;void CreateHCode; 用c++写哈夫曼树及编码的函数代码构造哈夫曼树计算WPL。函数接口定义:void CreateHTree;void CreateHCode;](https://img.cveoy.top/0/AC0838D14963E8F1377A0CF903B31715.webp)
#include
const int MAXN = 100; // 最大字符集大小
struct HuffmanNode { char ch; // 字符 int weight; // 权值 int parent, lchild, rchild; // 父亲、左孩子、右孩子 string code; // 编码 };
HuffmanNode htree[MAXN]; // 哈夫曼树 int n; // 字符集大小
// 建立哈夫曼树 void CreateHTree() { priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq; // 小根堆 for (int i = 0; i < n; i++) { pq.push(make_pair(htree[i].weight, i)); } int m = n - 1; // 哈夫曼树的节点数 for (int i = 0; i < m; i++) { int x = pq.top().second; pq.pop(); int y = pq.top().second; pq.pop(); htree[x].parent = htree[y].parent = n + i; htree[n + i].lchild = x; htree[n + i].rchild = y; htree[n + i].weight = htree[x].weight + htree[y].weight; pq.push(make_pair(htree[n + i].weight, n + i)); } }
// 编码 void CreateHCode() { for (int i = 0; i < n; i++) { int p = htree[i].parent; while (p != -1) { if (htree[p].lchild == i) { htree[i].code = '0' + htree[i].code; } else { htree[i].code = '1' + htree[i].code; } i = p; p = htree[i].parent; } } }
int main() { cout << "请输入字符集大小:"; cin >> n; cout << "请输入每个字符的权值:" << endl; for (int i = 0; i < n; i++) { cin >> htree[i].ch >> htree[i].weight; htree[i].parent = htree[i].lchild = htree[i].rchild = -1; } CreateHTree(); CreateHCode(); int wpl = 0; // 带权路径长度 for (int i = 0; i < n; i++) { cout << htree[i].ch << " 的编码为:" << htree[i].code << endl; wpl += htree[i].weight * htree[i].code.length(); } cout << "WPL = " << wpl << endl; return 0;
原文地址: https://gggwd.com/t/topic/ftrd 著作权归作者所有。请勿转载和采集!