huffman.c

理用霍夫曼算法进行压缩,解压算法还未编出来

/*
 * 程序功能：对文本文件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;
}