完成数据结构pta实验7-1 哈夫曼树哈夫曼编码
输入一组整型权值，构建哈夫曼树，实现哈夫曼编码，并输出带权路径长度。
输入格式:
第一行输入叶子结点个数，接着依次输入权值。若叶子数为0或1，则输出error
输出格式:
输出哈夫曼编码，输出带权路径长度。
输入样例:
在这里给出一组输入。例如：
8
5 29 7 8 14 23 3 11
输出样例:
在这里给出相应的输出。例如：
5编码为0001
29编码为10
7编码为1110
8编码为1111
14编码为110
23编码为01
3编码为0000
11编码为001
WPL:271
点击查看代码
#include <iostream>
#include <cstring>
using namespace std;
typedef char** HuffmanCode;
typedef struct {
int weight;
int lchild, rchild, parent;
} HTNode, *HuffmanTree;
// 寻找最小值
void findMinimum(HuffmanTree HT, int pos, int &s1, int &s2) {
s1 = -1; s2 = -1;
for (int i = 1; i < pos; ++i) {
if (HT[i].parent == 0) {
if (s1 == -1 || HT[i].weight < HT[s1].weight) {
s2 = s1;
s1 = i;
} else if (s2 == -1 || HT[i].weight < HT[s2].weight) {
s2 = i;
}
}
}
}
// 创建哈夫曼树
void createHuffmanTree(HuffmanTree &HT, int n) {
if (n <= 1) return;
int m = 2 * n - 1;
HT = new HTNode[m + 1];
for (int i = 1; i <= m; ++i) {
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for (int i = 1; i <= n; i++) {
cin >> HT[i].weight;
}
for (int i = n + 1; i <= m; i++) {
int s1, s2;
findMinimum(HT, i, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
// 创建哈夫曼编码
void createHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) {
HC = new char*[n + 1];
char *cd = new char[n + 1];
cd[n] = '\0';
for (int i = 1; i <= n; i++) {
int start = n;
int c = i, f = HT[i].parent;
while (f != 0) {
if (c == HT[f].lchild) cd[--start] = '0';
else cd[--start] = '1';
c = f;
f = HT[c].parent;
}
HC[i] = new char[n - start + 1];
strcpy(HC[i], &cd[start]);
}
delete[] cd;
}
int main() {
HuffmanTree HT;
HuffmanCode HC;
int n, WPL = 0;
cin >> n;
if (n <= 1) {
cout << "error" << endl;
return 0;
}
createHuffmanTree(HT, n);
createHuffmanCode(HT, HC, n);
for (int i = 1; i <= n; i++) {
cout << HT[i].weight << "编码为";
cout << HC[i] << endl;
WPL += strlen(HC[i]) * HT[i].weight;
}
cout << "WPL:" << WPL << endl;
// 释放内存
for (int i = 1; i <= n; i++) {
delete[] HC[i];
}
delete[] HC;
delete[] HT;
return 0;
}