huffancoding.cpp

赫夫曼编码与译码 本程序完全采用链式存储结构

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
const int codeMax=100;
typedef struct htnode{
	unsigned short asc;
	unsigned int weight;
	unsigned short code[codeMax];
	struct htnode *parent,*lchild,*rchild;
	struct htnode *next;
}HTNode,*HuffmanTree;

void build(unsigned int count[],int m,HuffmanTree &head){
	HuffmanTree s;
	for(int i=0;i<m;i++){
		if(count[i]!=0){
			s=(HTNode *)malloc(sizeof(HTNode));
			s->asc=i;s->weight=count[i];
			s->parent=s->lchild=s->rchild=NULL;
			s->next=head->next;head->next=s;
		}
	}
}

HuffmanTree arrange(HuffmanTree &head){
	HuffmanTree temp1,temp2,s1,s=head->next;
	unsigned int w;
	if(s) w=s->weight;
	else exit(0);
	s1=temp2=head;temp1=s;
	while(s){
		if(w>s->weight){
			w=s->weight;
			temp1=s;
			temp2=s1;
		}
		s1=s;
		s=s->next;
	}
	temp2->next=temp1->next;
	temp1->next=NULL;
	return temp1;
}
	


HuffmanTree BuildTree(HuffmanTree &head){
			HuffmanTree s=arrange(head);
			HuffmanTree t=arrange(head);
			HuffmanTree u=(HTNode *)malloc(sizeof(HTNode));
			u->weight=s->weight+t->weight;
			u->lchild=t;u->rchild=s;u->parent=u->next=NULL;
			s->parent=t->parent=u;
			if(head->next){
				u->next=head->next;
				head->next=u;
				BuildTree(head);
			}
			else return u;
}

void HuffmanCoding(HuffmanTree &u,HuffmanTree &ahead,unsigned short c[],int &i){
	if(u->lchild){
		c[i++]=0;
		HuffmanCoding(u->lchild,ahead,c,i);
	}
	else{
		c[i]=3;
		int j=0;
		while(c[j]!=3){
			u->code[j]=c[j];
			j++;
		}
		u->code[j]=3;
		u->next=ahead->next;ahead->next=u;
	}
	if(u->rchild){
		c[i++]=1;
		HuffmanCoding(u->rchild,ahead,c,i);
	}
	i--;
}

void out(HuffmanTree ahead){
	while(ahead=ahead->next){
		printf("%c(ASC码为%d)出现%d次,编码为",ahead->asc,ahead->asc,ahead->weight);
		int j=0;
		while(ahead->code[j]!=3){
			printf("%d",ahead->code[j]);
			j++;
		}
		printf("\n");
	}
}

void coding(HuffmanTree ahead,FILE *fp1,FILE *&fp2){
	char ch;
	while(!feof(fp1)){
		ch=fgetc(fp1);
		HuffmanTree temp=ahead;
		while((temp=temp->next)){
			if(ch==temp->asc){
				int j=0;
				while(temp->code[j]!=3){
					fputc(temp->code[j]+'0',fp2);
					j++;
				}
				break;
			}			
		}
	}
	fclose(fp1);
}

void recoding(HuffmanTree u,FILE *fp){
	HuffmanTree t=u;
	unsigned short i;
	while(!feof(fp)){		
		if(t->lchild){
			i=fgetc(fp)-'0';
			if(i==0) t=t->lchild;
			else t=t->rchild;
		}
		else{
			printf("%c",t->asc);
			t=u;
		}
	}
	fclose(fp);
}


void main(){
	unsigned int count[256]={0};
	char ch;
	int m=0;
	HuffmanTree head,ahead;
	head=(HTNode *)malloc(sizeof(HTNode));
	head->lchild=head->rchild=head->parent=head->next=NULL;
	FILE *fp1,*fp2;
	if((fp1=fopen("input.txt","w+"))==NULL){
		printf("cannot open this file");
		exit(0);
	}
    while((ch=getchar())!=EOF){
		fputc(ch,fp1);
		short i=ch;
		count[i]++;
	}
    rewind(fp1);
	build(count,256,head);
	HuffmanTree u=BuildTree(head);
	free(head);
	ahead=(HTNode *)malloc(sizeof(HTNode));
	ahead->lchild=ahead->rchild=ahead->parent=ahead->next=NULL;
	unsigned short c[codeMax];
	int i=0;
	HuffmanCoding(u,ahead,c,i);	
	if((fp2=fopen("output.txt","w+"))==NULL){
		printf("cannot open this file");
		exit(0);
	}
	out(ahead);
	coding(ahead,fp1,fp2);
	rewind(fp2);
	recoding(u,fp2);
}