decode.cpp

编解码分为2个文件

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define maxsize 256
#define maxweight 2.0

typedef struct element{
	float weight;
	float EffCodeLenght;
	unsigned char ch;
	unsigned char* code;
	int codelen;
}Element;

typedef Element aType[maxsize];
typedef struct node *Position;

typedef struct node{
	Element el;
	char pst;
	int depth;//用于记录节点深度
	Position left,right,father,link;
	Position leaflink;
}Node;

//读取文本信息
void ReadTextInformation(unsigned long &textlength, int &n, aType &B, FILE* f_code)
{
	fread(&textlength, 4, 1, f_code);
	fread(&n, 4, 1, f_code);
	for(int i = 0; i < n; i++)
		fread(&B[i], sizeof(struct element), 1, f_code);
}
///////////////////////////////////////////////////////////////////////////////////


//概率相等,按深度排序
void InsertByDepth(Position &q1,Position &q2,Position &p, bool &flag, bool Order)
{
	bool flag2 = 0;
	while(!flag2){
    	if(p->depth < q1->depth){
	    	p->link = q1;
		    q1 = p;
    		flag2 = 1;
			if(Order)
				p->leaflink = p->link;
		}
		else if((p->depth >= q1->depth && p->depth < q2->depth) || p->el.weight < q2->el.weight)
		{
			p->link = q2;
			q1->link =p;
			flag2 = 1;
			if(Order){
				q1->leaflink = q1->link;
				p->leaflink = p->link;
			}
		}
		else
		{
			q1 = q2;
			q2 = q1->link;
		}
	}
	flag = 1;
}
//////////////////////////////////////////////////////////////////////////////*/



//节点有序插入函数
void Insert(bool Order, Position &p, Position &head)
{
	Position q1,q2;	
	bool flag=0;
	q1 = head;
	q2 = q1->link;

	while(!flag){
		if(p->el.weight < head->el.weight){//概率最小
			p->link = q1;
			head = p;			
			flag = 1;
		}
		else if(q2 == NULL){//概率最大
			q1->link = p;
			p->link = NULL;			
			if(Order)
				q1->leaflink=q1->link;	//仅排序时用
			flag = 1;
		}
		else if(p->el.weight > q1->el.weight && p->el.weight < q2->el.weight){
			q1->link = p;
			p->link = q2;
			if(Order){
				q1->leaflink=q1->link;	//仅排序时用
				p->leaflink=p->link;
			}
			flag = 1;
		}
		else if(p->el.weight == q1->el.weight)//概率相同按深度排序
	        InsertByDepth(q1,q2,p,flag,Order);
		else{//没有找到合适的位置，下移一位
			q1 = q2;
			q2 = q1->link;
		}
        if(Order)
			p->leaflink = p->link;	//使叶节点链表指针有效
	}
}
////////////////////////////////////////////////////////////////////////////


//生成huffman树
void Huffman(aType &A, int n, Position &head, Position &codelist)
{
	int i;
	Position p;
	bool Order=1;	
	Position head2=new(Node);
	head = new(Node);
	codelist = new(Node);
	head ->el.weight = maxweight;	
	head ->link = head->leaflink = NULL;

	for(i=0;i<n;i++){
		p = new(Node);
		p ->el = A[i];
		p->depth = 1;//初始深度为1
		p ->left = p ->right = NULL;
		Insert(Order,p,head);
	}

    codelist = head;

	Order = 0;
	for(i = 1; i < n; i++){
		head2 = head ->link;
		p = new(Node);
		p->el.weight = head->el.weight + head2->el.weight;
		p->left = head; p->right = head2;
		p->depth = ( head->depth >= head2->depth ) ? ( head->depth*2+head2->depth) : ( head2->depth*2+head->depth );
		head->father = head2->father = p;
		head->pst = '0'; head2->pst = '1';//左树枝标0，右树枝标1
		head = head2->link;
		Insert(Order,p,head);
	}
	head ->father = NULL;
}
/////////////////////////////////////////////////////////////////////////////


