#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?）?//?初始化一個位流緩沖區
{
????B.buffer?=?B.count?=?0;
????return?1;
}
bool?AppendBit（?BitBuffer?&B?int?bit）??//?向位流緩沖區中追加一位
{
	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）//進行文件字節頻率統計
{
	int?ch;
	while（（ch=fgetc（fp））!=EOF）
		cal[ch]++;
	return?1;
}
//創建哈夫曼樹?
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	{//?選出兩棵根結點權值最小的樹
		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;
		????}
		}
		//?創建一個新的根結點，將選出的兩棵樹分別掛在新根結點的左右子上
		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個字節的位置加入空字節
	fputc（0outf）;
	//根據靜態三叉鏈構成的哈夫曼樹的結構，前buffer[0到leafnum-1]這leafnum個數據中存有葉子結點，根據讀到的數據調用對應位置的buffer[]即可?
	int?ch;
	BitBuffer?B;//位流?
	InitBitBuffer（B）;
	stack?temp;//用來存放每個字節對應的哈夫曼編碼?
	while（（ch=fgetc（fp））!=EOF）
	{//讀取fp文件中的字節?
		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（））
		{//位流轉換為字節流并輸出到文件中?
			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放入文件開始預留的位置
	fseek（outf511L0）;
	fputc（B.

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

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

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

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

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