165 lines
3.6 KiB
C++
165 lines
3.6 KiB
C++
#include"iostream"
|
||
#include<iomanip>
|
||
#include<string>
|
||
using namespace std;
|
||
|
||
struct HTNode
|
||
{
|
||
int weight; // 权值，设为整型
|
||
int parent; // 双亲位置
|
||
int lchild; // 左孩子位置
|
||
int rchild; // 右孩子位置
|
||
};
|
||
|
||
|
||
void select(HTNode* HT, int k, int& i1, int& i2) // 在前K-1个结点中选择权值最小的两个根结点i和j
|
||
{
|
||
int m1, m2;
|
||
m1 = m2 = 32767; //
|
||
i1 = i2 = 0;
|
||
for (int j = 0; j < k; j++)
|
||
{
|
||
if (HT[j].weight < m1 && HT[j].parent == -1)
|
||
{
|
||
m2 = m1, i2 = i1;
|
||
m1 = HT[j].weight;
|
||
i1 = j;
|
||
}
|
||
else if (HT[j].weight < m2 && HT[j].parent == -1)
|
||
{
|
||
m2 = HT[j].weight;
|
||
i2 = j;
|
||
}
|
||
}
|
||
}
|
||
// 算法5.16 // 构造哈夫曼树
|
||
void HuffmanTree(HTNode*& HT, int* w, int n)
|
||
{ // n是叶子结点的个数，w是叶子结点的权值数组
|
||
HTNode* p;
|
||
int k, i;
|
||
int i1, i2;
|
||
p = HT;
|
||
for (i = 0; i < 2 * n - 1; i++)
|
||
{ // 设置初始状态，所有结点的指针为空
|
||
HT[i].weight = 0;
|
||
HT[i].parent = -1;
|
||
HT[i].lchild = -1;
|
||
HT[i].rchild = -1;
|
||
}
|
||
for (i = 0; i < n; i++)
|
||
{ // 前n个结点的权值分别为个结点的权值
|
||
HT[i].weight = w[i];
|
||
}
|
||
for (k = n; k < 2 * n - 1; k++)
|
||
{ // 构造最优二叉树
|
||
select(HT, k, i1, i2); // 在前K-1个结点中选择权值最小的两个根结点i1和i2
|
||
HT[i1].parent = k;
|
||
HT[i2].parent = k;
|
||
HT[k].weight = HT[i1].weight + HT[i2].weight;
|
||
HT[k].lchild = i1;
|
||
HT[k].rchild = i2;
|
||
}
|
||
}
|
||
|
||
|
||
void DispHT(HTNode* HT, int n) // 显示哈夫曼树存储
|
||
{
|
||
HTNode* p;
|
||
p = HT;
|
||
cout << "k" << setw(7) << "Weight" << setw(7) << "parent"
|
||
<< setw(7) << "lchild" << setw(7) << "rchild" << endl;
|
||
for (int k = 0; k < 2 * n - 1; k++)
|
||
{
|
||
cout << k << setw(7) << (p + k)->weight << setw(7) << (p + k)->parent
|
||
<< setw(7) << (p + k)->lchild << setw(7) << (p + k)->rchild << endl;
|
||
}
|
||
}
|
||
|
||
//算法5.17 // 构建哈夫曼编码
|
||
void CreateHFCode(HTNode* HT, int n, char** HC)
|
||
{
|
||
int i, start, c, f;
|
||
char* cd;
|
||
cd = new char[n];
|
||
cd[n - 1] = '\0';
|
||
for (i = 0; i < n; i++)
|
||
{
|
||
start = n - 1;
|
||
c = i;
|
||
f = HT[i].parent;
|
||
while (f != -1)
|
||
{
|
||
if (HT[f].lchild == c)
|
||
cd[--start] = '0';
|
||
else
|
||
cd[--start] = '1';
|
||
c = f; f = HT[f].parent;
|
||
}
|
||
cout << endl;
|
||
HC[i] = new char[n - start];
|
||
HC[i] = &cd[start];
|
||
int j = 0;
|
||
while (HC[i][j] != '\0') // 显示编码
|
||
{
|
||
cout << HC[i][j];
|
||
j++;
|
||
}
|
||
|
||
}
|
||
delete cd;
|
||
cout << endl;
|
||
}
|
||
|
||
|
||
int op;
|
||
|
||
int main()
|
||
{
|
||
int* w; // 权值数组
|
||
int n; // 权值个数
|
||
int i; // 工作变量
|
||
HTNode* HT; // 哈夫曼树
|
||
char** HC;
|
||
do
|
||
{
|
||
cout << "1-输入结点权值" << endl;
|
||
cout << "2-生成最优二叉树" << endl;
|
||
cout << "3-求哈夫曼编码" << endl;
|
||
cout << "4-退出程序" << endl;
|
||
cout << "请选择操作(1~4)：";
|
||
cout << "\b\b";
|
||
cin >> op;
|
||
switch (op)
|
||
{
|
||
case 1:
|
||
cout << "测试案例" << endl;
|
||
cout << "7,5,2,3,5,6" << endl;
|
||
cout << "请输入结点的个数：";
|
||
cin >> n;
|
||
w = new int[n];
|
||
cout << "请依次输入权值：" << endl;
|
||
for (i = 0; i < n; i++)
|
||
{
|
||
cout << "请输入第" << i + 1 << "个权值：";
|
||
cin >> w[i];
|
||
}
|
||
break;
|
||
case 2:
|
||
HT = new HTNode[2 * n - 1]; // 申请最优二叉树存储空间
|
||
HuffmanTree(HT, w, n);
|
||
cout << "创建的哈夫曼树为：\n";
|
||
DispHT(HT, n);
|
||
system("pause");
|
||
break;
|
||
case 3:
|
||
HC = new char* [n]; // 存储哈示曼编码
|
||
cout << "哈夫曼编码为：\n";
|
||
CreateHFCode(HT, n, HC);
|
||
break;
|
||
case 4:
|
||
cout << "结束运行，Bye-Bye!" << endl;
|
||
break;
|
||
}
|
||
} while (op != 4);
|
||
return 0;
|
||
} |