霍夫曼编码.txt

利用VC++开发的霍夫曼压缩编码算法

数据结构与算法设计-对文本文件进行霍夫曼编码 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;
}