哈夫曼编码算法--我只想简单点

　

哈夫曼编码

哈夫曼树

哈夫曼树, 即带权路径最小的树, 权值最小的结点远离根结点, 权值越大的结点越靠近根结点

图解

图(3)即为哈夫曼树

哈夫曼编码

左孩子路径编码为 0, 右孩子路径编码为 1

图解

即

A 的编码: 0

D 的编码: 10

B 的编码: 110

C 的编码: 111

哈夫曼编码算法的实现

定义一个哈夫曼树

//定义一个哈夫曼树
typedef struct {
	//定义权值
	unsigned int weight;
	unsigned int parent, lchild, rchild;
}HTNode, *HuffmanTree;

定义存放哈夫曼编码的空间

//存放哈夫曼编码
typedef char** HuffmanCode;

创建一个哈夫曼树

//创建一个哈夫曼树
void CreateHuffmanTree(HuffmanTree* HT, int* w, int n) {
	int m = 0; //结点的总数(⊙﹏⊙)
	HuffmanTree adjust = NULL; //定义一个调整指针, 存放即时指向结点
	int i = 0; //即时调整索引
	//存放两个最小值
	int s1 = 0;
	int s2 = 0;
	//判断输入是否合理
	if (n <= 1) {
		return;
	}
	m = 2 * n - 1;
	//动态分配内存空间存放结点
	*HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
	if (!*HT) {
		exit(-1);
	}
	//初始化叶子结点, 第一个结点为空
	for (adjust = *HT + 1, i = 1; i <= n; ++adjust, ++i) {
		adjust->weight = *(w + i - 1);
		adjust->parent = 0;
		adjust->lchild = 0;
		adjust->rchild = 0;
	}
	//将最后一个结点的 parent 置为 0
	for (; i <= m; ++i, ++adjust) {
		adjust->parent = 0;
	}
	for (i = n + 1; i <= m; ++i) {
		//在前 i - 1 个结点中找出两个最小值
		Select(HT, i - 1, &s1, &s2);
		//找出双亲结点
		(*HT + s1)->parent = (*HT + s2)->parent = i;
		//找出双亲结点的两个孩子
		(*HT + i)->lchild = s1;
		(*HT + i)->rchild = s2;
		//计算出双亲结点的权值
		(*HT + i)->weight = (*HT + s1)->weight + (*HT + s2)->weight;
	}
}
//返回权值最小结点的索引(访问过的结点不再访问)
int Min(HuffmanTree HT, int n) {
	unsigned int f_min = 100;
	int flag = 0; //用来记录已遍历过的结点
	for (int i = 1; i <= n; ++i) {
		if ((HT + i)->weight < f_min && (HT + i)->parent == 0) {
			f_min = (HT + i)->weight;
			flag = i;
		}
	}
	//给选中的结点置 1, 下次不需要再遍历
	(HT + flag)->parent = 1;
	return flag;
}
//挑选 2 个权值最小的结点
void Select(HuffmanTree* HT, int n, int* s1, int* s2) {
	int tmp = 0; //临时变量
	*s1 = Min(*HT, n);
	*s2 = Min(*HT, n);
	//目的是 s1 的权值要不大于 s2 的权值
	if ((*HT + *s1)->weight > (*HT + *s2)->weight) {
		tmp = *s1;
		*s1 = *s2;
		*s2 = tmp;
	}
}

构造哈夫曼编码

void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n) {
	//动态开辟内存空间存放所有非叶子节点的编码
	*HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
	if (!*HC) {
		exit(-1);
	}
	//动态分配内存空间暂时存放某个结点的哈夫曼编码
	char* cd = (char*)malloc(n * sizeof(char));
	if (!cd) {
		exit(-1);
	}
	//求 n 个非叶子节点的哈夫曼编码
	*(cd + n - 1) = '\0';
	int start = 0; //用来存放编码起始位置
	for (int i = 1; i <= n; ++i) {
		start = n - 1;
		for (int c = i, f = (HT + i)->parent; f != 0; c = f, f = (HT + f)->parent) {
			if ((HT + f)->lchild == c) {
				*(cd + --start) = '0';
			} else {
				*(cd + --start) = '1';
			}
		}
		//根据该结点编码字符串的长度在指定位置动态开辟存放编码的空间
		*(*HC + i) = (char*)malloc((n - start) * sizeof(char));
		//将暂存编码空间中的编码字符串拷贝到地址空间去
		strcpy(*(*HC + i), cd + start);
	}
	//释放暂存编码字符串的空间
	free(cd);
}

