huffman.h

huffman的排序算法

#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "string.h"

/*****************************************************************************************************************
                                                           堆排序
*****************************************************************************************************************/
#define MAXSIZE 300
typedef struct{
	int key;
	int sign; //记录HT[i]中的i;
}RedType;

typedef struct {
	RedType r[MAXSIZE+1];  //r[0]为哨兵
	int length;
}SqList;


void HeapAdjust(SqList &L,int s,int m){
	RedType rc;
	rc=L.r[s];
	int j;
	for(j=2*s;j<=m;j*=2){
		if(j<m&&L.r[j].key<L.r[j+1].key) j++;
		if(rc.key>=L.r[j].key) break;
		L.r[s]=L.r[j];
		s=j;
	}
	L.r[s]=rc;
}//HeapAdjust

void HeapSort(SqList &L){
	int i;
	for(i=L.length/2;i>0;i--)
		HeapAdjust(L,i,L.length);
	for(i=L.length;i>1;i--){
		RedType t;
		t=L.r[1];
		L.r[1]=L.r[i];
		L.r[i]=t;
		HeapAdjust(L,1,i-1);
	}
}//HeapSort




/*****************************************************************************************************************
                                                    字符出现次数
*****************************************************************************************************************/
int emergetime(char filename[],char findch){
	int freq=0;
	char ch;
	FILE *fp;
	if((fp=fopen(filename,"r"))==NULL) exit(0);
	ch=fgetc(fp);
	while(ch!=EOF){
		if(ch==findch) freq++;
		ch=fgetc(fp);
	}
	return freq;
}


/*****************************************************************************************************************
                                                     Huffman编码
*****************************************************************************************************************/
typedef struct{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char* *HuffmanCode;


/***********************************利用堆排序找到权值最小的两个节点****************************/

void Select(HuffmanTree HT,int n,int &s1,int &s2){
	SqList L;
	int i;
	int j=1;
	for(i=1;i<=n;i++){
		if(HT[i].parent==0)
		{
			L.r[j].key=HT[i].weight;
			L.r[j].sign=i;
			j++;
		}
	}
	L.length=j-1;
	HeapSort(L);
	s1=L.r[1].sign;
	s2=L.r[2].sign;
}
		
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
	//w存放n个字符的权值
	if(n<=1)return;
	int m;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	int i;
	HTNode *p;
	for(p=HT+1,i=1;i<=n;i++,p++,w++){
		p->weight=*w;
		p->parent=0;p->lchild=0;p->rchild=0;
	}
	//所有叶子结点parent为0；
	for(;i<=m;i++,p++){
		p->weight=0;
		p->parent=0;p->lchild=0;p->rchild=0;
	}

	
	for(i=n+1;i<=m;i++){
		int s1,s2;
		Select(HT,i-1,s1,s2);//在HT[1...i-1]中选择parent为0的weight最小的两个结点
		HT[s1].parent=i; HT[s2].parent=i;
		HT[i].lchild=s1; HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	

/**********************下面从叶子结点到根逆向求每个字符的赫夫曼编码*******************************/
	
	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量
	char *cd;
	cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间
	for(i=1;i<=n;i++){
		int start,c,f;
		start=n-1;
		cd[n-1]='\0';
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
			if(HT[f].lchild==c) cd[--start]='0';
			else cd[--start]='1';
		}
		HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
		strcpy(HC[i],&cd[start]);	
	}
	free(cd);
}//HuffmanCoding


/*****************************************************************************************************************
                                                    解码生成原文件
*****************************************************************************************************************/

/*******************************根据Huffman编码建一棵二叉树***********************************/

typedef struct BiTNode{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


struct Huffman_type{
	char ch;         //字符
	char str[30];    //Huffman编码
}HCode[91]; //换行符另外处理


void CreateTree(BiTree &T,Huffman_type hcode){
	int j;
	int length;
	length=strlen(hcode.str);
	BiTree F;
	F=T;
	for(j=0;j<length-1;j++){
		if(hcode.str[j]=='0') 
		{
			if(!F->lchild) 
			{
				 F->lchild=(BiTree)malloc(sizeof(BiTNode));
				 F->lchild->lchild=NULL;
				 F->lchild->rchild=NULL;
			}
			F=F->lchild;	
		}
		else 
		{
			if(!F->rchild) 
			{
				F->rchild=(BiTree)malloc(sizeof(BiTNode));
				F->data='0';
				F->rchild->lchild=NULL;
				F->rchild->rchild=NULL;
			}
			F=F->rchild;
		}
	}
	F->data=hcode.ch;
}


/*****************************************************************************************************************                                                   
													 end...
*****************************************************************************************************************/