equal_length_en-decode.c

自己用C编写的Huffman编码通信系统应用

#include "huffman.h"

/*------------------------------------------------------------------*/
//等长编码
//对一个字符进行等长编码
char EqualLengthEncode(EqualLengthCodeTable E,FILE* fp1,FILE* fp2)
{
	int i = 0;
	char ch;
	char code[N1 + 1]; //临时存放编码	

	ch = ReadACharFromFile(fp1); //从原始数据文件中读取一个字符
	if(ch == '\0') //当读到文件尾标记EOF时返回了标记'\0'
		return ch; //返回'\0'标记读到文件尾标记EOF

	FindChar1(E,ch,&i); //在等长编码表E中找到字符ch的位置i
	if(ch == E[i].ch)
		strcpy(code,E[i].bits); //编码结果存在code中
	WriteStringsToFile(fp2,code);//把字符串code写入编码文件保存
	return '!'; //返回非'\0'
}

/*------------------------------------------------------------*/
//等长译码
////对1个字符对应的编码序列进行等长译码
char EqualLengthDecode(EqualLengthCodeTable E,FILE* fp1,FILE* fp2)
{   
	int length;
	int sum = 0;
	char ch;
	char ch1; //临时存储所译码的对应字符集中的字符。

	length = strlen(E[0].bits); //求编码时一个字符对应的等长编码的0，1编码序列的长度
	while(--length >= 0){ //从文件读取length个字符
		ch = ReadACharFromFile(fp1); //从编码文件中读取一个二进制码'0'或'1'字符
		if(ch == '\0')  //当读到文件尾标记EOF时返回了标记'\0'
			return ch; //返回'\0'标记读到文件尾标记EOF
		
		if(ch == '1')
			sum += (int)(pow(2,length)); //求编码序列以2为权时的和
	}
	ch1 = E[sum].ch; //对应表中的数组下表为sum的成员字符	
	WriteACharToFile(ch1,fp2); //把译码结果写入译码文件保存	
    return '!'; //返回非'\0'
}

/*-------------------------------------------------------------------*/
//等长编码算法——由分析原始数据文件求得的字符集数组string求得"等长编码表E"
void SetEqualLengthEncodeTable(EqualLengthCodeTable E,const char* const filename)
{
	int i;	
	int sum;
	int length;
	char string[N1];
	char code[N1 + 1];

    characters_analysis1(string,filename);
	sum = strlen(string); //字符集字符个数

	i = 1;
	while((int)(pow(2,i)) < sum) //求幂运算，强制转换为int型。若sum为33，则取i为6
		++i;
    length = i; //求得的length为一个字符等长编码的0，1编码序列的位数
    
	for(i = 0;i < sum;++i){
		E[i].ch = string[i];
		convert10to2(i,code,length); //把整数i转化为对应的二进制0，1序列
		strcpy(E[i].bits,code);
	}
}  

/*------------------------------------------------------------------------------*/
//等长编码时分析文件中含有哪些字符，并存到数组string中
/*要想不改变数组名string的值，必须写成char* const string，表示string为一个指向字符串的常量指针；
  而const char* string表示string是一个指向常字符串的指针，注意区分!*/
void characters_analysis1(char* const string,const char* const filename)
{
	int ch; //把一个字符当作一个整数(即字符的ASCII值)
	int i;	
	int flag;	
	FILE* fp;

//初始化字符集数组
	strcpy(string,"\0"); //初始化为空字符串		

//统计各字符的个数
    if((fp = fopen(filename,"rb")) == NULL){
		printf("\nOpen file \"%s\" to read ERROR !\n",filename);
		exit(1); //退出程序
	}	
	flag = -1;//当前放入数组F的最后一个字符的位置标记;初始位置为-1。当前F中已有(flag+1)个字符。
	while((ch = fgetc(fp)) != EOF){ //一直读到文件尾EOF
		for(i = 0;i <= flag;++i){
			if(ch == string[i])				
				break;			
		}
		if(i == flag + 1){ //在数组string的已存放字符中不存在字符ch
			++flag; //修正位置标记
			string[flag] = ch;
		}
	}
}

/*-------------------------------------------------------------------------------*/
//在等长编码表E中找到字符ch的位置i
void FindChar1(EqualLengthCodeTable E,char ch,int* ptr_i)
{
	int j;

	for(j = 0;j < N1;++j){
		if(E[j].ch == ch){
			*ptr_i = j;
			break;
		}
	}
}

/*------------------------------------------------------------------------------*/
/*将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，很容易通过"除B取余法"来解决。
例：将十进制数13转化为二进制数。
解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。
分析：由于最先得到的余数是转化结果的最低位,最后得到的余数是转化结果的最高位,因此很容易用栈来解决。
*/
void convert10to2(int i,char* const code,int length) //把整数i转化为对应的二进制0，1序列
{
	int j = 0;
	char ch;

	SeqStack S; 
	InitStack(&S); //初始化栈
	while(i){  //从右向左产生2进制的各位数字，并将其进栈
		Push(&S,(char)(i % 2)); //进栈
		i /= 2;
	}
	while(!StackEmpty(&S)){  //栈非空时退栈输出
		ch = Pop(&S); //退栈
		code[j++] = ch;		
	}
	code[j] = '\0'; //加上字符串结尾标记'\0'
}