霍夫曼樹和霍夫曼編碼

#include <stdio.h>
#include <stdlib.h>
#include <cstring>
using namespace std;

typedef struct HuffNode
{
	int weight;
	int parent, lchild, rchild;
}HuffNode, HuffTree;

void select(HuffTree* H, int m, int* s1, int* s2)
//在索引為0~m的元素中找到**parent為0**且權重最小的兩個元素的索引s1,s2
{
	//初始化兩個最小的元素min1,與min2, 且min1<min2
	int min1 = 500;
	int min2 = 1000;
	int min1_index, min2_index = 1000;
	for(int i = 0; i<=m; i++)
	{
		if(H[i].parent==0)    //這個條件很重要!!它使得前一次被選中的根節點在這次選擇中不會被選中
		{
			if(H[i].weight < min1)  //則目前元素<min1<min2, 應将min2用min1指派, 再将目前元素賦給min1
			{
			min2 = min1;
			min2_index = min1_index;
			min1 = H[i].weight;
			min1_index = i;
			continue;
			}
			if(H[i].weight < min2)   //則min1<目前元素<min2, 應将目前元素賦給min2
			{
			min2 = H[i].weight;
			min2_index = i;
			}
		}

	}
	*s1 = min1_index;
	*s2 = min2_index;

}

void display(HuffTree* H, int n)
{
	for(int i = 0; i<=n-1; i++)
	{
		printf("%d, weight:%d, parent:%d, lchild:%d, rchild:%d\n", i, H[i].weight, H[i].parent, H[i].lchild, H[i].rchild);
	}
}


void HuffmanCoding(int n, HuffTree* H, char** HuffCode, int w[])
{
	//n個葉子結點, n-1個非葉子結點.共2n-1個結點
	int m = 2*n-1;
	//為線性存儲結構配置設定空間
	H = (HuffNode *)malloc(sizeof(HuffNode)*m);  
	HuffNode* p = H;
	int * p_w = w;
	//對前n個葉子結點,其權重等于w[]中的元素值
	for(int i = 0; i<=n-1; i++)
	{
		//*p = {*p_w, 0,0,0};//這句話的作用等價于下面四句:
		H[i].weight = *p_w;
		H[i].parent = 0;
		H[i].lchild = 0;
		H[i].rchild = 0;

		p++;
		p_w++;
	}

	//對後n-1個非葉子結點,其權重0
	for(int i = n; i<=m-1; i++)
	{
		//*p = {0,0,0,0};

		H[i].weight = 0;
		H[i].parent = 0;
		H[i].lchild = 0;
		H[i].rchild = 0;
		p++;
	}
	//對n-1個非葉子結點
	for(int i = n; i<=m-1; i++)
	{
		int s1, s2 = 0;
		select(H, i-1, &s1, &s2);//在前i-1個元素中找到parent為0且權重最小的兩個元素的索引s1,s2
		H[i].lchild = s1;
		H[i].rchild = s2;
		H[i].weight = H[s1].weight + H[s2].weight;
		H[s1].parent = i;
		H[s2].parent = i;
		display(H, m);
	}

	display(H, m);

	//為二維霍夫曼編碼結構配置設定空間, 共n個元素, 每個元素是一個char*類型的指針
	HuffCode = (char**)malloc(sizeof(char*)*(n));
    	if(!HuffCode)
		printf("error to malloc for HUffCode.");

	//為每一個字元編碼首先預配置設定長度為n的空間,	
	char * codestring = (char*)malloc(sizeof(char)*n);
	codestring[n-1] = '\0';
	//從葉子結點到根逆向求每個字元的Huffmancode
	for(int i = 0; i<=n-1; i++)
	{
		int start_index = n-2;

		int c = i;   //initialize index of current node to index of the first leaf node
		int f = H[c].parent;  //initialize the inde of current parent
		while(f!=0)
		{
			if(H[f].lchild == c)
				codestring[start_index--] = '0';
			if(H[f].rchild == c)
				codestring[start_index--] = '1';
			c = f;
			f = H[c].parent;
		}

		//由于HuffCode的每一維都是一個指針, 是以, 這裡對每個指針配置設定長度為n-1-start_index的空間
		HuffCode[i]=(char *)malloc((n-1-start_index)*sizeof(char));
		strcpy(HuffCode[i], &(codestring[start_index+1]));

		printf("code string[%d] is:%s\n",i, &(codestring[start_index+1]));
	}
	free(codestring);
	codestring=NULL;

}




int main()

{
	int w[] = {5,29,7,8,14,23,3,11};
	HuffTree H;
	char **HuffCode;
	HuffmanCoding(8, &H, HuffCode, w);
}
           

運作結果:

注意:

霍夫曼編碼并不是唯一的,隻要平均帶權路徑長度最小就OK.