2024年4月20日发(作者：今晚斯诺克比赛直播)
合肥学院
计算机科学与技术系
一、问题分析和任务定义
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]
在文件中出现次数
父结点
左孩子结点
右孩子结点
字符编码
原文件 压缩文件
Compress
内容相同
Uncompress
解压后
图1 程序的实现过程
表1 程序中所包括的函数及其功能
函数名
compress( )
huffman()
所实现的功能
实现 文件压缩 （被主函数调用）
对文件中出现的字符进行编码（被以上两函数调用）
uncompress( ) 实现 文件解压缩 （被主函数调用）
Main()
compress uncompress
huffam
图2 程序模块间的调用关系
发布者：admin，转转请注明出处：http://www.yc00.com/xitong/1713627051a2286686.html
评论列表（0条）