博客

#include<stdio.h>  
#include<stdlib.h>  
#include<string.h> 
#include<time.h> 
typedef struct{
	char a;
	int weight=0;
}W;
typedef struct{  
      int weight;  
      int parent,lchild,rchild;  
      char data;  
}HTNode,*HuffmanTree;   
typedef char **HuffmanCode;  
void Suiji(char *a, int n){
    char all[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    srand(time(0));
    for (int i=0;i<n-1;i++){
        a[i]=all[rand()%62]; 
    }
    a[n-1]='\0';
    FILE *fp;
    fp=fopen("text.txt","w");
    fprintf(fp,"%s",a);
    fclose(fp);
}
void Weight(char *a,W w[],int &n){
	char *p;
	p=a;
	int i=0,j=0,k;
	w[i].a=*p;
	w[i].weight++;
	p++;
	while(*p!='\0'){
		for(k=0;k<=i;k++){
			if(w[k].a==*p){
				w[k].weight++;
				break;  
			}
		}
		if(k>i){
			i++;
			w[i].a=*p;
			w[i].weight++;
		}
		p++;
	}
	n=i+1;
	for(i=0;i<n;i++)
		printf("%d",w[i].weight);
	printf("\n");
}
void Select(HuffmanTree HT,int n,int &s1,int &s2){  
    int i=1;  
    int min1=10000,min2=10000;  
    s1=s2=0;  
    while(i<=n){  
        if(HT[i].parent==0){  
            if(min1>HT[i].weight){  
                min2=min1;  
                s2=s1;  
                min1=HT[i].weight;  
                s1=i;  
            }  
            else if(min2>HT[i].weight){  
                s2=i;  
                min2=HT[i].weight;  
            }  
        }  
        i++;  
    }  
}   
void CreateHuffman(HuffmanTree &HT,char *a,W w[],int n){  
    int i,s1,s2;  
    int m=2*n-1;  
    if(n<=1)  
        return ;  
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));  
    for(i=0;i<=n;i++){  
        HT[i].weight=w[i].weight;  
        HT[i].data=w[i].a;  
        HT[i].lchild=0;  
        HT[i].parent=0;  
        HT[i].rchild=0;  
    }  
    for(;i<=m;++i){  
        HT[i].weight=0;  
        HT[i].lchild=0;  
        HT[i].parent=0;  
        HT[i].rchild=0;  
    }  
    for(i=n+1;i<=m;i++){//建立哈夫曼树  
        s1=s2=0;  
        Select(HT,i-1,s1,s2);  
        HT[s1].parent=i;HT[s2].parent=i;  
        HT[i].lchild=s1;HT[i].rchild=s2;  
        HT[i].weight=HT[s1].weight+HT[s2].weight;  
    }  
}   
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n){//求出n个字符的哈夫曼编码HC  
    int i;  
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));  
    char *cd=(char*)malloc(n*sizeof(char));  
    cd[n-1]='\0';  
    for(i=1;i<=n;++i){  
        int start=n-1;  
        for(int 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';  
        HC[i]=(char*)malloc((n-start)*sizeof(char));  
        strcpy(HC[i],cd+start);  
    }  
    for(i=1;i<=n;i++){  
       printf("%c %d的编码为: %s\n",HT[i-1].data,HT[i-1].weight,HC[i]);  
    }  
    free(cd);
	FILE *fp;
    fp=fopen("codefile.txt","w");
    for(i=1;i<=n;i++){  
       fprintf(fp,"%s",HC[i]);  
    }  
    fclose(fp);
}  
void HuffmanDecode(HuffmanTree HT,int n){  
    char decode[100];  
    int i,len,p;  
    FILE *fp,*fp1;
    fp=fopen("codefile.txt","r"); 
    fscanf(fp,"%s",decode);  
    fclose(fp);    
    len=strlen(decode);  
    p=2*n-1;  
    printf("该编码的译码结果为:\n"); 
	fp1=fopen("textfile.txt","w");
    for(i=0;i<=len;i++){  
        if(HT[p].lchild==0&&HT[p].rchild==0){  
            printf("%c",HT[p-1].data); 
			fprintf(fp1,"%c",HT[p-1].data);
            p=2*n-1;  
        }  
        if(decode[i]=='0')  
            p=HT[p].lchild;  
        else if(decode[i]=='1')  
            p=HT[p].rchild;  
    }   
	fclose(fp1);
}  
int main(){
	int n;
	char a[500];
	W w[100];
	HuffmanTree Ht;
	HuffmanCode Hc;
	printf("输入字符个数：");
	scanf("%d",&n);
    Suiji(a,n+1);
    printf("%s",a);
    printf("\n");
    Weight(a,w,n);
    CreateHuffman(Ht,a,w,n);
    HuffmanCoding(Ht,Hc,n);
    HuffmanDecode(Ht,n);
    return 0;
}