《哈夫曼树的压缩VC++程序及其效果》由会员分享，可在线阅读，更多相关《哈夫曼树的压缩VC++程序及其效果（28页珍藏版）》请在金锄头文库上搜索。
1、使用 huffman 编码压缩文件-课设成果问题描述：哈夫曼是一种常用的压缩方法。是 1952 年为文本文件建立的，其基本原理是频繁使用的数据用较短的代码代替，很少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。如: 有一个原始数据序列，ABACCDAA 则编码为 A(0)，B(10)，C(110),(D111)，压缩后为 010011011011100。产生霍夫曼编码需要对原始数据扫描两遍，第一遍扫描要精确地统计出原始数据中的每个值出现的频率，第二遍是建立霍夫曼树并进行编码，由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但
2、简单有效，因而得到广泛的应用。 哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列 哈夫曼压缩，首先用 ASCII 值初始化 511 个哈夫曼节点，然后，计算在输入缓冲区数据中，每个 ASCII 码出现的频率。然后，根据频率进行排序，现在，构造哈夫曼树，获取每个 ASCII 码对应的位序列，构造哈夫曼树，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频
3、率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。压缩的最后一步是将每个 ASCII 编码写入输出缓冲区中 哈夫曼解压缩，将输入缓冲区中的每个编码用对应的 ASCII 码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个 ASCII 值的编码的位流。因此，为了用 ASCII 值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的 ASCII 值添加到输出缓冲区中： 复制内容到剪贴板 代码:/*/*/*程序: compress.c */*功能:压缩与解压缩单个文件 */*详情:利用 hufffman 算法生成输
4、入文件的 huffman 编码，并转换成二进制字节*/* 流输出从而达到压缩的效果；解压缩则是从压缩文件中读入 huffman 树 */* 信息，从而还原为原编码，达到解压缩的目的。 */* 压缩文件结构 */* 偏移量 存储信息类型 */* 03 文件头标志 */* 4 源文件名长度 :n_s */* 54+n_s 文件名 */* 5+n_s8+n_s 源文件长度 */* 9+n_s1028+n_s huffman 树非叶子节点孩子信息 */* 1029+n_sFILE_END 源文件的 huffman 二级制编码信息 */*环境: AM2_4000+ & Windows_Server_20
5、08 & VC+_2008 */*其他: davelv 2008-12-18 */*/*/ 头文件、自定义类型、预定义宏常量 /#define _CRT_SECURE_NO_DEPRECATE/VC2005 或更新的编译器不显示 I/O 安全警告#include #include #include typedef unsigned int UINT;typedef unsigned char UCHAR;typedef unsigned short USHORT;typedef struct nodelong w;/权short p,l,r;/父亲，左孩子，右孩子htnode,*htnp;/霍
6、夫曼树的结点typedef struct huffman_codeUCHAR len;/长度UCHAR *codestr;/字符串hufcode;/字符版本的霍夫曼编码#define OK 1#define ERROR -1#define UNUSE -1#define ARGS_ERR -2/参数错误#define FILE_ERR -3/文件错误#define HEAD_ERR -4/头标错误#define MALLOC_ERR -5/内存分配错误#define HUFTREE_ERR -6/霍夫曼树错误#define HUFCODE_ERR -7/霍夫曼编码错误#define CHAR_
7、BITS 8/一个字符中的位数#define INT_BITS 32/一个整型中的位数#define CODE_SIZE 256/霍夫曼编码个数#define CACHE_SIZE 256/I/O 缓存大小#define UINT_SIZE sizeof(UINT)#define UCHAR_SIZE sizeof(UCHAR)#define USHORT_SIZE sizeof(USHORT)#define ZIP_HEAD 0xFFFFFFFF/压缩文件头标/ 函数声明 /压缩相关函数UCHAR chars_to_bits(const UCHAR charsCHAR_BITS);/将一个字
8、符数组转换成二进制数字 write_compress_file()int search_set(htnp ht,int n);/查找当前最小权值的霍夫曼树节点并置为占用create_huffmantree()int create_huffmantree(long w,int n,htnode ht);/生成霍夫曼树compress()int encode_huffmantree(htnp htp,int n,hufcode hc);/生成霍夫曼编码compress()long calc_data_frequency(FILE *in,long frequency);/计算每个不同字节的频率以及
9、所有的字节数compress()int compress(char *source_filename,char *obj_filename);/处理压缩文件的流程process_args()int c_initial_files(char *source_filename,FILE *inp,char *obj_filename,FILE *outp);/为处理压缩流程初始化文件compress()int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc,char* source_filename,long source_fil
10、esize);/写压缩文件compress()/解压缩相关函数void get_mini_huffmantree(FILE* in,short mini_ht2);/从待解压缩文件中得到一个小型的 huffman 树decompress()int decompress(char *source_filename,char *obj_filename);/处理解压缩文件的流程process_args()int d_initial_files(char *source_filename,FILE *inp,char *obj_filename,FILE *outp);/为处理解压缩流程初始化文件d
11、ecompress()int write_decompress_file(FILE *in,FILE* out,short mini_ht2,long bits_pos,long obj_filesize);/写解压缩文件decompress()/辅助函数void print_help();/在屏幕上显示帮助process_args(),main()void process_error(int error_code);/处理函数中返回的错误代码process_args(),main()void process_args(char *first,char*second,char*third);/处理命令行参数main()char *create_default_obj_filename(char *source_filename,char* obj_filename);/生成一个默认的文件名c_initial_files()/
