lzw算法1050320103.cpp

这是一个密码学实验程序,主要是用LZW算法进行数据的处理

/*
*大作业二
*哈尔滨工业大学
*05级计算机学院信息安全专业
*作者：吴世山 1050320103
*程序作用：实现lzw算法的压缩与解压缩
*          
*/
#include <iostream>
#define max 256

struct string                //字典表
{
	int a[max];              //存放原始字符
    int c[max][2];           //存放串字典
};

void enlzw();                //压缩函数
void delzw();                //解压缩函数
int findsame(struct string* a,int k, int i, int m);
//*****查找字符的函数，返回在数组中的位置，参数为字典指针、开始位置、结束位置、要找的字符
int findstring(struct string* a, int k, int i, int prefix, int suffix);
//*****查找字符串函数，返回在字典中的位置，参数为字典指针、开始查找的位置、结束位置、串的前缀、后缀
int findfirst(struct string* a, int m);
//*****查找首字符的函数，返回值为要找串m的首字符
void print(struct string* a, int m, FILE* cfptr);
//*****将解压缩结果输出到文件

int main(void)
{
	int n=0;
	printf("1、LZW压缩；\n2、LZW解压缩\n3、退出\n");
	scanf("%d", &n);
	getchar();
	switch(n)
	{
	case 1:
		enlzw();
		break;
	case 2:
		delzw();
		break;
	case 3:
		return 0;
	}
	
	return 0;
}

//*****压缩函数 
void enlzw()          
{
	struct string s, *a=&s;
	char filename[50];
	int m=0, n=0, i, j=0, k, prefix, suffix;

	FILE* cfptr1, *cfptr2;
	printf("请输入要压缩的文件名：\n");
	gets(filename);
	if((cfptr1=fopen(filename, "rb"))==NULL)
	{
		printf("不能打开文件或文件不存在！\n");
		return ;
	}
	printf("压缩文件存为：");
	gets(filename);
	cfptr2=fopen(filename, "w");
	if(cfptr2==NULL)
	{
		printf("不能创建文件！\n");
		return;
	}

	rewind(cfptr1);
    i=k=128;
	prefix=fgetc(cfptr1);             //从这里开始建立字典表，同时输出压缩文件
	do
	{
		suffix=fgetc(cfptr1);
		if(suffix==13)
		{
			suffix=fgetc(cfptr1);
		}
		if(suffix==EOF)
		{
			fputc(prefix, cfptr2);
			break;
		}
		if((m=findstring(a, k, i, prefix, suffix))==-1) //如果字典表中没有这个串，就将其存入字典当中
		{
			s.c[i][0]=prefix;
			s.c[i][1]=suffix;
			i++;
			fputc(prefix, cfptr2);
			prefix=suffix;
		}
		else
		{			
			prefix=m;              //如果有就以这个串为前缀继续进行下一次编码
		}	
	}while(!feof(cfptr1));
	fclose(cfptr1);
	fclose(cfptr2);
	return;
}

 //*****解压缩函数
void delzw()                       
{
	struct string s, *a=&s;
	char filename[50];
	int m=0, n=0, i, j=0, k, prefix, suffix;
	FILE* cfptr1, *cfptr2, *cfptr;

	for(i=0;i<max;i++) //初始化字典
	{
		s.a[i]=0;
		s.c[i][1]=s.c[i][2]=0;
	}
	printf("请输入要解压缩的文件名：\n");
	gets(filename);
	if((cfptr1=fopen(filename, "rb"))==NULL)
	{
		printf("不能打开文件或文件不存在！\n");
		return ;
	}
	printf("解压文件存为：");
	gets(filename);
	cfptr2=fopen(filename, "w");
	if(cfptr2==NULL)
	{
		printf("不能创建文件！\n");
		return;
	}
	
	prefix=fgetc(cfptr1);     //从这里开始建立解压缩字典
	i=k=128;
	do
	{
		suffix=fgetc(cfptr1);
		if(prefix<128&&suffix<128) //如果前、后缀都为字符
		{
			if((m=findstring(a, k, i, prefix, suffix))==-1) //并且字典中没有这个串，则存入字典
			{
				s.c[i][0]=prefix;
				s.c[i][1]=suffix;
				i++;
				prefix=suffix;
			}
			else                                            //有则进行下一次编码
			{
				prefix=suffix;
			}
		}
		else if(prefix<128&&suffix>=128) //如果前缀为字符，后缀为串
		{
			if((m=findstring(a, k, i, prefix, suffix))==-1)
			{
				if(s.c[suffix][0]==0&&s.c[suffix][1]==0)
				{
					s.c[i][0]=prefix;
					s.c[i][1]=prefix;
					i++;
				}
				else
				{
					s.c[i][0]=prefix;
					s.c[i][1]=findfirst(a, suffix);
					i++;
				}
			}
			prefix=suffix;
		}
		else if(prefix>=128&&suffix<128) //如果前缀为串，后缀为字符
		{
			if((m=findstring(a, k, i, prefix, suffix))==-1)
			{
				s.c[i][0]=prefix;
				s.c[i][1]=suffix;
				i++;
				prefix=suffix;
			}
			else
				prefix=suffix;
		}
		else      //如果前后缀都为串
		{
			if((m=findstring(a, k, i, prefix, suffix))==-1)
			{
				if(s.c[suffix][0]==0&&s.c[suffix][1]==0)
				{
					s.c[i][0]=prefix;
					s.c[i][1]=findfirst(a, prefix);
					prefix=suffix;
					i++;
				}
				else
				{
					s.c[i][0]=prefix;
					s.c[i][1]=findfirst(a, suffix);
					prefix=suffix;
				}
			}
		}
	}while(!feof(cfptr1));  //到此解压字典建立完毕
	rewind(cfptr1);
	m=fgetc(cfptr1);
	cfptr=cfptr2;
	do                  //根据解压字典和压缩文件进行解压输出
	{
		if(m<128)
			fputc(m, cfptr2);
		else
			print(a, m, cfptr2);
		m=fgetc(cfptr1);
	}while(!feof(cfptr1));
	fclose(cfptr1);
	fclose(cfptr2);
	return ;
}

//*****查找字符的函数，返回在数组中的位置，参数为字典指针、开始位置、结束位置、要找的字符
int findsame(struct string* a, int k, int i, int m)
{
	int j;
	for(j=k;j<=i;j++)
	{
		if(m==a->a[j])
		{
			return j;
		}
	}
	return -1;
}

//*****查找字符串函数，返回在字典中的位置，参数为字典指针、开始查找的位置、结束位置、串的前缀、后缀
int findstring(struct string* a, int k, int i, int prefix, int suffix)
{
	int j;
	for(j=k;j<=i;j++)
	{
		if((a->c[j][0]==prefix)&&(a->c[j][1]==suffix))
			return j;
	}
	return -1;
}

//*****查找首字符的函数，返回值为要找串m的首字符
int findfirst(struct string* a, int m)
{
	while(m>=128)
	{
		m=a->c[m][0];
	}
	return m;
}

//*****将解压缩结果输出到文件
void print(struct string* a, int m, FILE* cfptr)
{
	if(m<128)
	{
		fputc(m, cfptr);
		return;
	}
	print(a, a->c[m][0], cfptr);
	print(a, a->c[m][1], cfptr);
}