c++实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c++实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6099字，纯文字阅读大概需要9分钟。
内容图文
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdlib>
using namespace std;
//定义哈夫曼树存储结构
typedef struct
{
char data; //存放结点数据
int weight; //记录结点权值
int parent, lchild, rchild;
}HTNode, * HuffmanTree;
//哈夫曼编码存储表示
typedef char** HuffmanCode; //动态分配数组储存哈夫曼编码表
//初始化
HuffmanTree InitHuffman(HuffmanTree& HT, int n)
{
if (n < 0)
{
cout << "输入初态结点数目不正确！！！" << endl;
return NULL;
}
else
{
int m = 2 * n - 1; //n个叶子结点的哈夫曼树有2n-1个结点
HT = new HTNode[m + 1]; //0号单元未用，申请m+1个空间
for (int i = 1; i <= m; i++)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].weight = 0;
HT[i].data = '-';
}
//输入初始数据，为了方便理解HT[0]不存放数据
cout << "请输入初态结点数据及相应权值（格式形式：a 3）：";
for (int i = 1; i <= n; i++)
{
cin >> HT[i].data;
cin >> HT[i].weight;
}
return HT;
}
}
//打印HT
void PrintState(HuffmanTree& HT, int n)
{
int m = 2 * n - 1; //总结点数
cout << "结点i\tdata值\tweight\tparent\tlchild\trchild" << endl;
for (int i = 1; i <= m; i++)
{
cout << setw(3) << i << "\t";
cout << setw(4) << HT[i].data << "\t";
cout << setw(4) << HT[i].weight << "\t";
cout << setw(4) << HT[i].parent << "\t";
cout << setw(4) << HT[i].lchild << "\t";
cout << setw(4) << HT[i].rchild << "\t" << endl;
}
}
//选择双亲域为0且两权值最小的结点，选择范围为1到i-1
int* Select(HuffmanTree& HT, int n, int* Idx)
{
int MIN, MinSecond;
//打擂台法使权最小值和次权最小值最大（假设第一个值权值最小无法进行）
MIN = MinSecond = 99999;
//循环从1到n次
for (int i = 1; i <= n; i++)
{
//如果双亲为0（未删除结点与新生成结点），一定会执行if语句,寻找权最小值
if ((HT[i].parent == 0) && HT[i].weight < MIN)
{
//将最小的权值给MinSecond方便寻找次最小值
MinSecond = MIN;
MIN = HT[i].weight;
//记录权最小值下标
Idx[0] = i;
}
//否则如果满足条件寻找次最小值
else if ((HT[i].parent == 0) && HT[i].weight < MinSecond)
{
MinSecond = HT[i].weight;
//记录权次最小值下标
Idx[1] = i;
}
}
return Idx;
}
//构造哈夫曼树
void CreateHuffmanTree(HuffmanTree& HT, int n)
{
if (n <= 1)
return;
int m = 2 * n - 1; //n个叶子结点的哈夫曼树有2n-1个结点
//从n+1开始构造哈弗曼树
for (int i = n + 1; i <= m; i++)
{
//Idx用于存放两个返回最小权值的下标，i-1为前n个结点，后面随着i增加，n也增加
int* Idx = Idx = new int[2];
Idx = Select(HT, i - 1, Idx);
int s1 = Idx[0]; //权最小值下标
int s2 = Idx[1]; //权次最小值下标
//给两权值最小的结点置双亲,使s1，s2结点不在录入Select范围
HT[s1].parent = i;
HT[s2].parent = i;
//给新节点i左右孩子置位s1,s2
HT[i].lchild = s1;
HT[i].rchild = s2;
//给新结点赋权值
HT[i].weight = HT[s1].weight + HT[s2].weight;
delete[]Idx;
}
}
//哈夫曼编码
void CreateHuffmanCode(HuffmanTree& HT, HuffmanCode& HC, int n)
{
HC = new char* [n + 1]; //分配字符的空间
char* TempCode = new char[n]; //分配临时编码表空间n个
TempCode[n - 1] = '\0'; //编码有叶子结点开始逆序存放，先将末尾结束符标志打上，为后序strcpy
//for循环逐个逆序求叶子结点的哈夫曼编码
for (int i = 1; i <= n; i++)
{
int start = n - 1; //开始存放的起点指向末尾，用于后面HC拷贝是的起始地址
int NodeIdx = i; //NodeIdx最开始存放叶子结点序号
int ParentsIdx = HT[i].parent; //Parents指向其双亲结点序号
//若有双亲则由下到上进行编码，编码的字符，从序号1开始
while (ParentsIdx)
{
start--; //在一维数组末尾，strat先指向最后
//若双亲结点的左结点序号为NodeIdx，将0打入一维临时数组中，否则打入1
if (HT[ParentsIdx].lchild == NodeIdx)
TempCode[start] = '0';
else
TempCode[start] = '1';
//结点的序号更新，进入上一层
NodeIdx = ParentsIdx;
ParentsIdx = HT[NodeIdx].parent;
}
//临时一维数组存放编码成功，开始用HC顺序存放字符编码
HC[i] = new char[n - start]; //为序号为i的字符分配编码空间
strcpy_s(HC[i], n - start, &TempCode[start]); //编码字符串拷贝strcpy报错因为没有指定长度
}
//打印哈夫曼编码
cout << "---字符对应编码----" << endl;
for (int i = 1; i <= n; i++)
{
cout << HT[i].data << "\t\t" << HC[i] << endl;
}
delete []TempCode;
}
//输入字符打印哈夫曼编码
void PrintCode(HuffmanTree & HT, HuffmanCode & HC, int n)
{
char *str =new char[100]; //存储需要解码的字符
int flag = 0; //flag用于检查输入是否错误
cout << "请输入需要编码的字符：";
cin >> str;
//匹配字符并打印相应的哈夫曼编码
cout << "输入的字符哈夫曼编码为：";
for (int j = 0; j < strlen(str); j++)
{
flag = 0;
for (int i = 1; i <= n; i++)
{
//匹配成功打印编码
if (HT[i].data == str[j])
{
cout << HC[i] ;
flag = 1; //匹配成功
}
}
//如果有匹配失败的情况，则跳出循环
if (flag == 0)
{
cout << "\n第" << j+1 << "字符输入错误!" ;
break;
}
}
putchar(10);
delete []str; //释放str空间
}
//哈夫曼解码并打印
void HuffmanDecode(HuffmanTree& HT, int n)
{
char* str = new char[1024];
cout << "请输入二进制编码：";
cin >> str;
int flag = 0; //用于检查二进制编码是否输入错误
cout << "解码对应字符为：";
//遍历二进制编码
for (int i = 0; i < strlen(str);)
{
int Root = 2 * n - 1; //Root为根结点序号
//当结点的左右孩子不为空时进入循环，由根结点进入
while (HT[Root].lchild && HT[Root].rchild)
{
if (str[i] == '0')
Root = HT[Root].lchild;
else if (str[i] == '1')
Root = HT[Root].rchild;
else
{
cout << "输入的二级制编码有误！" << endl;
flag = 1;
break;
}
i++; //相后读取二进制编码，i值更新
}
//如果找到错误跳出循环
if (flag)
break;
//打印编码对应字符
cout << HT[Root].data;
}
delete []str;
}
int main()
{
int n;
cout << "请输入哈夫曼树初态结点数：";
cin >> n;
//初始化哈夫曼树
HuffmanTree HT = InitHuffman(HT, n);
//打印HT初态
cout << "--------------------HT初态--------------------" << endl;
PrintState(HT, n);
//构造哈夫曼树
CreateHuffmanTree(HT, n);
//打印HT终态
cout << "--------------------HT终态--------------------" << endl;
PrintState(HT, n);
HuffmanCode HC;
//哈夫曼编码-由下而上
CreateHuffmanCode(HT, HC, n);
//打印字符对应编码
PrintCode(HT, HC, n);
//哈夫曼解码并打印-由上而下
HuffmanDecode(HT, n);
return 0;
}
//由于编译器版本原因strcpy出现不安全原因，导致无法运行，后使用strcpy_s给予拷贝长度得到解决；把“==”写成“=”导致报错；
/*
输入字符串统计字符个数（权值）
int CreateWeightArray(char* str, int* Array) {
//初始化权值数组，128为str[i]的最大数值
for (int i = 0; i < 128; i++)
{
Array[i] = 0;
}
int length = 0;
//利用下标记录位权
for (int i = 0; str[i]; i++)
{
Array[str[i]]++; //值加1，下标即字符
}
//统计字符串去重后的长度
for (int i = 0; i < 128; i++)
{
if (Array[i] != 0)
{
length++;
}
}
return length;
}
*/
内容总结
以上是互联网集市为您收集整理的c++实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）全部内容，希望文章能够帮你解决c++实现哈夫曼树，哈夫曼编码，哈夫曼解码（字符串去重，并统计频率）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】