www.pudn.com > Huffman-Encoder.zip > HuffmanCoding.c, change:2011-11-05,size:8175b


/*  
 * 程序功能:对文本文件success.dat进行霍夫曼编码,用文本文件coding.dat保存编码  
 * 编程思路:  
   第一步:  
       首先打开扫描文件success.dat,统计出每个字符出现的次数,作为各个字符的权,  
   在这里我假设文本文件里面的字符只包含a~z这26个小写字母,用CharCount函数扫描文件,统计  
   出各个字符在文件中出现的次数(注意,如果某个字符一个都没出现,那就设它的权为1,因为权  
   是0的话将不能正确编码,血的教训) CharCount函数的原型如下:  
   void CharCount(FILE *fp, int *Count, int length);  
   其中fp是要扫描的文件的指针,数组Count的每个元素分别用来统计a,b..z在文件中出现的次数,  
   length是数组的长度。  
  
   第二步:  
       根据给定的字符集(这里设字符集为a~z这26个小写字母), 和各字符的权(用CharCount函数得到的),  
   创建哈夫曼树,函数原型如下:  
   void createHTree(HuffmanTree HT, char *c, int *w, int n);  
   其中数组c[0..n-1]就是要编码的字符集,w[0..n-1]就是Count函数得到的各字符的权,构造霍夫曼树HT  
  
   第三步:  
       对霍夫曼树中的n个叶子结点进行编码,第i个叶子结点的编码存放在HC[i]中(1 = i = n)  
	函数原型如下:  
	void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n);  
	若中HT是构造的一棵霍夫曼树,HC是一个字符串数组,n是霍夫曼树叶子结点的数目  
  
   第四步:  
       对文本文件success.dat进行霍夫曼编码,用文本文件coding.dat保存编码,函数原型如下:  
       void Coding(HuffmanTree HT, HuffmanCode HC, int n);  
    其中HT是构造好的一棵霍夫曼树,HC是保存着霍夫曼树各叶子结点编码的字符串数组,n是叶子结点  
	的数目。  
	    这个函数以读方式打开success.dat和写方式打开coding.dat,然后从success.dat里面读一个字符,  
	在字符串数组HC中找出该字符的编码,写入coding.dat文件,直到success.dat读完为止。   
  
 * Copyright (c) 2006 All rights reserved.  
 * 文件名:HuffmanCoding.c  
 *  
 * 文件标识:霍夫曼编码  
 * 摘要:对文本文件success.dat进行霍夫曼编码,用文本文件coding.dat保存编码  
 * 输入:无  
 * 输出:输出一个霍夫曼编码文件(文件内容是0或1的字符序)  
 *  
 * 当前版本 0.01  
 * 作者:罗  
 * 完成日期:2006年4月4日  
 */  
  
  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#define MAXLEAFNUM 50    /* 叶子结点的最大数目 */  
  
/* 定义一个霍夫曼树的结构 */  
typedef struct node  
{  
    char ch;                   /* 当前结点表示的字符,对于非叶子结点,此域不用 */  
	int weight;                /* 当前结点的权值 */  
    int parent;                /* 当前结点的父结点下标,为0表示无父结点 */  
    int lchild, rchild;        /* 当前结点左右孩子结点的下标,都为0时表示无孩子结点 */  
} HuffmanTree[2*MAXLEAFNUM];  
typedef char* HuffmanCode[MAXLEAFNUM+1];  
  
/* 在HT[1~n]中选择weigth最小的且parent为0的结点,用p1,p2带回 */  
void select(HuffmanTree HT, int n, int *p1, int *p2);  
  
/* 根据给定的字符集创建哈夫曼树 */  
void createHTree(HuffmanTree HT, char *c, int *w, int n);  
  
/* n个叶子结点在霍夫曼树HT中的下标为1~n,第i(i=i=n)个叶子的编码存放HC[i]中 */  
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n);  
  
/* 利用具有n个字符的霍夫曼编码的编码集(1~n)对字符逐个进行编码 */  
/* 最后把编码存储在buff 所指向的字符指针中 */  
void Coding(HuffmanTree HT, HuffmanCode HC, int n);  
  
  
/* 统计字符在文件中出现的次数,并作为该字符的权进行霍夫曼编码 */  
void CharCount(FILE *fp, int *Count, int length);  
  
//函数功能:在HT[1~n]中选择weigth最小的且parent为0的结点,用p1,p2带回  
//参数:HT为n棵霍夫曼树,p1和p2用来带回weight最小的且parent为0的两个结点  
//返回值:无  
void select(HuffmanTree HT, int n, int *p1, int *p2)  
{  
	static int first = 1;  
	int k, i;  
	while (HT[first].parent != 0)  
		first++;  
	k = first;  
	for (i = first+1; i = n; i++)  
	if ((HT[i].parent == 0) && (HT[i].weight  HT[k].weight))  
	{  
		k = i;  
	}  
	if (k = first)  
	{  
		first++;  
		while (HT[first].parent != 0)  
			first++;  
	}  
	*p1 = k;  
  
	k = first;  
	for (i = first+1; i = n; i++)  
	if ((HT[i].parent == 0) && (HT[i].weight  HT[k].weight) &&(i != *p1))  
	{  
		k = i;  
	}  
	if (k == first)  
	{  
		first++;  
		while (HT[first].parent != 0)  
			first++;  
	}  
	*p2 = k;  
}  
  
  
/*   
 * 函数功能:创建霍夫曼树  
 * 参数:数组c[0..n-1]和w[0..n-1]存放了n个字符,以及其概率,构造霍夫曼树HT  
 * 返回值:无  
*/  
void createHTree(HuffmanTree HT, char *c, int *w, int n)  
{  
	int i, s1, s2;  
	if (n = 1)  
		return;  
	/* 根据n个权值构造n棵只有根结点的二叉树 */  
	for (i = 1; i = n; i++)  
	{  
		HT[i].ch = c[i-1];  
		HT[i].weight = w[i-1];  
		HT[i].parent = HT[i].lchild = HT[i].rchild = 0;  
	}  
  
	for (; i  2*n; i++)  
	{  
		HT[i].parent = HT[i].lchild = HT[i].rchild = 0;  
	}  
  
	/* 构造霍夫曼树,从HT[1.. i-1]中选择parent 为0,且weight最小的两棵树,其序号为s1和s2 */  
    for (i = n+1; i  2*n; i++)  
	{  
		select(HT, i-1, &s1, &s2);  
		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;  
	}  
}  
  
