- #ifndef HFTREE #define HFTREE
#include
using namespace std;
template
class hfTree {
private:
struct Node
{
Type data;
int weight;
int parent, left, right;
};
Node * elem;
int length;
public:
struct hfCode {
Type data;
string code;
};
hfTree(const Type *x, const int * w, int size);
void getCode(hfCode result[]);
~hfTree() { delete [] elem; }
};
template
hfTree::hfTree(const Type * v, const int * w, int size)
{
const int max = 32767;
int min1, min2;//最小树，次最小树的权值
int x, y;//最小树，次最小树的下标
length = 2 * size;
elem = new Node[length];
//将数表初始化
for (int i = size; i < length; ++i)
{
elem[i].weight = w[i - size];
elem[i].data = v[i - size];
elem[i].parent = elem[i].left = elem[i].right = 0;
}
//归并森林中的树
for (int i = size - 1; i > 0; --i)
{
min1 = min2 = max; x = y = 0;
for (int j = i + 1; j<length; ++j)
if (elem[j].parent == 0)
if (elem[j].weight<min1)
{
min2 = min1; min1 = elem[j].weight; x = y; y = j;
}
else if (elem[j].weight<min2)
{
min2 = elem[j].weight; x = j;
}//第52-61:找出待归并的两棵树
elem[i].weight = min1 + min2;
elem[i].left = x; elem[i].right = y; elem[i].parent = 0;
elem[x].parent = i; elem[y].parent = i;
}
}
template
void hfTree::getCode(hfCode result[])
{
int size = length / 2;
int p, s;//p是s的父节点
for (int i = size; i<length; ++i)
{
result[i - size].data = elem[i].data;
result[i - size].code = " ";
p = elem[i].parent; s = i;
while (p) {
if (elem[p].left == s)
result[i - size].code = "0" + result[i - size].code;
else result[i - size].code = "1" + result[i - size].code;
s = p; p = elem[p].parent;
}
}
}
#include"hfTree.h"
#include
#include
using namespace std;
/*
输入一篇英文文章，统计每个字符出现的次数，
并以此构造哈夫曼树和输出每个字符的哈夫曼编码，
最后输出这篇文章的编码。
*/
int main()
{
struct Wen
{
char abc;
int weight;
}; Wen *elems;
//结点指针保存文章的字符和权重
cout << "请输入一段英文，按回车键结束。" << endl;
string str;
getline(cin, str);
int str_lenth = str.length();
elems=new Wen [str_lenth];
int _length = 0;
for (int j = 0; j < str_lenth; j++)
for (int i = 0; i <= j; i++)
{
if (elems[i].abc== str[j])
{
elems[i].weight++; break;
}
else if(elems[i].abc==0)
elems[i].abc = str[j];
elems[i].weight = 1;
_length++;
}//两次for循环统计文章相同的字符和权重
char *xx = new char[_length];
int *ww = new int[_length];
for (int i = 0; i < _length; i++) {
xx[i] = elems[i].abc;
ww[i] = elems[i].weight;
}//将文章出现的字符和权重保存在两个数组中
hfTree<char>tree(xx, ww, _length);
hfTree<char>::hfCode result [200];
tree.getCode(result);
for (int i = 0; i < _length; ++i)
cout << result[i].data << " " << result[i].code <<endl;
system("pause");
return 0;
}
VS2015和dev都可以编译，但是vs2015再输入文章后程序就无法运行了
dev则是输出不正确。
