#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
int n;
struct node{
	int w;
	int flag;
	char c;
	struct node *plink,*llink,*rlink;
	char code[50];
}*num[100],*root;
FILE *fp;
char tmpcode[50];
int t=0;
void main(void)
{
    int i;
	void settree(void);   //建立樹
	void code(void);     //對文件編碼
	void decode(void);   // 譯碼
	void disp(void)  ;
	root=(struct node*)malloc(sizeof(struct node));
	puts("*******************哈夫曼編/譯碼器演示******************************");
	while(1){
start:
	puts("1. 初始化      2. 編碼       3. 譯碼      4.顯示編碼表    5. 退出");
	while(scanf("%d",&i)!=1)
	{
		while(getchar()!='\n')
			continue;
		puts("輸入錯誤!");
		puts("請重新輸入！");
		puts("1. 初始化      2. 編碼       3. 譯碼    4.顯示編碼表   5. 退出");
    }
	switch (i)
	{
	case 1:
		settree();
		break;
	case 2:
		code();
		break;
	case 3:
		decode();
		break;
	case 4:
		disp();
		break;
	case 5:
		exit(0);
	default:
		puts("輸入錯誤！");
		puts("請重新輸入！");
		goto start;
	}
    }
}

void settree(void)
{
	int i,j,k;
	struct node *p1,*p2,*tmp,*p;
	void go(struct node *);
	void setcode(struct node *);//建立每一個字符的編碼
	void printtree(struct node *);
	puts("輸入字符個數：");
	scanf("%d",&n);
	while(getchar()!='\n')
		continue;
	for(i=0;i<n;i++)
	{
		p=(struct node *)malloc(sizeof(struct node));
		puts("請輸入一個字符"); 
		scanf("%c",&p->c);
		while(getchar()!='\n')
			continue;
		puts("請輸入該字符的權值:");
		scanf("%d",&p->w);
		while(getchar()!='\n')
			continue; 
		p->plink=NULL;
		p->rlink=NULL;
		p->llink=NULL;
		num[i]=p;
	}
	for(i=0;i<n-1;i++)  //（遞增）排序
	{
		for(j=i+1;j<n;j++)
		{
			if(num[i]->w>num[j]->w)
			{
				tmp=num[i];
				num[i]=num[j];
				num[j]=tmp;
			}
		}
	}
	/*******************************開始建立樹***********************/
	num[n]=NULL;    //結束標志
	k=n;
	while(num[1]!=NULL)
	{
		p=(struct node *)malloc(sizeof(struct node));
		p1=num[0];
		p2=num[1];
		p->llink=p1;
		p->rlink=p2;
		p->plink=NULL;
		p1->plink=p;
		p2->plink=p;
		p->w=p1->w+p2->w;
		for(i=1;i<k;i++)
		{
            num[i]=num[i+1];
		}
		k--;
		num[0]=p;
		for(i=0;i<k-1;i++)  //排序
		{
			for(j=i+1;j<k;j++)
			{
				if(num[i]->w>num[j]->w)
				{
					tmp=num[i];
                    num[i]=num[j];
                    num[j]=tmp;
				}
			}
		}
	}
	root=num[0];
	/*建立完畢*/
	/*寫入文件，前序*/
	if((fp=fopen("c:\\hfmtree.wxl","wb"))==NULL)
	{
		puts("文件打開錯誤！");
		getchar();
		exit(0);
	}
	setcode(root);
	go(root);
	fclose(fp);
}
void setcode(struct node *p)
{
	if(p->llink==NULL&&p->rlink==NULL)
	{
		tmpcode[t]='\0';
		strcpy(p->code,tmpcode);
	}
	else
	{
		tmpcode[t++]='0';
		setcode(p->llink);
		t--;
		tmpcode[t++]='1';
		setcode(p->rlink);
		t--;
	}
}

void go(struct node *p)
{
	if(p->llink==NULL&&p->rlink==NULL)
	{
		fputc('(',fp);
		fputc(p->c,fp);
		fputs(p->code,fp);
		fputc(')',fp);
	} 
	else
	{ 
		go(p->llink);
		go(p->rlink);
	}
}
void code(void)
{
    FILE *fp1,*fp2,*fp3;
	char ch1,ch2,c;
	if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
	{
		puts("文件打開錯誤！");
		getchar();
		exit(0);
	}
    if((fp2=fopen("c:\\tobetrans.txt","rb"))==NULL)
	{
		puts("文件打開錯誤！");
		getchar();
		exit(0);
	}
	if((fp3=fopen("c:\\codefile.wxl","wb"))==NULL)
	{
		puts("文件打開錯誤！");
		getchar();
		exit(0);
	}
	while((ch1=fgetc(fp2))!=EOF)
	{
		t=0;
		
		while((ch2=fgetc(fp1))!=EOF)
		{
            if(ch1==ch2)
            {
                while((c=fgetc(fp1))!=')')
                {
                    tmpcode[t++]=c;
                }
                tmpcode[t]='\0';
                fputs(tmpcode,fp3);
                fputc('@',fp3);
                rewind(fp1);
                break;
            }
		}
	}
	fclose(fp1);
	fclose(fp2);
	fclose(fp3);
}
void decode(void)
{
    FILE *fp1,*fp2,*fp3;
	char ch1,ch2,ch3;
	char temp_3[20];
	char temp_1[20];
	int t1,t3;
	if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
	{
		puts("文件打開錯誤！");
		getchar();
		exit(0);
	}
    if((fp2=fopen("c:\\textfile.txt","wb"))==NULL)
    {
		puts("文件打開錯誤！");
		getchar();
		exit(0);
    }
    if((fp3=fopen("c:\\codefile.wxl","rb"))==NULL)
	{
		puts("文件打開錯誤！");
		getchar();
		exit(0);
	}
	while((ch3=fgetc(fp3))!=EOF)
	{
		t3=0;
		while(ch3!='@')
		{
			temp_3[t3++]=ch3;
			ch3=fgetc(fp3);
		}
		temp_3[t3]='\0';
		while((ch1=fgetc(fp1))!=EOF)
		{
			if(isalpha(ch1))
			{
				ch2=ch1;
				t1=0;
				while((ch1=fgetc(fp1))!=')')
				{
					temp_1[t1++]=ch1;
				} 
				temp_1[t1]='\0'; 
				if(strcmp(temp_1,temp_3)==0)
				{
					fputc(ch2,fp2);
					rewind(fp1);
					break;
				}
			}
		}
	}
	fclose(fp1);
	fclose(fp2);
	fclose(fp3);
}

void disp(void)
{
    FILE *fp1,*fp2;
	char ch1,ch2;
	char tmp[20];
	int t;
	if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
	{
		puts("文件打開錯誤！");
		getchar();
		exit(0);
	}
	if((fp2=fopen("c:\\hfmcode.txt","wb"))==NULL)
	{
		puts("文件打開錯誤！");
		getchar();
		exit(0);
	}
	while((ch1=fgetc(fp1))!=EOF)
	{
		if(ch1=='(')
		{
			t=0;
			ch1=fgetc(fp1);
			ch2=ch1;
			while((ch1=fgetc(fp1))!=')')
			{
				tmp[t++]=ch1;
			}
			tmp[t]='\0';
			printf("%c-----%s\n",ch2,tmp);
			fputc(ch2,fp2);
			fputc('-',fp2);
			fputc('-',fp2);
			fputc('-',fp2);
			fputs(tmp,fp2);
			fputc('\n',fp2);
		}
	}
	fclose(fp1);
	fclose(fp2);
}