目录
哈夫曼树功能函数
void CreatHuffmanTree(HuffmanTree &HT, int n); //构造哈夫曼树
void PrintT(HuffmanTree HT, int n); //打印哈夫曼树
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n); //构造哈夫曼编码
void PrintC(HuffmanTree HT, HuffmanCode HC, int n); //打印哈夫曼编码
测试样例
样例输入:
8
7 19 2 6 32 3 21 10
样例输出:
打印哈夫曼树
7 11 0 0
19 13 0 0
2 9 0 0
6 10 0 0
32 14 0 0
3 9 0 0
21 13 0 0
10 11 0 0
5 10 3 6
11 12 9 4
17 12 1 8
28 14 10 11
40 15 2 7
60 15 12 5
100 0 13 14打印哈夫曼编码
7:1010
19:00
2:10000
6:1001
32:11
3:10001
21:01
10:1011
上述例子中的哈夫曼树如下图所示
实现代码
#include<bits/stdc++.h>
using namespace std;
typedef struct {
int weight;
int parent, lch, rch;
} HTNode, *HuffmanTree;
typedef char * HuffmanCode[10];
//找权值最小和第二小的结点 ,s1第二小,s2最小
void Select(HuffmanTree HT, int n, int &s1, int &s2) {
int min = 32767 , low = 32767;
for(int i = 1; i <= n; i++) {
if(min > HT[i].weight && !HT[i].parent) {
s1 = s2;
low = min;
s2 = i;
min = HT[i].weight;
}
else if(low > HT[i].weight && !HT[i].parent) {
s1 = i;
low = HT[i].weight;
}
}
}
//构造哈夫曼树
void CreatHuffmanTree(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].lch = 0;
HT[i].rch = 0;
HT[i].parent = 0;
}
for(int i = 1; i <= n; i++) {
cin >> HT[i].weight;
}
for(int i = n + 1; i <= m; i++) {
int s1 = -1, s2 = -1;
Select(HT, i, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].rch = s1;
HT[i].lch = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
//打印哈夫曼树
void PrintT(HuffmanTree HT, int n) {
int m = 2 * n - 1;
for(int i = 1; i <= m; i++) {
cout << HT[i].weight << " " << HT[i].parent << " " << HT[i].lch << " " << HT[i].rch <<endl;
}
}
//构造哈夫曼编码
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) {
char tmp[n];
tmp[n-1] = '\0';
int start, c, f;
for(int i = 1; i <= n; i++) {
start = n - 1;
c = i;
f = HT[i].parent;
while(f){
if(HT[f].lch == c)
tmp[--start] = '0';
else
tmp[--start] = '1';
c = f;
f = HT[f].parent;
}
HC[i] = (char *)malloc((n-start)*sizeof(char));
strcpy(HC[i], &tmp[start]);
}
}
//打印哈夫曼编码
void PrintC(HuffmanTree HT, HuffmanCode HC, int n) {
for(int i = 1; i <= n; i++)
cout << HT[i].weight << ":" << HC[i] << endl;
}
int main() {
int n;
cout << "请输入结点数:" << endl;
cin >> n;
HuffmanTree HT;
CreatHuffmanTree(HT, n);
cout << endl << "打印哈夫曼树" << endl;
PrintT(HT, n);
HuffmanCode HC;
CreatHuffmanCode(HT, HC, n);
cout<< endl << "打印哈夫曼编码" << endl;
PrintC(HT, HC, n);
return 0;
}
版权声明:本文为m0_63330233原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。