#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 = ' ';
}
/*// 有多少个字符
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.nFrequency);
QueueInsert(i);
alphabet = 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.nBits[nBitCount] = cd.nBits[nBitCount];
}
code.nStartPos = cd.nStartPos;
}
for(i = 0; i < nSymbolsNum; i++)
{
printf("\n%c %d ", alphabet, node.nFrequency);
for(nBitCount = code.nStartPos; nBitCount < MAXBITS; nBitCount++)
{
printf("%d", code.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;
}
|
楼主
标题置顶
标题高亮
