ヘフマンツリーのコード実装

そのストレージ構造を定義します.典型的なツリーは、重み値が1つ増えただけです.

typedef struct
{
	int weight;
	int parent, lchild, rchild;
}HTNode, *HuffmanTree;

typedef char **HuffmanCode;

HuffmanCodeは、リーフノードの最終的な符号化結果を保存する文字列配列です.
 
ストレージスペースはいくらですか?前章で述べたヘフマンの木を構築する過程は法則を見つけることができ,n個の葉の結点が構築したヘフマンの木には2 n−1個の結点があり,これが私たちが割り当てる空間である.
 

int m = 2 * n - 1;
*HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));// ，0 

関数のインタフェース形式は次のとおりです.

bool HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, int *w, int n)

HTは最終的に構築されたヘフマンツリーであり、出力パラメータであり、HCも出力関数であり、文字列配列であり、最終的な符号化を出力する.Wはn個のリーフノードの重み値を格納し,もちろんいずれも0より大きい整数であり,nはリーフノードの個数であり,最後の2つは入力パラメータである.
ヘフマンツリーを構築するプロセスコードは簡単です.

// 
	for (i = n + 1; i <= m; i++)
	{
		if (!Select(*HT, i - 1, &s1, &s2)) return false;
		(*HT)[s1].parent = i;
		(*HT)[s2].parent = i;
		(*HT)[i].lchild = s1;
		(*HT)[i].rchild = s2;
		(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
	}

select関数はHT[1...nEnd]からparentが0であり、weightが最小の2つのノードを選択し、シーケンス番号はそれぞれs 1とs 2によって返され、その実現は以下の通りである.

static bool Select(HuffmanTree HT, int nEnd, int *s1, int *s2)
{
	int i = 0;
	int nComp = 0;
	
	nComp = MAX;
	*s1 = MAX;
	*s2 = MAX;

	// ， s1
	for (i = 1; i <= nEnd; i++)
	{
		if ((HT[i].weight < nComp) && (HT[i].parent == 0))
		{
			nComp = HT[i].weight;
			*s1 = i;
		}
			
	}

	// ， s2
	nComp = MAX;

	for (i = 1; i <= nEnd; i++)
	{
		if ((HT[i].weight < nComp) && (i != *s1) && (HT[i].parent == 0))
		{
			nComp = HT[i].weight;
			*s2 = i;
		}
			
	}
	if ((*s1 == MAX) || (*s2 == MAX))
	{
		return false;
	}
	return true;
}

符号化の結果はHCに保存されており,葉から根まで符号化を求めて出力すると順方向になる逆保存形式を容易に採用するためである.

for (i = 1; i <= n; i++)
	{
		start = n - 1;
		for (c = i, f = (*HT)[i].parent; f != 0; c = f, f = (*HT)[f].parent)
		{
			// 0 1
			if ((*HT)[f].lchild == c)
			{
				cd[--start] = '0';
			}
			else
			{
				cd[--start] = '1';
			}
		}
		(*HC)[i] = (char *)malloc((n - start));
		strcpy((*HC)[i], &cd[start]);
	}

 
コードダウンロードアドレス:
http://download.csdn.net/detail/pony_maggie/8209175
または
https://github.com/pony-maggie/HuffmanCode