1、此程序为c++程序
2、以下代码可实现手动输入，即去掉代码中的/*...*/注释符，并同时去掉赋值代码段
3、源代码
#include<iostream>
using namespace std;
typedef struct
{
int weight, parent, lchild, rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct
{
int weight, locate;
}TNode,*Temp;
void CreatHuffmanTree(HuffmanTree &HT, int n);
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n);
int main()
{
HuffmanTree HT;
HuffmanCode HC;
int n = 8;
char p = 'y';
while (p=='y')
{
/*cout << "请输入待编码数据的个数:";
cin >> n;*/
CreatHuffmanTree(HT, n);
CreatHuffmanCode(HT, HC, n);
cout << "再次执行请输入：y，不执行请输入：n" << endl;
cin >> p;
}
system("pause");
return 0;
}
//生成哈夫曼树
void CreatHuffmanTree(HuffmanTree &HT, int n)
{
int i, j, k, s1, s2, num;
HT = new HTNode[2 * n];
for (i = 1; i < 2 * n; i++)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
/*cout << "请输入数据:";
for (i = 1; i <= n; i++)
{
cin >> HT[i].weight;
}*/
HT[1].weight = 5;
HT[2].weight = 29;
HT[3].weight = 7;
HT[4].weight = 8;
HT[5].weight = 14;
HT[6].weight = 23;
HT[7].weight = 3;
HT[8].weight = 11;
for (i = n + 1; i < 2 * n; i++)
{
//从1~i-1中选取两个双亲为0，且权值最小的结点的下标
//统计1~i-1中双亲为0的结点的个数
num = 0;
for (k = 1; k < i; k++)
{
if (HT[k].parent == 0)
{
num++;
}
}
//将双亲为0的结点的权值和下标存储进一个新的结构体数组中
Temp T;
T = new TNode[num];
for (j = 0, k = 1; k < i; k++)
{
if (HT[k].parent == 0)
{
T[j].weight = HT[k].weight;
T[j].locate = k;
j++;
}
}
//选择排序
for (j = 0; j < num - 1; j++)
{
for (k = j + 1; k < num; k++)
{
if (T[j].weight > T[k].weight)
{
TNode temp;
temp = T[k];
T[k] = T[j];
T[j] = temp;
}
}
}
s1 = T[0].locate;
s2 = T[1].locate;//选取下标结束
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;
delete T;
}
cout << "哈夫曼树:" << endl;
for (i = 1; i < 2 * n; i++)
{
cout << HT[i].weight << '\t' << HT[i].parent << '\t' << HT[i].lchild << '\t' << HT[i].rchild << endl;
}
}
//哈夫曼编码
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
int i, c, f,start;
char *cd;
HC = new char*[n + 1];
cd = new char[n];
cd[n - 1] = '\0';
for (i = 1; i <= n; i++)
{
start = n - 1;
c = i;
f = HT[i].parent;
while (f != 0)
{
start--;
if (HT[f].lchild == c)
{
cd[start] = '0';
}
else
{
cd[start] = '1';
}
c = f;
f = HT[f].parent;
}
HC[i] = new char[n - start];
strcpy_s(HC[i], n + 1, &cd[start]);
}
delete cd;
cout << "哈夫曼编码:";
for (i = 1; i <= n; i++)
{
cout << HC[i];
}
cout << endl;
}