知新_RL

这个屌丝很懒，什么也没留下！

热门标签

详解C语言实现哈夫曼编码压缩_c语言,数据结构哈夫曼文件压缩设计

作者：知新_RL | 2024-07-30 23:40:27

踩

c语言,数据结构哈夫曼文件压缩设计

更新

这个项目是大一写的，现在大三了，将它重新实现了一下，比原来的看起来更干净一点。

新的链接在这里手把手教你C语言哈夫曼压缩/解压缩

下面的都是以前写的，比较笨拙，但保留了原始的思路。

如果你想了解思路，可以看下面讲的细节（屎山）。
如果你水平比较高，不想看废话，可以看新实现的那篇。

最终状态：

现在已经可以对 1G任意文件(因为我只试了1G，再大的话有点费时间，足以说明代码是没大问题的)压缩后100%解压还原，文本压缩后约占原来70%~76% ，代码改动挺多的，下方的思路依然是正确的，只是代码有些bug(下方的代码只能100MB左右无误)，

最新文件(更新日期2021/6/28 10:48)

至此我要结束我的课设了，下面的代码也不太想改动了，这里放个文件提取码：qw77里面有三个版本：
1.调试版(这是给想了解过程的人看的)，因为这个代码想用IDE调试简直是做梦，这出错率至少千万分之一，调不出来的，我都是拿宏调试+合理猜测推断，真的很不容易(从最初的150字节无误到现在的至少1G无误，鬼知道我经历了什么)。
2.无界面版，这个和调试版代码一样，只是不带宏，更整洁一些,DevCpp编译可通过。
3.带界面版，这个是带点花样的，用了基于对话框的win窗体程序(CodeBlocks的,不过好像复制到VS2019项目也能跑)，还有音效、个性图标，给截个图看下
在这里插入图片描述

在这里插入图片描述
修改部分的代码，有的是bug(循环的判断与边界情况、数组分配过小越界)，还有的是为了效率提升(主要是频繁打开文件的)。

目标：

能对任意格式的文件进行压缩

必备知识：

1.哈夫曼树的编码
2.C语言文件操作、按位运算(压榨存储空间的关键)

IDE:CodeBlocks

===========================================================

思路

关键点

模块一：
计算机以字节为最小单位进行数据存储、一个字节8bit位，要做到对任意格式的压缩，映射是关键，也就是把字节数据映射成一个值(0b00000000~0b11111111)，然后对它编码。
模块二：
要明确编码对象：字节值(0~0xFF)，权值：字节值频次
模块三：
经实践，决定此处将编码表与压缩文件分别存放。
模块四：解压缩。

流程

模块	任务	结果
模块一	统计文件中字节值频次，字节值作为编码对象，频次作为哈夫曼编码的权值	得到权值
模块二	利用权值对字节值进行哈夫曼编码	得到编码表
模块三	利用编码表改写文件实现压缩	得到压缩文件
模块四	利用编码表解压缩	实现解压缩
本人评估
模块	难度
–	–
一	★
二	★★
三	★★★★★
四	★★★

细节流程图

模块一

在这里插入图片描述

模块二

在这里插入图片描述

模块三

(点击图片放大)

模块四

(点击图片放大)

文件展示(样例)

fOriginFile

在这里插入图片描述

fDataTimes

在这里插入图片描述

fHuffmanCode

在这里插入图片描述

fCompress

在这里插入图片描述

fDeCompress

在这里插入图片描述

(讲解部分有详细注释)

核心代码

//#define TEST_ShowWriteStr
//#define TEST_ShowRead_01Str
//#define TEST_ShowReadSearchList
//#define TEST_ShowOriginData

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define Line 200

#define ErrOpen(filename); { printf("文件%s打开失败!\n",filename); exit(1);}

typedef struct
{
	int hufnode;
}DataType;

typedef struct HTNode
{
	DataType data;
	int weight;
	int lchild,rchild,parent;
}HTNode,*HTree;

typedef char **HuffmanCode;

/*全局变量*/
char fOriginFile[]="1.txt";
char fDataTimes[]="DataTimes.txt";
char fCompress[]="Compress.txt";
char fHuffmanCode[]="HuffmanCode.txt";
char fDeCompress[]="DeCompress.txt";

