合肥学院
计算机科学与技术系
一、问题分析和任务定义
1、题目
采用哈夫曼编码思想实现英文文本的压缩与解压缩，并提供压缩前后的占用空间比。
要求 1）压缩原文件规模不小于5K
        2) 提供解压缩文件后文件与原文件的相同性比较功能
2、问题分析
压缩过程     
1、以读的形式打开需要压缩的一个英文本文件，把其中出现的所有字符按其在文本中出现的频率利用哈夫曼树进行编码。
2、以写的形式打开一个新的文本文件，把它作为英文文本压缩后的文本文件，扫描需要压缩的英英文本文件（ ）中所有字符，把其对应的编码通过转换后存入新的文本文件( )中。
3、把需要压缩的英文文本（ ）中所出现的字符及其编码等原始文件的信息保存在新的文本文件中。
解压缩过程   
1、以读的形式打开一个压缩文件  ，按其中保存的原始文件的信息还原哈夫曼树及字符编码。
2、 以写的形式打开一个新的文本文件，作为解压后的英文文本 ，逐个扫描压缩文件 中的所有字符，把其中所有转换后的编码再转换回来并与哈夫曼树中存储的字符编码比较，把其对应的字符写入 中。
一个字符在文本文件中存储时占一个字节，而其二进制编码若直接存入文本文件其所占的空间不会少于一个字节。例如：假设字符E的编码为001，若把001直接存入文件只能用字符串
的形式，其所占用的空间为三个字节。达不到文件压缩的目的，所以必须对编码的存储空间进行转换。
3 编码转换
在文本文件中字符之间是连续的，所以在文本文件中存储编码也是连续的。可以把连续的不同字符的编码存入同一个字节，再把这一个字节的二进制码转换成一个字符，把转换后的字符存储在文本文件中。
二、数据结构的选择和概要设计：
1 此程序采用的数据结构为顺序表。哈夫曼树是二叉树的一种，二叉树的顺序存储结构中可以把结点间的关系放在其存储位置中，无需附加任何信息就能在这种结构中到每个结点的双亲结点和孩子结点，这正是哈夫曼编码所需要的。
哈夫曼树顺序表：结构体header[512],表中每个结点包括以下信息
unsigned char b
  字符名
long count
  在文件中出现次数
long parent
  父结点
Long lch
  左孩子结点
Long  rch
  右孩子结点
char bits[256]
  字符编码
           
   
压缩文件
解压后
N
原文件
Compress
Uncompress
内容相同
                        图1    程序的实现过程
表1    程序中所包括的函数及其功能 
  函数名
      所实现的功能
  compress(  )
实现 文件压缩    （被主函数调用）
  uncompress(  )
实现 文件解压缩  （被主函数调用）
  huffman()
对文件中出现的字符进行编码（被以上两函数调用）
Main()
compress
huffam
uncompress
图2    程序模块间的调用关系
2、算法流程   
（假如  原文件中只有一句话    I am here  ）
1）压缩过程 （主函数调用  compress(  )函数  ）
    扫描文档知  alcount=9      n=6

权值：count              表2    利用权值进行编码
e
I
a
m
h
r
count
2
  2
    1
1
1
1
    1
  parent
    10
 
    7
    7
  8
    8
    9
bits
    10
  11
  0000
  0001
  010
  011
  001
h
4
I
a
2
r
3
e
5
9
m
2
                    图3      进行哈夫曼树的构造 
0
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
压缩文件怎么解压
        12
      86
        227
        0
     
因为八位的二进制码转化为的整数完全可以用ASCLL码值对应的字符来代替
在原文件（）中一共占用了9个字节，而如果按上图的存储方式存入文件则只要4个字节
2)解压缩过程
        12
      86
        227
        0
把以字符的形式存储在文件（）中的编码还原
0
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
依次把还原后的存储编码与字符的编码比较，若相同则把字符写入文件（）
1
1
0
0
0
1
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
0
0
0
1
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
0
1
0
1
1
0
1
1
1
0
0
0
1
1
0
1
1
0
1
1
1
0
0
0
1
1
0
0
1
1
1
0
0
0
1
1
0
1
0
0
0
1
1
0
0
0
1
1
0
1
0
图4      哈夫曼编码的还原过程
二、详细设计和编码
1．要完成对文件的压缩和解压缩，首先要建立哈夫曼编码的算法，而要建立哈夫曼编码的算法，就要定义哈夫曼树采用的顺序表结构
以下是基本的数据结构的定义
哈夫曼树采用顺序表的结构
    struct head{          //结构体
    unsigned char b;    //存储字符
    int count;          //权值
    long parent,lch,rch;
    char bits[256];    //编码 
}header[512],tmp;
2．//文件压缩过程
a.要实现文件的压缩过程，首先要从文本中读入一个字符，若读入的是哈夫曼树中的第i个字符，则把第i个字符的编码接在之前定义过的字符串buf的未尾
Buf[0]=0；
while(q!=alcount)                   
    {
       
        fread(&c,1,1,ifp);                      // 从文本中读入一个字符
        q++;                                     
        for(i=0;i<n;i++)                        // n 为不重复计数的所有字符数
            if(c==header[i].b) break;            //如果读入的是哈夫曼树中的第i个字符
        strcat(buf , header[i].bits);            //把第i个字符的编码接在字符串buf的末尾     
        j=strlen(buf);                     
b. 当字符串buf的长度大于或等于8时,把前8位的编码转化为整数,之后再把这个整数强制转化为字符串并写入压缩文件，最后把已经写入文件的编码从buf中去掉
        while(j>=8)                          //当字符串buf的长度大于或等于8时
        {
            f=0;                           
              for(p=7;p>=0;p--)                  //把前8位的编码转化为整数（调用了
                  if(buf[p]=='1')                    shuxue函数求2的 次方）
                      f=shuxue(7-p)+f;         
              c=(unsigned char)f;                  //把这个整数变为字符串
              fwrite(&c,1,1,ofp);                  // 写入压缩文件
              pt1++;                             
              strcpy(buf,buf+8);                  //把已经写入文件的编码从buf中去掉