哈夫曼压缩算法（源代码 实现报告）

使用哈夫曼算法实现的文件压缩（源代码+实现报告）

#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 << 1） | 1;//如果bit为1buffer左移一位并与1位或，也就是最右面添1
    else B.buffer = B.buffer << 1;
    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 << 1;//最后追加0
	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