//为每个字符编码/////////////////////////////////////////////////////////////
void ProduceCodeList(int n, Position codelist, Position head)
{
	Position pleaf = new(Node), pjunk = new(Node);
	unsigned char *InverseCode = new unsigned char[n+1];
	int CodeLength = 0;
	int count_1_length = 0;//计连续1的长度
	int max_1_length = 0;//记录连续1的个数
	int value_1_count = 0;//记录除全1码以外的最长的连续1的个数
	int value_1_code = 0;//判断全1码
	int i = 0;
	InverseCode[0] = '\0';

	pleaf = codelist;
	while(pleaf->leaflink){
		int all_1_code = 1;
		pjunk = pleaf;
		while(pjunk->father){
			CodeLength++;
			InverseCode[CodeLength] = pjunk->pst;
			if(pjunk->pst == '1')
			{
				count_1_length++;
				if(count_1_length > max_1_length)
					max_1_length = count_1_length;
			}
			else 
			{
				count_1_length = 0;
				all_1_code = 0;
			}
			pjunk = pjunk->father;
		}
		if(all_1_code == 0){
			if(max_1_length > value_1_count)
				value_1_count = max_1_length;
		}
		else max_1_length = 0;

		count_1_length = 0;
		if(all_1_code == 1)//全1码长度，而且只有一个全1码，所以不必初始化
			value_1_code = CodeLength;
		pleaf->el.code = new unsigned char[CodeLength+1];
		pleaf->el.codelen = CodeLength;//统计每一个编码的长度
		pleaf->el.EffCodeLenght = pleaf->el.weight * pleaf->el.codelen;//相对有效码长
		for( i = 0; i <= CodeLength; i++ )
			pleaf->el.code[i] = InverseCode[CodeLength-i];
		pleaf = pleaf->leaflink;
		CodeLength = 0;
	}
}
////////////////////////////////////////////////////////////////////////////*/


//输出编码表到标准输出设备(屏幕)
void PrintCL(const int n, const Position CodeList)	//输出编码表到标准输出设备(屏幕)
{
	Position p;
	p = CodeList;
	float AvgCodeLength = 0;
	printf("Character\tFrequency\t\tHuffman Code\t\tCodeLength\n");
	for(int i = 0; i < n; i++)
	{
		if(p->el.ch!=7){
			printf("%c\t\t%-5.6f%c\t\t\t%s\t\t%d\n",p->el.ch, p->el.weight*100, '%', p->el.code,p->el.codelen);
			AvgCodeLength += p->el.EffCodeLenght;
		}
		p = p->leaflink;
	}

	printf("\n***** 一共出现%d种字符 ***** \n",n);
	printf("\n****** 平均码长: %.6f ****** \n",AvgCodeLength);

}
///////////////////////////////////////////////////////////////////////


//解码函数
void DeCode0(FILE *fpcode, FILE *ffppcode, Position head, unsigned long textlength)
{
	Position p;
	p = head;
	unsigned long low_counter=0;
	unsigned long high_counter = 0;
	int i = 0; 
	int j = 0;
    unsigned long TextLengthCount = 0;

	unsigned char buffer[4096] = {0};
	unsigned int bit = 0x80;

	fread(&buffer[0],1,4096,fpcode);//读取第一段数据
	while(TextLengthCount < textlength-1){ 
		p = head;
		while(p->left||p->right){
			if(!(buffer[j]&bit)){
				p = p->left;
			    low_counter++;	
			}
			else{
				p = p->right;
				high_counter++;
			}
            i+=1;
			if(i == 8){
				i = 0;
				bit = 0x100;
				j += 1;
			}
			if(j == 4096){//每次译码完成4096个字节后，读入新的数据
				fread(&buffer[0],1,4096,fpcode);
				j = 0;
			}
			bit >>= 1;		
		}			
		fprintf(ffppcode, "%c", p->el.ch);
		TextLengthCount++;
	}
	printf("1:  %.2f%%\n",100*(float)high_counter/(low_counter+high_counter));
	printf("0:  %.2f%%\n",100*(float)low_counter/(low_counter+high_counter));
}
/////////////////////////////////////////////////////////////////////////////


//释放内存
void FreeTree(Position tree)
{
	if (tree == NULL) return;
	FreeTree(tree->left);
	FreeTree(tree->right);
	delete tree;
}
/////////////////////////////////////////////////////////////////////////////

//主函数
int main()
{
	int n = 26;
	aType B;
	clock_t start,finish, clock();
	double duration;
	unsigned long textlength = 0; 
	
	Position head;
	Position codelist;
	FILE *f_code, *f_result; 

	if(!(f_code = fopen("huf_code.wangchao","rb"))){/////读取文本长度、字符概率、编码
		printf("2.can not open the file correctly!\n");
		return 0;
	}

	if(!(f_result = fopen("result.pdf","wb+"))){/////"wb+"---为写建立一个新的二进制文件,输出解码结果
		printf("4.can not open the file correctly!\n");
		return 0;
	}

    ////读取文本信息
	ReadTextInformation(textlength, n, B, f_code);

	//根据统计结果建立huffman树
	Huffman(B, n, head, codelist);

	///step2:为每个出现的字符制定编码
	ProduceCodeList(n, codelist, head);
	
	printf("\n解码中......\n");
	start = clock();
    DeCode0(f_code, f_result, head, textlength);
    finish = clock();
	duration = (double)(finish - start);
	printf("\n解码用时:%.2fms\n\n",duration);
	///////////////////////////////*/

	fclose(f_code);
	fclose(f_result);

	////资源释放
	FreeTree(head);

	return 0; 
}