哈夫曼树-贪心算法的应用实例

/*
*哈夫曼编码-链式结构
* 
*功能实现： 
*	源文件字符权值确认操作 
*	哈夫曼树的建立操作 
*	字符字典的建立操作 
*	源文件转码操作操作 
*	二进制文件译码操作
*	文件输出操作
*	内存清理操作 
*/

#include 
#include 
#define _HFMAlgorithm_
#define codesize 30

//哈夫曼树结点定义 
typedef struct forest{
	struct forest *left;
	struct forest *right;
	struct forest *parent;
	unsigned int weight;
	char word;
}HFMNode;

//字符字典结点定义 
typedef struct hfmtable{
	char word;
	char code[codesize];
	int start;//标记起始位置 
	struct hfmtable *next;
}Table;

//函数声明
HFMNode * ReadFile(void);
HFMNode * CreateHFMTree(HFMNode *F);
void HFMCode(HFMNode * root,Table * &table);
void PrintHFMTree(HFMNode *root);
void PrintTable(Table *t);
void TransCoding(Table * table);
void ReTransCoding(HFMNode * root);
void SelectFile(void);
void PrintFileInformation(char FileName[]);
void DestroyHFMTree(HFMNode *root);
void DestroyTable(Table *table);

//读取源文件，确认各字符权值建立森林 
HFMNode * ReadFile(void)
{
	HFMNode *head,*p;
	FILE *fp = NULL;
	char a;
	
	//创建表头结点 
	head = (HFMNode *)malloc(sizeof(HFMNode));
	head->left = head->right = head->parent = NULL;
	head->word = '';
	head->weight = 0;
	
	//读取源文件，确认权重 
    fp = fopen("input.data","r");
	while( (a = fgetc(fp)) != EOF ){
        for(p = head;p->parent && p->parent->word - a;p = p->parent);
        if(!p->parent){//没找到结点，追加一个新结点 
        	p->parent = (HFMNode *)malloc(sizeof(HFMNode));
        	p->parent->left = p->parent->right = p->parent->parent = NULL;
        	p->parent->word = a;
        	p->parent->weight = 0;
    	}//end if
        p->parent->weight++;
    }//end while
    
    fclose(fp);
    return head;
}

//根据权值建立哈夫曼树 
HFMNode * CreateHFMTree(HFMNode *F)
{
	HFMNode *p,*k1,*k2;//k1,k2为最小值次小值前驱结点 
	HFMNode *d1,*d2;//d1,d2为最小值次小值结点 
	
	while(F->parent->parent){
		for(k1 = F,p = k2 = F->parent;p->parent;p = p->parent){
			//从链表森林中找最小值次小值前驱结点 
			if(p->parent->weight < k1->parent->weight){
				k2 = k1;
				k1 = p;
			}//end if
			else if(p->parent->weight < k2->parent->weight){
				k2 = p;
			}//end if
		}//end for
		
		//取出最小值，次小值结点，合并后放回森林 
		d1 = k1->parent;
		d2 = k2->parent;
		if(d1->parent == d2){//分情况处理取结点顺序 
			k2->parent = d2->parent;
			k1->parent = d1->parent;
		}//end if
		else{
			k1->parent = d1->parent;
			k2->parent = d2->parent;
		}//end else
		
		//建立一个过渡结点 
		p = (HFMNode *)malloc(sizeof(HFMNode));
		p->left = d1;
		p->right = d2;
        p->word = '';
        p->weight = d1->weight + d2->weight;
        d1->parent = d2->parent = p;

        p->parent = F->parent;
        F->parent = p;
	}
	
	F->parent->parent = NULL;
	p = F->parent;
	free(F);
	return p;
}

//建立哈夫曼字符字典 
void HFMCode(HFMNode * root,Table * &table)
{
	Table *p;
	HFMNode *q,*r;
	if(root){
		HFMCode(root->left,table);
		HFMCode(root->right,table);
		if(root->left == NULL && root->right == NULL){
			for(p = table;p && p->word - root->word;p = p->next);
			if(!p){//表中尚无该字符的译码字典,头插式添加字典信息 
				p = (Table *)malloc(sizeof(Table));
				p->next = table;
				table = p;
				p->word = root->word;
				p->start = codesize;
				p->code[--p->start] = '';
				q = root->parent;
				r = root;
				while(q){
					p->code[--p->start] = '0' + (q->left != r);
					r = q;
					q = q->parent;
				}
			}
		}
	}
}

