数据结构--哈弗曼编码器

哈夫曼编码本人比较懒….关于哈夫曼树知识点的介绍就不在博客上说了, 请同学们自行查阅相关资料, 直接上代码, 简单 ,粗暴. 如果有哪里没看明白或者是对程序有更好的见解, 请评论在博文的下方, 或者私信我, 我看到后会第一时间回复, 希望大家踊跃发言语言: C知识点: 哈夫曼编码问题描述: 问题描述:设计一个赫夫曼编码译码系统,对某个英文文本文件(.txt)中的字符进行哈夫曼编码,并将该txt文件生

哈夫曼编码


本人比较懒….关于哈夫曼树知识点的介绍就不在博客上说了, 请同学们自行查阅相关资料, 直接上代码, 简单 ,粗暴.
如果有哪里没看明白或者是对程序有更好的见解, 请评论在博文的下方, 或者私信我, 我看到后会第一时间回复, 希望大家踊跃发言


语言: C

知识点: 哈夫曼编码


问题描述: 问题描述:设计一个赫夫曼编码译码系统,对某个英文文本文件(.txt)中的字符进行哈夫曼编码,并将该txt文件生成编码文件(.cod);反过来还可将一个编码文件(.cod)还原为一个文本文件(.txt)。


功能及界面要求

本题可采用console控制台或可视化界面,console控制台参考界面如下
                   哈夫曼编码译码器                           
*       1、选择需要进行编码的文件                                   
*       2、建立哈夫曼树                                             
*       3、建立密码本并对文件编码                                   
*       4、选择需要进行解码的文件并解码                             
*       5、按位压缩方式对文件进行压缩                               

功能说明

①“选择需要进行编码的文件”:选择该选项后,提示用户输入(或选择)要进行编码(加密)的文件(包括路径和文件名)。
②“建立哈夫曼树”: 选择该选项后,程序根据1中确定的文件建立哈夫曼树。
③“建立密码本并对文件编码”: 选择该选项后,程序根据2中建立好的哈夫曼树为1中出现的每个字符建立编码,并对文件进行编码,在进行编码前提示用户将编码文件存放在哪个文件(文件扩展名为cod)中。
④“选择需要进行解码的文件并解码”: 选择该选项后,提示用户输入(或选择)需要进行解码(译码)的文件(文件扩展名为cod),并输入(或选择)将解码(译码)后的文件存放到哪个文件(文件扩展名为txt),程序将cod文件根据3建立的密码本进行解码,解码到txt文件中。
⑤“按位压缩方式对文件进行压缩”:对cod文件进行压缩,显示压缩比(即压缩后的编码文件字节数/编码前的原txt文件字节数),并能对压缩后的cod文件进行解码。


存储要求:

 哈夫曼树采用数组存储
 密码本在内存中采用数组存储,也可根据用户选择将密码本存到文件中。
 编码文件和译码文件都采用文本文件存储。


算法及技术指导:

①为实现功能2,首先用对原txt文件进行扫描,得到每个字符(包括空格、标点符号和回车换行)出现的次数,并根据教材提供的算法得到哈夫曼树。
②为实现功能3,首先根据哈夫曼树及教材提供的算法得到每个出现字符的哈夫曼编码( 即建立密码本),并对原txt文件重新进行扫描,扫描到某个字符时在密码本中找到该字符的哈夫曼编码,写入到编码文件中。
③为实现功能4,要扫描编码文件,扫描(读)到‘0’或‘1’时,根据哈夫曼树进行相应的处理,直到扫描(读)到某个‘0’或‘1’后,哈夫曼树已经到达某个叶子,将该叶子对应的字符写入到解码文件中。
④为实现功能5,对编码后的cod文件进行处理,将每8个(‘0’或‘1’)字符串转化为相应的整数(用1个字节存储)并写入压缩文件中,注意对最后一个01串(长度<=8)的处理。


