这个东西搞了我半天,其实也不算太复杂,只能说最近学习效率有点低,这个是一个求最优编码的算法 可以使得WPL最小 本质上使用了贪心策略

Huffman编码

在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码

这里是算法的基本实现原理 最高频率出现的字符用尽量短的编码 并且不能有编码之间的歧义产生 这可以用二叉树实现

哈夫曼编码（Huffman Coding）原理详解-CSDN博客

挺麻烦的 源代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//构建树节点和树
typedef struct 
{
	unsigned int weight;
	unsigned int parent;
	unsigned int lchild, rchild;
}HTNode, * HuffmanTree;

//构建存放字符串的数组 数组里面的每一个元素都是一个字符串
typedef char** HuffmanCode;

//求权重最小值并进行标记
int min(HuffmanTree HT, int n)
{
	int flag = 0;
	int j = 0;
	unsigned int k = UINT_MAX;
	for (j = 1; j <= n; j++)
	{
		//权重较小且未标记 更新最小值并标记这个下标
		if (HT[j].weight <= k && HT[j].parent == 0)
		{
			k = HT[j].weight;
			flag = j;
		}
	}
	HT[flag].parent = 1;
	return flag;
}

//获得权重最小的两个结点的下标
void Select(HuffmanTree HT, int n, int& s1, int& s2)
{
	s1 = min(HT, n);
	s2 = min(HT, n);
	if (s1 > s2)
	{
		int temp = s1;
		s1 = s2;
		s2 = temp;
	}
}

//Huffman编码算法
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int n, int* w)
{

	if (n <= 1)return;
	//n个字符 一共需要2n-1个结点存放另外的数据
	//n0=n2+1;
	//n2=n0-1=n-1
	//m=n-1+n=2n-1
	int m = 2 * n - 1;

	//多申请一个节点 第一个节点不存放信息
	HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
	HTNode* p;
	int i = 1;
	//初始化前n个节点
	for (i = 1, p = HT + 1; i <= n; ++p, ++i, ++w)
	{
		p->weight = *w;
		p->parent = 0;
		p->lchild = 0;
		p->rchild = 0;
	}
	//初始化后n-1个结点
	for (; i <= m; ++i, ++p)
	{
		p->parent = 0;
		p->lchild = 0;
		p->rchild = 0;
		p->weight = 0;
	}
	//更新每个节点的parent child weight信息
	for (int i = n + 1; i <= m; i++)
	{
		int s1, s2;
		Select(HT, i - 1, s1, s2);
		HT[i].weight = HT[s1].weight + HT[s2].weight;
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1;
		HT[i].rchild = s2;
	}

	HC = (HuffmanCode)malloc((n + 1) * (sizeof(char*)));

	char* cd = (char*)malloc(n * sizeof(char));

	cd[n - 1] = '\0';

	for (int i = 1; i <= n; i++)
	{
		//从后往前添加数据信息
		int start = n - 1;
		//一直循环找父节点 
		for (int c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
		{
			//左0 右1
			if (HT[f].lchild == c)
			{
				cd[--start] = '0';
			}
			else
			{
				cd[--start] = '1';
			}
		}
		//根据start位置申请字符数组大小
		HC[i] = (char*)malloc((n - start) * sizeof(char));
		//从cd数组start位置开始复制给HC[i]
		strcpy(HC[i], &cd[start]);
	}
	free(cd);
}

int main()
{
	int weights[] = { 7,5,2,4 };
	int len = sizeof(weights) / sizeof(weights[0]);
	HuffmanCode HC;
	HuffmanTree HT;
	HuffmanCoding(HT, HC, len, weights);
	printf("Huffman Codes:\n");
	for (int i = 1; i <= len; i++)
	{
		printf("Character %d :%s\n", i, HC[i]);
	}
	for (int i = 1; i <= len; i++)
	{
		free(HC[i]);
	}
	free(HC);
	free(HT);
	return 0;
}

泪目了 小有成就感>.<