数据结构与算法设计-对文本文件进行霍夫曼编码 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 函数原型如下：
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
#include
#include
#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 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 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 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 return;
/* 根据n个权值构造n棵只有根结点的二叉树 */
for (i = 1; 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 * 参数：HT为一棵霍夫曼树，HC为一个存放霍夫曼编码的字符串数组，n为叶子的个数
* 返回值：无
*/
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n)
{
/*n个叶子结点在霍夫曼树HT中的下标为1~n，第i(i char *cd;
int i, start, c, f;
if (n return;
cd = (char *)malloc(n);
cd[n-1] = '\0';
i = 1;
while (i {
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 {
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 {
printf("%c = %s\n", HT[i].ch, HC[i]);
}
/* 对文件进行编码，执行完后看看你的当前工作目录下的coding.dat文件，是不是有字符编码了 */
Coding(HT, HC, size);
return 0;
}