/*   
 * 函数功能:对霍夫曼树中的叶子结点进行编码,第i个结点的编码放在HC[i]中(1 = i = n)  
 * 参数:HT为一棵霍夫曼树,HC为一个存放霍夫曼编码的字符串数组,n为叶子的个数  
 * 返回值:无  
*/  
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n)  
{  
    /*n个叶子结点在霍夫曼树HT中的下标为1~n,第i(i=i=n)个叶子的编码存放HC[i]中*/  
    char *cd;  
    int i, start, c, f;  
    if (n = 1)  
        return;  
    cd = (char *)malloc(n);  
    cd[n-1] = '\0';  
    i = 1;  
    while (i = n)  
    {  
        start = n-1;  
        for (c=i, f=HT[c].parent; f!=0; c=f, f=HT[c].parent)  
        {  
            if (HT[f].lchild == c)  
               cd[--start] = '1';  
            else  
               cd[--start] = '0';  
        }  
        HC[i] = (char *)malloc(n - start);  
        strcpy(HC[i], &cd[start]);  
        i++;  
    }   
}  
  
  
/*  
 * 函数功能: 利用具有n个字符的霍夫曼编码的编码集(1~n)对字符逐个进行编码  
 * 最后把编码存储在buff 所指向的字符指针中  
 * 参数:一棵霍夫曼树,字符集  
*/  
void Coding(HuffmanTree HT, HuffmanCode HC, int n)  
{  
	char ch;  
	int i;  
	FILE *IN, *OUT;  
  
	if ((IN = fopen("success.dat", "r")) == NULL)  
	{  
		printf("File Open Error!\n");  
		exit(1);  
	}  
  
	if ((OUT = fopen("coding.dat", "w+")) == NULL)  
	{  
		printf("File Open Error!\n");  
		exit(1);  
	}  
  
	while (!feof(IN))  
	{  
		ch = fgetc(IN);  
		i = 1;  
		while ((HT[i].ch != ch) && (i = n))  
		{  
			i++;  
			if (i > n)  
				return;  
		}  
  
		/* 将ch代表的字符的编码写入到输出文件 */  
		fputs(HC[i], OUT);  
	}  
  
	fclose(IN);  
	fclose(OUT);  
}  
  
  
/*  
 * 函数名:CharCount  
 * 参数:一个指向文件的指针,以及一个整型数组  
 * 函数功能:统计文件中每个字符出现的次数,由Count数组带回字符出现的次数  
 * 返回值:无  
*/  
void CharCount(FILE *fp, int *Count, int length)  
{  
	char ch;  
	int i;  
	/* 如果某个字符在文件中没有出现,则它的权为1 */  
	for (i = 0; i  length; i++)  
	{  
		Count[i]++;  
	}  
  
	/* 碰到一个出现的字符,就将它的权增1 */  
	while (!feof(fp))  
	{  
		ch = fgetc(fp);  
		Count[(ch) - 97]++;  
	}  
}  
  
int main(int argc, char* argv[])  
{  
	/* 要进行霍夫曼编码的字符集 */  
    char CharSet[] = "abcdefghijklmnopqrstuvwxyz";  
  
    /* 字符的权 */  
    static int weight[26];  
  
	/* 字符集字符个数 */  
	int size, i;  
      
	/* 霍夫曼树变量 */  
  
    HuffmanTree HT;  
	/* 霍夫曼编码集 */  
	HuffmanCode HC;  
  
	FILE *IN;  
  
	if ((IN = fopen("success.dat", "r")) == NULL)  
	{  
		printf("File Open Error!\n");  
		exit(1);  
	}  
  
  
	size = strlen(CharSet);   
	/* 统计各个字符在文件中出现的次数 */  
    CharCount(IN, weight, size);  
  
	/* 输出各字符在文件中出现的次数,次数为1表示在文件中没有出现该字符 */  
	printf("各个字符的权为:\n");  
	for (i = 0; i  size; i++)  
	{  
		printf("%3d", weight[i]);  
		if ((i+1) % 10 == 0)  
			printf("\n");  
	}  
	printf("\n");  
	fclose(IN);  
  
	/* 根据字符集和权值创建霍夫曼树 */  
	createHTree(HT, CharSet, weight, size);  
  
	/* 对哈夫曼树中的叶子结点进行编码 */  
	HuffmanCoding(HT, HC, size);  
	/* 输出各个字符对应的编码 */  
	printf("各个字符的编码分别为:\n");  
	for (i = 1; i = size; i++)  
	{  
		printf("%c = %s\n", HT[i].ch, HC[i]);  
	}  
  
	/* 对文件进行编码,执行完后看看你的当前工作目录下的coding.dat文件,是不是有字符编码了 */  
	Coding(HT, HC, size);  
  
	return 0;  
}