//输出哈夫曼树叶子结点信息,中序遍历 
void PrintHFMTree(HFMNode *root)
{
	if(root){
		PrintHFMTree(root->left);
		if(root->left == NULL && root->right == NULL)
			printf("字符:%c 权值:%dn",root->word,root->weight);
		PrintHFMTree(root->right);
	}
}

//输出哈夫曼字符字典信息 
void PrintTable(Table *t)
{
	printf("字符t哈夫曼码n");
	for(;t;t = t->next){
		printf("%-4ct%sn",t->word,t->code + t->start);
	}
	putchar('n'); 
}

//读取源文件将其进行哈夫曼转码 
void TransCoding(Table * table)
{
	FILE *fp1,*fp2;
	Table *p;
	char a;
	
	fp1 = fopen("input.data","r");
	fp2 = fopen("password.data","w");
	
	while( (a = fgetc(fp1)) != EOF){
		for(p = table;p && p->word - a;p = p->next);
		if(!p)
		{
			printf("Found Error In TransCoding!n");
			exit(0);
		}
		fputs(p->code + p->start,fp2);
	}
	
	fclose(fp1);
	fclose(fp2);
}

void ReTransCoding(HFMNode * root)
{
	FILE *fp1,*fp2;
	HFMNode *p;
	char a = 0;
	
	fp1 = fopen("password.data","r");
	fp2 = fopen("output.data","w");
	
	while( a != EOF )
	{
		p = root;
		while(1){
			a = fgetc(fp1);
			if(a - '0')
				p = p->right;
			else
				p = p->left;
			if(p->word)
			{
				fputc(p->word,fp2);
				break;
			}
		}
	}
	
	fclose(fp1);
	fclose(fp2);
}

void PrintFileInformation(char FileName[])
{
	FILE *fp;
	char a;
	
	//打印文件
	printf("%s内容如下:n",FileName); 
	if( (fp = fopen(FileName,"r")) == NULL ){
		printf("%s打开失败!n",FileName);
		exit(0);
	}
	while( (a = fgetc(fp)) != EOF ){
		putchar(a);
	}
	printf("nn");
	
	fclose(fp);
}

void SelectFile(void)
{
	PrintFileInformation((char *)"input.data");
	PrintFileInformation((char *)"password.data");
	PrintFileInformation((char *)"output.data");
}

void DestroyHFMTree(HFMNode *root)
{
	if(root){
		DestroyHFMTree(root->left);
		DestroyHFMTree(root->right);
		free(root);
	}
}

void DestroyTable(Table *table)
{
	Table *p;
	while(table)
	{
		p = table;
		table = table->next;
		free(p);
	}
}

int main(void)
{
	HFMNode *F;//森林 
	HFMNode *root;//最优二叉树根节点 
	Table *table = NULL;//哈夫曼译码字典 
	int n;
	
	//从文件中读取文章到内存，存储在vector Wordtable中
	F = ReadFile();
	printf("权值确认完毕...nn");
	
	//基于上表建立最优二叉树
	root = CreateHFMTree(F); 
	printf("最优二叉树建立完毕...nn");
	
	//输出HFMTree 
	printf("输出最优二叉树有效结点:n");
	PrintHFMTree(root);
	putchar('n');
	
	//建立HFM译码字典 
	HFMCode(root,table);
	printf("译码字典建立完毕...nn");
	
	//输出HFM译码字典
	printf("输出译码字典:n");
	PrintTable(table); 
	
	//读入文章进行转码处理
	TransCoding(table);
	printf("源文件转码完毕...nn");
	
	//二进制传输文件译码处理 
	ReTransCoding(root);
	printf("二进制文件译码完毕...nn");
	
	//将源文件，二进制文件，译码文件打印在DOS屏幕上
	SelectFile();
	
	//内存释放
	DestroyHFMTree(root);
	DestroyTable(table);
	printf("程序结束,清空内存完毕...n");
	
	return 0;
}