int HexDataTimes[0xFF+1]={0};
/*模块一*/
void ReadByte_WriteHex(const char *filename,const char *SaveName=fDataTimes);
void memset_int(int *num,int value,int size);
void TransToHex(char *ByteData,int *HexData,int bytenum);
void AddTimes(int *HexDataTimes,int *HexData);
/*模块二*/
void ReadDataTimes(int *HexDataTimes,const char *filename=fDataTimes);
void CreateHTree(HTree &HT,int &N);
void SelectMin(HTree HT,const int n,int &min1,int &min2);
void HuffmanCoding(HTree HT,HuffmanCode &HC,int n);
/*模块三*/
void CreateSearchList(HuffmanCode &HC,HuffmanCode &SearchList);
void Compress(HuffmanCode SearchList);
void _01StrCat(char *_01Str,char *OriginCode,int strlen,HuffmanCode SearchList);
void TransWrite(char *_01Str,int _01StrLen);
inline void Set_bit(char &a,int bit,int _01);
void WriteHuffmanCode(HuffmanCode SearchList,char *_01Str);
/*模块四*/
void DeCompress();
void BitToStr(char a,char *Each_Str);
void TransWrite2(char *_01Str,char SearchList[0xFF+1][100],int byetnum);


int main(void)
{
    printf("男同专用压缩软件启动！\n");

    ReadByte_WriteHex(fOriginFile);


    int N;
	HTree HT=NULL;
	HuffmanCode HC=NULL;
	CreateHTree(HT,N);//CreateHTree将会改变N的值
	HuffmanCoding(HT,HC,N);


	HuffmanCode SearchList=NULL;
	CreateSearchList(HC,SearchList);
    Compress(SearchList);


    DeCompress();
}
/*模块一*///###############################################################
void ReadByte_WriteHex(const char *filename,const char *SaveName)
{
	int i,bytenum;
	FILE *pfile=NULL,*pfile_2=NULL;
	if( (pfile=fopen(filename,"rb")) ==NULL)
		ErrOpen(filename);
	if( (pfile_2=fopen(SaveName,"ab")) ==NULL)
	{
		fclose(pfile);
		ErrOpen(SaveName);
	}
	char ByteData[Line+1]={0};
	int HexData[Line+1]={0};
	for(;feof(pfile)==0;)
	{
		memset_int(HexData,-1,sizeof(HexData)/sizeof(int));//每次都重置
		memset(ByteData,0,sizeof(ByteData)/sizeof(char));
		bytenum=fread(ByteData,sizeof(char),Line,pfile);
		#ifdef TEST_ShowOriginData
		printf("%s\n\n\n\n\n",ByteData);
		getchar();
		#endif
		TransToHex(ByteData,HexData,bytenum);//ByteData转换成16进制数存储
		AddTimes(HexDataTimes,HexData);
	}
	for(i=0;i<=0xFF;++i)
		fprintf(pfile_2,"%02X==%010d\n",i,HexDataTimes[i]);

	fclose(pfile);
	fclose(pfile_2);
}
void memset_int(int *num,int value,int size)
{
	for(int i=0;i<size;++i)
		num[i]=value;
}
void TransToHex(char *ByteData,int *HexData,int bytenum)
{
	for(int i=0;i<bytenum;++i)
		HexData[i]=ByteData[i]&0b11111111;
		//抹去高位，保留低位
}
void AddTimes(int *HexDataTimes,int *HexData)
{
	for(int i=0;HexData[i]!=-1;++i)
		++HexDataTimes[ HexData[i] ];
}
//###############################################################/*模块一*/

/*模块二*///###############################################################
void ReadDataTimes(int *HexDataTimes,const char *filename)
{
	FILE *pfile=NULL;
	if((pfile=fopen(filename,"rb"))==NULL)
		ErrOpen(filename);
	for(int i=0;i<0xFF+1;++i)
		fscanf(pfile,"%02X==%010d",&HexDataTimes[i],&HexDataTimes[i]);
		//这里重复赋值，是因为发现VS2019不支持*赋值跳过，就重复赋值覆盖了
	fclose(pfile);
}

void CreateHTree(HTree &HT,int &N)
{
	int i,n,m;
	int min1,min2;
	ReadDataTimes(HexDataTimes);
	int weight[0xFF+1],weight_Hex[0xFF+1];
	for(i=0,n=0;i<0xFF+1;++i)
	{
		if(HexDataTimes[i]!=0)
		{
			weight[n]=HexDataTimes[i];//把非0权值提取出来
			weight_Hex[n]=i;		//保留对应非0权值的映射值
			++n;
		}
	}
	N=n;
	m=2*n-1;//weight[0~n-1]存放了所以非0权值
	HT=(HTree)malloc((m+1)*sizeof(HTNode));//分配编码空间舍去0单元不用
	for(i=0;i<=m;++i)
		HT[i]={{0},0,0,0};//初始化
	for(i=1;i<=n;++i)
		HT[i].weight=weight[i-1];//这里错开一位，因为weight[]是从0开始存放的
	for(i=n+1;i<=m;++i)
	{
		SelectMin(HT,i-1,min1,min2);
		HT[min1].parent=i;
		HT[min2].parent=i;
		HT[i].lchild=min1;
		HT[i].rchild=min2;
		HT[i].weight=HT[min1].weight+HT[min2].weight;
	 }

}

