Question

一、实验题目：用哈夫曼编码实现文件压缩用C++实现

Answer 1

这是我的实验报告： http://student.csdn.net/space.php?uid=395622&do=blog&id=51206 /** * @brief 哈夫曼编码 * @date 2010-11-30 */ #include <iostream> #include <string> #include <queue> #include <map> using namespace std; /** * @brief 哈弗曼结点 * 记录了哈弗曼树结点的数据、权重及左右儿子 */ struct HTNode { char data; HTNode *lc, *rc; int w; /** 节点构造函数 */ HTNode(char _d, int _w, HTNode *_l = NULL, HTNode *_r = NULL) { data = _d; w = _w; lc = _l; rc = _r; } /** 节点拷贝构造函数 */ HTNode(const HTNode &h) { data = h.data; lc = h.lc; rc = h.rc; w = h.w; } /** 用于优先队列比较的运算符重载 */ friend bool operator < (const HTNode &a, const HTNode &b) { return a.w > b.w; } }; /** 哈弗曼树叶子节点数、各叶子结点数据及权重 */ /** 权值从Lolita小说中抽样取出 */ const char ch[] = { 10, 32, 33, 37, 40, 41, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 63, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 161, 164, 166, 168, 170, 173, 174, 175, 176, 177, 180, 186, 255, '\r', '\0' }; const int fnum[] = { 2970, 99537, 265, 1, 496, 494, 9032, 1185, 5064, 108, 180, 132, 99, 105, 82, 64, 62, 77, 126, 296, 556, 548, 818, 443, 543, 435, 225, 271, 260, 797, 3487, 158, 50, 1053, 589, 498, 332, 316, 61, 276, 724, 855, 54, 293, 543, 11, 185, 11, 25, 26, 42416, 7856, 12699, 23670, 61127, 10229, 10651, 27912, 32809, 510, 4475, 23812, 13993, 34096, 38387, 9619, 500, 30592, 30504, 42377, 14571, 4790, 11114, 769, 10394, 611, 1, 4397, 12, 71, 117, 1234, 81, 5, 852, 1116, 1109, 1, 3, 1, 2970 }; const int n = 91; /** 优先队列 */ priority_queue<HTNode> pq; /** 哈弗曼编码映射 */ map<string, char> dcode; map<char, string> ecode; /** 根节点以及总权重+边长 */ HTNode *root; int sum = 0; /** 初始化叶节点，并加入到优先队列中 */ void Init() { for(int i = 0; i < n; i++) { HTNode p(ch[i], fnum[i]); pq.push(p); } } /** 建立哈夫曼树 */ void CreateHT() { HTNode *lmin, *rmin; /** 当队列中不止一个元素时 */ while(!pq.empty() && 1 != pq.size()) { /** 取队首两个元素（权值最小） */ lmin = new HTNode(pq.top()); pq.pop(); rmin = new HTNode(pq.top()); pq.pop(); /** 合并元素重新入队 */ HTNode p(0, lmin->w + rmin->w, lmin, rmin); pq.push(p); } if(!pq.empty()) { /** 根节点 */ root = new HTNode(pq.top()); pq.pop(); } } /** 创建哈夫曼编码 */ void CreateHTCode(HTNode *p, string str) { if(!p) return; if(0 != p->data) { /** 若是叶节点，则记录此节点的编码值 */ dcode[str] = p->data; ecode[p->data] = str; sum += (str.length() * p->w); return; } CreateHTCode(p->lc, str + "0"); CreateHTCode(p->rc, str + "1"); } /** 显示哈夫曼编码 */ void DispCode() { printf("输出哈弗曼编码：\n"); for(int i = 0; i < n; i++) { printf("\t'%c':\t%s\n", ch[i], ecode[ch[i]].c_str()); } printf("平均长度：%.5lf\n", double(sum) / double(root->w)); } /** 释放哈夫曼树 */ void Release(HTNode *p) { if(!p) return; Release(p->lc); Release(p->rc); delete p; } /** 输出压缩文 */ void putEncode(FILE *fp, char *buf) { unsigned char code = 0; for(int i = 0; i < 8; i++) code = (code << 1) + (buf[i] - '0'); fwrite(&code, sizeof(unsigned char), 1, fp); } /** 判断是否在字符串内 */ bool instr(char c, const char str[]) { for(int i = 0; i < strlen(str); i++) if(c == str[i]) return true; return false; } /** 压缩文件 */ void Encode() { FILE *OF; FILE *IF; char ifn[255]; const char ofn[] = "Encode.txt"; char buf[9]; int cnt = 0, newcnt = 0; printf("Input the filename: "); scanf("%s", ifn); IF = fopen(ifn, "rb"); if(!IF) { printf("Wrong file.\n"); return; } OF = fopen(ofn, "wb+"); if(!OF) { printf("Wrong file.\n"); } /** 开始读文件 */ memset(buf, 0, sizeof(buf)); while(!feof(IF)) { unsigned char c; fread(&c, sizeof(unsigned char), 1, IF); if(instr(c, ch)); else c = ' '; for(int i = 0; i < ecode[c].length(); i++) { buf[strlen(buf)] = ecode[c][i]; if(8 == strlen(buf)) { newcnt++; putEncode(OF, buf); memset(buf, 0, sizeof(buf)); } } cnt++; } cnt--; if(0 != strlen(buf)) { for(int i = strlen(buf); i < 8; i++) buf[i] = '0'; putEncode(OF, buf); } fwrite(&cnt, 4, 1, OF); fclose(IF); fclose(OF); printf("压缩成功！压缩率：%.2f%c\n", (((double)newcnt + 4.0f) / (double)cnt) * 100, '%'); } /** 补0 */ void putZeros(char *buf) { char tmpbuf[9]; memset(tmpbuf, 0, sizeof(tmpbuf)); if(8 != strlen(buf)) { for(int i = 0; i < 8 - strlen(buf); i++) tmpbuf[i] = '0'; strcat(tmpbuf, buf); strcpy(buf, tmpbuf); } } /** 解压缩 */ void Decode() { char buf[256]; char oldbuf[9]; const char ifn[] = "Encode.txt"; const char ofn[] = "Decode.txt"; FILE *IF = fopen(ifn, "rb"); if(!IF) { printf("Wrong file.\n"); return; } FILE *OF = fopen(ofn, "wb+"); if(!OF) { printf("Wrong file.\n"); return; } int tot, cnt = 0; fseek(IF, -4L, SEEK_END); fread(&tot, 4, 1, IF); fseek(IF, 0L, SEEK_SET); memset(buf, 0, sizeof(buf)); while(true) { if(cnt == tot) break; unsigned char c; fread(&c, sizeof(unsigned char), 1, IF); itoa(c, oldbuf, 2); putZeros(oldbuf); for(int i = 0; i < 8; i++) { if(cnt == tot) break; buf[strlen(buf)] = oldbuf[i]; if(dcode.end() != dcode.find(string(buf))) { fwrite(&dcode[string(buf)], sizeof(char), 1, OF); memset(buf, 0, sizeof(buf)); cnt++; } } } fclose(IF); fclose(OF); printf("解压成功！文件名Decode.txt。\n"); } int main() { Init(); CreateHT(); CreateHTCode(root, ""); DispCode(); Encode(); Decode(); Release(root); system("pause"); return 0; }