文章目录
- 哈夫曼树的构造和查找最小的的权值结点代码
- 哈夫曼编码思想
- 哈夫曼编码的算法实现
哈夫曼树的构造和查找最小的的权值结点代码
#include<iostream>
using namespace std;
typedef struct {
int parent, lch, rch;//双亲结点和孩子结点的下标
int weight;//权值
}htNode,*HuffmanTree;
void SelectHuff(HuffmanTree& HT, int n, int& s1, int& s2);
//构造哈夫曼树----哈夫曼算法
void CreateHuffmanTree(HuffmanTree &HT,int n) {
int m,i,s1,s2;
if (n <= 1) {
return;
}
m = 2 * n - 1;//数组共2n-1个元素
HT = new htNode[m + 1];//0号单元未用，HT[m]表示根结点
for (i = 1; i <= m; ++i) {
//将2n-1个元素的lch,rch,parent置为0
HT[i].lch = 0;
HT[i].rch = 0;
HT[i].parent = 0;
}
cout << "初始化成功" << endl;
for (i = 1; i <= n; ++i) {
cout << "请输入你想要输入的第" << i << "个元素的权值：" << endl;
cin >> HT[i].weight;//输入前n个元素的weight值
//初始化结束，下面开始建立哈夫曼表
}
for (i = n + 1; i <= m; i++) {//合并产生n-1个结点，构造Huffman树
SelectHuff(HT, i - 1, s1, s2);
HT[s1].parent = i;//表示从F中删除s1，s2
HT[s2].parent = i;
//s1,s2分别作为i的左右孩子
HT[i].lch = s1;
HT[i].rch = s2;
//i的权值为左右孩子权值之和
HT[i].weight = HT[s1].weight + HT[s2].weight;
cout << HT[i].weight <<" " << HT[s1].weight<<" " << HT[s2].weight;
cout << endl;
}
cout << endl;
}
//int Select(HuffmanTree HT, int n, int s1, int s2) {
// //在HT[K]（1<=k<=i-1)中选择两个其双亲域为0，
// //且权值最小的结点，并返回s1,s2;
// int k;
// for (k = 0; k < 2 * n - 1; k++) {
// if (HT[k].lch = HT[k].rch = 0 && HT[k].weight) {
//
// return s1, s2;
// }
// }
//}
//查找最小的权值的两个结点
//1.构造森林全是根；2.选用两小造新树；
//3.删除两小添新人；4.重复2, 3剩单根；
void SelectHuff(HuffmanTree &HT, int n, int &s1, int &s2) {
int i;
int minum;//定义一个临时变量保存最小值
for (i = 1; i <= n; i++) {
//以下是找到第一个最小值
if (HT[i].parent == 0) {
minum = i;
break;
}
}
for (i = 1; i <= n; i++) {
if (HT[i].parent == 0) {
if (HT[i].weight < HT[minum].weight)
minum = i;
}
}
s1 = minum;
//以下是找第二个最小值，且与第一个不同
for (i = 1; i <= n; i++) {
if (HT[i].parent == 0 && i != s1) {
minum = i;
break;
}
}
for (i = 1; i <= n; i++) {
if (HT[i].parent == 0 && i != s1) {
if (HT[i].weight < HT[minum].weight) {
minum = i;
}
}
}
s2 = minum;
}
int main() {
HuffmanTree ht = nullptr;
int n;
cout << "请输入你想输入多少个值：" << endl;
cin >> n;
CreateHuffmanTree(ht, n);
return 0;
}
哈夫曼编码思想
关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一字符编码的前缀。
方法：1.统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）。
2.利用哈夫曼树的特点：权越大的叶子离根越近；将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点，路径越短。
3.在哈夫曼树的每个分支上标为0或1：
结点的左分支标0，右分支标1；
把从根到每个叶子的路径上的标号连接起来，作为叶子代表的字符的编码。
问题：为什么哈夫曼树是前缀编码？
因为没有一片树叶是另外一片树叶的祖先，所以每个叶结点的编码就不可能是其他叶结点的前缀。
为什么哈夫曼编码能够保证字符编码总长最短？
因为哈夫曼树的带权路径长度最短，故字符编码的总长最短。
哈夫曼编码的算法实现
从哈夫曼树到哈夫曼数组
以下是算法的推导过程：
例如是找D的哈弗曼编码：
先找到D在哈夫曼树中的位置，然后查看D的双亲结点，在哈夫曼数组表中找到双亲0.09的位置在i= 9，所以在i=9这一排查找D在他这里是左子树还是右子树，这里是右子树所以最后一位编码就是1.然后再向前以此类推。
代码如下：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include<string.h>
#define nodeenum 10//叶子结点数
typedef struct {
int parent, lch, rch;//双亲结点和孩子结点的下标
int weight;//权值
}htNode,*HuffmanTree;
//哈夫曼编码
typedef char** huffmanCode;//第一个*代表的是指针变量，说明他是数组。
//第二个*说明他是指针数组，代表这个char类型数组里面的每一个元素都是*huffmanCode变量
void SelectHuff(HuffmanTree& HT, int n, int& s1, int& s2);
//构造哈夫曼树----哈夫曼算法
void CreateHuffmanTree(HuffmanTree &HT,int n) {
int m,i,s1,s2;
if (n <= 1) {
return;
}
m = 2 * n - 1;//数组共2n-1个元素
HT = new htNode[m + 1];//0号单元未用，HT[m]表示根结点
for (i = 1; i <= m; ++i) {
//将2n-1个元素的lch,rch,parent置为0
HT[i].lch = 0;
HT[i].rch = 0;
HT[i].parent = 0;
}
cout << "初始化成功" << endl;
for (i = 1; i <= n; ++i) {
cout << "请输入你想要输入的第" << i << "个元素的权值：" << endl;
cin >> HT[i].weight;//输入前n个元素的weight值
//初始化结束，下面开始建立哈夫曼表
}
for (i = n + 1; i <= m; i++) {//合并产生n-1个结点，构造Huffman树
SelectHuff(HT, i - 1, s1, s2);
HT[s1].parent = i;//表示从F中删除s1，s2
HT[s2].parent = i;
//s1,s2分别作为i的左右孩子
HT[i].lch = s1;
HT[i].rch = s2;
//i的权值为左右孩子权值之和
HT[i].weight = HT[s1].weight + HT[s2].weight;
cout << HT[i].weight <<" " << HT[s1].weight<<" " << HT[s2].weight;
cout << endl;
}
cout << endl;
}
//int Select(HuffmanTree HT, int n, int s1, int s2) {
// //在HT[K]（1<=k<=i-1)中选择两个其双亲域为0，
// //且权值最小的结点，并返回s1,s2;
// int k;
// for (k = 0; k < 2 * n - 1; k++) {
// if (HT[k].lch = HT[k].rch = 0 && HT[k].weight) {
//
// return s1, s2;
// }
// }
//}
//初始化
int initHuffmanTree(HuffmanTree& HT) {
int i;
HT = new htNode[2 * nodeenum];
for (i = 1; i <= 2 * nodeenum - 1; i++) {
HT[i].parent = HT[i].lch = HT[i].rch = -1;
}
cout << "请输入权值：" << endl;
for (i = 1; i <= nodeenum; i++) {
cin >> HT[i].weight;
}
return 1;
}
//查找最小的权值的两个结点
//1.构造森林全是根；2.选用两小造新树；
//3.删除两小添新人；4.重复2, 3剩单根；
void SelectHuff(HuffmanTree &HT, int n, int &s1, int &s2) {
int i;
int minum;//定义一个临时变量保存最小值
for (i = 1; i <= n; i++) {
//以下是找到第一个最小值
if (HT[i].parent == 0) {
minum = i;
break;
}
}
for (i = 1; i <= n; i++) {
if (HT[i].parent == 0) {
if (HT[i].weight < HT[minum].weight)
minum = i;
}
}
s1 = minum;
//以下是找第二个最小值，且与第一个不同
for (i = 1; i <= n; i++) {
if (HT[i].parent == 0 && i != s1) {
minum = i;
break;
}
}
for (i = 1; i <= n; i++) {
if (HT[i].parent == 0 && i != s1) {
if (HT[i].weight < HT[minum].weight) {
minum = i;
}
}
}
s2 = minum;
}
//构造哈夫曼编码
void CreateHuffmanCode(HuffmanTree HT,huffmanCode HC,int n){
int i;
int start = 0, c = 0, f = 0;//start记录cd数组的下标，c初始为叶子结点下标，就是孩子结点的下标，
//f记录的是双亲结点的下标
//从叶子到根逆向求每一个字符的哈夫曼编码，存储在编码表HC中
HC = new char*[n + 1];//分配存储n个字符编码的编码表空间
char *cd = new char[n];//分配临时存放每个字符编码的动态数组空间
cd[n - 1] = '\n';//编码结束符
for (i = 1; i <= n; i++) {
start = n - 1;//start开始时指向最后，即编码结束的位置
c = i;
f = HT[c].parent;//f指向结点c的双亲结点
while (f!=-1)//从叶子结点开始向上回溯，直到到达根结点
{
start--;//回溯依次start先前指向一个一个位置
if (HT[f].lch == c) {
cd[start] = '0';//结点c是左孩子就生成代码0
}
else {
cd[start] = '1';//若结点c是右孩子就生成代码1
}
c = f; f = HT[c].parent;//继续向上回溯，求出第i个字符的编码
}
HC[i] = new char[n - start];//为第i个字符分配存储空间
strcpy(HC[i], &cd[start]);//将求得的代码从临时空间cd复制到HC的当前行中
}
delete cd;//释放临时空间
}
int main() {
HuffmanTree ht = nullptr;
huffmanCode hc;
int n;
cout << "请输入你想输入多少个值：" << endl;
cin >> n;
CreateHuffmanTree(ht, n);
CreateHuffmanCode(ht, hc, n);
return 0;
}
