C++ 哈弗曼编码的实现与反编码
C++ 哈弗曼编码的实现与反编码
C++ 哈弗曼编码的实现与反编码
- #include<iostream>
- #include<stdlib.h>
- #include<string.h>
- using namespace std;
- typedef struct{
- int weight;
- int parent,lchild,rchild;
- int asc;
- }HTNode,*HuffmanTree; //定义赫夫曼存储结构
- struct node{
- int ASCII;
- int n;
- };
- struct node a[127];
- struct node w[127];
- //一些全局变量
- int count;
- HTNode H_T[250];
- char ** HC;
- char filename[20];
- //函数声明
- void menu1(); //菜单1
- HuffmanTree HeapSort(HuffmanTree HT,int length); //堆排序
- void MinHeapify(HuffmanTree HT, int k,int len); //调整成一个小顶堆
- void buildMinHeap(HuffmanTree HT,int len); //建一个小顶堆
- void swap(HTNode &t1,HTNode &t2); //交换两结构体
- void savefile(); //把输入的英文文章保存到文件
- void loadfile(); //从文件中读取文章
- HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n); //建立赫夫曼数并存入文件
- void BianMa(HuffmanTree HT,int n ); //字符编码
- void BianMa_all(HuffmanTree HT,char**HC,char *filename); //整篇文章编码
- int loadfile2(); //从文件读入文章
- void JieMa(); //解码
- //主函数
- void main()
- {
- char s;
- while(s!='0')
- {
- system("cls");
- cout<<"/n/n/n";
- cout<<"/t/t/t/t赫夫曼编码/译码器"<<endl<<endl<<endl<<endl<<endl;
- cout<<"/t/t/t/t 1.编码"<<endl<<endl<<endl<<endl;
- cout<<"/t/t/t/t 2.译码"<<endl<<endl<<endl<<endl;
- cout<<"/t/t/t/t 0.退出"<<endl<<endl<<endl<<endl;
- cout<<"/t请输入0—2进行选择,按回车确认";
- cin>>s;
- switch(s)
- {
- case '1': menu1(); break;
- case '2':
- {
- system("cls");
- JieMa();
- system("pause");
- break;
- }
- }
- }
- }
- //菜单1
- void menu1(){
- char s;
- int i;
- int a;
- char c;
- char fpname[20]="article.txt";
- HuffmanTree HT;
- while(s!='0'){
- system("cls");
- cout<<"/n/t/t/t/t编码界面";
- cout<<"/n/n/n/t/t/t/t1.输入英文文章"<<endl;
- cout<<"/n/n/t/t/t/t2.从文件中读入文章"<<endl;
- cout<<"/n/n/t/t/t/t0.返回上一层"<<endl;
- cout<<"/n/t请输入0—2进行选择,按回车确认";
- cin>>s;
- switch(s){
- case'1':
- system("cls");
- savefile();
- loadfile();
- CreateHuffman(HT,w,count);
- BianMa(HT,count);
- BianMa_all(HT,HC,fpname);
- system("cls");
- cout<<"出现字符种类共计:";
- cout<<count<<endl;
- for(i=1;i<=count;i++)
- { a=HT[i].asc;
- c=(char)a;
- cout<<"________________________________________________________________________________"<<endl;
- cout<<"/t/t/t字符:";
- cout<<c<<endl;
- cout<<"/t/t/tASCII码:";
- cout<<a<<endl;
- cout<<"/t/t/t频数:";
- cout<<HT[i].weight<<endl;
- cout<<"/t/t/t赫夫曼编码:";
- cout<<HC[i]<<endl;
- }
- cout<<"________________________________________________________________________________";
- cout<<"/n/t/t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl;
- system("pause");
- break;
- case'2':
- system("cls");
- if(loadfile2())
- { system("pause");
- return;}
- CreateHuffman(HT,w,count);
- BianMa(HT,count);
- BianMa_all(HT,HC,filename);
- system("cls");
- cout<<"出现字符种类共计:";
- cout<<count<<endl;
- for(i=1;i<=count;i++)
- { a=HT[i].asc;
- c=(char)a;
- cout<<"________________________________________________________________________________"<<endl;
- cout<<"/t/t/t字符:";
- cout<<c<<endl;
- cout<<"/t/t/tASCII码:";
- cout<<a<<endl;
- cout<<"/t/t/t频数:";
- cout<<HT[i].weight<<endl;
- cout<<"/t/t/t赫夫曼编码:";
- cout<<HC[i]<<endl;
- }
- cout<<"________________________________________________________________________________";
- cout<<"/n/t/t整篇文章的编码已存入文件“赫夫曼编码.txt”"<<endl;
- system("pause");
- break;
- }
- }
- }
- //交换结构体
- void swap(HTNode &t1,HTNode &t2)
- {
- HTNode m;
- m = t1;
- t1 = t2;
- t2 = m;
- }
- //从键盘输入文章并保存
- void savefile(){
- FILE *fp;
- char article;
- if((fp=fopen("article.txt","w"))==NULL){
- printf("打开文件不成功!");
- exit(0);
- }
- cout<<"请输入英文文章,以#结束:";
- getchar();
- article=getchar();
- while(article!='#'){
- fputc(article,fp);
- article=getchar();
- }
- fclose(fp);
- }
- //从文件读取文章,并统计字符出现频数
- void loadfile(){
- FILE *fp;
- char ch;
- int i,k,j=0;
- count=0;
- for(i=0;i<=127;i++) //把所有字符的ascii码存在数组
- { a[i].ASCII=i;
- a[i].n=0;
- }
- if((fp=fopen("article.txt","r"))==NULL){
- printf("打开文件不成功!");
- exit(0);
- }
- ch=fgetc(fp);
- k=(int)ch;
- a[k].n++;
- while(!feof(fp)){
- ch=fgetc(fp);
- k=(int)ch;
- a[k].n++;
- }
- fclose(fp);
- for(i=0;i<=127;i++) //统计字符种类总数
- {
- ch=(char)i;
- if(a[i].n){
- count++;
- }
- }
- for(i=0;i<=127;i++)
- {
- for(;j<count;)
- {
- if(a[i].n)
- {
- w[j].n=a[i].n;
- w[j].ASCII=a[i].ASCII;
- j++;
- break;
- }
- else break;
- }
- }
- }
- //调整为小顶堆
- void MinHeapify(HuffmanTree HT, int k,int len)
- {
- int left=k*2;
- int right=k*2+1;
- int large;
- int l=len;
- large = k;
- if (left<=l&&HT[left].weight<HT[large].weight)
- large = left;
- if (right<=l&& HT[right].weight<HT[large].weight)
- large=right;
- if (large!=k)
- {
- swap(HT[k],HT[large]);
- MinHeapify(HT,large,l);
- }
- }
- //建立小顶堆
- void buildMinHeap(HuffmanTree HT,int len)
- {
- int i;
- for (i=len/2;i>=1;i--)
- {
- MinHeapify(HT,i,len);
- }
- }
- //堆排序
- HuffmanTree HeapSort(HuffmanTree HT,int length)
- {
- int i;
- int l=length;
- buildMinHeap(HT,length);
- for (i=length;i>= 2;i--)
- {
- swap(HT[1],HT[i]);
- length--;
- MinHeapify(HT,1,length);
- }
- return HT;
- }
- //建立赫夫曼数
- HuffmanTree CreateHuffman(HuffmanTree &HT,struct node *w,int n)
- {
- int i,m,s1,s2,k1,k2,j,x,a;
- FILE *fp,*fp2;
- if(n<=1) return HT;
- m=2*n-1;
- HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0不用
- for(i=1,j=0;i<=n;i++,j++)
- { HT[i].asc=w[j].ASCII;
- HT[i].weight=w[j].n;
- HT[i].parent=0;
- HT[i].lchild=0;
- HT[i].rchild=0;
- }
- for(;i<=m;i++)
- { a=250+i;
- HT[i].asc=a;//父亲节点的asc可以是大于127的任意值
- HT[i].weight=0;
- HT[i].parent=0;
- HT[i].lchild=0;
- HT[i].rchild=0;
- }
- for(i=1;i<=n;i++){
- H_T[i].asc=HT[i].asc;
- H_T[i].parent=HT[i].parent;
- H_T[i].lchild=HT[i].lchild;
- H_T[i].rchild=HT[i].rchild;
- H_T[i].weight=HT[i].weight;
- }
- for(i=n+1,x=n;i<=m;i++,x--)
- {
- HeapSort(H_T,x);
- k1=H_T[x].asc;
- k2=H_T[x-1].asc;
- for(j=1;j<=127;j++)
- {
- if(HT[j].asc==k1)
- { s1=j;break;}
- }
- for(j=1;j<=127;j++)
- {
- if(HT[j].asc==k2)
- { s2=j;break;}
- }
- HT[s2].parent=i;
- HT[s1].parent=i;
- HT[i].lchild=s1;
- HT[i].rchild=s2;
- HT[i].weight=HT[s1].weight+HT[s2].weight;
- H_T[x-1].asc=HT[i].asc;
- H_T[x-1].lchild=HT[i].lchild;
- H_T[x-1].parent=HT[i].parent;
- H_T[x-1].rchild=HT[i].rchild;
- H_T[x-1].weight=HT[i].weight;
- }
- if((fp2=fopen("count.txt","w"))==NULL) //保存赫夫曼树
- {
- cout<<"文件打开不成功!"<<endl;
- exit(0);
- }
- fputc(count,fp2);
- if((fp=fopen("HuffmanTree.dat","wb"))==NULL)
- { cout<<"文件打开不成功!"<<endl;
- exit(0);
- }
- for(i=1;i<=(2*count-1);i++){
- fwrite(&HT[i],sizeof(HTNode),1,fp);
- }
- fclose(fp);
- fclose(fp2);
- return HT;
- }
- //逆向编码
- void BianMa(HuffmanTree HT,int n){
- char *cd,temp;
- int c,f,i,j,len,p,q;
- cd=(char *)malloc(n*sizeof(char));
- HC=(char * *)malloc(n*sizeof(char*));
- for(i=1;i<=n;i++){
- for(c=i,f=HT[i].parent,j=0;f!=0;c=f,f=HT[f].parent,j++)
- { if(HT[f].lchild==c) cd[j]='0';
- else cd[j]='1';
- if(HT[f].parent==0)
- cd[j+1]='/0';
- }
- len=strlen(cd);
- for(p=0,q=len-1;p<=q;p++,q--)
- {
- temp=cd[q];
- cd[q]=cd[p];
- cd[p]=temp;
- }
- cd[len]='/0';
- HC[i]=(char*)malloc((len+10)*sizeof(char));
- strcpy(HC[i],cd);
- }
- }
- //整篇文章编码,并存入文件
- void BianMa_all(HuffmanTree HT,char**HC,char *filename){
- char ch;
- int k,i;
- FILE *fp,*fp2;
- char code[100];
- if((fp=fopen(filename,"r"))==NULL){
- printf("打开文件不成功!");
- exit(0);
- }
- if((fp2=fopen("赫夫曼编码.txt","w"))==NULL){
- printf("打开文件不成功!");
- exit(0);
- }
- ch=fgetc(fp);
- k=(int)ch;
- while(!feof(fp))
- {
- for(i=1;i<=count;i++)
- {
- if(k==HT[i].asc)
- strcpy(code,HC[i]);
- }
- fputs(code,fp2);
- ch=fgetc(fp);
- k=(int)ch;
- }
- fclose(fp);
- fclose(fp2);
- }
- void JieMa(){
- int i,k,a,t,n=0;
- FILE *fp1,*fp2,*fp3;
- char ch,c;
- HuffmanTree ht;
- if((fp3=fopen("count.txt","r"))==NULL) //从文件读出字符总数
- {
- printf("打开文件不成功!");
- exit(0);
- }
- n=fgetc(fp3);
- ht=(HuffmanTree)malloc(2*n*sizeof(HTNode));
- if((fp1=fopen("赫夫曼编码.txt","r"))==NULL)
- {
- printf("打开文件不成功!");
- exit(0);
- }
- if((fp2=fopen("HuffmanTree.dat","rb"))==NULL)
- { cout<<"文件打开不成功!"<<endl;
- exit(0);
- }
- for(i=1;i<=2*n-1;i++)
- fread(&ht[i],sizeof(HTNode),1,fp2);
- for(i=1;i<=2*n-1;i++)
- {
- if(ht[i].parent==0){t=k=i;break;}
- }
- ch=fgetc(fp1);
- while(!feof(fp1)){
- if(ch=='0')
- {
- k=ht[k].lchild;
- if(ht[k].lchild==0)
- {a=ht[k].asc;
- c=(char)a;
- printf("%c",c);;
- k=t;
- }
- }
- if(ch=='1')
- {
- k=ht[k].rchild;
- if(ht[k].lchild==0)
- { a=ht[k].asc;
- c=(char)a;
- printf("%c",c);
- k=t;
- }
- }
- ch=fgetc(fp1);
- }
- fclose(fp1);
- fclose(fp2);
- }
- //读取文件中的文章,可自己选择文件
- int loadfile2(){
- FILE *fp;
- char ch;
- int i,k,j=0;
- count=0;
- for(i=0;i<=127;i++)
- { a[i].ASCII=i;
- a[i].n=0;
- }
- cout<<"/n/n/n/t/t/t请输入你要打开的文件名:";
- cin>>filename;
- if((fp=fopen(filename,"r"))==NULL){
- printf("打开文件不成功!");
- return 1;
- }
- ch=fgetc(fp);
- k=(int)ch;
- a[k].n++;
- while(!feof(fp)){
- ch=fgetc(fp);
- k=(int)ch;
- a[k].n++;
- }
- fclose(fp);
- for(i=0;i<=127;i++){
- ch=(char)i;
- if(a[i].n){
- count++;
- }
- }
- for(i=0;i<=127;i++)
- {
- for(;j<count;)
- {
- if(a[i].n)
- {
- w[j].n=a[i].n;
- w[j].ASCII=a[i].ASCII;
- j++;
- break;
- }
- else break;
- }
- }
- return 0;
- }
评论暂时关闭