데이터 구조 과정 설계 - 하프 만 인 코딩 디 코딩

//********************************************
//    :        
//
//  :2014 11 18
//
//********************************************
#include
#include
#include
#include 

#define MAX 128             //      (  ASCII )
#define M 2*MAX-1           //      

typedef struct node{
	int weight;				//  
	int parent;				//    
	int LChild;				//     
	int RChild;				//     
}HTNode,HuffmanTree[M+1];
typedef struct Node{
	char letter;//  
	char* code;//  
	int w;//  (       (letter)    )
}Huffman[MAX+1];

HuffmanTree ht;					//      
Huffman qz;						//      
int weight[M+1]={0};			//      
int t=0;						//        

/*********************    **********************/
void select(int *s1,int *s2);//            

int ReadWeight();//           ，      

void CrtHuffmanTree();//      

void Encoding();//  

void Print();//  

void WriteTree();//          

void Initialization();//   

void WriteCode();//        

void Decoding();//  

int find_letter(char ch);//    

int find_code(char s[]);//    

void InitTree();//    

void TreePrinting();//      

void Menu();//  

void load();//loading

void _print(FILE *fp,node hft,int n);

//   
int main()
{
	Menu();//    ,       
	return 0;
}

void Menu()
{
	char chose;
	load();
	InitTree();
	printf("**************************Menu*************************
");
	printf("******   (I)***********  (E)********  (D)*******
");
	printf("****      (P)***      (T)****  (O)*******
");
	printf("*******************************************************
");
	while(true){
		printf("   :");
		scanf("%c",&chose);
		getchar();//    
		switch(chose){
		case 'I':Initialization();break;		//   
		case 'E':Encoding();break;				//         
		case 'D':Decoding();break;				//  
		case 'P':Print();break;					//    
		case 'T':TreePrinting();break;			//      
		case 'O':
			printf("     !
");			//    
			Sleep(2000);						//  
			exit(1);							//    
		default:printf("      !
");
		}
	}
}

//loading
void load()
{
	printf("loading");
	for(int i=1;i<=10;i++){
		printf(".");
		Sleep(500);
	}
	printf("
     !
");
	Sleep(2000);
}
//    
void InitTree()
{
	ht[0].weight = 0;//          
	qz[0].w = 0;	//      
}
//   
void Initialization()
{
	ht[0].weight = 1;		//     ,         
	t=ReadWeight();			//    
	CrtHuffmanTree();		//      
	WriteTree();			//         
	printf(" !'   '   !
");
}
//         
void WriteTree()
{
	FILE *fp;//hfmTree     
	int m=2*t-1;
	int i;

	//    
	if((fp=fopen("F:\\hfmTree.txt","w")) == NULL){
		printf("open hfmTree.txt--file error
");
		exit(0);
	}//else printf("open hfmTree.txt--file sucess!
");
	//        
	for(i=1;i<=m;i++)
		fprintf(fp,"%d %d %d %d
",ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
	//    
	if(fclose(fp)){
		printf("close hfmTree.txt--file error!
");
		exit(0);
	}//else printf("close hfmTree.txt--file success!
");
}
//  s1,s2
void select(int n,int *s1,int *s2)
{
	int i;
	int min;
	//           ,       
	for(i=1; i<=n; i++){
		if(ht[i].parent == 0){
			min = i;
			break;
		}
	}
	//         
	for(i=1; i<=n; i++){
		if(ht[i].weight=1){
			qz[n].letter = (char)i;
			qz[n].w = weight[i];
			n++;
		}
	}
	return n-1;//n 1    
}

//      
void CrtHuffmanTree()
{
	int i,s1,s2,m = 2*t-1;
	//*   *//
	for(i=1; i<=t; i++){// 1 n     n     
		ht[i].weight = qz[i].w;
		ht[i].parent = ht[i].LChild = ht[i].RChild = 0;
	}
	for(i=t+1;i<=m;i++){// n+1   m          
		ht[i].weight = ht[i].parent = ht[i].LChild = ht[i].RChild = 0;
	}

	//*  *//
	for(i=t+1; i<=m; i++){
		select(i-1,&s1,&s2);
		//printf("s1 = %d,s2 = %d
",s1,s2);
		ht[i].weight = ht[s1].weight + ht[s2].weight;
		ht[s1].parent = ht[s2].parent = i;
		ht[i].LChild = s1;
		ht[i].RChild = s2;
	}

}
//     
void Encoding()
{
	if(ht[0].weight == 0){
		printf("  !!      !!
");
		Sleep(2000);//      
		return;
	}
	int i,start,c,p;
	char *cd;
	cd = (char*)malloc(t*sizeof(char));
	cd[t-1]='\0';
	for(i=1; i<=t; i++){// n         
		start = t-1;//              
		c = i;//        
		p = ht[i].parent;//           
		while(p!=0){
			--start;
			if(ht[p].LChild == c)//            ,   0
				cd[start]='0';
			else//        1
				cd[start]='1';
			c = p;//         
			p = ht[p].parent;
		}
		qz[i].code=(char*)malloc((t-start)*sizeof(char));
		strcpy(qz[i].code,&cd[start]);
	}
	free(cd);
	
	//          
	
	/*    
	for(i=1;i<=n;i++)
	printf("%c %d %s
",hc[i].letter,hc[i].w,hc[i].code);*/
	//       
	WriteCode();
	/*for(i=1;i<=n;i++){
	printf("%s
",hc[i].code);
	}*/
	qz[0].w = 1;//      
	printf(" !'  '   !
");
}

//      
void WriteCode()
{
	FILE *fp_code,*fp_text;
	char ch;
	int i;
	//        
	if((fp_code=fopen("F:\\CodeFile.txt","w")) == NULL){
		printf("open CodeFile.txt--file error !
");
		exit(0);
	}//else printf("open CodeFile.txt--file success!
");

	//           
	if((fp_text=fopen("F:\\ToBeTran.txt","r")) == NULL){
		printf("open ToBeTran.txt--file error !
");
		exit(0);
	}//else printf("open ToBeTran.txt--file success!
");

	while(!feof(fp_text)){
		ch = fgetc(fp_text);
		//printf("%c ",ch);
		i = find_letter(ch);
		//printf("i = %d
",i);
		if(i!=0)
			fprintf(fp_code,"%s ",qz[i].code);
	}

	//    
	if(fclose(fp_code)){
		printf("close CodeFile.txt--file error!
");
		exit(0);
	}//else printf("close CodeFile.txt--file success !
");
	if(fclose(fp_text)){
		printf("close ToBeTran.txt--file error!
");
		exit(0);
	}//else printf("close ToBeTran.txt--file success !
");
}

//    
int find_letter(char ch)
{
	int low,high,i;
	low = 1;high = t;
	//    
	while(high - low >= 0){
		i=(low+high)/2;
		if(qz[i].letter == ch)
			return i;
		else if(qz[i].letter < ch){
			low = i+1;
		}
		else
			high = i-1;
	}
	return 0;
}
//           
void Print()
{
	if(ht[0].weight == 0){
		printf("  !!      !
");
		Sleep(2000);//      
		return;
	}
	if(qz[0].w == 0){
		printf("  !!     !!
");
		Sleep(2000);
		return;
	}
	int i=0;
	char code[100];
	FILE *fp_r,*fp_w;
	if((fp_r=fopen("F:\\CodeFile.txt","r")) == NULL){
		printf("open CodeFile.txt--file error!
");
		exit(0);
	}//else printf("open CodeFile.txt success!
");
	if((fp_w=fopen("F:\\CodePrint.txt","w")) == NULL){
		printf("open CodePrint.txt--file error!
");
		exit(0);
	}//else printf("open CodePrint.txt success!
");
	while(!feof(fp_r)){
		fscanf(fp_r,"%s
",code);
		printf("%s ",code);
		fprintf(fp_w,"%s",code);
		i++;
		if(i%5 == 0){
			printf("
");
			fprintf(fp_w,"
");
		}
	}
	printf(" !'  '   !
");
}

//  
void Decoding()
{
	if(ht[0].weight == 0){
		printf("  !!      !
");
		Sleep(2000);//      
		return;
	}
	if(qz[0].w == 0){
		printf("  !!     !!
");
		Sleep(2000);//      
		return;
	}
	char code[100];
	FILE *fp_r,*fp_w;
	int i;
	//  CodeFile.txt  ,      
	if((fp_r=fopen("F:\\CodeFile.txt","r")) == NULL){
		printf("open CodeFile.txt--file error!
");
		exit(0);
	}//else printf("open CodeFile.txt success!
");
	
	//  TextFile.txt  ，       
	if((fp_w=fopen("F:\\TextFile.txt","w")) == NULL){
		printf("open TextFile.txt--file error!
");
		exit(0);
	}//else printf("open TextFile.txt success!
");
	
	while(!feof(fp_r)){
		fscanf(fp_r,"%s
",code);
		i = find_code(code);
		if(i!=0)
			fprintf(fp_w,"%c",qz[i].letter);
	}
	if(fclose(fp_r)){
		printf("close CodeFile.txt--file error!
");
		exit(0);
	}//else printf("close CodeFile.txt--file success !
");
	if(fclose(fp_w)){
		printf("close TextFile.txt--file error!
");
		exit(0);
	}//else printf("close TextFile.txt--file success !
");
	printf(" !'  '   !
");
}

int find_code(char s[])//    
{
	int i;
	for(i=1;i<=t;i++){
		if(strcmp(qz[i].code,s) == 0)
			return i;
	}
	return 0;
}

void TreePrinting()
{
	if(ht[0].weight == 0){
		printf("  !!      !
");
		Sleep(2000);//      
		return;
	}
	FILE *fp;
	int i,r=t*2-1;
	//    
	if((fp=fopen("F:\\TreePrint.txt","w")) == NULL){
		printf("open CodeFile.txt--file error !
");
		exit(0);
	}
	for(i=1;i<=r;i++){
		if(ht[i].parent == 0)
			break;
	}
	//printf("%d
",ht[i].parent );
	_print(fp,ht[i],0);
	if(fclose(fp)){
		printf("close hfmTree.txt--file error!
");
		exit(0);
	}
	printf(" !'  '   !
");
}
//             
void _print(FILE *fp,node hft,int n)
{
	if(hft.LChild == 0 && hft.RChild == 0){
		for(int i=0;i