【实现】Huffman树及Huffman编码的实现
根据《数据结构》（C语言版，严蔚敏、吴伟民编著）算法6.12，实现的Huffman树创建及Huffman编码函数HuffmanCoding。源文件如下：“
程序代码：
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
#include <iomanip>
using std::setw;
// ------------赫夫曼树和赫夫曼编码的存储表示-------------
typedef struct
{
unsigned int weight;
unsigned int parent, lchild, rchild;
} HTNode, * HuffmanTree; // 动态分配数组存储赫夫曼树
typedef char * HuffmanCodeLine;
typedef char * * HuffmanCode; // 动态分配数组存储赫夫曼编码表
void Select(HuffmanTree &HT, int count, int &min1, int &min2);
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int * w, int n) // 用"引用"!!!??? SLL, 2011-11-06
{ // !!!指针本身的在存储空间中的位置是一直没变啊. 2011-11-06
// w存放n个字符的权值(均>0), 构造赫夫曼树HT,
// 并求出n个字符的赫夫曼编码HC.
if (n <= 1)
{
return;
}
int m = 2*n-1; // n个叶子结点的赫夫曼树共有2*n-1个结点.
HT = new HTNode[m+1]; // 0号单元未用.
int i; // 循环变量
HTNode * p;
for (p=HT+1, i=1; i<=n; ++i, ++p, ++w) // 0号单元未用.
{
(*p).weight = *w;
(*p).parent = 0;
(*p).lchild = 0;
(*p).rchild = 0;
}
for (; i<=m; ++i, ++p)
{
(*p).weight = 0;
(*p).parent = 0;
(*p).lchild = 0;
(*p).rchild = 0;
}
int s1, s2;
for (i=n+1; i<=m; ++i)
{
// 建赫夫曼树:
// 在HT[1...i-1]选择parent为0且weight最小的两个结点,
// 其序号分别为s1和s2.
Select(HT, i-1, 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;
}
#if 1
// ---------从叶子到根逆向求每个字符的赫夫曼编码---------
HC = new HuffmanCodeLine[n+1]; // 分配n个字符编码的头指针向量
// 也是0号单元未用!!!
char * cd = new char[n]; // 分配求编码的工作空间
cd[n-1] = '\0'; // 编码结束码
int start;
for (i=1; i<=n; ++i)
{
start = n-1; // 编码结束符位置
int l;
unsigned int f;
for (l=i, f=HT[i].parent; f!=0; l=f, f=HT[f].parent)
{
if (HT[f].lchild == l)
{
cd[--start] = '0';
}
else
{
cd[--start] = '1';
}
}
HC[i] = new char[n - start];
strcpy(HC[i], &cd[start]);
}
delete [] cd; // 释放工作空间
#else
// ---------无栈非递归遍历赫夫曼树, 求赫夫曼编码---------
// ...
#endif
}
void Select(HuffmanTree &HT, int count, int &min1, int &min2)
{
int i = 0;
int c = 0;
int minWeight1 = 0xffff;
int minWeight2 = 0xffff;
int * order = new int[count];
for (i=1; i<=count; ++i)
{
if (HT[i].parent == 0) // 统计parent为0的结点的个数及下标
{
order[c++] = i;
}
}
for (i=0; i<c; ++i)
{ // 在该循环之前, minWeight1==minWeight2;
// 在每次循环中, 始终将较小值存入minWeight1, 较大值存入minWeight2;
// 执行完毕后, minWeight1中是最小值, minWeight2中是次小值.
int d = HT[order[i]].weight;
if (d < minWeight1)
{
minWeight2 = minWeight1;
min2 = min1;
minWeight1 = d;
min1 = order[i];
}
else if (d < minWeight2)
{
minWeight2 = d;
min2 = order[i];
}
}
delete [] order;
}
int main()
{
int i = 0;
int cntLeaf = 0;
int cntNode = 0;
cout << "请输入叶子个数: ";
cin >> cntLeaf;
while (cntLeaf == 0)
{
cout << "叶子个数不能为0, 请重新输入: ";
cin >> cntLeaf;
}
cntNode = cntLeaf*2-1;
char * pLetter = new char[cntLeaf];
int * pWeight = new int[cntLeaf];
for (i=0; i<cntLeaf; ++i)
{
cout << "请分别输入叶子结点的字符值和权值: ";
cin >> pLetter[i] >> pWeight[i];
}
HuffmanTree HT = NULL;
HuffmanCode HC = NULL;
HuffmanCoding(HT, HC, pWeight, cntLeaf);
cout << "Huffman树结构如下:\n";
cout << setw(7) << "No."
<< setw(6+1) << "weight"
<< setw(6+1) << "parent"
<< setw(6+1) << "lchild"
<< setw(6+1) << "rchild"
<< '\n';
for (i=0; i<cntNode; ++i)
{
cout << setw(6+1) << i+1
<< setw(6+1) << HT[i+1].weight
<< setw(6+1) << HT[i+1].parent
<< setw(6+1) << HT[i+1].lchild
<< setw(6+1) << HT[i+1].rchild
<< '\n';
}
cout << "\n各叶子结点的Huffman编码如下:\n";
for (i=0; i<cntLeaf; ++i)
{
cout << pLetter[i] << ' ' << HC[i+1] << '\n';
}
return 0;
}
”。
希望各位大虾们对上述代码进行改善
