#include
#include
#include
#include
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 pq;
/** 哈弗曼编码映射 */
map dcode;
map 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;
}
