|
|
输入一组字符及其权重，构建哈夫曼树，利用哈夫曼树进行编码，并输出编码结果
哈夫曼树构建：
给定的一组权重中找出其中最小的两个树生成一颗新树，新树父节点权重为孩子节点权重的和，然后将新生成的树的父节点和其他结点一起，再找到他们中最小的两个，以此类推，直到只有一棵树为止。
首先介绍几个代码编写过程中出现的错误
1.
在哈夫曼树创建函数以及编码函数，这两个参数一定要添加取地址符，传过去的应该是一个地址，而不仅仅是值传递。编译器虽然不会报错但代码运行中会出现问题。
2.
HC,HT,使用前要先申请存储空间
3.使用循环时要特别注意开始值和结束值
完整代码：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstring>
using namespace std;
#define OVERFLOW -2
#define ERROR 0
#define N 100
//哈夫曼树和哈夫曼树的存储表示
typedef struct{
char data;//结点值
int weight;//权重
int parent, lchild, rchild;
}HTNode, *HuffmanTree;//动态分配数组存储哈夫曼树
typedef struct
{
char cd[N];//存放当前结点的哈夫曼码
int start;//表示cd[start...n0]部分是哈夫曼码
}HCode;
typedef char ** HuffmanCode;//动态分配数组存储哈夫曼编码
void Select(HuffmanTree HT, int n, int *s1, int *s2)//在HT[1...n-1]选择parent为0，且weight最小的两个结点，序号分别为s1,s2
{
int i=0,j=0;//i控制HT数组，j保证比较进行下去
int min1 = 1000;
int min2 = 1000;//规定了一个特别大的数
for (i = 0; i <= n-1; i++)
{
if (HT.parent == 0)//只在未构造二叉树的结点中找
{
if (j == 0)
{
min1 = HT.weight;
*s1 = i;
}
else
{//始终保证min1最小，min2第二小
if (HT.weight < min1)
{
min2 = min1;
*s2 = *s1;
min1 = HT.weight;
*s1 = i;
}
else if (HT.weight >= min1 && HT.weight < min2)
{
min2 = HT.weight;
*s2 = i;
}
}
++j;
}
}
}
//哈夫曼树创建
void CreateHuffmanTree(HuffmanTree &HT,int *w,char *c,int n)
{
int m,i;
int s1, s2;
HuffmanTree p = HT;
if (n <= 1)return ;
m = 2 * n - 1;//数组共2n-1个元素
HT = new HTNode[m + 1];//0号单元未用，HT[m]表示根节点
for (i = 0; i < n; i++, p++, w++,c++)//将给定的权值输入
{
HT.data = *c;
HT.weight = *w;
HT.lchild = 0;
HT.rchild = 0;
HT.parent = 0;
}
for (; i <= m; i++){//将2n-个元素的lch,rch,parent置为0
HT.lchild = 0;
HT.rchild = 0;
HT.parent = 0;
HT.weight = 0;
HT.data = 0;
}
//初始化结束，下面开始建立哈夫曼树
for (i = n ; i < m; i++)//合并产生n-1个结点-构造哈夫曼树
{
Select(HT, i , &s1, &s2);//在HT[0...k-1]选择parent为0，且weight最小的两个结点，序号分别为s1,s2
HT[s1].parent = i; HT[s2].parent = i;//表示从f中删除s1,s2
HT.lchild = s1; HT.rchild = s2;//s1,s2分别作为i的左右孩子
HT.weight = HT[s1].weight + HT[s2].weight;//i的权值为左右孩子权值之和
}
}
void CreateHuffmanCode(HuffmanTree &HT, HuffmanCode &HC, int n)
{//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
int start,c,f,i;
HC = new char *[n + 1];//分配n个字符编码的头指针矢量
char *cd = new char[n];//分配临时存放编码的动态数组空间
cd[n - 1] = '\0';
for ( i = 0; i < n; i++)//逐个求哈夫曼编码
{
start = n - 1;
c = i;
f = HT.parent;
while (f != 0)
{//从叶子结点开始向上回溯直到根节点
--start;
if (HT[f].lchild == c)cd[start] = '0';//结点c是f的左孩子，则生成代码0
else cd[start] = '1';//右孩子，1
c = f; //继续向上回溯
f = HT[f].parent;
}//while
HC = new char[n - start];//为第i个字符串分配空间
strcpy(HC, &cd[start]);//将求得的编码从临时空间cd复制到HC的当前行中
}//for
delete cd;//释放临时空间
}
int main()
{
HuffmanTree HT ;
HuffmanCode HC;
char ch1, ch2;
int n,i;
char *c = (char*)malloc(N*sizeof(char));
int *w = (int*)malloc(N*sizeof(int));
ch1 = 'y';
while (ch1=='y')
{
cout << "----------哈夫曼树----------" << endl;
cout << "------1.创建哈夫曼树 ------" << endl;
cout << "------2.哈夫曼编码 ------" << endl;
cout << "------0.退出 ------" << endl;
cout << "------请选择菜单号 ------" << endl;
cin >> ch2;
getchar();
cout << endl;
switch (ch2)
{
case'1':
cout << "你想要输入的结点个数n：" << endl;
cin >> n;
fflush(stdin);//清空缓冲区
cout << "请输入待编码的" << n << "个字符以及对应的权重（eg:a 11)" << endl;
for (i = 0; i < n; i++)
{
scanf("%c %d", &c, &w);
fflush(stdin);//清空缓冲区
}
CreateHuffmanTree(HT,w,c, n);
cout << "创建哈夫曼树成功" << endl;
cout << "哈夫曼树为" << endl;
printf("char weight parent lchild rchild\n");
for (i = 0; i < n; i++)
{
printf("%4c %5d %6d %6d %6d\n", c, w, HT.parent, HT.lchild, HT.rchild);
}
break;
case'2':
cout << "每个字符对应哈夫曼编码为：" << endl;
CreateHuffmanCode(HT, HC, n);
for (i = 0; i < n; i++)
{
cout << c << ": " << HC << endl;
}
break;
case'0':
ch1 = 'n';
break;
default:
cout << "输入有误" << endl;
}//switch
}//while
return 0;
}
运行结果：
|
免责声明：
1. 本站所有资源来自网络搜集或用户上传，仅作为参考不担保其准确性！
2. 本站内容仅供学习和交流使用，版权归原作者所有！© 查看更多
3. 如有内容侵害到您，请联系我们尽快删除，邮箱：kf@codeae.com
|
编程语言
发布于：2021-07-17 09:13
|
阅读数：318
|
评论：0
QQ好友和群
QQ空间
