用c++写哈夫曼树及编码的函数代码构造哈夫曼树计算WPL。函数接口定义：void CreateHTree;void CreateHCode;

#include #include using namespace std;

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;