当前位置:网站首页>哈夫曼编码压缩文件
哈夫曼编码压缩文件
2022-07-07 07:09:00 【moyangxian】
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
const long INF = 0x7FFFFFFF;
struct HuffNode {
unsigned char b;
long count;
long parent;
long lch, rch;
char bits[256];
};
HuffNode HuffTree[512];
/* 函数描述:初始化HuffTree 函数名:init 返回值:void 参数描述:无 注意事项:无 */
void init() {
for (int i = 0; i < 512; i++) {
//初始化
HuffTree[i].b = 0;
HuffTree[i].count = 0;
HuffTree[i].parent = -1;
HuffTree[i].lch = -1;
HuffTree[i].rch = -1;
HuffTree[i].bits[0] = 0;
}
}
/* 函数描述:自定义cmp函数,按权值从大到小排序 返回值:bool 参数描述:无 注意事项:无 */
bool cmp(HuffNode A, HuffNode B) {
//按权值从大到小排序
return A.count > B.count;
}
void compress() {
//压缩
init(); //初始化
char filename[255],outputfile[255],buf[255];
unsigned char c;
long f, p, l;
long n, m, i, j;
long min1, pt1;
long flength=0,length1;
FILE* ifp, * ofp;
printf("\t请您输入需要压缩的文件名:");
//getchar();
//gets_s(filename);
scanf("%s", &filename); //文件路径
ifp = fopen(filename, "rb"); //以二进制流形式打开文件
if (ifp == NULL) {
//判断文件是否存在
printf("\n\t文件打开失败!\n\n");
return;
}
printf("\t将在当前目录下压缩,请您输入压缩后文件名包括扩展名:");
//gets_s(outputfile);
scanf("%s", outputfile);
ofp = fopen(outputfile, "wb");
if (ofp == NULL) {
printf("\n\t解压缩文件失败!\n");
return;
}
while (!feof(ifp)) {
fread(&c, 1, 1, ifp); //从文件读取一个字节到c
HuffTree[c].count++;
flength++; //原文件长度
}
flength--;
length1 = flength;
HuffTree[c].count--;
for (int i = 0; i < 512; i++) {
if (HuffTree[i].count != 0) {
HuffTree[i].b = (unsigned char)i;
}
else {
HuffTree[i].b = 0;
}
HuffTree[i].parent = -1;
HuffTree[i].lch = HuffTree[i].rch = -1;
}
sort(HuffTree,HuffTree+256,cmp); //按照权值大小排序
for (i = 0; i < 256; i++)
if (HuffTree[i].count == 0) break;
n = i; //叶子节点个数
m = 2 * n - 1; //哈夫曼总结点数
for (i = n; i < m; i++) {
min1 = INF;
for (j = 0; j < i; j++) {
//取出权值最小的节点
if (HuffTree[j].parent != -1) //该节点已在哈夫曼树中
continue;
if (min1 > HuffTree[j].count) {
pt1 = j;
min1 = HuffTree[j].count;
continue;
}
}
//将取出的节点作为哈夫曼树的左节点
HuffTree[i].count = HuffTree[pt1].count;
HuffTree[pt1].parent = i;
HuffTree[i].lch = pt1;
min1 = INF;
for (j = 0; j < i; j++) {
//重复取出权值最小的节点的操作
if (HuffTree[j].parent != -1)
continue;
if (min1 > HuffTree[j].count) {
pt1 = j;
min1 = HuffTree[j].count;
continue;
}
}
//将取出的节点作为哈夫曼树的右节点
HuffTree[i].count += HuffTree[pt1].count;
HuffTree[i].rch = pt1;
HuffTree[pt1].parent = i;
}
for (i = 0; i < n; i++) {
//哈夫曼编码
f = i;
HuffTree[i].bits[0] = 0;
while (HuffTree[f].parent != -1) {
j = f;
f = HuffTree[f].parent;
if (HuffTree[f].lch == j) {
j = strlen(HuffTree[i].bits);
memmove(HuffTree[i].bits + 1, HuffTree[i].bits, j + 1);
HuffTree[i].bits[0] = '0';
}
else {
j = strlen(HuffTree[i].bits);
memmove(HuffTree[i].bits + 1, HuffTree[i].bits, j + 1);
HuffTree[i].bits[0] = '1';
}
}
}
/* for (int i = 0; i < n; i++) { printf("%d %c %d %d %d %d %s\n", i, HuffTree[i].b, HuffTree[i].count, HuffTree[i].parent, HuffTree[i].lch, HuffTree[i].rch, HuffTree[i].bits); } */
fseek(ifp, 0, SEEK_SET);
fseek(ofp, 8, SEEK_SET);
buf[0] = 0;
pt1 = 8;
f = 0;
while (!feof(ifp)) {
//扫描原文件
c = fgetc(ifp);
//cout << c;
f++;
for (i = 0; i < n; i++) {
if (c == HuffTree[i].b)
break;
}
//cout << HuffTree[i].bits<<" ";
strcat(buf, HuffTree[i].bits);
j = strlen(buf);
c = 0;
while (j >= 8) {
//如果长度大于8进行拆分写入
for (i = 0; i < 8; i++) {
if (buf[i] == '1')c = (c << 1) | 1;
else c = c << 1;
}
fwrite(&c, 1, 1, ofp); //把凑好的一个字节编码写入文件
pt1++;
strcpy(buf, buf + 8);
j = strlen(buf);
}
if (f == flength)
break;
}
if (j > 0) {
//若buf中还有内容且不足一个字节,需要补0
strcat(buf, "00000000");
for (i = 0; i < 8; i++) {
if (buf[i] == '1')c = (c << 1) | 1;
else c <<= 1;
}
fwrite(&c, 1, 1, ofp);
pt1++;
}
fseek(ofp, 0, SEEK_SET);
fwrite(&flength, sizeof(long), 1, ofp);
fwrite(&pt1, sizeof(long), 1, ofp);
fseek(ofp, pt1, SEEK_SET);
fwrite(&n, sizeof(long), 1, ofp);
//cout << pt1 << " " << n << endl;
for (i = 0; i < n; i++) {
fwrite(&(HuffTree[i].b), 1, 1, ofp); //写入每个字节的代表字符
c = strlen(HuffTree[i].bits);
fwrite(&c, 1, 1, ofp); //写入每个字符哈夫曼编码长度
j = strlen(HuffTree[i].bits);
if (j % 8 != 0) {
//如果不是8的倍数,需要补0
for (f = j % 8; f < 8; f++)
strcat(HuffTree[i].bits, "0");
}
while (HuffTree[i].bits[0] != 0) {
c = 0;
for (j = 0; j < 8; j++) {
if (HuffTree[i].bits[j] == '1')
c = (c << 1) | 1;
else
c = c << 1;
}
strcpy(HuffTree[i].bits, HuffTree[i].bits + 8);
fwrite(&c, 1, 1, ofp);
}
}
long length2 = pt1--;
double div = ((double)length1 - (double)length2) / (double)length1;
fclose(ifp);
fclose(ofp);
printf("\n\t压缩文件成功!\n");
printf("\t压缩率为 %f%%\n\n", div * 100);
}
void uncompress() {
//解压
init();
char filename[255], outputfile[255], buf[255], bx[255];
unsigned char c;
long i, j, m, n, f, p, l;
long flength;
FILE* ifp, * ofp;
printf("\t请您输入需要解压缩的文件名:");
//getchar();
scanf("%s", &filename);
//gets_s(filename);
ifp = fopen(filename, "rb");
if (ifp == NULL) {
printf("\n\t文件打开失败!\n");
return;
}
printf("\t将在当前目录下解压,请您输入解压后文件名包括扩展名:");
scanf("%s", &outputfile);
//gets_s(outputfile);
ofp = fopen(outputfile, "wb");
if (ofp == NULL) {
printf("\n\t解压缩文件失败!\n");
return;
}
fseek(ifp, 0, SEEK_SET);
for (int i = 0; i < 9; i++) {
fread(&c, 1, 1, ifp);
}
fseek(ifp, 0, SEEK_SET);
fread(&flength, sizeof(long), 1, ifp);
fread(&f, sizeof(long), 1, ifp);
fseek(ifp, f, SEEK_SET);
fread(&n, sizeof(long), 1, ifp);
//cout << flength<<" "<<f << " " << n << endl;
for (i = 0; i < n; i++) {
//构造Huffman树的n个叶子结点
fread(&HuffTree[i].b, 1, 1, ifp);
fread(&c, 1, 1, ifp);
p = (long)c;
HuffTree[i].count = p;
HuffTree[i].bits[0] = 0;
if (p % 8 > 0)
m = p / 8 + 1;
else
m = p / 8;
for (j = 0; j < m; j++) {
fread(&c, 1, 1, ifp);
f = c; //十六进制转十进制
itoa(f, buf, 2);
f = strlen(buf);
for (l = 8; l > f; l--) {
strcat(HuffTree[i].bits, "0");
}
strcat(HuffTree[i].bits, buf);
}
HuffTree[i].bits[p] = 0;
}
HuffNode tmp;
for (i = 0; i < n; i++) {
//根据哈夫曼编码长度排序
for (j = i+1; j < n; j++) {
if (strlen(HuffTree[i].bits) > strlen(HuffTree[j].bits)) {
tmp = HuffTree[i];
HuffTree[i] = HuffTree[j];
HuffTree[j] = tmp;
}
}
}
p = strlen(HuffTree[n - 1].bits);
fseek(ifp, 8, SEEK_SET);
m = 0;
bx[0] = 0;
while (1) {
//解码
while (strlen(bx) < (unsigned int)p) {
fread(&c, 1, 1, ifp);
f = c;
itoa(f, buf, 2);
f = strlen(buf);
for (l = 8; l > f; l--) {
strcat(bx, "0");
}
strcat(bx, buf);
}
for (i = 0; i < n; i++) {
if (memcmp(HuffTree[i].bits, bx, HuffTree[i].count) == 0)
break;
}
strcpy(bx, bx + HuffTree[i].count);
c = HuffTree[i].b;
fwrite(&c, 1, 1, ofp);
m++;
if (m == flength) break;
}
fclose(ifp);
fclose(ofp);
printf("\n\t解压缩文件成功!\n");
if (m == flength)
printf("\t解压缩文件与原文件相同!\n\n");
else
printf("\t解压缩文件与原文件不同!\n\n");
return;
}
int main() {
int c;
while (1) {
printf("\t_________________________________________\n");
printf("\n");
printf("\t * 压缩、解压缩 小工具 * \n");
printf("\t_________________________________________\n");
printf("\t_________________________________________\n");
printf("\t| |\n");
printf("\t|1.压缩 |\n");
printf("\t|2.解压缩 |\n");
printf("\t|0.退出 |\n");
printf("\n");
printf("\t 说明:(1)采用哈夫曼编码\n");
printf("\t (2)适用于字符型文本文件\n");
printf("\n");
do {
printf("\n\t*请选择相应功能(0-2):");
c = getchar();
//printf("%c\n", c);
if (c != '0' && c != '1' && c != '2') {
printf("\[email protected][email protected]请检查您输入的数字在0~2之间!\n");
printf("\t请再输入一边!\n");
}
} while (c != '0' && c != '1' && c != '2');
if (c == '1') {
compress();
}
else if (c == '2') {
uncompress();
}
else {
printf("\t欢迎您再次使用该工具^_^\n");
exit(0);
}
system("pause");
system("cls");
}
return 0;
}
边栏推荐
- Netease cloud wechat applet
- Unity shader (pass user data to shader)
- 【无标题】
- IIS faked death this morning, various troubleshooting, has been solved
- flink. CDC sqlserver. 可以再次写入sqlserver中么 有连接器的 dem
- Regular matching starts with XXX and ends with XXX
- PostgreSQL reports an error when creating a trigger,
- 有没有大佬帮忙看看这个报错,有啥排查思路,oracle cdc 2.2.1 flink 1.14.4
- Kubernetes cluster capacity expansion to add node nodes
- 大佬们,请问 MySQL-CDC 有什么办法将 upsert 消息转换为 append only 消
猜你喜欢
【原创】程序员团队管理的核心是什么?
Information Security Experiment 4: implementation of IP packet monitoring program
[4g/5g/6g topic foundation-146]: Interpretation of white paper on 6G overall vision and potential key technologies-1-overall vision
Esp8266 uses TF card and reads and writes data (based on Arduino)
小程序弹出半角遮罩层
sqlplus乱码问题,求解答
# Arthas 简单使用说明
iNFTnews | 时尚品牌将以什么方式进入元宇宙?
nlohmann json
Netease Cloud Wechat applet
随机推荐
Unity3d interface is embedded in WPF interface (mouse and keyboard can respond normally)
有没有大佬帮忙看看这个报错,有啥排查思路,oracle cdc 2.2.1 flink 1.14.4
Lesson 1: hardness of eggs
Binary tree high frequency question type
**grafana安装**
The configuration and options of save actions are explained in detail, and you won't be confused after reading it
Unity shader (to achieve a simple material effect with adjustable color attributes only)
Arthas simple instructions
在EXCEL写VBA连接ORACLE并查询数据库中的内容
4、 Fundamentals of machine learning
[Frida practice] "one line" code teaches you to obtain all Lua scripts in wegame platform
第一讲:鸡蛋的硬度
Unity shader (pass user data to shader)
VSCode+mingw64+cmake
golang select机制和超时问题怎么解决
PostgreSQL创建触发器的时候报错,
Huawei hcip datacom core_ 03day
信息安全实验二 :使用X-SCANNER扫描工具
如何成为一名高级数字 IC 设计工程师(5-3)理论篇:ULP 低功耗设计技术精讲(下)
进程和线程的区别