哈夫曼编码最终程序.rar_哈夫曼编码_哈夫曼编码 译码_哈夫曼编译码_最小生成树

#include<stdio.h> #include<conio.h> #include<ctype.h> #include<stdlib.h> typedef struct treenode{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; /*HuffmanTree存储结构*/ typedef struct tree{ unsigned int weight; unsigned int parent; int code;}Node; /*排序HuffmanTree存储结构*/ typedef char * *HuffmanCode; typedef int * weight1; typedef struct node{ unsigned int weight; char str; }String,*wei; typedef struct data { /*存储权值及相应字符结构*/ char character; int weight; }DATA1; #define NUM 130 #define N 40 void TranslateCode(HTNode *,char *,int); typedef char *ct; void main( ) { DATA1 DATA[NUM]; FILE *fp,*fb; int f,c,et,n=0,count=0,m,i,j,r=1,start,s1,s2; char *cd,cp[N],tr; HTNode *HT, *p; struct tree *VT; String *w1,w2; int w[N],count1[30]; /*count1数组用来保存Huffmancode编码长度*/ char b[100],ic; char * *HC; textbackground(BLACK); textcolor(WHITE); clrscr(); for(i=0;i<N;i++){ w[i]=0; cp[i]='0'; count1[i]=0;} for(i=0;i<NUM;i++){ DATA[i].character='0'; DATA[i].weight=0;} if((fp= fopen("g:\\input.dat","rb"))==NULL){ /*写入文件input.dat*/ fprintf(stderr,"Can't open the file\n"); exit(-1); } printf("\n"); printf("\n"); printf(" Huffman Compile & Translate System\n " ); printf(" ***************************************************\n"); c=getc(fp); /*读入一段文本*/ while(!feof(fp)){ et=c; DATA[et].character=c; ++DATA[et].weight; /*if(fwrite(&c,sizeof(char),1,fp)!=1){ fprintf(stderr,"write error\n"); break;} */ c=getc(fp); } fclose(fp); for(i=0;i<NUM;i++){ if(DATA[i].weight!=0) n++; else ; } for(i=0;i<NUM;i++){ if(DATA[i].weight!=0) printf("%c %d\n",DATA[i].character,DATA[i].weight); } printf("%d\n",n); if(n<=1) exit(0); m=2*n-1; printf("%d\n",m); /* w=(int *)malloc(n*sizeof(int)); */ w1=(wei)malloc(n*sizeof(String)); /* cp=(ct)malloc((n-1)*sizeof(char)); */ for(i=0;i<NUM;i++){ if(DATA[i].weight!=0){ w[count]=DATA[i].weight; cp[count]=DATA[i].character; count++; } } /* for(i=0;i<count;i++){ if(cp[i]!='0') printf("%2c",cp[i]); } */ for(i=0;i<count;i++){ w1[i].weight=w[i]; w1[i].str=cp[i];} /* for(i=0;i<count;i++) printf("%3d%3c",w1[i].weight,w1[i].str); */ for(i=0;i<n;i++){ for(j=0;j<n-i-1;j++) if(w1[j].weight>w1[j+1].weight){ w2=w1[j]; w1[j]=w1[j+1]; w1[j+1]=w2;} } HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); VT=(Node *)malloc((m+1)*sizeof(Node)); for(i=1;i<=n;++i){ p=HT; p[i].weight=*(w+i-1); p[i].parent=0;p[i].lchild=0;p[i].rchild=0;} for(;i<=m;++i) { p[i].weight=0; p[i].parent=0;p[i].lchild=0;p[i].rchild=0;} for(i=1;i<=n;++i){ VT[i].weight=p[i].weight; VT[i].code=i;} for(i=n+1;i<=m;++i){ sort(VT,i); s1=VT[r].code;s2=VT[r+1].code; HT[s1].parent=i;HT[s2].parent=i; if(s1>s2){ HT[i].lchild=s2;HT[i].rchild=s1;} else { HT[i].lchild=s1;HT[i].rchild=s2;} HT[i].weight=HT[s1].weight+HT[s2].weight; VT[i].weight=HT[i].weight; VT[i].code=i; r+=2; } clrscr(); printf("\n"); printf(" HuffmanTree\n"); printf(" *************************************************\n"); printf(" weight parent lchild rchild \n" ); for(i=1;i<=m;i++){ printf(" %2d %7d%8d%10d%10d\n",\ i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); if(i==18) getchar(); else ;} printf(" Press any key to continue."); getchar(); getchar(); HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; clrscr(); printf("\n"); printf("\n"); printf(" Translate Of HuffmanCode \n"); printf(" ***********************************************\n"); printf(" Huffmancode:\n"); for(i=1;i<=n;++i){ start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1' ; count1[i]=n-start; HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); if(cp[i-1]=='\n') printf(" The character of LF 's HuffmanCode is %s\n",HC[i]); else if(i==2) ; else printf(" The character of %c 's HuffmanCode is %s\n",cp[i-1],HC[i]); if(i==18) getchar(); else ;} if((fp=fopen("g:\\code.dat","wb"))==NULL){ fprintf(stderr,"Can't open the file\n"); exit(-1);} for(i=1;i<=n;i++){ /*将huffmancode编码保存到文件code.dat中去*/ if(fwrite(HC[i],count1[i]*sizeof(char),1,fp)!=1){ fprintf(stderr,"write error\n"); break;} } fclose(fp); if((fp=fopen("g:\\input.dat","rb"))==NULL){ fprintf(stderr,"Can't open the file\n"); exit(-1);} if((fb=fopen("g:\\huffmancode.dat","wb"))==NULL){ fprintf(stderr,"Can't open the file\n"); exit(-1);} while(!feof(fp)){ tr=getc(fp); for(i=0;i<n;i++){ if(tr==cp[i]){ if(fwrite(HC[i+1],(count1[i+1]-1)*sizeof(char),1,fb)!=1){ fprintf(stderr,"write error\n");break;} } } } fclose(fp); fclose(fb); TranslateCode(HT,cp,m); } sort(Node *v,int s) {/*对根节点进行排序*/ int j,k; Node temp; for(j=1;j<=s-1;j++) for(k=1;k<=s-j-1;k++){ if(v[k].weight>v[k+1].weight) { temp=v[k]; v[k]=v[k+1]; v[k+1]=temp; } else if(v[k].weight==v[k+1].weight) ; } } void TranslateCode(HTNode *tra,char *p,int t) { FILE *fp1,*fp2; char ch,*m,ct; int s3,a1,b1; HTNode temp1; if((fp1=fopen("g:\\huffmancode.dat","rb"))==NULL){ /*打开字符文本文件*/ fprintf(stderr,"Can't open the file\n"); exit(-1); } if((fp2=fopen("g:\\output.dat","wb"))==NULL){ /*打开输出文本文件*/ fprintf(stderr,"Can't open the file\n"); exit(-1);} clrscr(); printf("\n"); printf("\n"); printf(" Huffman Text \n"); printf(" ********************************************\n"); printf("The text is:\n"); while(!feof(fp1)){ ch=fgetc(fp1); temp1=tra[t];a1=temp1.lchild;b1=temp1.rchild; for(;a1!=0&&b1!=0;ch=fgetc(fp1)) { if(ch=='0'){ s3=temp1.lchild;temp1=tra[s3]; a1=temp1.lchild;} else if(ch=='1'){ s3=temp1.rchild;temp1=tra[s3]; b1=temp1.rchild;} } ct=p[s3-1]; printf("%c",ct); if(fwrite(&ct,sizeof(char),1,fp2)!=1){ /*写入输出文本文件*/ fprintf(stderr,"write error\n"); break;} } fclose(fp1); fclose(fp2); }