1#include<iostream> 2#include<stdlib.h> 3#include<string.h> 4using namespace std; 5 6typedef struct{ 7 int weight; 8 int parent,lchild,rchild; 9 int asc; 10}HTNode,*HuffmanTree; //定义赫夫曼存储结构 11 12struct node{ 13 int ASCII; 14 int n; 15}; 16struct node a[127]; 17struct node w[127]; 18//一些全局变量 19int count; 20HTNode H_T[250]; 21char ** HC; 22char filename[20]; 23 24//函数声明 25void menu1(); //菜单1 26HuffmanTree HeapSort(HuffmanTree HT,int length); //堆排序 27void MinHeapify(HuffmanTree HT, int k,int len); //调整成一个小顶堆 28void buildMinHeap(HuffmanTree HT,int len); //建一个小顶堆 29void swap(HTNode &t1,HTNode &t2); //交换两结构体 30void savefile(); //把输入的英文文章保存到文件 31void loadfile(); //从文件中读取文章 32HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n); //建立赫夫曼数并存入文件 33void BianMa(HuffmanTree HT,int n ); //字符编码 34void BianMa_all(HuffmanTree HT,char**HC,char *filename); //整篇文章编码 35int loadfile2(); //从文件读入文章 36void JieMa(); //解码 37 38 39 40//主函数 41void 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 } 64 65 } 66 67 } 68} 69 70 71 72 73 74//菜单1 75void menu1(){ 76 char s; 77 int i; 78 int a; 79 char c; 80 char fpname[20]="article.txt"; 81 HuffmanTree HT; 82while(s!='0'){ 83 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; 105 106 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; 116 117 118 119 } 120 cout<<"________________________________________________________________________________"; 121 cout<<"/n/t/t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl; 122 123 system("pause"); 124 break; 125 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; 140 141 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; 151 152 153 154 } 155 cout<<"________________________________________________________________________________"; 156 cout<<"/n/t/t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl; 157 system("pause"); 158 break; 159 } 160 161} 162 163} 164 165 166 167 168 169//交换结构体 170void swap(HTNode &t1,HTNode &t2) 171{ 172 HTNode m; 173 174 m = t1; 175 t1 = t2; 176 t2 = m; 177 } 178 179 180//从键盘输入文章并保存 181void savefile(){ 182 183 FILE *fp; 184 char article; 185 if((fp=fopen("article.txt","w"))==NULL){ 186 187 printf("打开文件不成功！"); 188 exit(0); 189 } 190 cout<<"请输入英文文章,以#结束:"; 191 getchar(); 192 article=getchar(); 193 while(article!='#'){ 194 195 fputc(article,fp); 196 197 article=getchar(); 198 } 199 fclose(fp); 200} 201 202 203 204//从文件读取文章，并统计字符出现频数 205void loadfile(){ 206 207 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; 215 216 } 217 if((fp=fopen("article.txt","r"))==NULL){ 218 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); 231 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 } 253 254} 255 256 257 258//调整为小顶堆 259void 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; 265 266 large = k; 267 if (left<=l&&HT[left].weight<HT[large].weight) 268 large = left; 269 270 if (right<=l&& HT[right].weight<HT[large].weight) 271 large=right; 272 273 if (large!=k) 274 { 275 swap(HT[k],HT[large]); 276 MinHeapify(HT,large,l); 277 } 278} 279 280 281//建立小顶堆 282void 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} 290 291 292//堆排序 293HuffmanTree 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 } 304 305 306 return HT; 307} 308 309 310 311//建立赫夫曼数 312HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n) 313{ 314 int i,m,s1,s2,k1,k2,j,x,a; 315 FILE *fp,*fp2; 316 317 318 if(n<=1) return HT; 319 m=2*n-1; 320 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0不用 321 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++){ 338 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 } 345 346 for(i=n+1,x=n;i<=m;i++,x--) 347 { 348 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;} 356 357 } 358 359 for(j=1;j<=127;j++) 360 { 361 if(HT[j].asc==k2) 362 { s2=j;break;} 363 364 365 } 366 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; 372 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; 378 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); 389 390 } 391 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; 398 399} 400 401 402 403 404//逆向编码 405void BianMa(HuffmanTree HT,int n){ 406 char *cd,temp; 407 408 int c,f,i,j,len,p,q; 409 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'; 418 419 } 420 421 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); 432 433 } 434 435 436 437} 438 439 440 441 442 443//整篇文章编码，并存入文件 444void BianMa_all(HuffmanTree HT,char**HC,char *filename){ 445 char ch; 446 int k,i; 447 FILE *fp,*fp2; 448 449 char code[100]; 450 if((fp=fopen(filename,"r"))==NULL){ 451 452 printf("打开文件不成功！"); 453 exit(0); 454 } 455 if((fp2=fopen("赫夫曼编码.txt","w"))==NULL){ 456 457 printf("打开文件不成功！"); 458 exit(0); 459 } 460 ch=fgetc(fp); 461 k=(int)ch; 462 while(!feof(fp)) 463 { 464 465 for(i=1;i<=count;i++) 466 { 467 if(k==HT[i].asc) 468 strcpy(code,HC[i]); 469 470 } 471 fputs(code,fp2); 472 ch=fgetc(fp); 473 k=(int)ch; 474 475 } 476 fclose(fp); 477 fclose(fp2); 478 479 480 481} 482 483void 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 { 497 498 printf("打开文件不成功！"); 499 exit(0); 500 } 501 502 if((fp2=fopen("HuffmanTree.dat","rb"))==NULL) 503 { cout<<"文件打开不成功！"<<endl; 504 exit(0); 505 506 } 507for(i=1;i<=2*n-1;i++) 508 509 fread(&ht[i],sizeof(HTNode),1,fp2); 510 511 512 for(i=1;i<=2*n-1;i++) 513 { 514 if(ht[i].parent==0){t=k=i;break;} 515 } 516 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);; 526 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); 537 538 k=t; 539 } 540 541 } 542 543 544 ch=fgetc(fp1); 545 } 546 fclose(fp1); 547 fclose(fp2); 548 549} 550 551 552 553 554//读取文件中的文章，可自己选择文件 555int loadfile2(){ 556 557 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; 565 566 } 567 cout<<"/n/n/n/t/t/t请输入你要打开的文件名："; 568 cin>>filename; 569 if((fp=fopen(filename,"r"))==NULL){ 570 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); 583 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}
C++ 哈弗曼编码的实现与反编码
Wesley13
2021-10-11
1267 0 0
点赞
收藏
评论区
加载中...