#include #include #include /队列容器using namespace std;const int leaf = 256;/最多可能出现的不同字符数const long MAX = 99999999;/表示无穷大typedef struct HTnodelong 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;class huffmanTree public:huffmanTree();virtual huffmanTree();bool count(char *input);/统计各字符出现的次数，将其写入对应结点的权值void create();/构造huffman树void code();/计算每个字符的huffman编码void addbit(int bit);/压缩时对一个未满8个bit的byte中加入一个bitvoid resetbyte();/将byte清空bool compress(char *input, char *output);/压缩函数 成功执行返回 true 失败 falsebool decompress(char *input, char *output);/解压函数 成功执行返回 true 失败 falsevoid compare(char *input, char *output);/将原文件与压缩后的文件比较private:int root;/记录根结点的位置int leafnum;/记录不同字符的个数HTnode HTleaf*2-1;/HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1char byte;/压缩文件时用来缓冲bit的变量int bitsnum;/byte中bit的个数int lacknum;/压缩到最后byte中的bit不满8个时填充的0的个数;huffmanTree:huffmanTree()/初始化成员变量root = 0;leafnum = 0;byte = 0;bitsnum = 0;lacknum = 0;huffmanTree:huffmanTree()for(int i=0; ileaf; i+)if(HTi.codelen != 0)delete HTi.code;/统计各字符出现的次数bool huffmanTree:count(char *input)ifstream ifs;char c;ifs.open(input,ios:binary);if(!ifs)cout 无法打开文件 input ! endl;return false;while(ifs.get(c)if(HTc+128.weight=MAX)/若该字符是第一次出现，先初始化权值HTc+128.weight = 0;leafnum+;HTc+128.weight+;/权值+1ifs.close();return true;/选权值最小的两棵树组成新的数void huffmanTree:create()for(int i=leaf; i2*leaf-1; i+)int loc1=-1, loc2=-1;for(int j=0; ji; j+)if(HTj.parent != -1)continue;if(loc1=-1 | HTj.weight HTloc1.weight)loc2 = loc1;loc1 = j;else if(loc2=-1 | HTj.weight loc2 ? loc2 : loc1;HTi.rchild = loc1loc2 ? loc1 : loc2;HTloc1.parent = i;HTloc2.parent = i;root = i;/计算每个字符的huffman编码void huffmanTree:code()for(int i=0; i=0; j-)/从后往前找，记录结点的huffman编码if(loc=HTHTloc.parent.lchild)HTi.codej = 0;elseHTi.codej = 1;loc = HTloc.parent;/压缩时对一个未满8个bit的byte中加入一个bitvoid huffmanTree:addbit(int bit)if(bit = 0)byte = byte 1;/若新增的bit为0，则直接将byte按位左移elsebyte = (byte 1) | 1);/若新增的bit为1，先将byte按位左移，再与1按位或运算bitsnum+;/将byte清空void huffmanTree:resetbyte()byte = 0;bitsnum = 0;/压缩函数 成功执行返回 true 失败 falsebool 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 无法打开文件 input ! endl;return false;if(!ofs)cout 无法打开文件 output ! endl;return false;ofs.put(0);/预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数ofs.put(root-384);/将根节点的位置-384写入（为使该值不超过char的最大表示范围）for(int i=0; ileaf*2-1; i+)/写入每个结点的双亲结点位置if(HTi.parent=-1)/若该节点没有双亲结点，则写入127(一个字节所能表示的最大值)ofs.put(127);else/否则将双亲结点的位置-384再写入（为使该值不超过char的最大表示范围）ofs.put(HTi.parent-384);while(ifs.get(c)/将字符的huffman编码并加入byte中int tmp = c+128;for(int i=0; iHTtmp.codelen; i+)addbit(HTtmp.codei);if(bitsnum=8)/若byte已满8位，则输出该byte并将byte清空ofs.put(byte);resetbyte();if(bitsnum!=0)/处理最后未满8个字符的byte，用0填充并记录填充的个数for(int i=bitsnum; i8; i+)addbit(0);lacknum+;ofs.put(byte);resetbyte();ofs.seekp(0,ios:beg);/将写指针移动到文件开头ofs.put(lacknum);/写入最后一个字节缺失的bit个数ifs.close();ofs.close();return true;/解压函数 成功执行返回 true 失败 falsebool huffmanTree:decompress(char *input, char *output)queue q;char c;ifstream ifs;ofstream ofs;ifs.open(input,ios:binary);ofs.open(output,ios:binary);if(!ifs)cout 无法打开文件 input ! endl;return true;if(!ofs)cout 无法打开文件 output ! endl;return false;