将该文件翻译成 Huffman编码文件void zipHuffmanTree& HT HuffmanCode& HC vectorstring& code ofstream codeFilecodefiletxt; ifstream originFilepoemtxt; if !codeFile cout Cant find the file! endl; else char _d

//头文件 #include //输入输出流 #include //文件流 #include //位集合 #include //向量 #include //算法 #include <windows.h> //Windows系统API

using namespace std;

const int N = 256; //字符集大小

//哈夫曼树结点的定义 typedef struct { char data; //字符 int weight; //权重 int parent; //父亲结点下标 int lchild; //左孩子结点下标 int rchild; //右孩子结点下标 } HTNode, *HuffmanTree;

//哈夫曼编码表的定义 typedef struct { char data; //字符 string code; //编码 } HCNode, *HuffmanCode;

//用于比较两个结点的权重 bool cmp(HTNode a, HTNode b) { return a.weight < b.weight; }

//统计字符出现的频率 void frequencyRecord(HuffmanTree& HT) { ifstream file("binaryfile.txt"); //打开二进制编码文件 HT = new HTNode[2 * N - 1]; //动态分配哈夫曼树结点的存储空间 for (int i = 0; i < N; ++i) { HT[i].data = i; //ASCII码值即为下标 HT[i].weight = 0; //初始化权重为0 HT[i].parent = -1; //初始化父亲结点下标为-1 HT[i].lchild = -1; //初始化左孩子结点下标为-1 HT[i].rchild = -1; //初始化右孩子结点下标为-1 } char _data; cin.unsetf(ios::skipws); //取消忽略空格的设置 while (!file.eof()) { //读取文件直至文件结束 if (file.get(_data)) { //读取一个字符 ++HT[_data].weight; //对应字符的权重加1 } } file.close(); //关闭文件 sort(HT, HT + N, cmp); //根据权重从小到大排序 }

//构建哈夫曼树 void HuffmanTreeBuilding(HuffmanTree& HT) { int m = 2 * N - 1; //哈夫曼树的结点数 int i, j; for (i = N; i < m; ++i) { HT[i].weight = 0; //初始化权重为0 HT[i].parent = -1; //初始化父亲结点下标为-1 HT[i].lchild = -1; //初始化左孩子结点下标为-1 HT[i].rchild = -1; //初始化右孩子结点下标为-1 } for (i = 0; i < N - 1; ++i) { //构建哈夫曼树 int min1 = -1, min2 = -1; //记录权重最小的两个结点的下标 for (j = 0; j <= i; ++j) { //在前i个结点中找到权重最小的两个结点 if (HT[j].parent == -1) { //如果该结点没有父亲结点 if (min1 == -1 || HT[j].weight < HT[min1].weight) { //如果min1未被赋值或者当前结点的权重小于min1的权重 min2 = min1; //min2记录上一次的min1 min1 = j; //min1记录当前结点 } else if (min2 == -1 || HT[j].weight < HT[min2].weight) { //如果min2未被赋值或者当前结点的权重小于min2的权重 min2 = j; //min2记录当前结点 } } } HT[min1].parent = i + N; //最小权重的结点作为新结点的左孩子 HT[min2].parent = i + N; //次小权重的结点作为新结点的右孩子 HT[i + N].weight = HT[min1].weight + HT[min2].weight; //新结点的权重为左右孩子结点的权重之和 HT[i + N].lchild = min1; //左孩子结点为权重最小的结点 HT[i + N].rchild = min2; //右孩子结点为次小权重的结点 } }

//从叶子结点开始逆向求每个字符的哈夫曼编码 void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC) { HC = new HCNode[N]; //动态分配哈夫曼编码表结点的存储空间 char* cd = new char[N]; //动态分配求解哈夫曼编码的临时存储空间 cd[N - 1] = '\0'; //结束符 for (int i = 0; i < N; ++i) { //求解每个字符的哈夫曼编码 int start = N - 1; //从结束符开始向前求解 int c = i; //当前字符的下标 int f = HT[i].parent; //当前结点的父亲结点下标 while (f != -1) { if (HT[f].lchild == c) { //如果当前结点是父亲结点的左孩子 cd[--start] = '0'; //编码为0 } else { //如果当前结点是父亲结点的右孩子 cd[--start] = '1'; //编码为1 } c = f; //当前结点变为父亲结点 f = HT[f].parent; //父亲结点上移一层 } HC[i].data = HT[i].data; //记录当前字符 HC[i].code = &cd[start]; //保存当前字符的哈夫曼编码 } delete[] cd; //释放临时存储空间 }

