数据结构课程设计
报告
数据结构课程设计报告
压缩软件
一·问题描述
利用哈夫曼编码设计一个压缩软件，能对任何类型的文件进行哈夫曼编码，产生编码后的文件——压缩文件;也能对输入的压缩文件进行译码，生成压缩前的文件——解压文件。

二·基本要求
要求编码和译码的效率尽可能地高。

三·工具/准备工作
已学内容:哈夫曼树，哈夫曼树构造算法，哈夫曼编码，Huffman压缩算法。

需要的硬件设施与开发软件：一台计算机，并安装了Visual C++.
四·分析与实现
Huffman树中，叶子结点包含字符以及对应的字符频度（权值）
struct HTNode{ //压缩用Huffman树结点
unsigned long weight; //字符频度（权值）
unsigned int parent,lchild,rchild;
};
使用哈夫曼编码能够对文件进行压缩，由于字符的哈夫曼编码以比特为单位，而当将哈夫曼编码以压缩文件进行存储时，压缩文件最少以字节为单位进行存储，因此需要定义字节缓冲器，以便自动将比特转换为字节，定义如下：
struct Buffer{ //字节缓冲压缩用Huffman树
char ch; //字节
unsigned int bits; //实际比特数
};
定义哈夫曼树的抽象基类模板，实现建树，压缩，解压等功能
class HuffmanTree{ //Huffman树
public:
void Code(); //编码
void UnCode(); //译码
private:
HTNode HT[m+1]; //树结点表(HT[1]到HT[m])
char Leaf[n+1]; //叶结点对应字符(leaf[1]到leaf[n])
char *HuffmanCode[n+1]; //叶结点对应
编码(*HuffmanCode[1]到*HuffmanCode[n])
unsigned int count; //频度大于零的字符数
unsigned int char_index[n]; //字符对应在树结点表的下标(char_index[0]到char_index[n-1])
unsigned long size; //被压缩文件长度
FILE *infp,*outfp; //输入/出文件
Buffer buf; //字符缓冲
void Stat(); //统计字符出现频度并过滤掉频度为零的字符
//在HT[0]~HT[k]中选择parent为-1，树值最小的两个结点s1,s2
void Select(unsigned int k, unsigned int &s1, unsigned int &s2);
void Write(unsigned int bit); //向outfp中写入一个比特
void Write(unsigned int num,unsigned int k);//向outfp中写入k个比特
void WriteToOutfp(); //强行写入outfp
void Read(unsigned int &bit); //从infp中读出一个比特
void Read(unsigned int &num,unsigned int k);//从infp中读出k个比特
int NToBits(unsigned int num); //0~num之间的整数用二进位表示所需的最少位数
void CreateFromCodeFile(); //由编码文件中存储的树结构建立Huffman树
//由被压缩文件建立Huffman树,将树结构存入编码文件的文件头部中,并求每个字符的Huffman编码
void CreateFromSourceFile();
};
辅助函数Write用于一次向字符缓存中写入一比特，当缓冲器中的比特数为8（也就是一个字节）时，将缓存中的字符写入目标文件中，实现如下：
void HuffmanTree::Write(unsigned int bit)
//向outfp中写入一个比特
{
buf.bits++;
buf.ch=(buf.ch<<1)+bit;
if(buf.bits==8){ //缓冲区已满,写入outfp
fputc(buf.ch,outfp);。