遍历叶子结点

从上到下, 从左到右

void Traverse(HuffmanTree HT, int n) {
	//遍历叶子结点
	HuffmanTree p = HT + 2 * n - 1;
	int i = 0;
	while ((p - HT > 0) && (p - HT <= 2 * n - 1)) {
		if (p->lchild == 0 && p->rchild == 0) {
			break;
		}
		if (p->lchild < p->rchild) {
			i = p->lchild;
			printf("%u ", (HT + i)->weight);
			p = HT + p->rchild;
		} else {
			i = p->rchild;
			printf("%u ", (HT + i)->weight);
			p = HT + p->lchild;
		}
	}
	printf("%u ", p->weight);
	printf("\n");
}

遍历哈夫曼编码

//遍历哈夫曼编码
void TraverseCoding(HuffmanCode HC, int n) {
	for (int i = 1; i <= n; ++i) {
		printf("哈夫曼编码:");
		puts(*(HC + i));
	}
}

销毁哈夫曼树

//销毁哈夫曼树
void Destroy(HuffmanTree* HT, HuffmanCode* HC, int n) {
	for (int i = 1; i <= n; ++i) {
		free(*(*HC + i));
	}
	free(*HC);
	free(*HT);
	*HC = NULL;
	*HT = NULL;
}

测试

//函数的声明
void CreateHuffmanTree(HuffmanTree* HT, int* w, int n);
void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n);
void TraverseTree(HuffmanTree HT, int n);
void TraverseCoding(HuffmanCode HC, int n);
void Destroy(HuffmanTree* HT, HuffmanCode* HC, int n);
int main() {
	HuffmanTree HT = NULL;
	HuffmanCode HC = NULL;
	//存放权值
	int* w = 0;
	int n = 0; //叶子结点个数
	printf("请输入叶子结点的个数:");
	scanf("%d", &n);
	//动态分配内存空间存放权值
	w = (int*)malloc(n * sizeof(int));
	if (!w) {
		exit(-1);
	}
	printf("请输入权值:");
	for (int i = 0; i < n; ++i) {
		scanf("%d", w + i);
	}
	CreateHuffmanTree(&HT, w, n);
	HuffmanCoding(HT, &HC, n);
	printf("遍历哈夫曼树\n");
	TraverseTree(HT, n);
	printf("遍历哈夫曼编码\n");
	TraverseCoding(HC, n);
	printf("销毁哈夫曼树\n");
	Destroy(&HT, &HC, n);
	if (!HT && !HC) {
		printf("OK\n");
	}
	system("pause");
	return 0;
}

效果图

愿本篇文章能对大家有所帮助, 欢迎大家的评论和建议

相关阅读

[图像处理] Sobel边缘检测算法

完成时间：2017/1/23 我的实现结果如下：（图一为原图，图二为边缘检测结果）             关于Sobel算子（英文部分来源于Wikipedia

最小生成树之克鲁斯卡尔算法和普里姆算法

一、最小生成树简介   假设有一个很实际的问题：我们要在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，这个

遗传算法入门

原文地址为：遗传算法入门优化算法入门系列文章目录（更新中）：1. 模拟退火算法2. 遗传算法遗传算法 ( GA , Genetic Algorithm ) ，也称进

图的四种最短路径算法

本文总结了图的几种最短路径算法的实现：深度或广度优先搜索算法，弗洛伊德算法，迪杰斯特拉算法，Bellman-Ford算法1），深度或广度优先搜索

Bilateral Filters（双边滤波算法）原理及实现

双边滤波算法原理： 双边滤波是一种非线性滤波器，它可以达到保持边缘、降噪平滑的效果。和其他滤波原理一样，双边滤波也是采用加权平