代码如下

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
char filenamemi[100];
char filefile[100];
char filebian[100];
typedef struct
{
int weight;
char flag;
int parent, lchild, rchild;
} HTNode, *HuffmanTree;
typedef struct ASCII
{
char flag;
int c;
struct ASCII *next;
} ASCII, *LinkList;
typedef struct txt
{
char flag;
char hafuman[5000];
} txtNode;
LinkList L;
typedef char **HuffmanCode;
bool InitList(LinkList &L)//初始化链表
{
L = new ASCII;
L->c = 1;
L->next = NULL;
return true;
}
void Show(LinkList L)//显示链表
{
LinkList p;
p = L->next;
while(p)
{
printf(" %c, %d\n", p->flag, p->c);
p = p->next;
}
cout<<endl;
}
int Choice() //选择文件以及创建权重值
{
FILE *fp;
char a;
int num = 0, key = 0;
int instance = 0;
LinkList p, s, m;
InitList(L);
s = L;
m = L;
getchar();
//char filefile[100] ;
while(!key)
{
printf("请输入你要打开的文件名及路径,如c:\\users\\lenovo\\desktop\\7\\1.txt\n");
gets(filefile);
if ((fp=fopen(filefile,"r"))==NULL)
{
printf("打开文件%s出现错误\n",filefile);
key = 0;
return 0;
}
key = 1;
}
while((a = fgetc(fp)) != EOF)
{
s = L->next;
printf("%c ", a);
while(s)
{
if(s->flag == a)//如果在文本中出现了, 当前字符, 那么当前字符的权重值++
{
s->c++;
instance = 1;
break;
}
s = s->next;
}
if(instance == 0)//如果当前文本没有改字符, 那么, 创建该字符,插入到文本当中
{
p = new ASCII;
p->flag = a;
p->c = 1;
m->next = p;
p->next = NULL;
m = p;
num++;//文本中多少结点
}
instance = 0;
}
cout<<endl;
Show(L);
//fseek(fp,0,SEEK_SET);
fclose(fp);
return num;
}
void Select(HuffmanTree &HT, int num, int *s1, int *s2) //寻找两个最小的且双亲为0的最小节点
{
int i, sec = 0, fir = 0;//a是次小, b是最小
int second = -1, first = -1;
HTNode L1, L2;//L1次小, L2最小
for(i = num; i >= 1; i--)//选择两个双亲部不为0的结点
{
if(HT[i].parent == 0 && second == -1) second = i;
else if(HT[i].parent == 0 && first == -1) first = i;
if(first!=-1 && second!=-1) break;
}
//cout<<second<<" "<<first<<endl;
if(HT[second].weight > HT[first].weight)
{
L1 = HT[second];
L2 = HT[first];
sec = second;
fir = first;
}
else
{
L1 = HT[first];
L2 = HT[second];
sec = first;
fir = second;
}
for(i = num; i >= 1; i--)//从剩下的节点中找到两个最小的节点
{
if( (HT[i].weight < L2.weight) &&(HT[i].parent == 0) && i!=second && i!=first)
{
L1 = L2;
L2 = HT[i];
sec = fir;
fir = i;
}
else if( (HT[i].weight < L1.weight) && (HT[i].parent == 0) && i!=second && i!=first)
{
L1 = HT[i];
sec = i;
}
}
*s1 = fir;
*s2 = sec;
}
bool CreatHuffmanaTree(HuffmanTree &HT, int num) //创建哈夫曼树
{
int m, i;
LinkList p;
p = L->next;
if(num <= 1) return false;
m = 2*num-1;
HT = new HTNode[m+1];
for(i = 1; i <= m; i++)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
for(i = 1; i <= num; i++)
{
HT[i].weight = p->c;
HT[i].flag = p->flag;
p = p->next;
}
int s1=0, s2=0;
for(i = num+1; i <= m; i++)
{
Select(HT, i-1, &s1, &s2);
//cout<<s1<<" "<<s2<<endl;
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
return true;
}
bool CreatHuffmanaCode(HuffmanTree HT, int num) //创建哈夫曼编码
{
char *cd;
int i, c, f, start, key = 0;
FILE *fp;
char flag;
getchar();
while(!key)
{
printf("请输入你要保存密码本的文件名及路径,如c:\\users\\lenovo\\desktop\\7\\密码本.txt\n");
gets(filenamemi);
if ((fp=fopen(filenamemi,"w"))==NULL)
{
printf("保存文件%s出现错误, 请重新输入\n",filenamemi);
key = 0;
}
key = 1;
}
cd = new char[num];
cd[num-1] = '\0';
for(i = 1; i <= num; i++)
{
start = num-1;
c = i;
f = HT[i].parent;
flag = HT[i].flag;
while(f != 0)
{
--start;
if(HT[f].lchild == c) cd[start] = '0';
else cd[start] = '1';
c = f;
f = HT[f].parent;
}
printf("%c %s\n", flag, &cd[start]);
fprintf(fp,"%c %s\n", flag, &cd[start]);
}
delete cd;
fclose(fp);
}
bool CreatTxtCode(int num)//创建文本编码
{
FILE *fp, *fp1, *fp2;
int key = 0;
//char filename[100];
txtNode txt[257];
char a;
getchar();
while(!key)
{
printf("请输入你要保存编码的文件名及路径,如c:\\users\\lenovo\\desktop\\7\\1.cod\n");
gets(filebian);
if ((fp=fopen(filebian,"w"))==NULL)
{
printf("保存文件%s出现错误, 请重新输入\n",filebian);
key = 0;
}
key = 1;
}
int i = 0, nu = 1, j;
fp1 = fopen(filenamemi,"r");
fp2 = fopen(filefile,"r");
char interim[1000];
fgets(interim, 100, fp1);
while(!feof(fp1))
{
txt[nu-1].flag = interim[0];
i = strlen(interim);
for(j = 2; j < i-1; j++)
{
txt[nu-1].hafuman[j-2] = interim[j];
}
fgets(interim, 100, fp1);
nu++;
}
for(i = 0; i <= nu; i++)
{
cout<<txt[i].flag<<" "<<txt[i].hafuman<<endl;
}
while((a = fgetc(fp2)) != EOF)
{
for(i = 0; i <= nu; i++)
{
if(a == txt[i].flag)
{
fprintf(fp,"%s",txt[i].hafuman);
}
}
}
fclose(fp);
fclose(fp1);
fclose(fp2);
return true;
}
bool ReductionTxt(HuffmanTree HT, int num)//创建文本节点
{
FILE *fp, *fp1;//fp----编码文件 fp1------还原之后的文件
int key = 0;
char filename[100], filename1[100];
char a;
getchar();
if ((fp=fopen(filebian,"r"))==NULL)
{
printf("打开文件%s出现错误\n",filebian);
key = 0;
return false;
}
while(!key)
{
printf("请输入你要保存的文件名及路径,如c:\\users\\lenovo\\desktop\\7\\2.txt\n");
gets(filename1);
if ((fp1=fopen(filename1,"w"))==NULL)
{
printf("打开文件%s出现错误\n",filename1);
key = 0;
return false;
}
key = 1;
}
int kk = 2*num-1;
while((a = fgetc(fp)) != EOF)
{
if(a == '0')
{
kk = HT[kk].lchild;
}
else
{
kk = HT[kk].rchild;
}
if( (HT[kk].lchild == 0) && (HT[kk].rchild == 0) )
{
fprintf(fp1,"%c", HT[kk].flag);
kk = 2*num-1;
}
}
fclose(fp);
fclose(fp1);
return true;
}
void zip()//压缩文件
{
FILE *fp, *fp1;//fp----编码文件 fp1------压缩文件
int key = 0, in, i;
char filename[100], filename1[100];
char a;
int twopower[11] = {1,2,4,8,16,32,64,128,256,512,1024};
getchar();
if ((fp=fopen(filebian,"r"))==NULL)
{
printf("打开文件%s出现错误\n",filebian);
key = 0;
return;
}
key = 0;
while(!key)
{
printf("请输入保存的文件名及路径,如C:\\users\\lenovo\\desktop\\7\\2.cod\n");
gets(filename1);
if ((fp1=fopen(filename1,"w"))==NULL)
{
printf("打开文件%s出现错误\n",filename1);
key = 0;
return ;
}
key = 1;
}
//fp1=fopen("C:\\users\\lenovo\\desktop\\7\\2.cod","w");
in = 0;
int sum = 0, fla = 2;
a = fgetc(fp);
while(!feof(fp))
{
sum = sum + int(a-'0')*twopower[7-in];
//cout<<int(a-'0')<<" "<<twopower[in]<<" "<<sum<<endl;
in++;
a = fgetc(fp);
if(in == 8 || feof(fp))
{
in = 0;
fprintf(fp1, "%d ", sum);
sum = 0;
}
}
fclose(fp);
fclose(fp1);
}
int main()
{
int num;
HuffmanTree L;
start:
printf("******************************************************************\n\n");
printf("哈夫曼编码译码器\n\n");
printf("*\t1、选择需要进行编码的文件\t\t*\n\n");
printf("*\t2、建立哈夫曼树\t\t\t\t*\n\n");
printf("*\t3、建立密码本并对文件编码\t\t*\n\n");
printf("*\t4、选择需要进行解码的文件并解码\t\t*\n\n");
printf("*\t5、按位压缩方式对文件进行压缩\t\t*\n\n\n");
printf("******************************************************************\n\n");
int option = 0;
cin>>option;
while(1)
{
switch(option)
{
case 1:
num = Choice();
break;
case 2:
if(CreatHuffmanaTree(L, num))cout<<"成功"<<endl;
break;
case 3:
CreatHuffmanaCode(L, num);
if(CreatTxtCode(num)) cout<<"成功"<<endl;
break;
case 4:
if(ReductionTxt(L, num)) cout<<"成功"<<endl;
break;
case 5:
zip();
break;
}
goto start;
}
//cout<<endl;
//cout<<endl;
//releasezip();
return 0;
}
越来越多的平台(微信公众平台,新浪微博,简书,百度打赏等)支持打赏功能,付费阅读时代越来越近,特此增加了打赏功能,支持微信打赏和支付宝打赏。坚持原创技术分享,您的支持将鼓励我继续创作!