void SelectMin(HTree HT,const int n,int &min1,int &min2)
{
	int i,min_value=INT_MAX;
	for(i=1;i<=n;++i)
		if(HT[i].parent==0 && HT[i].weight<min_value)
		{
			min_value=HT[i].weight;
			min1=i;
		}
	for(i=1,min_value=INT_MAX;i<=n;++i)
		if(HT[i].parent==0 && HT[i].weight<min_value &&i!=min1)
		{
			min_value=HT[i].weight;
			min2=i;
		}
}

void HuffmanCoding(HTree HT,HuffmanCode &HC,int n)
{
	int start,parent,current;
	HC=(HuffmanCode)malloc( (n+1) *sizeof(char*) );
	char *Each_Code=(char*)malloc( n*sizeof(char) );
	Each_Code[n-1]='\0';
	for(int i=1;i<=n;++i)
	{
		start=n-1;//从start开始时指向最后，即编码结束符位置
		current=i;
		parent=HT[i].parent;
		while(parent!=0)
		{
			--start;
			if(HT[parent].lchild==current)
				Each_Code[start]='0';
			else
				Each_Code[start]='1';
			current=parent;
			parent=HT[parent].parent;
		 }
		 HC[i]=(char *)malloc( (n-start) *sizeof(char) );
		 strcpy(HC[i],&Each_Code[start]);
	}
	free(Each_Code);
}

//###############################################################/*模块二*/

/*模块三*///###############################################################
void CreateSearchList(HuffmanCode &HC,HuffmanCode &SearchList)
{
    int i, j;
	SearchList = (HuffmanCode)calloc(0xFF+1, sizeof(char*));
	for (i = 0; i <= 0xFF; ++i)
		SearchList[i] = NULL;
	for (i = 0, j = 1; i <= 0xFF; ++i)
	{
		if (HexDataTimes[i] != 0)
		{
			SearchList[i] = HC[j];
			++j;
		}
	}
}
void Compress(HuffmanCode SearchList)
{
    FILE *pfile=NULL;
    if((pfile=fopen(fOriginFile,"rb"))==NULL)
        ErrOpen(fOriginFile)
    char OriginCode[Line+10]={0},_01Str[10*Line]={0};
    for(;feof(pfile)==0;)
    {
        memset(OriginCode,0,strlen(OriginCode));
        fread(OriginCode,sizeof(char),Line,pfile);
        _01StrCat(_01Str,OriginCode,strlen(OriginCode),SearchList);
        TransWrite(_01Str,strlen(_01Str));
    }
    fclose(pfile);
    WriteHuffmanCode(SearchList,_01Str);
}

void _01StrCat(char *_01Str,char *OriginCode,int strlen,HuffmanCode SearchList)
{

    int i;
    for(i=0;i<strlen;++i)
    {

        strcat(_01Str,SearchList[ OriginCode[i]&0b11111111 ]);
        #ifdef TEST_ShowWriteStr
        printf("%s",SearchList[ OriginCode[i]&0b11111111 ]);
        #endif
    }
}

void TransWrite(char *_01Str,int _01StrLen)
{
    int i,last,bytenum;
    char BitCode[_01StrLen/8+10]={0};
    char temp[10];
    last=_01StrLen%8;
    _01StrLen-=last;
    for(i=7,bytenum=0;i<_01StrLen;i+=8)
    {

        Set_bit(BitCode[bytenum],1,_01Str[i]-48);
		Set_bit(BitCode[bytenum],2,_01Str[i-1]-48);
		Set_bit(BitCode[bytenum],3,_01Str[i-2]-48);
		Set_bit(BitCode[bytenum],4,_01Str[i-3]-48);
		Set_bit(BitCode[bytenum],5,_01Str[i-4]-48);
		Set_bit(BitCode[bytenum],6,_01Str[i-5]-48);
		Set_bit(BitCode[bytenum],7,_01Str[i-6]-48);
		Set_bit(BitCode[bytenum],8,_01Str[i-7]-48);
		bytenum++;
    }
    BitCode[bytenum]='\0';
    strcpy(temp,&_01Str[_01StrLen]);
    strcpy(_01Str,temp);

    FILE *pfile=NULL;
    if((pfile=fopen(fCompress,"ab"))==NULL)
        ErrOpen(fCompress)
    fwrite(BitCode,sizeof(char),bytenum,pfile);
    fclose(pfile);
}

