lzw.cpp

数据压缩编码LZW演示版本,基于文件的输入输出操作.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_BUF 10000
struct	DICT{
	int n;char *s;
	DICT	*next;
};
DICT *GenDictTest(char from,char to)
{
	int i=0;
	DICT	*pHead=NULL,*pc;
	for(i=from;i<=to;i++){
		pc=(DICT*)malloc(sizeof(DICT));
		pc->n=i-from+1;
		pc->s=(char*)malloc(sizeof(char)*2);
		pc->s[0]=i;pc->s[1]='\0';
		pc->next=pHead;
		pHead=pc;
	}//
	return pHead;
}
DICT   *StrInDict(char *s,DICT *Head)
{
	DICT	*pc=Head;  //puts(s);
	while(pc!=NULL){
		if(strcmp(pc->s,s)==0)return pc;
		else pc=pc->next;
	}//pc
	return NULL;
}
char   *NumInDict(int n,DICT *Head)
{
	DICT	*pc=Head;  //puts(s);
	while(pc!=NULL){
		if((pc->n)==n)return pc->s;
		else pc=pc->next;
	}//pc
	return NULL;
}
DICT   *Insert(char *s,DICT *pHead)
{
	DICT	*pc;
	pc=(DICT*)malloc(sizeof(DICT));
	pc->s=(char *)malloc(sizeof(char)*(strlen(s)+1));
	strcpy(pc->s,s);
	pc->n=pHead->n+1;
	pc->next=pHead;
	pHead=pc;
	return pHead;
}
bool EnCode(DICT  *Head)
{
	puts("编码过程");
	char ch;
	char *sp,*sc;
	int	  len;
	DICT*	pc=Head,*pos=NULL,*pos0=NULL;
	FILE *fps,*fpt;
	sp=(char *)malloc(sizeof(char));
	sp[0]='\0';
	//while(pc!=NULL){puts(pc->s);pc=pc->next;}//pc
	fps=fopen("Source.txt","r");
	if(!fps){puts("Source File Open Error !");exit(0);}
	fpt=fopen("Encode.txt","w+");
	if(!fpt){puts("Codestream File Write Error !");exit(0);}
	while(!feof(fps)){
		len=strlen(sp);
		pos0=StrInDict(sp,Head);
		ch=fgetc(fps);
		sc=(char *)malloc(sizeof(char)*(len+2));
		strcpy(sc,sp);
		sc[len+1]=sp[len];
		sc[len]=ch; //P: P + C; 
		pos=StrInDict(sc,Head);// puts(sc);
		if(pos!=NULL){//pre 和 cur 交换
			sp=sc;
		}//true
		else{
			Head=Insert(sc,Head);
			if(pos0!=NULL){fprintf(fpt,"%d ",pos0->n);   printf("%d ",pos0->n);	puts(sc);}
			sp[0]=ch;
			sp[1]='\0';
		}//false
	}//
	fclose(fps);
	fclose(fpt);
	return true; 
}
void	DeCode(DICT *Head)
{
	puts("解码过程");
	char *sc=NULL,*sp=NULL,*s,ch[2];
	bool find=false;
	int pre=0,cur=1;
	int cw,pw;
	DICT *pc=Head;
	FILE *fps,*fpt;
	fps=fopen("Encode.txt","r");
	if(!fps){puts("Codestream File Open Error !");exit(0);}
	fpt=fopen("Decode.txt","w+");
	if(!fpt){puts("Decode File Write Error !");exit(0);}
	if(fscanf(fps,"%d",&cw)!=1){puts("Error read numbers !");exit(0);}
	sc=NumInDict(cw,Head);
	if(sc!=NULL){
		fprintf(fpt,"%s",sc);	printf("%d ",cw);puts(sc);
	}
	ch[1]='\0';
	while(!feof(fps)){
		pw=cw;
		sp=NumInDict(pw,Head);
		s=(char*)malloc(sizeof(char)*(strlen(sp)+1));
		strcpy(s,sp);
		if(fscanf(fps,"%d",&cw)!=1){exit(0);}//	
		printf("%d ",cw);	
		sc=NumInDict(cw,Head);
		if(sc!=NULL){
			fprintf(fpt,"%s",sc);		puts(sc);
			find=true;
			ch[0]=sc[0]; 
		}//in
		else {
			ch[0]=sp[0];
			find=false;
		}
		strcat(s,ch);
		if(!find){
			fprintf(fpt,"%s",s); 			puts(s);
		}
		Head=Insert(s,Head);//Add to Dict 
		//pc=Head;while(pc!=NULL){printf("%d--",pc->n);puts(pc->s);pc=pc->next;}
	}//fps
	fclose(fps);
	fclose(fpt);
}
int main()
{

	DICT	*pdHead=NULL;
//	pdHead=GenDictTest('a','c');
	pdHead=GenDictTest(0,127);	
	EnCode(pdHead);
	DeCode(pdHead);
	return 0;
}