huffman.c

huffman编码的C语言实现

#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;
}