哈夫曼压缩解压-数据结构设计报告

附录：

// stdafx.h

#include //输入输出头文件 #include //文件操作的类和方法 #include //队列容器 using namespace std;

const int leaf = 256; //最多可能出现的不同字符数 const long MAX = 99999999; //表示无穷大

//huffman树的结点结构体 typedef struct HTnode { long weight; //记录结点的权值 int parent; //记录结点的双亲结点位置 int lchild; //结点的左孩子 int rchild; //结点的右孩子 int *code; //记录该结点的huffman编码 int codelen; //记录该结点huffman编码的长度

//初始化结点，令其权值为无穷大，无双亲及左右孩子 HTnode() { weight = MAX; parent = -1; lchild = -1; rchild = -1; codelen = 0; }

}HTnode;

//##############################################################

//huffmanTree.h

//huffman树类

class huffmanTree {

public:

huffmanTree();

virtual ~huffmanTree();

bool count(char *input); //压缩时统计各字符出现的次数，将其写入对应结点的权值 void create(); //压缩时根据各结点的权值构造huffman树 void code(); //压缩时，利用建好的huffman树计算每个字符的huffman编码

void printcode(); //列出每个字符的huffman编码 void addbit(int bit); //压缩时对一个未满8个bit的byte中加入一个bit

void resetbyte(); //将byte清空 bool compress(char *input, char *output); //压缩函数 成功执行返回 true 失败 false

bool decompress(char *input, char *output); //恢复函数 成功执行返回 true 失败 false

void compare(char *input, char *output); //将原文件与压缩后的文件比较 void compare2(char *input, char *output); //将原文件与恢复后的文件比较 private: int root; //记录根结点的位置 int leafnum; //记录不同字符的个数 HTnode HT[leaf*2-1]; //HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1 char byte; //压缩文件时用来缓冲bit的变量 int bitsnum; //byte中bit的个数 int lacknum; //压缩到最后byte中的bit不满8个时填充的0的个数 };

//##############################################################

//huffmanTree.cpp

#include \

#include \

////////////////////////////////////////////////////////////////////// // Construction/Destruction

//////////////////////////////////////////////////////////////////////

huffmanTree::huffmanTree() {

//初始化成员变量 root = 0; leafnum = 0; byte = 0; bitsnum = 0; lacknum = 0; }

huffmanTree::~huffmanTree() {

for(int i=0; i

//统计各字符出现的次数

bool huffmanTree::count(char *input)

{ ifstream ifs; char c;

ifs.open(input,ios::binary); if(!ifs){ cout << \无法打开文件 \ return false; }

while(ifs.get(c)){ if(HT[c+128].weight==MAX){ //若该字符是第一次出现，先初始化权值 HT[c+128].weight = 0; leafnum++; } HT[c+128].weight++; //权值+1 }

ifs.close(); return true; }

//选权值最小的两棵树组成新的数 void huffmanTree::create() {

for(int i=leaf; i<2*leaf-1; i++) { int loc1=-1, loc2=-1; for(int j=0; jloc2 ? loc2 : loc1; HT[i].rchild = loc1>loc2 ? loc1 : loc2; HT[loc1].parent = i; HT[loc2].parent = i; root = i; } }

//列出每个字符的huffman编码

void huffmanTree::printcode() {

for(int i=0; i

//压缩时，利用建好的huffman树计算每个字符的huffman编码 void huffmanTree::code() { for(int i=0; i=0; j--) { //从后往前找，记录结点的huffman编码 if(loc==HT[HT[loc].parent].lchild) HT[i].code[j] = 0; else HT[i].code[j] = 1; loc = HT[loc].parent; } } }

//压缩时对一个未满8个bit的byte中加入一个bit void huffmanTree::addbit(int bit) {

if(bit == 0) byte = byte << 1; //若新增的bit为0，则直接将byte按位左移 else byte = ((byte << 1) | 1); //若新增的bit为1，先将byte按位左移，再与1按位或运算

bitsnum++;

}

//将byte清空

void huffmanTree::resetbyte() {

byte = 0; bitsnum = 0; }

//压缩函数 成功执行返回 true 失败 false

bool huffmanTree::compress(char *input, char *output) {

if( !count(input) ) return false;

create(); code(); ifstream ifs; ofstream ofs;

ifs.open(input,ios::binary); ofs.open(output,ios::binary); char c; if(!ifs) { cout << \无法打开文件 \ return false; }

if(!ofs) { cout << \无法打开文件 \ return false; }

ofs.put(0); //预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数 ofs.put(root-384); //将根节点的位置-384写入（为使该值不超过char的最大表示范围）

for(int i=0; i

while(ifs.get(c)) { //将字符的huffman编码并加入byte中 int tmp = c+128;