//将源文件进行哈夫曼编码，写入编码文件 void zip(HuffmanTree& HT, HuffmanCode& HC, vector& code) { ofstream codeFile("codefile.txt"); //打开编码文件 ifstream originFile("poem.txt"); //打开源文件 if (!codeFile) { //如果打开编码文件失败 cout << "Can't find the file!" << endl; //输出错误信息 } else { char _data; cin.unsetf(ios::skipws); //取消忽略空格的设置 while (!originFile.eof()) { //读取文件直至文件结束 if (originFile.get(_data)) { //读取一个字符 for (int i = 1; i <= N; ++i) { //在哈夫曼编码表中查找对应的编码 if (HT[i].data == _data) { codeFile << HC[i]; //将编码写入编码文件 code.push_back(HC[i]); //保存编码 } } } } } codeFile.close(); //关闭编码文件 }

//将哈夫曼编码文件进行解码，写入解码文件 void unzip(HuffmanTree& HT, HuffmanCode& HC, vector& code) { ofstream decodeFile("decodefile.txt"); //打开解码文件 if (!decodeFile) { //如果打开解码文件失败 cout << "Can't find the file!" << endl; //输出错误信息 } else { vector::iterator v = code.begin(); //迭代器 while (v != code.end()) { //读取编码直至编码结束 for (int i = 1; i <= N; ++i) { //在哈夫曼编码表中查找对应的字符 if (HC[i] == *v) { decodeFile << HT[i].data; //将字符写入解码文件 } } v++; } } decodeFile.close(); //关闭解码文件 }

//将源文件以一个字节进行二进制编码，写入二进制编码文件 void binaryCode() { ofstream binaryFile("binaryfile.txt"); //打开二进制编码文件 ifstream originFile("poem.txt"); //打开源文件 originFile.seekg(0); //将读取指针指向文件开头 if (!originFile) { //如果打开源文件失败 cout << "Can't find the file!" << endl; //输出错误信息 } else { char _data; cin.unsetf(ios::skipws); //取消忽略空格的设置 while (!originFile.eof()) { //读取文件直至文件结束 if (originFile.get(_data)) { //读取一个字符 bitset<8> data(_data); //将字符转换为8位二进制数 binaryFile << data; //将二进制数写入二进制编码文件 } } originFile.close(); //关闭源文件 } }

//主函数 int main() { system("color 02"); //设置控制台字体颜色 cout << "" << endl; cout << "哈夫曼编码解码器" << endl; cout << "" << endl; Sleep(1000); //延时1秒 HuffmanTree HT; //哈夫曼树 HuffmanCode HC; //哈夫曼编码表 vector code; //编码 cout << "\n\n\n需要进行编码的文件内容为：\n\n"; system("more poem.txt"); //显示源文件 Sleep(2000); //延时2秒 cout << "\n\n正在打开poem.txt进行二进制编码......" << endl; Sleep(2000); //延时2秒 binaryCode(); //进行二进制编码 cout << "\n\n二进制编码内容为：" << endl; Sleep(2000); //延时2秒 system("more binaryfile.txt"); //显示二进制编码文件 Sleep(2000); //延时2秒 cout << "\n\n正在统计字符权重......" << endl; Sleep(2000); //延时2秒 frequencyRecord(HT); //统计字符出现的频率 HuffmanTreeBuilding(HT); //构建哈夫曼树 HuffmanCoding(HT, HC); //求解每个字符的哈夫曼编码 cout << "\n\n写入编码文件......" << endl; Sleep(2000); //延时2秒 zip(HT, HC, code); //将源文件进行哈夫曼编码，写入编码文件 cout << "\n\n编码结果为：" << endl; system("more codefile.txt"); //显示编码文件 Sleep(2000); //延时2秒 cout << "\n\n解码编码文件......" << endl; Sleep(2000); //延时2秒 unzip(HT, HC, code); //将哈夫曼编码文件进行解码，写入解码文件 cout << "\n\n解码结果为：" << endl; Sleep(2000); //延时2秒 system("more decodefile.txt"); //显示解码文件 cout << "\n\n编码前占用字节空间：" << endl; Sleep(1000); //延时1秒 ifstream file_before("binaryfile.txt", ios::binary | ios::ate); //打开二进制编码文件 auto size_before = file_before.tellg(); //获取文件大小 cout << size_before << endl; //输出文件大小 file_before.close(); //关闭文件 cout << "\n\n编码后占用字节空间：" << endl; Sleep(1000); //延时1秒 ifstream file_after("codefile.txt", ios::binary | ios::ate); //打开编码文件 auto size_after = file_after.tellg(); //获取文件大小 cout << size_after << endl; //输出文件大小 file_after.close(); //关闭文件 Sleep(1000); //延时1秒 cout << "\n\n压缩率为：" << (static_cast(size_before - size_after)) / size_before * 100.0 << "%" << endl; //计算压缩率 Sleep(100000); //延时100秒 return 0; //程序结束