inline void Set_bit(char &a,int bit,int _01)
{
	char bit_to_1[9]={0, 0b1 , 0b10, 0b100, 0b1000, 0b10000,
							0b100000, 0b1000000, (char)0b10000000};
	char bit_to_0[9]={0,(char)0b11111110,(char)0b11111101,(char)0b11111011,(char)0b11110111
		 				,(char)0b11101111,(char)0b11011111,(char)0b10111111,(char)0b01111111};
	if(_01==0)
	{
		a&=bit_to_0[bit]; //表示要将bit位变为0，也即是将第bit位&0，其他位&1即可
	}
	else if(_01==1)
	{
		a|=bit_to_1[bit];//表示要将bit位变为1，也即时将第bit位|1，其他位|0即可
	}
}

void WriteHuffmanCode(HuffmanCode SearchList,char  *_01Str)
{
    int i;
    FILE *pfile=NULL;
    if((pfile=fopen(fHuffmanCode,"wb"))==NULL)
        ErrOpen(fHuffmanCode);
    for(i=0;i<=0xFF;++i)
        fprintf(pfile,"%s\n",SearchList[i]);
    fprintf(pfile,"%s",_01Str);
    fclose(pfile);
}

//###############################################################/*模块三*/

/*模块四*///###############################################################
void DeCompress()
{
    int i;
    char surplus[12]={0};
    char  SearchList[0xFF+1][100];
    FILE *pfile=NULL;

    if((pfile=fopen(fHuffmanCode,"rb"))==NULL)
        ErrOpen(fHuffmanCode)
    for(i=0;i<=0xFF;++i)
    {
        fscanf(pfile,"%s\n",SearchList[i]);
        #ifdef TEST_ShowReadSearchList
        printf("%s\n",SearchList[i]);
        #endif
    }
    fgets(surplus,10,pfile);
    fclose(pfile);

    for(i=0;i<=0xFF;++i)
        if(strcmp(SearchList[i],"(null)")==0)
            SearchList[i][0]='\0';

    if((pfile=fopen(fCompress,"rb"))==NULL)
        ErrOpen(fCompress)

    char BitCode[Line+10],_01Str[8*Line+10]={0},EachStr[50];
    int bytenum;

    for(;feof(pfile)==0;)
    {
        memset(BitCode,0,strlen(BitCode));
        bytenum=fread(BitCode,sizeof(char),Line,pfile);
        for(i=0;i<bytenum;++i)
        {
            BitToStr(BitCode[i],EachStr);
            #ifdef TEST_ShowRead_01Str
            printf("%s",EachStr);
            #endif;
            strcat(_01Str,EachStr);
        }
        TransWrite2(_01Str,SearchList,bytenum);
    }
    fclose(pfile);
    strcat(_01Str,surplus);
    if((pfile=fopen(fDeCompress,"ab"))==NULL)
        ErrOpen(fDeCompress);

    for(i=0;i<=0xFF;++i)
        {
            if(SearchList[i][0]!='\0')
                if(strcmp(_01Str,SearchList[i])==0)
            {
                char OneCode=i;
                fwrite(&OneCode,sizeof(char),1,pfile);
                break;
            }
        }
    fclose(pfile);

}
void BitToStr(char a,char *Each_Str)
{
	int bit[8]={0b00000001,0b00000010,0b00000100,
	0b00001000,0b00010000,0b00100000,0b01000000,0b10000000};
  Each_Str[0]=((a&bit[7])>> 7)+48;
  Each_Str[1]=((a&bit[6])>> 6)+48;
  Each_Str[2]=((a&bit[5])>> 5)+48;
  Each_Str[3]=((a&bit[4])>> 4)+48;
  Each_Str[4]=((a&bit[3])>> 3)+48;
  Each_Str[5]=((a&bit[2])>> 2)+48;
  Each_Str[6]=((a&bit[1])>> 1)+48;
  Each_Str[7]=((a&bit[0])>> 0)+48;
  Each_Str[8]='\0';
}

void TransWrite2(char *_01Str,char SearchList[0xFF+1][100],int bytenum)
{
    FILE    *pfile=NULL;
    if((pfile=fopen(fDeCompress,"ab"))==NULL)
        ErrOpen(fDeCompress);
    int i=0,times=0,j,Bitnum=bytenum*8,len=0;
    char *p=NULL;
    char temp[100];
    char OneCode;

    while(i<=Bitnum)
    {
        for(j=0;j<=0xFF;++j)
        {
            if(SearchList[j][0]!='\0')
                if(strncmp(&_01Str[i],SearchList[j],strlen(SearchList[j]))==0)
            {
                len+=strlen(SearchList[j]);
                OneCode=j;
                fwrite(&OneCode,sizeof(char),1,pfile);
                #ifdef TEST_DeCompress
                printf("%c",OneCode);
                #endif
                times++;
                i+=strlen(SearchList[j]);
                break;
            }
        }
        if(j==0xFF+1)
            ++i;
    }
    strcpy(_01Str,&_01Str[len]);
    fclose(pfile);

}

