hafuman.rar_hafuman_visual c

#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX 20 typedef struct { char data; int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree;//结点类型 void Select(HuffmanTree *H,int n,int *p,int *q)//求前n个结点中父结点不存在，并且权值最小的两个结点 { HuffmanTree HT,HT2; int i; HT=NULL; HT2=NULL; for(i=1;i<=n;i++)//求权值最小的结点 if(H[i]->parent==0 && HT==NULL) { HT=H[i]; *p=i; } else if(H[i]->parent==0 && H[i]->weight < HT->weight) { HT=H[i]; *p=i; } for(i=1;i<=n;i++)//求权值次小的结点 if(H[i]->parent==0 && HT2==NULL && H[i]!=HT) { HT2=H[i]; *q=i; } else if(H[i]->parent==0 && H[i]!=HT && H[i]->weight < HT2->weight) { HT2=H[i]; *q=i; } }//Select void Read(int geshu)//读出bianma1.txt即所得编码文件中的内容 { FILE *fp; int i=1; char *ch; if((fp=fopen("D:\\bianma1.txt","r"))==NULL) exit(-1); printf("所得电文编码如下：\n"); for(i=1;i<geshu;i++) { ch=(char *)malloc(sizeof(char)); fread(&ch,sizeof(char *),1,fp); printf("%s ",ch); } putchar('\n'); fclose(fp); } HuffmanTree * Bian_ma(int *a)//给出电文文件，对该电文进行编码并保存在文件中 { HuffmanTree *HT,*H; FILE *fp,*fp1; int w[28]={0}; int num=0,m=0,i=1,start=0,geshu=0,j=1; int cout[27]={0},n=1; int p1=0,p2=0; char d[50]={'\0'},*cd,**HC; if((fp=fopen("D:\\dianwen.txt","r"))==NULL)//dianwen.txt为电文文件 { printf("cannot open the file1\n"); exit(-1); } while(!feof(fp)) { d[i++]=fgetc(fp); }//while geshu=i-1;//电文中含有的总字母个数 i=1; while(d[i]>='a' && d[i]<='z') { w[d[i++]-96]++;//求电文中各个字母的权值，如w[1]为A的权值 } i=1; while(i <= 26)//求含有几个非同字母 { if(w[i++]) num++; } for(i=1;i<=26;i++)//cout[i]表示电文中字母X的编码为HC[cout[X-96]] { if(w[i]) cout[i]=n++; //n开始为1 } m=2*num-1;//需要的总结点数目 *a=m;//返回树的结点个数，用于译码函数 HT=(HuffmanTree * ) malloc ((m+1)*sizeof(HuffmanTree)); for(i=1;i<=m;i++) HT[i]=(HuffmanTree ) malloc (sizeof(HTNode)); H=&HT[1]; for(i=1;i<28;i++)//初始化HT[] { if(w[i]) { (*H)->data=96+i; (*H)->weight=w[i]; (*H)->parent=0; (*H)->lchild=0; (*H)->rchild=0; H++; } } for(i=num+1;i<=m;i++)//初始化 { (*H)->data='\0'; (*H)->weight=0; (*H)->parent=0; (*H)->lchild=0; (*H)->rchild=0; H++; } for(i=num+1;i<=m;i++)//构造哈夫曼树 { Select(HT,i-1,&p1,&p2);//在前i-1个节点中选择parent为0的两个权值最小的结点位置赋给p1，p2 HT[p1]->parent=i; HT[p2]->parent=i; HT[i]->lchild=p1; HT[i]->rchild=p2; HT[i]->weight=HT[p1]->weight+HT[p2]->weight; } HC=(char **) malloc ((num+1)*sizeof(char *));//HC为字符串数组，0号单元未用 cd=(char *) malloc (num*sizeof(char)); cd[num-1]='\0';//使cd为字符串 for(i=1;i<=num;i++)//对每个字母求编码 { start=num-1; for(p1=i,p2=HT[i]->parent;p2!=0;p1=p2,p2=HT[p2]->parent)//从叶子结点逆向求编码 { if(HT[p2]->lchild==p1)//p1为左子树 cd[--start]='0'; else cd[--start]='1'; } HC[i]=(char *) malloc ((num-start)*sizeof(char)); strcpy(HC[i],&cd[start]);//字符串复制HC[i]为第i个非同字母的编码 }//for i free(cd); if((fp1=fopen("D:\\bianma1.txt","w"))==NULL) exit(-1); while(d[j]>= 'a' && d[j]<='z')//将编码存入到文件2中 { if(fwrite(&HC[cout[d[j]-96]],sizeof(char *),1,fp1)!=1) printf("存储编码时出错\n"); j++; } fclose(fp); fclose(fp1); Read(geshu);//输出电文编码 return HT; }//GouHuff void Du_yima()//输出译码后的文件的内容 { FILE *fp1; char ch; if((fp1=fopen("D:\\yima2.txt","r"))==NULL) { printf("can not open yima2.txt\n"); exit(-1); } printf("所得译码为:\n"); while(!feof(fp1)) { ch=fgetc(fp1); if(ch>='a' && ch<='z') putchar(ch); } putchar('\n'); fclose(fp1); return; } void Yi_ma(HuffmanTree *HT,int m)//给出编码要求译码 { HuffmanTree H; FILE *fp,*fp2; char ch=' ',ma[MAX]; int i=0,j=0; if((fp=fopen("D:\\yima1.txt","r"))==NULL) exit(-1);//yima1.txt是所给的编码文件 while(!feof(fp))//译码过程 { H=HT[m]; while(H->lchild||H->rchild)//从根开始直到找到叶子结点 { ch=fgetc(fp); if(ch==EOF) break; if(ch=='0') H=HT[H->lchild]; else if(ch=='1') H=HT[H->rchild]; } if(ch==EOF) break;//文件结束则，跳出循环 else ma[i++]=H->data;//H为叶子结点，将其包含的字母赋给ma[] } ma[i]='\0'; fp2=fopen("D:\\yima2.txt","w");//yima2.txt为所得电文 for(j=0;j<i;j++)//将所得译码存入文件 { fputc(ma[j],fp2); } fclose(fp); fclose(fp2); Du_yima();//读取yima2.txt中的内容 return; } void main()//说明：电文为小写字母 { HuffmanTree *HT; int m=1;//m返回所求哈夫曼树的结点个数，对译码过程有用处 HT=Bian_ma(&m);//给出电文求编码 Yi_ma(HT,m);//给编码译为电文 }//main