大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

【数据结构】赫夫曼树与编码-创新互联

赫夫曼树与赫夫曼编码
  • 前言
  • 赫夫曼树
    • 存储结构
    • 初始化树
    • 构建树
  • 赫夫曼编码
    • 初始化编码
    • 构建编码

创新互联建站主营吉林网站建设的网络公司,主营网站建设方案,成都App定制开发,吉林h5成都微信小程序搭建,吉林网站营销推广欢迎吉林等地区企业咨询前言

(概念)
路径:从一个节点到另一个节点的分支
路径长度:从一个节点到另一个节点的分支总数
节点的带权路径:该节点到根节点之间路径长度与权值的乘积
树的带权路径长度(WPL):所有叶子节点的带权路径长度之和
在这里插入图片描述

赫夫曼树 存储结构

赫夫曼树采取静态存储的方式,以下面为例:
在这里插入图片描述

初始化树

所需头文件:

#includeusing namespace std;
#include#include#include

初始化树:

const int n = 8;                   //叶子个数(权值个数)
const int m = 2 * n;               //树节点个数+1(第0下标不放值,是标记位)
typedef unsigned int WeightType;   //权值类型
typedef unsigned int NodeType;     //节点类型

typedef struct       //树节点
{WeightType weight;
	NodeType parent, leftchild, rightchild;
}HtNode;

typedef HtNode HuffmanTree[m];    //赫夫曼树

void InitHuffmanTree(HuffmanTree hft,const WeightType w[])
{for (int i = 0; i< n; i++)
	{hft[i + 1].weight = w[i];
	}
}

打印树:

void PrintHuffmanTree(HuffmanTree hft)
{cout<< "(赫夫曼树:)"<< endl;
	for (int i = 1; i< m; i++)
	{cout<< "  index: "<< i<< "\tweight: "<< hft[i].weight<< "\tparent: "<< hft[i].parent<< "\tLchild: "<< hft[i].leftchild<< "\tRchild: "<< hft[i].rightchild<< endl;
	}
	cout<< endl<< endl;
}

主函数:

int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
	HuffmanTree hft = {0 };
	InitHuffmanTree(hft, w);
	PrintHuffmanTree(hft);
	return 0;
}

初始化结果:
在这里插入图片描述

构建树

在这里插入图片描述

使用优先级队列来存放存有下标和权值的结构体,使用greater:将数据大的下沉(形成小顶堆),使用less:将小数据下沉(形成大顶堆)

代码实现:

struct IndexWeight
{int index;   //下标
	WeightType weight;   //权值
	operator WeightType() const {return weight; }   //重载(当用此结构体作比较时,用weight来进行比较)
};

void CreateHuffmanTree(HuffmanTree hft)
{std::priority_queue, std::greater>qu;     //优先级队列(小顶堆)
	for (int i = 1; i<= n; i++)
	{qu.push(IndexWeight{i,hft[i].weight });
	}

	int k = n + 1;
	while (!qu.empty())
	{if (qu.empty()) {break; }
		IndexWeight left = qu.top();
		qu.pop();
		if (qu.empty()) {break; }
		IndexWeight right = qu.top();
		qu.pop();
		hft[k].weight = left.weight + right.weight;
		hft[k].leftchild = left.index;
		hft[k].rightchild = right.index;
		hft[left.index].parent = k;
		hft[right.index].parent = k;
		qu.push(IndexWeight{k,hft[k].weight });
		k++;
	}
}

打印树:

void PrintHuffmanTree(HuffmanTree hft)
{cout<< "(赫夫曼树:)"<< endl;
	for (int i = 1; i< m; i++)
	{cout<< "  index: "<< i<< "\tweight: "<< hft[i].weight<< "\tparent: "<< hft[i].parent<< "\tLchild: "<< hft[i].leftchild<< "\tRchild: "<< hft[i].rightchild<< endl;
	}
	cout<< endl<< endl;
}

主函数:

int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
	HuffmanTree hft = {0 };
	InitHuffmanTree(hft, w);
	CreateHuffmanTree(hft);
	PrintHuffmanTree(hft);
	return 0;
}

构建结果:
在这里插入图片描述

赫夫曼编码

以此赫夫曼树为例:
在这里插入图片描述

原本发送"ABCDEFGH"这些字符时,每个字符都是8个二进制位(char 1字节)总共要发:8*8=64位二进制,但通过赫夫曼编码后总共要发:27位二进制,因此赫夫曼编码在文件传输时有巨大作用

初始化编码

代码实现:

typedef struct
{char ch;        //节点对应的数据
	char code[n+1]; //该节点的赫夫曼编码
}HuffmanCode;

typedef HuffmanCode HuffmanCoding[n];

void InitHuffmanCode(HuffmanCoding hfc,const char ch[])
{for(int i=0;ihfc[i].ch=ch[i];
		hfc[i].code[n]={'\0'};
	}
}

打印编码:

void PrinthuffmanCode(HuffmanCoding hfc)
{for (int i = 0; i< n; i++)
	{cout<< " data: "<< hfc[i].ch<< " 的赫夫曼编码:"<< hfc[i].code<< endl;
	}
}

主函数:

int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
	HuffmanTree hft = {0 };
	InitHuffmanTree(hft, w);
	CreateHuffmanTree(hft);
	PrintHuffmanTree(hft);
	const char ch[n + 1] = {"ABCDEFGH" };  //必须是n+1,双引号最后会有一个'\0'
	HuffmanCoding hfc = {0 };
	InitHuffmanCode(hfc, ch);
	PrinthuffmanCode(hfc);
	return 0;
}

初始化结果:
在这里插入图片描述

构建编码

从叶子节点向根节点走,如果是左孩子则为0,反之则为1
创建一个数组来存放0,1值,从后向前存放,这样读取的时候就是正着读取的

代码实现:

void CreateHuffmanCode(HuffmanTree hft, HuffmanCoding hfc)
{char code[n + 1] = {0 };
	for (int i = 1; i<= 8; i++)
	{int k = n;
		int child = i;
		int parent = hft[i].parent;
		while (parent != 0)
		{	if (child == hft[parent].leftchild)
			{		code[--k] = {'0' };
			}
			else if (child == hft[parent].rightchild)
			{		code[--k] = {'1' };
			}
			child = parent;
			parent = hft[child].parent;
		}
		strcpy_s(hfc[i - 1].code, n, &code[k]);
	}
}

打印编码:

void PrinthuffmanCode(HuffmanCoding hfc)
{for (int i = 0; i< n; i++)
	{cout<< " data: "<< hfc[i].ch<< " 的赫夫曼编码:"<< hfc[i].code<< endl;
	}
}

主函数:

int main()
{WeightType w[n] = {5,29,7,8,14,23,3,11 };
	HuffmanTree hft = {0 };
	InitHuffmanTree(hft, w);
	CreateHuffmanTree(hft);
	PrintHuffmanTree(hft);

	const char ch[n + 1] = {"ABCDEFGH" };  //必须是n+1,双引号最后会有一个'\0'
	HuffmanCoding hfc = {0 };
	InitHuffmanCode(hfc, ch);
	CreateHuffmanCode(hft, hfc);
	PrinthuffmanCode(hfc);
}

构建结果:
在这里插入图片描述

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


新闻名称:【数据结构】赫夫曼树与编码-创新互联
本文URL:http://dzwzjz.com/article/cddgps.html
在线咨询
服务热线
服务热线:028-86922220
TOP