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

#define TRUE 1
#define FALSE 0

// 編碼的最大位數
#define MAXBITS		50
// 最大的字符數
#define MAXSYMBS	MAXBITS
// 樹中的最大節點
#define MAXNODES	2 * MAXSYMBS-1

struct CodeType {
	int nBits[MAXBITS];
	int nStartPos;
};

struct NodeType {
	int nFrequency;
	int nParent;
	int iSLeft;
};

// 隊列的插入刪除處理
void QueueInsert(int nWhich);
int QueueDelete(void);

// 定義全局變量
struct NodeType node[MAXNODES];
// 隊列最初位空
int rootnodes = -1;

void main(void)
{
	struct CodeType cd, code[MAXSYMBS];
	int i;
	int nSymbolsNum;
	int nBitCount;
	int nNextNode;
	int nLeftNode, nRightNode;
	int root;
	int thisnode;
	char symbol, alphabet[MAXSYMBS];

	// 清空字符數組
	for(i = 0; i < MAXSYMBS; i++)
	{
		alphabet[i] = ' ';
	}

	/*// 有多少個字符
	printf("Please input char's count\n");
	scanf("%d", &nSymbolsNum);

	printf("Please input char and frequencies\n");
	// 得到數據和每個字符的頻率
	for(i = 0; i < nSymbolsNum; i++)
	{
		scanf("%s%d", &symbol, &node[i].nFrequency);
		QueueInsert(i);
		alphabet[i] = symbol;
	}*/

	//構造信源數據
	nSymbolsNum = 3;
	alphabet[0] = 'a';
	node[0].nFrequency = 8;
	QueueInsert(0);
	alphabet[1] = 'b';
	node[1].nFrequency = 2;
	QueueInsert(1);
	alphabet[2] = 'c';
	node[2].nFrequency = 5;
	QueueInsert(2);

	// 形成Huffman樹
	for(nNextNode =  nSymbolsNum;
		nNextNode < 2 * nSymbolsNum - 1;
		nNextNode ++)
	{
		nLeftNode = QueueDelete();
		nRightNode = QueueDelete();
		
		// 形成新的樹，作為子節點
		node[nLeftNode].nParent = nNextNode;
		node[nRightNode].nParent = nNextNode;
		node[nLeftNode].iSLeft = TRUE;
		node[nRightNode].iSLeft = FALSE;
	
		// 父節點的頻率是兩個子節點頻率之和
		node[nNextNode].nFrequency = 
			node[nLeftNode].nFrequency + node[nRightNode].nFrequency;
		
		//插入節點
		QueueInsert( nNextNode);
	}

    // 根節點
	root = QueueDelete();
	// 根據樹進行編碼
	for(i = 0; i < nSymbolsNum; i++)
	{
		// 搜索的初始點
		cd.nStartPos = MAXBITS;

		// 對樹進行遍歷，對內容進行編碼
		thisnode = i;
		while(thisnode != root)
		{
			--cd.nStartPos;
			cd.nBits[cd.nStartPos] = node[thisnode].iSLeft ? 0 : 1;
			thisnode = node[thisnode].nParent;
		}

		// 內容拷貝
		for(nBitCount = cd.nStartPos; nBitCount < MAXBITS; nBitCount++)
		{
			code[i].nBits[nBitCount] = cd.nBits[nBitCount];
		}
		code[i].nStartPos = cd.nStartPos;
	}

	for(i = 0; i < nSymbolsNum; i++)
	{
		printf("\n%c %d ", alphabet[i], node[i].nFrequency);
		for(nBitCount = code[i].nStartPos; nBitCount < MAXBITS; nBitCount++)
		{
			printf("%d", code[i].nBits[nBitCount]);
		}
		printf("\n");
	}
}
// 將節點插入到隊列里
void QueueInsert(int nWhich)
{
	int thisnode, previous;
	// 隊列是否為空
	if(rootnodes == -1)
	{
		// 空隊列
		node[nWhich].nParent = -1;
		rootnodes = nWhich;
	}
	else
	{
		thisnode = rootnodes; 
		previous = -1;
		//搜索大的節點
		while((thisnode != -1) && 
			(node[thisnode].nFrequency < node[nWhich].nFrequency))
		{
			previous = thisnode;
			thisnode = node[thisnode].nParent;
 		}

		// 連接到第一個大的節點
		node[nWhich].nParent = thisnode;
		if(previous != -1)
		{
			// 拷貝
			node[previous].nParent = nWhich;
		}
		else
		{
			// 插入到開始位置
			rootnodes = nWhich;
		}
	}
}

//從優先隊列里去掉第一個結點
int QueueDelete(void)
{
	int thisnode = rootnodes;
	rootnodes = node[thisnode].nParent;
	return thisnode;
}