Huffman Tree

哈夫曼（Huffman）树又称最优二叉树。它是一种带权路径长度最短的树，应用非常广泛。

关于Huffman Tree会涉及到下面的一些概念：

1. 路径和路径长度
路径是指在树中从一个结点到另一个结点所走过的路程。路径长度是一个结点到另一个结点之间的分支数目。树的路径长度是指从树的树根到每一个结点的路径长度的和。

2. 树的带权路径长度
结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。

3. 哈夫曼树
哈夫曼树就是带权路径长度最小的树，权值最小的结点远离根结点，权值越大的结点越靠近根结点。
哈夫曼树的构造算法如下。
①由给定的n个权值{w1,w2,…,wn}构成n棵只有根结点的二叉树集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。

②在二叉树集合F中选取两棵根结点的权值最小和次小的树作为左、右子树构造一棵新的二叉树，新二叉树的根结点的权重为这两棵子树根结点的权重之和。
③在二叉树集合F中删除这两棵二叉树，并将新得到的二叉树加入到集合F中。
④重复步骤②和③，直到集合F中只剩下一棵二叉树为止。这颗二叉树就是哈夫曼树。

typedef struct    /*哈夫曼树类型定义*/
{
  unsigned int weight;
  unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode; //存放哈夫曼编码

下面是自己写的有关HUffman编码的代码， 但是在经过多次修改之后还是不能将编码之前与编码之后的文件内容相匹配，希望大神指点~~

#include <stdio.h>
#include<stdlib.h>
#include<windows.h>
#include"string.h"
#include<time.h>

/*
  Name: Huffman Tree
  Copyright:
  Author:Hxm
  Date: 16/4/22 14:43
  Description:
实验题目：Huffman树及Huffman编码的算法实现
实验目的：
1、 了解该树的应用实例，熟悉掌握Huffman树的构造方法及Huffman编码的应用，
2、 了解Huffman树在通信、编码领域的应用过程。
实验要求：
1、输入一段100—200字的英文短文，存入一文件a中。
2、写函数统计短文出现的字母个数n及每个字母的出现次数
3、写函数以字母出现次数作权值，建Haffman树（n个叶子），给出每个字母的Haffman编码。
4、用每个字母编码对原短文进行编码，码文存入文件b中。
5、用Haffman树对b中码文进行译码，结果存入文件c中，比较a,c是否一致，以检验编码、译码的正确性。
*/

//-------------------------------------------------------------
//Huffman Tree结构体定义
typedef struct HTNode
{
   unsigned int weight;
   unsigned int parent, lchild, rchild;
 }HTNode, * HuffmanTree;

typedef char** HuffmanCode;    //指向字符指针的指针的数据的定义

int times[27];   //存储英文短文中26个字母出现的次数

HuffmanTree HuffTree;
HuffmanCode HuffCode;

//----------------------------------------------------

//1. 打开存储100~200个英文短文的文件a.txt 并且在屏幕回显
void OpenAtxt()
{
/*way1:  自己通过键盘写入文件然后回显， 但是这种方法太慢， 需要每次运行时输入100~200
        字的文件内容， 所以换了另外一种方法， 查找资料用随机生成文件的方式进行
         对于文件的读写操作， 特别方便， 而且有利于每次检查编码是否正确， 可以使得每次的文件任宁
         都不一样， 所以比已经存在的文件或者是一边一边敲进去的文件要简便多了， 所以下面的 这种方法先
          注释掉了。。。。。。。。。。。
*/
/*
  FILE *fp, *fq;
  int i;
  //fp=fopen("a.txt", "w"); //以只写方式打开文件
  //fprintf(fp, "1. 先打开文件a.txt\n"); 

  char  str[201];
  char c;

   if((fp=fopen("a.txt", "w+"))==0)
   {
      printf("Can not open the file a.txt\n");
      exit(0);
    }

    printf("输入100~200纯英文短文存于文件a.txt中, 并以换行符结束\n");

    while((c=getchar())!='\n')
       fputc(c, fp);
       rewind(fp);   //重置文件指针于文件开头处
       while((c=fgetc(fp))!=EOF)
          str[i++]=c;   //循环读取文件a.txt中所有字符的并写入字符数组str中
       fclose(fp);

    if((fq=fopen("a.txt","r"))==0)
    {
       printf("Can not open file a.txt......\n");
       exit(0);
     }

     printf("回显a.txt文件中的内容\n");   

    for(i=0; i<strlen(str); i++)
       fputc(str[i], fp);

       rewind(fp);
       while((c=fgetc(fp))!=EOF)
       putchar(c);
      printf("\n");
   fclose(fq);
}      

*/

//way 2
    FILE *fp, *fo;
    int i;
    char c;
    srand((unsigned)time(NULL));
    fo=fopen("./compile.txt", "w");
    fprintf(fo, "1. 生成可以存储100~200个英文短文的文件a.txt\n");
    fp=fopen("./a.txt", "w");

    for(i=0; i<200;i++)
    {
       c=(char)(97+rand()%26);
       fputc(c, fp);
     }
     fclose(fp);
     fclose(fo);
}     

//--------------------------------------------------
//**2.写函数统计短文中出现的字母个数n以及每个字母出现的次数\n");
void CountWordTimes(char *fileName)
{
  int count;
  FILE  *fp=fopen(fileName, "r");
  while((count=fgetc(fp))!=EOF)
  {
    times[count%96]++;
    times[0]++;
  }
}

//-------------------------------------------------
//"**3.写函数以字母出现 的次数作为权值， 建立HUffman树（n个叶子）， 给出每个字母 的Huffman编码\n");
//3.1   权统计转换选择
void  WeightSelect(HuffmanTree HuffTree, int w, int *s)
{
   int temp=0;
   int i;
   for(i=1; i<=w; i++)
   {
      if(HuffTree[i].parent != 0)
      continue;
      if(temp==0)
      temp=i;
      else if(HuffTree[temp].weight > HuffTree[i].weight)
      temp = i;
    }

      *s=temp;
}

//-----------------------------------------------------
//3.2   HUffman 编码
void HuffmanCoding(int* w, int n)
{
  int i, s1, s2, start, m;
  m=2*n-1;
  unsigned int c,par;
  char *str;

  if(n<=1)
     return ;
  HuffTree=(HTNode *)malloc((m+1)*sizeof(HTNode));  //不用0号元素
  for(i=1; i<=n; i++, w++)
  {
    HuffTree[i].weight=*w;
    HuffTree[i].rchild=0;
    HuffTree[i].lchild=0;
    HuffTree[i].parent=0;
   }

   for(; i<=m; i++)
   {
     HuffTree[i].weight=*w;
     HuffTree[i].lchild=0;
     HuffTree[i].parent=0;
     HuffTree[i].rchild=0;
    }

     for(i=n+1; i<=m; i++)
     {
       WeightSelect(HuffTree, i-1, &s1); //选择HT[1…i-1]中Parent为0且Weight最小的一个点
       HuffTree[s1].parent=i;
       WeightSelect(HuffTree, i-1, &s2);
       HuffTree[s2].parent=i;
       HuffTree[i].lchild=s1;    //左右孩子对编码没有影响，因为如果出现全职相同时Huffman树的不唯一性
       HuffTree[i].rchild=s2;
       HuffTree[i].weight=HuffTree[s1].weight+HuffTree[s2].weight;
      }

    HuffCode=(HuffmanCode)malloc((n+1)*sizeof(char*));
    str=(char *)malloc(n*sizeof(char));
    str[n-1]='\0';   //让字符数组中的最后一个元素为换行符
    for(i=1; i<=n; i++)
    {
      start = n-1;
      for(c=i, par=HuffTree[i].parent; par!=0; c=par, par=HuffTree[par].parent)
          if(HuffTree[par].lchild == c)
             str[--start]='0';
          else
              str[--start]='1';

       HuffCode[i]=(char*)malloc((n-start)*sizeof(char));
       strcpy(HuffCode[i], &str[start]);
    }
      free(str);
}

//----------------------------------------------------
//3.3 给出每个字母 的Huffman编码\n"

void PerCode()
{
  FILE *fp;
  int i;
  fp=fopen("./compile.txt", "a+");   //以读取/追加的方式建立一个系的文件
  fprintf(fp, "Huffman 树的结构：---\n");
  for(i=1; i<52; i++)
     fprintf(fp, "%-3d: parent:%-4d weight:%-5d lchild:%-3d rchild:%-3d\n", i, HuffTree[i].parent, HuffTree[i].weight, HuffTree[i].lchild, HuffTree[i].rchild);
  fprintf(fp, "Huffman 编码入夏：-------\n");
  for(i=1; i<27; i++)
     fprintf(fp, "%c:  %4d %2s\n", 'a'+i-1, times[i], HuffCode[i]);
}

//---------------------------------------------------------------------
//**4.用每个字母编码对原短文进行编码， 码文放在文件b.txt中\n")
void  CodingAtxt()
{
   FILE *fi, *fo;
   int c;
   fi=fopen("./a.txt", "r");
   fo=fopen("./b.txt", "w");
   if(fi==NULL)
      printf("Can not find file a.txt...\n");

   while((c=fgetc(fi))!=EOF)   //输出编码后的二进制编码
   {
      fprintf(fo, "%s", HuffCode[c-96]);
   }
   fclose(fi);
   fclose(fo);
}

//----------------------------------------------------------------------------
//**5.用Huffman树对b.txt文件中的码文进行译码， 结果存入文件c.txt中， 比较a, c是否一致， 以检验编码、译码的正确性\n");
void CodingBtCtxt()
{
  FILE *fi, *fo;
  unsigned char out=0;
  char c, *buff;
  int i, count=0;
  buff=(char *)malloc(sizeof(char)*20);
  fi=fopen("./a.txt", "r");

  fo=fopen("./com.txt", "r");
  if(fi==NULL)
    printf("Can not find file a.txt....\n");
  while((c=fgetc(fi))!=EOF)    //输出二进制编码文件流文件
  {
     buff=HuffCode[c-96];
     for(i=0; buff[i]!='\0'; i++)
     {
       if(count ==8)
       {
         fprintf(fo, "%c", out);
         count=0;
         out=0;
        }
        out<<=1;
        count++;
        if(buff[i]=='1')
        out=out|1;
     }
  }
  if(count!=8)
  {
     out<<=(8-count);
     fprintf(fo, "%c", out);
   }

  fclose(fi);
  fclose(fo);
}    

//--------------------------------------------------------

void UnCodingCtxt()
{
  FILE *fi, *fo, *ffo;
  unsigned char c=0, *buff;
  int i, k, t=51;
  buff=(char *)malloc(sizeof(char)*10);
  fi=fopen("./com.txt", "rb");

  fo=fopen("./ucom.txt", "wb");
  ffo=fopen("./c.txt", "wb");

  if(fi==NULL)
     printf("Can not find file a.txt....\n");
  while(!feof(fi))      //输出二进制编码流。。
  {
    c=fgetc(fi);
    for(i=7; i>=0; i--)
    {
       k=(c>>i)&1;
       fprintf(fo, "%d", k);
       if(k==0)
          t=HuffTree[t].lchild;
       else
          t=HuffTree[t].rchild;
       if(HuffTree[t].lchild==0 && HuffTree[i].rchild==0)
       {
          fprintf(ffo, "%c", 96+t);
          t=51;
        }
      }
    }
    fclose(fi);
    fclose(fo);
}   

int main(int arg, char *argv[])
{
  printf("【---------Huffman Tree-----------】\n");  //分配有n个字符编码的头指针

  printf("**1.打开未编码的文件a.txt\n");

  //openFile;
  //-------------------------------------------------
  OpenAtxt();

  //--------------------------------------------------
  printf("**2.写函数统计短文中出现的字母个数n以及每个字母出现的次数\n");
  CountWordTimes("a.txt");

   //-------------------------------------------------
   printf("**3.写函数以字母出现 的次数作为权值， 建立HUffman树（n个叶子）， 给出每个字母 的Huffman编码\n");
   //creatHuffmanTree
    HuffmanCoding(&times[1], 26);
    PerCode();

   //------------------------------------------------
   printf("**4.用每个字母编码对原短文进行编码， 码文放在文件b.txt中\n");
   //HuffmanCoding

   CodingAtxt();

   CodingBtCtxt();     

  //------------------------------------------------
  printf("**5.用Huffman树对b.txt文件中的码文进行译码， 结果存入文件c.txt中， 比较a, c是否一致， 以检验编码、译码的正确性\n");
  //HuffmanDecoding

    UnCodingCtxt();      

     system("pause");
  return 0;
}