C++ 哈弗曼編碼的實現與反編碼

C++ 哈弗曼編碼的實現與反編碼

1. #include<iostream>
2. #include<stdlib.h>
3. #include<string.h>
4. using namespace std;
6. typedef struct{
7. int weight;
8. int parent,lchild,rchild;
9. int asc;
10. }HTNode,*HuffmanTree; //定義赫夫曼存儲結構
12. struct node{
13. int ASCII;
14. int n;
15. };
16. struct node a[127];
17. struct node w[127];
18. //一些全局變量
19. int count;
20. HTNode H_T[250];
21. char ** HC;
22. char filename[20];
24. //函數聲明
25. void menu1(); //菜單1
26. HuffmanTree HeapSort(HuffmanTree HT,int length); //堆排序
27. void MinHeapify(HuffmanTree HT, int k,int len); //調整成一個小頂堆
28. void buildMinHeap(HuffmanTree HT,int len); //建一個小頂堆
29. void swap(HTNode &t1,HTNode &t2); //交換兩結構體
30. void savefile(); //把輸入的英文文章保存到文件
31. void loadfile(); //從文件中讀取文章
32. HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n); //建立赫夫曼數並存入文件
33. void BianMa(HuffmanTree HT,int n ); //字符編碼
34. void BianMa_all(HuffmanTree HT,char**HC,char *filename); //整篇文章編碼
35. int loadfile2(); //從文件讀入文章
36. void JieMa(); //解碼
40. //主函數
41. void main()
42. {
43. char s;
44. while(s!='0')
45. {
46. system("cls");
47. cout<<"/n/n/n";
48. cout<<"/t/t/t/t赫夫曼編碼/譯碼器"<<endl<<endl<<endl<<endl<<endl;
49. cout<<"/t/t/t/t 1.編碼"<<endl<<endl<<endl<<endl;
50. cout<<"/t/t/t/t 2.譯碼"<<endl<<endl<<endl<<endl;
51. cout<<"/t/t/t/t 0.退出"<<endl<<endl<<endl<<endl;
52. cout<<"/t請輸入0—2進行選擇，按回車確認";
53. cin>>s;
54. switch(s)
55. {
56. case '1': menu1(); break;
57. case '2':
58. {
59. system("cls");
60. JieMa();
61. system("pause");
62. break;
63. }
65. }
67. }
68. }
74. //菜單1
75. void menu1(){
76. char s;
77. int i;
78. int a;
79. char c;
80. char fpname[20]="article.txt";
81. HuffmanTree HT;
82. while(s!='0'){
84. system("cls");
85. cout<<"/n/t/t/t/t編碼界面";
86. cout<<"/n/n/n/t/t/t/t1.輸入英文文章"<<endl;
87. cout<<"/n/n/t/t/t/t2.從文件中讀入文章"<<endl;
88. cout<<"/n/n/t/t/t/t0.返回上一層"<<endl;
89. cout<<"/n/t請輸入0—2進行選擇，按回車確認";
90. cin>>s;
91. switch(s){
92. case'1':
93. system("cls");
94. savefile();
95. loadfile();
96. CreateHuffman(HT,w,count);
97. BianMa(HT,count);
98. BianMa_all(HT,HC,fpname);
99. system("cls");
100. cout<<"出現字符種類共計：";
101. cout<<count<<endl;
102. for(i=1;i<=count;i++)
103. { a=HT[i].asc;
104. c=(char)a;
107. cout<<"________________________________________________________________________________"<<endl;
108. cout<<"/t/t/t字符：";
109. cout<<c<<endl;
110. cout<<"/t/t/tASCII碼：";
111. cout<<a<<endl;
112. cout<<"/t/t/t頻數：";
113. cout<<HT[i].weight<<endl;
114. cout<<"/t/t/t赫夫曼編碼：";
115. cout<<HC[i]<<endl;
119. }
120. cout<<"________________________________________________________________________________";
121. cout<<"/n/t/t整篇文章的編碼已存入文件“赫夫曼編碼.txt”"<<endl;
123. system("pause");
124. break;
126. case'2':
127. system("cls");
128. if(loadfile2())
129. { system("pause");
130. return;}
131. CreateHuffman(HT,w,count);
132. BianMa(HT,count);
133. BianMa_all(HT,HC,filename);
134. system("cls");
135. cout<<"出現字符種類共計：";
136. cout<<count<<endl;
137. for(i=1;i<=count;i++)
138. { a=HT[i].asc;
139. c=(char)a;
142. cout<<"________________________________________________________________________________"<<endl;
143. cout<<"/t/t/t字符：";
144. cout<<c<<endl;
145. cout<<"/t/t/tASCII碼：";
146. cout<<a<<endl;
147. cout<<"/t/t/t頻數：";
148. cout<<HT[i].weight<<endl;
149. cout<<"/t/t/t赫夫曼編碼：";
150. cout<<HC[i]<<endl;
154. }
155. cout<<"________________________________________________________________________________";
156. cout<<"/n/t/t整篇文章的編碼已存入文件“赫夫曼編碼.txt”"<<endl;
157. system("pause");
158. break;
159. }
161. }
163. }
169. //交換結構體
170. void swap(HTNode &t1,HTNode &t2)
171. {
172. HTNode m;
174. m = t1;
175. t1 = t2;
176. t2 = m;
177. }
180. //從鍵盤輸入文章並保存
181. void savefile(){
183. FILE *fp;
184. char article;
185. if((fp=fopen("article.txt","w"))==NULL){
187. printf("打開文件不成功！");
188. exit(0);
189. }
190. cout<<"請輸入英文文章,以#結束:";
191. getchar();
192. article=getchar();
193. while(article!='#'){
195. fputc(article,fp);
197. article=getchar();
198. }
199. fclose(fp);
200. }
204. //從文件讀取文章，並統計字符出現頻數
205. void loadfile(){
208. FILE *fp;
209. char ch;
210. int i,k,j=0;
211. count=0;
212. for(i=0;i<=127;i++) //把所有字符的ascii碼存在數組
213. { a[i].ASCII=i;
214. a[i].n=0;
216. }
217. if((fp=fopen("article.txt","r"))==NULL){
219. printf("打開文件不成功！");
220. exit(0);
221. }
222. ch=fgetc(fp);
223. k=(int)ch;
224. a[k].n++;
225. while(!feof(fp)){
226. ch=fgetc(fp);
227. k=(int)ch;
228. a[k].n++;
229. }
230. fclose(fp);
232. for(i=0;i<=127;i++) //統計字符種類總數
233. {
234. ch=(char)i;
235. if(a[i].n){
236. count++;
237. }
238. }
239. for(i=0;i<=127;i++)
240. {
241. for(;j<count;)
242. {
243. if(a[i].n)
244. {
245. w[j].n=a[i].n;
246. w[j].ASCII=a[i].ASCII;
247. j++;
248. break;
249. }
250. else break;
251. }
252. }
254. }
258. //調整為小頂堆
259. void MinHeapify(HuffmanTree HT, int k,int len)
260. {
261. int left=k*2;
262. int right=k*2+1;
263. int large;
264. int l=len;
266. large = k;
267. if (left<=l&&HT[left].weight<HT[large].weight)
268. large = left;
270. if (right<=l&& HT[right].weight<HT[large].weight)
271. large=right;
273. if (large!=k)
274. {
275. swap(HT[k],HT[large]);
276. MinHeapify(HT,large,l);
277. }
278. }
281. //建立小頂堆
282. void buildMinHeap(HuffmanTree HT,int len)
283. {
284. int i;
285. for (i=len/2;i>=1;i--)
286. {
287. MinHeapify(HT,i,len);
288. }
289. }
292. //堆排序
293. HuffmanTree HeapSort(HuffmanTree HT,int length)
294. {
295. int i;
296. int l=length;
297. buildMinHeap(HT,length);
298. for (i=length;i>= 2;i--)
299. {
300. swap(HT[1],HT[i]);
301. length--;
302. MinHeapify(HT,1,length);
303. }
306. return HT;
307. }
311. //建立赫夫曼數
312. HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n)
313. {
314. int i,m,s1,s2,k1,k2,j,x,a;
315. FILE *fp,*fp2;
318. if(n<=1) return HT;
319. m=2*n-1;
320. HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0不用
322. for(i=1,j=0;i<=n;i++,j++)
323. { HT[i].asc=w[j].ASCII;
324. HT[i].weight=w[j].n;
325. HT[i].parent=0;
326. HT[i].lchild=0;
327. HT[i].rchild=0;
328. }
329. for(;i<=m;i++)
330. { a=250+i;
331. HT[i].asc=a;//父親節點的asc可以是大於127的任意值
332. HT[i].weight=0;
333. HT[i].parent=0;
334. HT[i].lchild=0;
335. HT[i].rchild=0;
336. }
337. for(i=1;i<=n;i++){
339. H_T[i].asc=HT[i].asc;
340. H_T[i].parent=HT[i].parent;
341. H_T[i].lchild=HT[i].lchild;
342. H_T[i].rchild=HT[i].rchild;
343. H_T[i].weight=HT[i].weight;
344. }
346. for(i=n+1,x=n;i<=m;i++,x--)
347. {
349. HeapSort(H_T,x);
350. k1=H_T[x].asc;
351. k2=H_T[x-1].asc;
352. for(j=1;j<=127;j++)
353. {
354. if(HT[j].asc==k1)
355. { s1=j;break;}
357. }
359. for(j=1;j<=127;j++)
360. {
361. if(HT[j].asc==k2)
362. { s2=j;break;}
365. }
367. HT[s2].parent=i;
368. HT[s1].parent=i;
369. HT[i].lchild=s1;
370. HT[i].rchild=s2;
371. HT[i].weight=HT[s1].weight+HT[s2].weight;
373. H_T[x-1].asc=HT[i].asc;
374. H_T[x-1].lchild=HT[i].lchild;
375. H_T[x-1].parent=HT[i].parent;
376. H_T[x-1].rchild=HT[i].rchild;
377. H_T[x-1].weight=HT[i].weight;
379. }
380. if((fp2=fopen("count.txt","w"))==NULL) //保存赫夫曼樹
381. {
382. cout<<"文件打開不成功！"<<endl;
383. exit(0);
384. }
385. fputc(count,fp2);
386. if((fp=fopen("HuffmanTree.dat","wb"))==NULL)
387. { cout<<"文件打開不成功！"<<endl;
388. exit(0);
390. }
392. for(i=1;i<=(2*count-1);i++){
393. fwrite(&HT[i],sizeof(HTNode),1,fp);
394. }
395. fclose(fp);
396. fclose(fp2);
397. return HT;
399. }
404. //逆向編碼
405. void BianMa(HuffmanTree HT,int n){
406. char *cd,temp;
408. int c,f,i,j,len,p,q;
410. cd=(char *)malloc(n*sizeof(char));
411. HC=(char * *)malloc(n*sizeof(char*));
412. for(i=1;i<=n;i++){
413. for(c=i,f=HT[i].parent,j=0;f!=0;c=f,f=HT[f].parent,j++)
414. { if(HT[f].lchild==c) cd[j]='0';
415. else cd[j]='1';
416. if(HT[f].parent==0)
417. cd[j+1]='/0';
419. }
422. len=strlen(cd);
423. for(p=0,q=len-1;p<=q;p++,q--)
424. {
425. temp=cd[q];
426. cd[q]=cd[p];
427. cd[p]=temp;
428. }
429. cd[len]='/0';
430. HC[i]=(char*)malloc((len+10)*sizeof(char));
431. strcpy(HC[i],cd);
433. }
437. }
443. //整篇文章編碼，並存入文件
444. void BianMa_all(HuffmanTree HT,char**HC,char *filename){
445. char ch;
446. int k,i;
447. FILE *fp,*fp2;
449. char code[100];
450. if((fp=fopen(filename,"r"))==NULL){
452. printf("打開文件不成功！");
453. exit(0);
454. }
455. if((fp2=fopen("赫夫曼編碼.txt","w"))==NULL){
457. printf("打開文件不成功！");
458. exit(0);
459. }
460. ch=fgetc(fp);
461. k=(int)ch;
462. while(!feof(fp))
463. {
465. for(i=1;i<=count;i++)
466. {
467. if(k==HT[i].asc)
468. strcpy(code,HC[i]);
470. }
471. fputs(code,fp2);
472. ch=fgetc(fp);
473. k=(int)ch;
475. }
476. fclose(fp);
477. fclose(fp2);
481. }
483. void JieMa(){
484. int i,k,a,t,n=0;
485. FILE *fp1,*fp2,*fp3;
486. char ch,c;
487. HuffmanTree ht;
488. if((fp3=fopen("count.txt","r"))==NULL) //從文件讀出字符總數
489. {
490. printf("打開文件不成功！");
491. exit(0);
492. }
493. n=fgetc(fp3);
494. ht=(HuffmanTree)malloc(2*n*sizeof(HTNode));
495. if((fp1=fopen("赫夫曼編碼.txt","r"))==NULL)
496. {
498. printf("打開文件不成功！");
499. exit(0);
500. }
502. if((fp2=fopen("HuffmanTree.dat","rb"))==NULL)
503. { cout<<"文件打開不成功！"<<endl;
504. exit(0);
506. }
507. for(i=1;i<=2*n-1;i++)
509. fread(&ht[i],sizeof(HTNode),1,fp2);
512. for(i=1;i<=2*n-1;i++)
513. {
514. if(ht[i].parent==0){t=k=i;break;}
515. }
517. ch=fgetc(fp1);
518. while(!feof(fp1)){
519. if(ch=='0')
520. {
521. k=ht[k].lchild;
522. if(ht[k].lchild==0)
523. {a=ht[k].asc;
524. c=(char)a;
525. printf("%c",c);;
527. k=t;
528. }
529. }
530. if(ch=='1')
531. {
532. k=ht[k].rchild;
533. if(ht[k].lchild==0)
534. { a=ht[k].asc;
535. c=(char)a;
536. printf("%c",c);
538. k=t;
539. }
541. }
544. ch=fgetc(fp1);
545. }
546. fclose(fp1);
547. fclose(fp2);
549. }
554. //讀取文件中的文章，可自己選擇文件
555. int loadfile2(){
558. FILE *fp;
559. char ch;
560. int i,k,j=0;
561. count=0;
562. for(i=0;i<=127;i++)
563. { a[i].ASCII=i;
564. a[i].n=0;
566. }
567. cout<<"/n/n/n/t/t/t請輸入你要打開的文件名：";
568. cin>>filename;
569. if((fp=fopen(filename,"r"))==NULL){
571. printf("打開文件不成功！");
572. return 1;
573. }
574. ch=fgetc(fp);
575. k=(int)ch;
576. a[k].n++;
577. while(!feof(fp)){
578. ch=fgetc(fp);
579. k=(int)ch;
580. a[k].n++;
581. }
582. fclose(fp);
584. for(i=0;i<=127;i++){
585. ch=(char)i;
586. if(a[i].n){
587. count++;
588. }
589. }
590. for(i=0;i<=127;i++)
591. {
592. for(;j<count;)
593. {
594. if(a[i].n)
595. {
596. w[j].n=a[i].n;
597. w[j].ASCII=a[i].ASCII;
598. j++;
599. break;
600. }
601. else break;
602. }
603. }
604. return 0;
605. }