#include
#include
#include
#include
#include
#include
#include
using?namespace?std;
struct?HuffNode
{
	long?long?weight;
	int?parent?lchild?rchild;
};
struct?HuffTree
{
	HuffNode?*buffer;
	int?leafnum;??//?buffer的長度為2*leafnum?-?1
};
struct?BitBuffer
{
????int?buffer?count;
};

int?InitBitBuffer（?BitBuffer?&B?）?//?初始化一個位流緩沖區(qū)
{
????B.buffer?=?B.count?=?0;
????return?1;
}
bool?AppendBit（?BitBuffer?&B?int?bit）??//?向位流緩沖區(qū)中追加一位
{
	if?（bit==1）?B.buffer?=?（B.buffer?<????else?B.buffer?=?B.buffer?<????B.count++;
????return?B.count>=8;??//?如果已填充滿了8位，返回真
}
int?countfre（FILE?*fplong?long?*&cal）//進行文件字節(jié)頻率統(tǒng)計
{
	int?ch;
	while（（ch=fgetc（fp））!=EOF）
		cal[ch]++;
	return?1;
}
//創(chuàng)建哈夫曼樹?
int?CreateHuffTree（HuffTree?&T?int?leafnum?long?long?weight[]）
{
	//?初始化哈夫曼樹的空間
	T.buffer?=?new?HuffNode[2*leafnum-1];
	T.leafnum?=?leafnum;
	for?（int?i=0;?i	{
	????T.buffer[i].weight?=?weight[i];
	????T.buffer[i].parent?=?-1;
	????T.buffer[i].lchild?=?-1;
	????T.buffer[i].rchild?=?-1;
	}
	for?（int?i=0;?i	{//?選出兩棵根結(jié)點權(quán)值最小的樹
		int?m1=-1?m2=-1;
		for?（int?j=0;?j		{//?先判斷buffer[j]是否是根，如果不是根，則跳過
		????if?（T.buffer[j].parent==-1）
		????{
		????????if?（m1==-1?||?T.buffer[j].weight		????????{//m2為次小的，m1為最小的下標?
		????????????m2?=?m1;?m1?=?j;
		????????}
		????????else?if?（m2==-1?||?T.buffer[j].weight		????????????m2?=?j;
		????}
		}
		//?創(chuàng)建一個新的根結(jié)點，將選出的兩棵樹分別掛在新根結(jié)點的左右子上
		T.buffer[m1].parent?=?i+leafnum;
		T.buffer[m2].parent?=?i+leafnum;
		T.buffer[i+leafnum].parent?=?-1;
		if（m1		{
			T.buffer[i+leafnum].lchild?=?m1;
			T.buffer[i+leafnum].rchild?=?m2;
		}
		else
		{
			T.buffer[i+leafnum].lchild?=?m2;
			T.buffer[i+leafnum].rchild?=?m1;
		}
		T.buffer[i+leafnum].weight?=?T.buffer[m1].weight?+?T.buffer[m2].weight;
	}
	return?1;
}
//使用哈夫曼編碼對文件進行重編碼，并輸出新文件
int?coding（HuffTree?T?FILE?*fp?FILE?*outf）
{
	//把哈夫曼樹寫入文件
	for（int?i=0;i<511;i++）
	{
		int?byte=T.buffer[i].parent-256;
		fputc（byteoutf）;
	}
	//在第512個字節(jié)的位置加入空字節(jié)
	fputc（0outf）;
	//根據(jù)靜態(tài)三叉鏈構(gòu)成的哈夫曼樹的結(jié)構(gòu)，前buffer[0到leafnum-1]這leafnum個數(shù)據(jù)中存有葉子結(jié)點，根據(jù)讀到的數(shù)據(jù)調(diào)用對應(yīng)位置的buffer[]即可?
	int?ch;
	BitBuffer?B;//位流?
	InitBitBuffer（B）;
	stack?temp;//用來存放每個字節(jié)對應(yīng)的哈夫曼編碼?
	while（（ch=fgetc（fp））!=EOF）
	{//讀取fp文件中的字節(jié)?
		while（T.buffer[ch].parent!=-1）
		{
			if（ch==T.buffer[T.buffer[ch].parent].lchild）?temp.push（0）;
			else?if（ch==T.buffer[T.buffer[ch].parent].rchild）?temp.push（1）;
			ch=T.buffer[ch].parent;
		}
		while（!temp.empty（））
		{//位流轉(zhuǎn)換為字節(jié)流并輸出到文件中?
			if（AppendBit（Btemp.top（））==1）
			{
				fputc（B.bufferoutf）;
				InitBitBuffer（B）;
			}
			temp.pop（）;
		}
	}
	//處理buffer沒到8位的情況
	for（int?i=B.count;i<8;i++）
		B.buffer?=?B.buffer?<	fputc（B.bufferoutf）;
	//把B.count放入文件開始預(yù)留的位置
	fseek（outf511L0）;
	fputc（B.

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????7469??2007-01-11?19:12??哈夫曼壓縮算法.cpp

?????文件??????50176??2007-12-08?09:44??哈夫曼壓縮算法.doc

-----------?---------??----------?-----??----

????????????????57645????????????????????2