[数据结构与算法]哈夫曼编码C++实现

#include<iostream>
#include<iomanip>
using namespace std;
#pragma warning (disable: 4996)

类型定义

typedef struct {//哈夫曼树
	int weight;//权值
	int lch, rch, parent;//左右孩子，父结点
}HTNode,*HuffmanTree;

二级指针建立一个哈夫曼编码表

typedef char** HuffmanCode;

void CreatHuffmanTree(HuffmanTree& HT, int n) {
    //构造哈夫曼树
	if (n <= 1)return;
	int m = 2 * n - 1;//数组2n-1个元素
	HT = new HTNode[m + 1];//0号不用
	for (int i = 1; i <= m; i++) {
		//将2n-1个元素的lch，rch，parent设置为0
		HT[i].lch = 0; HT[i].rch = 0; HT[i].parent = 0;
	}
	for (int i = 1; i <= n; i++)
		cin >> HT[i].weight;//输入前n个元素的weight
	//初始化结束
	//建立哈夫曼树
	for (int i = n + 1; i <= m; i++) {
		//合并产生n-1个结点，构造哈夫曼树
		int s1, s2;
		Select(HT, i - 1, s1, s2);//找到i以前的最小的俩下标，用s1，s2返回
		HT[s1].parent = i;
		HT[s2].parent = i;
		//parent的初值为0，如果parent不为0，则说明已经构造成树了，可以用来Select函数判定
		HT[i].lch = s1;
		HT[i].rch = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}

}

Select函数是哈夫曼算法的重要过程，找到未成树的叶子结点的两个最小权值结点，并用s1，s2返回下标

void Select(HuffmanTree HT, int n, int& s1, int& s2) {
	s1 = s2 = 0;
	for (int i = 1; i <= n; i++) {
		if (HT[i].parent == 0) {
			s1 = i;
			break;
		}

	}//找一个未归树的结点开始判断

	for (int i = 1; i <= n; i++) {
		if (HT[i].parent == 0 && HT[i].weight < HT[s1].weight)
			s1 = i;
	}
	for (int i = 1; i <= n; i++) {
		if (HT[i].parent == 0 && i != s1) {//排除掉s1
			s2 = i;
			break;
		}
	}//找一个未归树的结点开始判断
	for (int i = 1; i <= n; i++) {
		if (HT[i].parent == 0 && HT[i].weight < HT[s2].weight && i != s1)//排除掉s1
			s2 = i;
	}
}

构造哈夫曼编码

从叶子一步一步向上回溯，找到自己的parent，然后得到自己是左还是右孩子

void CreateHuffmanCode(HuffmanTree&HT,HuffmanCode&HC,int n) {
	//从叶子到根逆向求每个字符的哈夫曼编码，储存在编码表HC中
	HC = new char* [n + 1];//分配n个字符编码的头指针矢量，第0个不放
	char* cd = new char[n];
	cd[n - 1] = '\0';
	for (int i = 1; i <= n; i++) {//i为初始为叶子，后面为当前回溯结
		int start = n - 1, c = i, f = HT[i].parent;
		while (f != 0) {
			--start;
			if (HT[f].lch == c)
				cd[start] = '0';//左0
			else cd[start] = '1';//右1
			c = f; f = HT[f].parent;
			//向上回溯一级
		}
		HC[i] = new char[n - start];//分配该编码所需要的空间
		strcpy(HC[i], &cd[start]);//从start开始复制
	}
	delete cd;
}

打印哈夫曼树表，setw是#include<iomanip>里面的，用来方便输出

void PrintHuffman(HuffmanTree HT, int n) {
	cout << "index weight parents lchild rchild" << endl;
	cout << left;
	for (int i = 1; i <= 2 * n - 1; i++) {
		cout << setw(6) << i << " ";
		cout << setw(6) << HT[i].weight << " ";
		cout << setw(6) << HT[i].parent << " ";
		cout << setw(6) << HT[i].lch << " ";
		cout << setw(6) << HT[i].rch << " " << endl;
	}
}

打印编码表

void PrintHuffmancode(HuffmanCode&HC,int n) {
	cout << "每个叶子的哈夫曼编码为" << endl;
	for (int i = 1; i <= n; i++) {
		cout << HC[i] << endl;
	}
}

测试函数test01

void test01() {
	HuffmanTree HT;
	HuffmanCode HC;
	int n=0;
	cin >> n;

	CreatHuffmanTree(HT, n);
	PrintHuffman(HT, n);
	CreateHuffmanCode(HT, HC, n);
	PrintHuffmancode(HC, n);

	//7 40 30 15 5 4 3 3

}

?结果

?