数据结构-自底向上的赫夫曼编码 （C语言代码）

解题思路:

    现学现用。

注意事项:

    见代码第114行。

参考代码:

#include<stdio.h>
#include<string.h>
#include<malloc.h>

typedef struct HTNode {
	int weight; // 权重
	int parent; // 父结点的下标
	int lchild, rchild; // 左右孩子的下标
} HTNode, *HuffTree;

typedef char **HuffCode; // 动态二维数组，存放哈夫曼编码

// 创建哈夫曼树 --------------------- 权重数组 - 字符数
void CreateHuffmanTree(HuffTree *htree, int *w, int n);

// 选择最小权重的两个字符 --- 当前结点数 - 权重最小的两个结点下标 
void SelectHTNode(HuffTree htree, int n, int *s1, int *s2);

// 哈夫曼编码 ------------------ 传入动态二维数组地址
void HuffmanCode(HuffTree htree, HuffCode *hcode, int n);

// 打印哈夫曼编码 ------------------- 字符数
void PrintHuffmanCode(HuffCode hcode, int n);

int main()
{
	int n, i, *w;
	HuffTree htree = NULL;
	HuffCode hcode = NULL;

	scanf_s("%d", &n); // 需编码字符数
	w = (int *)malloc(sizeof(int) * (n + 1)); // 权重数组，0号位置不用
	for (i = 1, w[0] = 0; i <= n; i++) {
		scanf_s("%d", w + i);
	}

	CreateHuffmanTree(&htree, w, n);
	HuffmanCode(htree, &hcode, n);
	PrintHuffmanCode(hcode, n);

	free(w);
	free(htree);
	return 0;
}


void CreateHuffmanTree(HuffTree *htree, int *w, int n) {

	if (n <= 1) return;

	int m = 2 * n - 1; // 最终哈夫曼树的结点数
	int i, s1, s2; // s1，s2为当前未建树最小权重结点的下标

	*htree = (HuffTree)malloc(sizeof(HTNode) * (m + 1)); // 0号位置不用
	
	// --- 初始化结点数据 --- //
	for (i = 1; i <= n; i++) {

		(*htree)[i].weight = w[i];
		(*htree)[i].parent = 0;
		(*htree)[i].lchild = 0;
		(*htree)[i].rchild = 0;
	}
	for (i = n + 1; i <= m; i++) {

		(*htree)[i].weight = 0;
		(*htree)[i].parent = 0;
		(*htree)[i].lchild = 0;
		(*htree)[i].rchild = 0;
	}

	for (i = n + 1; i <= m; i++) { // 进行n - 1次循环构建哈夫曼树

		SelectHTNode(*htree, i - 1, &s1, &s2);
		(*htree)[i].lchild = s1;
		(*htree)[i].rchild = s2;
		(*htree)[s1].parent = (*htree)[s2].parent = i;
		(*htree)[i].weight = (*htree)[s1].weight + (*htree)[s2].weight;
	}
}


void SelectHTNode(HuffTree htree, int n, int *s1, int *s2) {

	int i;

	for (i = 1, *s1 = 0; i <= n; i++) {

		if (!htree[i].parent && *s1 == 0) {

			*s1 = i;
			continue;
		}
		if (!htree[i].parent) { // 先找到两个未建树的结点

			*s2 = i;
			break;
		}
	}

	for (i = *s2; i <= n; i++) { // i从s2开始，第一次循环是s2与s1的比较，使得s1 < s2

		if (!htree[i].parent) {

			if (htree[i].weight < htree[*s1].weight) { // 如果比当前最小权重还小

				*s2 = *s1; // 使s1成为次小
				*s1 = i; // s1始终为最小
			}
			else if (htree[i].weight < htree[*s2].weight) { // 如果仅比次小的小

				*s2 = i; // i取代s2
			}
		}
	}

	// 进行到这，s1、s2分别为当前未建树的最小、次小权重的结点下标
	// 但观察题目，s1、s2不以权重值来划分左右孩子结点，而是下标。

	if (*s1 > *s2) { // 故一定要加上判断！！！

		int t = *s1;
		*s1 = *s2;
		*s2 = t;
	}
}


void HuffmanCode(HuffTree htree, HuffCode *hcode, int n) {

	*hcode = (HuffCode)malloc(sizeof(char *) * (n + 1)); // 0号位置不用
	char *cd = (char *)malloc(sizeof(char) * n); // 临时存放编码
	cd[n - 1] = '\0';

	for (int i = 1; i <= n; i++) {

		int start = n - 1; // 自下而上逆序编码
		int t = i; // 当前结点下标
		int par; // 父结点下标

		do {

			par = htree[t].parent;

			if (t == htree[par].lchild) {

				cd[--start] = '0';
			}
			if (t == htree[par].rchild) {

				cd[--start] = '1';
			}

			t = par;
			par = htree[t].parent;

		} while (par); // 自下而上直到根结点

		(*hcode)[i] = (char *)malloc(sizeof(char) * n - start); // 编码长度为start移动的长度
		strcpy_s((*hcode)[i], n - start, cd + start); // 编码从start开始
	}

	free(cd);
}


void PrintHuffmanCode(HuffCode hcode, int n) {

	for (int i = 1; i <= n; i++) {

		printf("%s\n", hcode[i]);
		free(hcode[i]);
	}

	free(hcode);
}