lzw.cpp

多媒体课内实验：用C语言实现的LZW压缩和解压算法。

#include <iostream>
#include <fstream>
#include <malloc.h>

using namespace std;

#define HASH_SIZE 4097

struct Table
{
	char *str;

}HashTable[HASH_SIZE];

ifstream input;
ofstream output;



ofstream result("result.txt");



int  ItemPt;

void InitHashTable()
{
	for(int i=0; i<256; i++)
	{
		HashTable[i].str = (char *)malloc(2*sizeof(char));
		HashTable[i].str[0] = i;
		HashTable[i].str[1] = '\0';
	}
	HashTable[256].str = NULL;
	HashTable[257].str = NULL;
	ItemPt = 258;
}

int InHashTable(char *str)
{
	for(int i=0; i<ItemPt; i++)
	{
		if(i==256 || i==257)
			continue;
		if(!strcmp(HashTable[i].str,str))
			return i;
	}

	return -1;
}
void AddToHashTable(char *str)
{
	
	HashTable[ItemPt].str = (char *)malloc(strlen(str));
	strcpy(HashTable[ItemPt].str, str);
	ItemPt++;
}
char* CopyStr(char *des, char *src)
{
	des = (char *)malloc(strlen(src));
	strcpy(des, src);
	return des;
}
char* JoinChar(char *str, char ch)
{
	if(!str)
	{
		str = (char *) malloc(2*sizeof(char));
		str[0] = ch;
		str[1] = '\0';
		return str;
	}
	else
	{
		char *temp = (char *)malloc(sizeof(char)*(strlen(str)+1));
		for(int i=0; i<strlen(str); i++)
			temp[i] = str[i];
		temp[i++] = ch;
		temp[i] = '\0';
		return temp;
	}
	
}


void LZW_Encode()
{
	char cur_char,character;
	char *str=NULL,*temp=NULL;
	input>>cur_char;
	str = JoinChar(str, cur_char);
	temp = JoinChar(temp, cur_char);
	while(input>>character)
	{
		temp = JoinChar(temp, character);

	//	cout<<temp;
	//	cout<<InHashTable(temp);

		if(InHashTable(temp)!=-1)
		{
			str = JoinChar(str, character);
		
		}
		else
		{
			result<<"<"<<InHashTable(str)<<">";
			//cout<<InHashTable(str)<<endl;

			AddToHashTable(temp);
			str = NULL;
			temp = NULL;
			str = JoinChar(str, character);
			temp = JoinChar(temp, character);
		}
	}
	result<<"<"<<InHashTable(str)<<">";
	result<<"<257>";
}
int getNextCode()
{
	char tmp;
	int code;
	if(input >> tmp)
	{
		
		input >> code;
		input >> tmp;
		return code;
	}
	return -1;
	

}
void LZW_Decode()
{
	ItemPt = 258;
	int old_Code,new_Code;
	char *str,character;

	old_Code = getNextCode();
	result<<HashTable[old_Code].str;
	while((new_Code=getNextCode())!=-1)
	{
		if(new_Code == 257)
			break;
		if(new_Code >= ItemPt)
		{
			str = CopyStr(str,HashTable[old_Code].str);
			str = JoinChar(str,character);
		}
		else
			str = CopyStr(str,HashTable[new_Code].str);
		result<<str;
		character = str[0];
		
		AddToHashTable(JoinChar(HashTable[old_Code].str,character));
		old_Code = new_Code;

	}

}
int main()
{
	char str[100];
	InitHashTable();
	printf("请选择：1 压缩  2 解压\n");
	int sel;

	cin >> sel ;
	if(sel == 1)
	{
		printf("请输入待压缩的文件名: ");
		cin >> str;
		input.open(str);
		
		LZW_Encode();

		input.close();
	}
	else if(sel == 2)
	{
		printf("请输入待解压的文件名: ");
		cin >> str;
		input.open(str);

		LZW_Decode();	
		
		input.close();
	}

	
	return 0;
}