哈夫曼实现⽂件压缩解压缩（c语⾔）
写⼀个对⽂件进⾏压缩和解压缩的程序，功能如下：
① 可以对纯英⽂⽂档实现压缩和解压；
② 较好的界⾯程序运⾏的说明。
介绍哈夫曼：
效率最⾼的判别树即为哈夫曼树
在计算机数据处理中，霍夫曼编码使⽤变长编码表对源符号（如⽂件中的⼀个字母）进⾏编码，其中变长编码表是通过⼀种评估来源符号出现机率的⽅法得到的，出现机率⾼的字母使⽤较短的编码，反之出现机率低的则使⽤较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从⽽达到⽆损压缩数据的⽬的。
例如，在英⽂中，e的出现机率最⾼，⽽z的出现概率则最低。当利⽤霍夫曼编码对⼀篇英⽂进⾏压缩时，e极有可能⽤⼀个⽐特来表⽰，⽽z 则可能花去25个⽐特（不是26）。⽤普通的表⽰⽅法时，每个英⽂字母均占⽤⼀个字节，即8个⽐特。⼆者相⽐，e使⽤了⼀般编码的1/8的长度，z则使⽤了3倍多。倘若我们能实现对于英⽂中各个字母出现概率的较准确的估算，就可以⼤幅度提⾼⽆损压缩的⽐例。
霍夫曼树⼜称最优⼆叉树，是⼀种带权路径长度最短的⼆叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每⼀结点的路径长度之和，记为
WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成⼀棵有N个叶结点的⼆叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最⼩的。
⽂件压缩与解压
姓名： 范天祚
1 程序说明
1.1数据结构
哈夫曼树
1.2函数功能说明
printfPercent界⾯
compress()读取⽂件内容并加以压缩，将压缩内容写⼊另⼀个⽂档
uncompress()解压缩⽂件，并将解压后的内容写⼊新⽂件
1.3 程序编写的思路及流程
压缩：统计字符出现次数、将节点按出现次数排序、构造哈夫曼树、设置字符编码、读⽂件字符、按设置好的编码替换字符、写⼊存储⽂件解压：读取⽂件各参数、转换成⼆进制码、按码求对应字符、写⼊存储⽂件
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct head
{
int b; //字符
long count; //⽂件中该字符出现的次数
long parent, lch, rch; //make a tree
char bits[256]; //the huffuman code
};
struct head header[512], tmp; //节点树
void printfPercent(int per)
{
int i = 0;
printf("|");
for(i = 0; i < 10; i++)
{
if(i < per/10)
printf(">");
else
printf("-");
}
printf("|已完成%d%%\n",per);
}
//函数：compress()
//作⽤：读取⽂件内容并加以压缩
//将压缩内容写⼊另⼀个⽂档
{
char buf[512];
unsigned char c;
long i, j, m, n, f;
long min1, pt1, flength;
FILE *ifp, *ofp;
int per = 10;
ifp = fopen(filename, "rb"); //打开原始⽂件
if (ifp == NULL)
{
printf("打开⽂件失败:%s\n",filename);
return 0; //如果打开失败，则输出错误信息
}
ofp = fopen(outputfile,"wb"); //打开压缩后存储信息的⽂件 if (ofp == NULL)
{
printf("打开⽂件失败:%s\n",outputfile);
return 0;
}
flength = 0;
while (!feof(ifp))
{
fread(&c, 1, 1, ifp);
header[c].count ++; //读⽂件，统计字符出现次数
flength ++; //记录⽂件的字符总数
}
flength --;
header[c].count --;
for (i = 0; i < 512; i ++) //HUFFMAN算法中初始节点的设置 {
if (header[i].count != 0)
header[i].b = (unsigned char) i;
else
header[i].b = -1;
header[i].parent = -1;
header[i].lch = header[i].rch = -1;
}
for (i = 0; i < 256; i ++) //将节点按出现次数排序
{
for (j = i + 1; j < 256; j ++)
{
if (header[i].count < header[j].count)
{
tmp = header[i];
header[i] = header[j];
header[j] = tmp;
}
}
}
for (i = 0; i < 256; i ++) //统计不同字符的数量
{
if (header[i].count == 0)
break;
}
n = i;
m = 2 * n - 1;
for (i = n; i < m; i ++)
{
min1 = 999999999;
for (j = 0; j < i; j ++)
if (header[j].parent != -1) continue;
if (min1 > header[j].count)
{
pt1 = j;
min1 = header[j].count;
continue;
}
}
header[i].count = header[pt1].count;
header[pt1].parent = i;
header[i].lch = pt1;
min1 = 999999999;
for (j = 0; j < i; j ++)
{
if (header[j].parent != -1) continue;
if (min1 > header[j].count)
{
pt1 = j;
min1 = header[j].count;
continue;
}
}
header[i].count += header[pt1].count;
header[i].rch = pt1;
header[pt1].parent = i;
}
for (i = 0; i < n; i ++) //构造HUFFMAN树，设置字符的编码
{
f = i;
header[i].bits[0] = 0;
while (header[f].parent != -1)
{
j = f;
f = header[f].parent;
if (header[f].lch == j)
{
j = strlen(header[i].bits);
memmove(header[i].bits + 1, header[i].bits, j + 1);
header[i].bits[0] = '0';
}
else
{
j = strlen(header[i].bits);
memmove(header[i].bits + 1, header[i].bits, j + 1);
header[i].bits[0] = '1';
}
}
}
//下⾯的就是读原⽂件的每⼀个字符，按照设置好的编码替换⽂件中的字符
fseek(ifp, 0, SEEK_SET); //将指针定在⽂件起始位置 fseek(ofp, 8, SEEK_SET); //以8位⼆进制数为单位进⾏读取
buf[0] = 0;
f = 0;
pt1 = 8;
printf("读取将要压缩的⽂件:%s\n",filename);
printf("当前⽂件有:%d字符\n",flength);
printf("正在压缩\n");
while (!feof(ifp))
{
c = fgetc(ifp);
for (i = 0; i < n; i ++)
{
if (c == header[i].b) break;
}
明解c语言
strcat(buf, header[i].bits);
j = strlen(buf);
c = 0;
while (j >= 8) //当剩余字符数量不⼩于8个时
{
for (i = 0; i < 8; i ++) //按照⼋位⼆进制数转化成⼗进制ASCII码写⼊⽂件⼀次进⾏压缩 {
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(100 * f/flength > per)
{
printfPercent(per);
per += 10;
}
if (f == flength)
break;
}
printfPercent(100);
if (j > 0) //当剩余字符数量少于8个时
{
strcat(buf, "00000000");
for (i = 0; i < 8; i ++)
{
if (buf[i] == '1') c = (c << 1) | 1;
else c = c << 1; //对不⾜的位数进⾏补零
}
fwrite(&c, 1, 1, ofp);
pt1 ++;
}
fseek(ofp, 0, SEEK_SET); //将编码信息写⼊存储⽂件
fwrite(&flength,1,sizeof(flength),ofp);
fwrite(&pt1, sizeof(long), 1, ofp);
fseek(ofp, pt1, SEEK_SET);
fwrite(&n, sizeof(long), 1, ofp);
for (i = 0; i < n; i ++)
{
tmp = header[i];
fwrite(&(header[i].b), 1, 1, ofp);
pt1++;
c = strlen(header[i].bits);
fwrite(&c, 1, 1, ofp);
pt1++;
j = strlen(header[i].bits);
if (j % 8 != 0) //当位数不满8时，对该数进⾏补零操作
{
for (f = j % 8; f < 8; f ++)
strcat(header[i].bits, "0");
}
while (header[i].bits[0] != 0)
{
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论