//###############################################################/*模块四*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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
92
93
94
95
96
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445

讲解

模块一：

void ReadByte_WriteHex(const char *filename,const char *SaveName)
{
	int i,bytenum;
	FILE *pfile=NULL,*pfile_2=NULL;
	if( (pfile=fopen(filename,"rb")) ==NULL)
		ErrOpen(filename);
	if( (pfile_2=fopen(SaveName,"ab")) ==NULL)
	{
		fclose(pfile);
		ErrOpen(SaveName);
	}
	//打开文件
	char ByteData[Line+1]={0};//存储原始字节数据
	int HexData[Line+1]={0};//以16进制存储字节值的
	for(;feof(pfile)==0;)
	{
		memset_int(HexData,-1,sizeof(HexData)/sizeof(int));//每次都重置为-1
		memset(ByteData,0,sizeof(ByteData)/sizeof(char));
		//重置数组为0
		bytenum=fread(ByteData,sizeof(char),Line,pfile);
		#ifdef TEST_ShowOriginData//自调试宏定义
		printf("%s\n\n\n\n\n",ByteData);
		getchar();
		#endif
		TransToHex(ByteData,HexData,bytenum);//将ByteData转换成16进制数存储
		AddTimes(HexDataTimes,HexData);
		//将16进制字节值的出现次数存储到HexDataTime[0~255]全局变量中
	}
	for(i=0;i<=0xFF;++i)
		fprintf(pfile_2,"%02X==%010d\n",i,HexDataTimes[i]);
		//以特定格式将频次数据写入文件

	fclose(pfile);
	fclose(pfile_2);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/*自定义memset函数，因为memset只能以0、-1来初始化，备不时之需*/
void memset_int(int *num,int value,int size)
{
	for(int i=0;i<size;++i)
		num[i]=value;
}
/*按位运算，将字节值转换成16进制方便使用*/
void TransToHex(char *ByteData,int *HexData)
{
	for(int i=0;i<bytenum;++i)
		HexData[i]=ByteData[i]&0b11111111;
		//抹去高位，保留低位
		//任何bit位 &0为0、|1为1
}
/*将出现字节值计次到全局变量HexDataTimes[0~0xFF]*/
void AddTimes(int *HexDataTimes,int *HexData)
{
	for(int i=0;HexData[i]!=-1;++i)
		++HexDataTimes[ HexData[i] ];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

模块二：

/*模块二*///###############################################################
/*读取字节值的频次，作为权值*/
void ReadDataTimes(int *HexDataTimes,const char *filename)
{
	FILE *pfile=NULL;
	if((pfile=fopen(filename,"rb"))==NULL)
		ErrOpen(filename);
	for(int i=0;i<0xFF+1;++i)
		fscanf(pfile,"%02X==%010d",&HexDataTimes[i],&HexDataTimes[i]);
		//这里重复赋值，是因为发现VS2019不支持*赋值跳过，就重复赋值覆盖了
	fclose(pfile);
}
/*建立哈夫曼树*/
void CreateHTree(HTree &HT,int &N)
{
	int i,n,m;
	int min1,min2;
	ReadDataTimes(HexDataTimes);
	int weight[0xFF+1],weight_Hex[0xFF+1];
	for(i=0,n=0;i<0xFF+1;++i)
	{
		if(HexDataTimes[i]!=0)
		{
			weight[n]=HexDataTimes[i];//把非0权值提取出来
			weight_Hex[n]=i;		//保留对应非0权值的映射值
			++n;
		}
	}
	N=n;
	m=2*n-1;//weight[0~n-1]存放了所以非0权值
	HT=(HTree)malloc((m+1)*sizeof(HTNode));//分配编码空间舍去0单元不用
	for(i=0;i<=m;++i)
		HT[i]={{0},0,0,0};//初始化
	for(i=1;i<=n;++i)
		HT[i].weight=weight[i-1];//这里错开一位，因为weight[]是从0开始存放的
	for(i=n+1;i<=m;++i)
	{
		SelectMin(HT,i-1,min1,min2);
		HT[min1].parent=i;
		HT[min2].parent=i;
		HT[i].lchild=min1;
		HT[i].rchild=min2;
		HT[i].weight=HT[min1].weight+HT[min2].weight;
	 }

}
/*哈夫曼建树辅助函数*/
void SelectMin(HTree HT,const int n,int &min1,int &min2)
{
	int i,min_value=INT_MAX;
	for(i=1;i<=n;++i)
		if(HT[i].parent==0 && HT[i].weight<min_value)
		{
			min_value=HT[i].weight;
			min1=i;
		}
	for(i=1,min_value=INT_MAX;i<=n;++i)
		if(HT[i].parent==0 && HT[i].weight<min_value &&i!=min1)
		{
			min_value=HT[i].weight;
			min2=i;
		}
}
/*根据哈弗曼树进行编码*/
void HuffmanCoding(HTree HT,HuffmanCode &HC,int n)
{
	int start,parent,current;
	HC=(HuffmanCode)malloc( (n+1) *sizeof(char*) );
	char *Each_Code=(char*)malloc( n*sizeof(char) );
	Each_Code[n-1]='\0';
	for(int i=1;i<=n;++i)
	{
		start=n-1;//从start开始时指向最后，即编码结束符位置
		current=i;
		parent=HT[i].parent;
		while(parent!=0)
		{
			--start;
			if(HT[parent].lchild==current)
				Each_Code[start]='0';
			else
				Each_Code[start]='1';
			current=parent;
			parent=HT[parent].parent;
		 }
		 HC[i]=(char *)malloc( (n-start) *sizeof(char) );
		 strcpy(HC[i],&Each_Code[start]);
	}
	free(Each_Code);
}

//###############################################################/*模块二*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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
92

模块三：

/*模块三*///###############################################################
/*HC[1~N]中的编码串指针赋给*SearchList[0~0xFF]中*/
/*两者区别：SearchList中有NULL，而HC只有[0]单元为空*/
void CreateSearchList(HuffmanCode &HC,HuffmanCode &SearchList)
{
    int i, j;
	SearchList = (HuffmanCode)calloc(0xFF+1, sizeof(char*));
	for (i = 0; i <= 0xFF; ++i)
		SearchList[i] = NULL;
	for (i = 0, j = 1; i <= 0xFF; ++i)
	{
		if (HexDataTimes[i] != 0)
		{
			SearchList[i] = HC[j];
			++j;
		}
	}
}
/*根据编码查询表SearchList[0~0xFF]进行编码*/
void Compress(HuffmanCode SearchList)
{
    FILE *pfile=NULL;
    if((pfile=fopen(fOriginFile,"rb"))==NULL)
        ErrOpen(fOriginFile)
    char OriginCode[Line+10]={0},_01Str[10*Line]={0};
    for(;feof(pfile)==0;)
    {
        memset(OriginCode,0,strlen(OriginCode));
        fread(OriginCode,sizeof(char),Line,pfile);
        _01StrCat(_01Str,OriginCode,strlen(OriginCode),SearchList);
        TransWrite(_01Str,strlen(_01Str));//写入BitCode
    }
    fclose(pfile);
    WriteHuffmanCode(SearchList,_01Str);
    //将编码查询表写入另一文件,同时将无法凑足8bit位的
    //编码以字符串形式写到该文件末尾
}
/*辅助函数，将读取的字节值对应的哈夫曼编码逐个连接到_01Str*/
void _01StrCat(char *_01Str,char *OriginCode,int strlen,HuffmanCode SearchList)
{

    int i;
    for(i=0;i<strlen;++i)
    {

        strcat(_01Str,SearchList[ OriginCode[i]&0b11111111 ]);
        #ifdef TEST_ShowWriteStr
        printf("%s",SearchList[ OriginCode[i]&0b11111111 ]);
        #endif
    }
}

void TransWrite(char *_01Str,int _01StrLen)
{
/*将_01Str(0101010000111……)字符数字数值存储到BitCode[]元素的bit位中*/
    int i,last,bytenum;
    char BitCode[_01StrLen/8+10]={0};
    char temp[10];
    last=_01StrLen%8;//将不足八位的截断
    _01StrLen-=last;
    for(i=7,bytenum=0;i<_01StrLen;i+=8)
    {

        Set_bit(BitCode[bytenum],1,_01Str[i]-48);
		Set_bit(BitCode[bytenum],2,_01Str[i-1]-48);
		Set_bit(BitCode[bytenum],3,_01Str[i-2]-48);
		Set_bit(BitCode[bytenum],4,_01Str[i-3]-48);
		Set_bit(BitCode[bytenum],5,_01Str[i-4]-48);
		Set_bit(BitCode[bytenum],6,_01Str[i-5]-48);
		Set_bit(BitCode[bytenum],7,_01Str[i-6]-48);
		Set_bit(BitCode[bytenum],8,_01Str[i-7]-48);
		bytenum++;
    }
    BitCode[bytenum]='\0';
    strcpy(temp,&_01Str[_01StrLen]);
    strcpy(_01Str,temp);//将截断未被写入的子字符串恢复到_01Str开头

    FILE *pfile=NULL;
    if((pfile=fopen(fCompress,"ab"))==NULL)
        ErrOpen(fCompress)
    fwrite(BitCode,sizeof(char),bytenum,pfile);
    fclose(pfile);
}
/*按位运算设定bit位，稍大数值用强制类型转换(char)，否则部分编译器报错数值溢出*/
inline void Set_bit(char &a,int bit,int _01)
{
	char bit_to_1[9]={0, 0b1 , 0b10, 0b100, 0b1000, 0b10000,
							0b100000, 0b1000000, (char)0b10000000};
	char bit_to_0[9]={0,(char)0b11111110,(char)0b11111101,(char)0b11111011,(char)0b11110111
		 				,(char)0b11101111,(char)0b11011111,(char)0b10111111,(char)0b01111111};
	if(_01==0)
	{
		a&=bit_to_0[bit]; //表示要将bit位变为0，也即是将第bit位&0，其他位&1即可
	}
	else if(_01==1)
	{
		a|=bit_to_1[bit];//表示要将bit位变为1，也即时将第bit位|1，其他位|0即可
	}
}
/*将哈夫曼编码表写到文件fHuffmanCode，格式为每行一个编码*/
void WriteHuffmanCode(HuffmanCode SearchList,char  *_01Str)
{
    int i;
    FILE *pfile=NULL;
    if((pfile=fopen(fHuffmanCode,"wb"))==NULL)
        ErrOpen(fHuffmanCode);
    for(i=0;i<=0xFF;++i)
        fprintf(pfile,"%s\n",SearchList[i]);
    fprintf(pfile,"%s",_01Str);//不足8bit位的，写到文件尾部
    fclose(pfile);
}

//###############################################################/*模块三*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

模块四：

/*模块四*///###############################################################
void DeCompress()
{
    int i;
    char surplus[12]={0};//读取编码查询表文件末尾的不足8位字符串
    char  SearchList[0xFF+1][100];//这里以数组形式使用编码表
    FILE *pfile=NULL;

    if((pfile=fopen(fHuffmanCode,"rb"))==NULL)
        ErrOpen(fHuffmanCode)
    for(i=0;i<=0xFF;++i)
    {
    	//自定义宏调试
        fscanf(pfile,"%s\n",SearchList[i]);
        #ifdef TEST_ShowReadSearchList
        printf("%s\n",SearchList[i]);
        #endif
    }
    fgets(surplus,10,pfile);//最后一行就是不足8位的字符串，读取它
    fclose(pfile);
	
	//编码查询表写入时有的为(null)，将其截断
    for(i=0;i<=0xFF;++i)
        if(strcmp(SearchList[i],"(null)")==0)
            SearchList[i][0]='\0';

    if((pfile=fopen(fCompress,"rb"))==NULL)
        ErrOpen(fCompress)

    char BitCode[Line+10],_01Str[8*Line+10]={0},EachStr[50];
    int bytenum;

    for(;feof(pfile)==0;)
    {
        memset(BitCode,0,strlen(BitCode));
        bytenum=fread(BitCode,sizeof(char),Line,pfile);
        //返回值为读取了的字节数
        for(i=0;i<bytenum;++i)
        {
        	//BitCode转为字符串
            BitToStr(BitCode[i],EachStr);
            #ifdef TEST_ShowRead_01Str
            printf("%s",EachStr);
            #endif;
            //将每个逆转得到的字符串连接到_01Str
            strcat(_01Str,EachStr);
        }
        //将_01Str写入到解压文件
        TransWrite2(_01Str,SearchList,bytenum);
    }
    fclose(pfile);
    //下面的代码作用：将不足8位的编码字符串连接到_01Str中，
    //按理将正好凑足8位。并将该(也是最后一个)字节写入解压文件
    strcat(_01Str,surplus);
    if((pfile=fopen(fDeCompress,"ab"))==NULL)
        ErrOpen(fDeCompress);

    for(i=0;i<=0xFF;++i)
        {
            if(SearchList[i][0]!='\0')
                if(strcmp(_01Str,SearchList[i])==0)
            {
                char OneCode=i;
                fwrite(&OneCode,sizeof(char),1,pfile);
                break;
            }
        }
    fclose(pfile);

}
/*基本操作，恕不解释*/
void BitToStr(char a,char *Each_Str)
{
	int bit[8]={0b00000001,0b00000010,0b00000100,
	0b00001000,0b00010000,0b00100000,0b01000000,0b10000000};
  Each_Str[0]=((a&bit[7])>> 7)+48;
  Each_Str[1]=((a&bit[6])>> 6)+48;
  Each_Str[2]=((a&bit[5])>> 5)+48;
  Each_Str[3]=((a&bit[4])>> 4)+48;
  Each_Str[4]=((a&bit[3])>> 3)+48;
  Each_Str[5]=((a&bit[2])>> 2)+48;
  Each_Str[6]=((a&bit[1])>> 1)+48;
  Each_Str[7]=((a&bit[0])>> 0)+48;
  Each_Str[8]='\0';
}

void TransWrite2(char *_01Str,char SearchList[0xFF+1][100],int bytenum)
{
    FILE    *pfile=NULL;
    if((pfile=fopen(fDeCompress,"ab"))==NULL)
        ErrOpen(fDeCompress);
    int i=0,times=0,j,Bitnum=bytenum*8,len=0;
    char *p=NULL;
    char temp[100];
    char OneCode;
    
	//循环遍历_01Str
    while(i<=Bitnum)
    {
        for(j=0;j<=0xFF;++j)//遍历编码查询表
        {
       			 //如果编码串不为空
            if(SearchList[j][0]!='\0')
            //比较 编码串长度个字符
                if(strncmp(&_01Str[i],SearchList[j],strlen(SearchList[j]))==0)
            {		//如果_01Str[i]开始匹配成功，
                len+=strlen(SearchList[j]);//统计总共写入了的_01Str中的字符数
                OneCode=j;//j的值即为该编码串对应的原字节值
                //把字节值写入解压文件，完成一个字节的解压
                //自定义宏调试
                fwrite(&OneCode,sizeof(char),1,pfile);
                #ifdef TEST_DeCompress
                printf("%c",OneCode);
                #endif
                times++;
                i+=strlen(SearchList[j]);
                //执行到这里说明已经解压了编码串长度个字符，i要随之变动
                break;
            }
        }
        if(j==0xFF+1)//说明遍历了编码查询表也没有匹配成功，继续从下一个字符匹配
            ++i;//所以加1
    }
    strcpy(_01Str,&_01Str[len]);//将未解压的子字符串安排到开头，下一次继续
    fclose(pfile);

}

//###############################################################/*模块四*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
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
92
93
94
95
96
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
124
125
126
127
128
129

主函数：

模块调用层次非常清晰，不多做解释

int main(void)
{
    printf("男同专用压缩软件启动！\n");//个性化
    ReadByte_WriteHex(fOriginFile);

    int N;
	HTree HT=NULL;
	HuffmanCode HC=NULL;
	CreateHTree(HT,N);//CreateHTree将会改变N的值
	HuffmanCoding(HT,HC,N);


	HuffmanCode SearchList=NULL;
	CreateSearchList(HC,SearchList);
    Compress(SearchList);


    DeCompress();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

效果展示

简单校验程序

#include <stdio.h>
#include <stdlib.h>
#define ErrOpen(filename){printf("文件%s打开失败\n",filename); exit(1);}
int main(void)
{
	char fOriginFile[]="1.txt",
		   fCompress[]="2.txt";

	FILE *pfile_1=NULL,*pfile_2=NULL;
	if((pfile_1=fopen(fOriginFile,"rb"))==NULL)
		ErrOpen(fOriginFile)
	if((pfile_2=fopen(fCompress,"rb"))==NULL)
	{
		fclose(pfile_1);
		ErrOpen(fCompress);
	}
	char Byte1,Byte2;
	int i;
	for(i=0;;)
	{
		if(feof(pfile_1)==0&&feof(pfile_2)==0)
		{
			fread(&Byte1,sizeof(char),1,pfile_1);
			fread(&Byte2,sizeof(char),1,pfile_2);
			if(Byte1!=Byte2)
				i++;
			printf("进行中！\n");
		}
		else
			break;
	}
	fclose(pfile_1);
	fclose(pfile_2);
	printf("\n\n\n有%d个字节不同",i);
	getchar();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

例一：朱自清《春》

在这里插入图片描述

压缩前：

在这里插入图片描述

压缩后：

在这里插入图片描述
解压还原率：100%
占原文件大小：74%

例二：《离骚》全文

在这里插入图片描述

压缩前：

在这里插入图片描述

压缩后：

在这里插入图片描述

解压还原率：100%
占原文件大小：71%

还试了一个压缩gif的，解压时候出了问题，有空再去改它。
更新日期:2020/6/18
美化什么的暂时先不搞，我要先挑战100M100%解压还原，然后估计一下数据量看看能不能搞1个G的

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/905846

详解C语言实现哈夫曼编码压缩_c语言,数据结构哈夫曼文件压缩设计

更新

最终状态：

最新文件(更新日期2021/6/28 10:48)

文章目录

目标：

必备知识：

思路

细节流程图

模块一

模块二

模块三

模块四

文件展示(样例)

fOriginFile

fDataTimes

fHuffmanCode

fCompress

fDeCompress

核心代码

讲解

模块一：

模块二：

模块三：

模块四：

主函数：

效果展示

简单校验程序

例一：朱自清《春》

压缩前：

压缩后：

例二：《离骚》全文

压缩前：

压缩后：