哈夫曼树、哈夫曼编码

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

#define Max 100
 
typedef struct HTNode{
	int weight;
	int parent, rchild, lchild;
}HTNode, *HuffmanTree;

// 指向指针类型的 指针 
typedef char* *HuffmanCode;

void Select(HuffmanTree HT, int n, int &s1, int &s2){
	int min;
	//找第一个最小值
	for(int i = 1; i <= n; i++){
		if (HT[i].parent == 0){
			min = i;
			break;
		}
	}
	for(int i = min + 1; i <= n; i++){
		if(HT[i].parent == 0 && HT[i].weight < HT[min].weight){
			min = i;
		}	
	}
	s1 = min; //第一个最小值给s1
	
	//找第二个最小值
	for(int i = 1; i <= n; i++){
		if(HT[i].parent == 0 && i != s1){
			min = i;
			break;
		}
	}
	for (int i = min + 1; i <= n; i++){
		if(HT[i].parent == 0 && HT[i].weight < HT[min].weight && i != s1){
			min = i;
		}	
	}
	s2 = min; //第二个最小值给s2
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int w[], int n){
	int i;

	if(n <= 1){
		return;
	}
	// n 个叶子结点的哈夫曼树共 2*n - 1 个结点 
	int m = 2*n - 1; 
	// 多分配一个空间，0 号单元未使用 
	HT = (HTNode*) malloc((m + 1)*sizeof(HTNode));
	
	// HuffTree数组初始化为 0.
	for(i = 1; i <= n; i++){
		HT[i].weight = w[i];
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0; 
	} 

	// 构建哈夫曼树.
	for(i = n + 1; i <= m; i++){
	    int s1, s2;
	    // 在 HT[1 ~ i-1]选择 parent 为 0 且 weight 最小的两个结点，其序号分别为 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;
	} 
	
	// 从 叶子到根逆向 求每个字符的哈夫曼编码 
	
	// 分配 n 个字符编码的头指针向量 
	HC = (HuffmanCode) malloc( (n + 1) * sizeof(char*) );
	// 分配求编码的工作空间 
	char* temp = (char*) malloc( n * sizeof(char) );
	// 编码结束符 
	temp[n - 1] = '\0';
	// 每一个字符求哈夫曼编码 
	int start, pos, parent;
	for(i = 1; i <= n; i++){
		start = n - 1;
		pos = i;
		parent = HT[i].parent;
		
		while(parent != 0){
			if(HT[parent].lchild == pos){
				// 左子树：置 0 
				temp[--start] = '0';
			}
			else{
				// 右子树：置 1 
				temp[--start] = '1';
			}
			pos = parent;
			parent = HT[parent].parent;
		}
		// 为每一个字符编码分配空间，分配的空间大小不同 
		HC[i] = (char*) malloc( (n - start) * sizeof(char) );
		// 从 temp 复制编码到 HC 
		strcpy(HC[i], &temp[start]);
	}
	// 释放工作空间 
	free(temp);
}

// 输出哈夫曼树、哈夫曼编码 
void printfHTAndHC(HuffmanTree HT, HuffmanCode HC, int n){
	for(int i = 1; i <= 2*n - 1; i++){
		printf("i = %d, weight = %d, parent = %d, lchild = %d, rchild = %d\n",
		 i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
	}
	
	for(int i = 1; i <= n; i++){
		printf("%d 的 哈夫曼编码为：%s\n",HT[i].weight, HC[i]);
	}
}

int main() {
	
	int n;
	int w[Max];
	HuffmanTree HT;
	HuffmanCode HC; 
	 
	printf("请输入叶子结点个数：");
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		printf("请输入第 %d 个叶子结点的权值：", i);
		scanf("%d", &w[i]);
	}
	
	HuffmanCoding(HT, HC, w, n);
	
	printfHTAndHC(HT, HC, n);
	
	return 0;
}