博客

代码展示

#include <stdio.h>
#include <malloc.h>
#include <string.h>

#define Max 1024

typedef struct HTNode{
	int weight;
	char data;
	int parent,lchild,rchild;
}*HufumanTree;

typedef struct count{
	char ch;
	int cent ;
}*Count;

typedef struct numcount{
	Count data;
	int length ;
}*NumCount;

typedef struct HTcode{
	char data;
	char *str;
}*HufmanCode;

void readString(char *s);
void wordCount(char *paraStr,NumCount paraCount);
void CreatHuffmanTree(HufumanTree paraTree,NumCount paraCount);
void CreatHuffmanTreeCode(HufumanTree paraTree,HufmanCode paraCode,int n);
void select(HufumanTree paraTree,int length,int *s1,int*s2);
void Encode(char *data,HufmanCode paraCode,int length);
void Decode(HufumanTree paraTree,int length);
HufumanTree initHTree(int n);
HufmanCode initCode(int n);
NumCount initCount();

int main(){
	char str[Max],*s=NULL;
	readString(str);
	NumCount Cntarray = initCount();
	wordCount(str,Cntarray);
	HufumanTree tree;
	tree = initHTree(Cntarray->length);
	CreatHuffmanTree(tree,Cntarray);
	HufmanCode code = initCode(Cntarray->length);;
	CreatHuffmanTreeCode(tree,code,Cntarray->length);
	Encode(str,code,Cntarray->length);
	Decode(tree,Cntarray->length);
	return 0;
}
void readString(char *s){
	FILE *fp=fopen("in.txt","r");
	fgets(s, Max, (FILE*)fp);
	
	fclose(fp);	
} 

NumCount initCount(){
	NumCount resultCount  = (NumCount)malloc(sizeof(struct numcount));
	resultCount->data = (Count)malloc(sizeof(struct count)*26);
	for(int i=0;i < 26;i++){
		resultCount->data[i].cent = 0;
	}
	resultCount->length = 0;
	
	return resultCount;
}

void wordCount(char *paraStr,NumCount paraCount){
	int len,i,judge = 0,j;
	len = strlen(paraStr);
	for(i = 0;i < len ;i++){
		for(j = 0;j < paraCount->length;j++){
			if(paraCount->data[i].ch == paraStr[i]){
				judge = 1;
				paraCount->data[i].cent++;
				break;
			}
		}
		if(judge == 0){
			paraCount->data[paraCount->length].ch = paraStr[i];
			paraCount->data[paraCount->length].cent ++;
			paraCount->length ++;
		}
	}
}

HufumanTree initHTree(int n){
	int m = 2*n;
	int i;
	HufumanTree resultTree = (HufumanTree)malloc(sizeof(struct HTNode)*m);
	for(i = 1; i < m;i++){
		resultTree[i].lchild = 0;
		resultTree[i].parent = 0;
		resultTree[i].rchild = 0;
	}
	return resultTree;
}
HufmanCode initCode(int n){
	HufmanCode resultCode = (HufmanCode)malloc(sizeof(struct HTcode)*n+1);
	return resultCode;
}

void CreatHuffmanTree(HufumanTree paraTree,NumCount paraCount){
	int m = paraCount->length*2;
	int s1,s2,i;
	for(i = 1;i <= paraCount->length ;i++){
		paraTree[i].weight = paraCount->data[i-1].cent;
		paraTree[i].data = paraCount->data[i-1].ch;
	}
	for(i = paraCount->length+1;i < m;i++){
		select(paraTree,i-1,&s1,&s2);
		paraTree[i].weight = paraTree[s1].weight + paraTree[s2].weight;
		paraTree[i].lchild = s1;
		paraTree[i].rchild = s2;
		paraTree[s1].parent = i;
		paraTree[s2].parent = i;
	}
	return;
}

void select(HufumanTree paraTree,int length,int *s1,int*s2){
	int min = paraTree[1].weight ;
	int i;
	for(i = 1;i <= length;i++){
		if(paraTree[i].weight <= min && paraTree[i].parent == 0){
			min = paraTree[i].weight;
			*s1 = i;
		}
	}
	for(i = 1;i <= length;i++){
		if(paraTree[i].weight <= min && paraTree[i].parent == 0&&i!=*s2){
			min = paraTree[i].weight;
			*s2 = i;
		}
	}
	return;
}

void CreatHuffmanTreeCode(HufumanTree paraTree,HufmanCode paraCode,int n){
	char *cd = (char*)malloc(sizeof(char)*n);
	int i,c,start,f;
	cd[n-1] = '\0';
	for(i = 1;i <= n;i++){
		start = n-1;
		c = i;
		f = paraTree[i].parent;
		while(f!=0){
			start--;
			if(paraTree[f].lchild = c){
				cd[start] = '0';
			}
			if(paraTree[f].rchild = c){
				cd[start] = '1';
			}
			c = f;
			f = paraTree[c].parent;
		}
		paraCode[i].str = (char*)malloc(sizeof(char)*(n-start));
		paraCode[i].data = paraTree[i].data; 
		strcpy(paraCode[i].str,cd);
	}
	free(cd);
	return;
}

void Encode(char *data,HufmanCode paraCode,int length){
	int i,len,j;
	len = strlen(data);
	FILE *fp = fopen("code.txt","w");
	for(i = 0;i < len ; i++){
		for(j = 1; j <= length;i++){
			if(data[i] == paraCode[j].data){
			fputs(paraCode[j].str ,fp);	
			}
		}
	}
	fclose(fp);
}

void Decode(HufumanTree paraTree,int length){
	char codetxt[Max*length];
	int i,j,n;
	FILE *fp = fopen("code.txt","r");
	fgets(codetxt, Max*length, (FILE*)fp);
	fclose(fp);
	fp = fopen("out,txt","w+");
	
	n = 2*length-1;
	
	for(i = 0;i < strlen(codetxt);i++){
		if(codetxt[i] == '0') n = paraTree[n].lchild;
		else if(codetxt[i] == '1') n = paraTree[n].rchild;
		if(paraTree[n].lchild ==0 && paraTree[n].rchild ==0){
			fputc(paraTree[n].data,fp);
		}
	}
	fclose(fp);
}