山东大学软件学院
数据结构课程设计报告
设计题目:
日期: 2010 年 3 月 16 日
设计报告内容:
1. 需求描述
输入:文本文件(压缩文件)
输出:压缩文件(文本文件)(压缩率)
知识点:堆排序、霍夫曼树、二叉树遍历
备注:字符文件、汉字文件
2. 实现思想
()利用最小堆建立霍夫曼树,通过霍夫曼编码对每个字符编号,出现
频率越高的字符,其编码越短,以此实现压缩
()要将建立的霍夫曼树存放到文件中,这样在解压缩时可以从文件中
读取树,进行遍历而得到每个字符所对应的编码。
()对字符在文件中的输入是以二进制代码的形式读入,在将压缩后的
二进制码输入文本中时则将每八位看作是一个新的字符
3. 数据结构设计
()霍夫曼树的建立
利用最小堆先找到两个权值最小的两个节点合并成一棵最小二叉树,每个
外部节点代表字符串中一个不同的字符,此后不断地从集合中选择两棵具
有最小权重的二叉树,并把它们合并成一棵新的二叉树,两棵树的权重之
和则为新的合并二叉树的权重
()权重的获得
将从文件中读取的字符强制转化成 型,与已经读取的字符相比较
若有重复则在相应字符上加 ,若无则添加该字符代码并增加数组长度
但在存储是建立两个对应的 型与 型数组以便于建立霍夫曼树。
()压缩
霍夫曼写入文件头
利 用 递 归 及 逐 层 遍 历 删 除 的 形 式 , 则 向 队 列 中 压 入
, 则向队列中压入 ,直到叶节点,然后读取相应队列中的代
码存放到该编码对应的长度中
!"
将树写入文件头
#$%&'()
这 样 在 调 用 时 可 以 利 用 的 方 法 将 整 个 数 据 块 读 出 , 通 过 遍 历
*+ 树将叶节点输出
#,,!"
压缩代码再次转化成字符
*+ 具有一般二叉树的所有特性,但是,在压缩处理过程中遇到
一个情况,我们无法正确处理最后一个字符,因为通常到最后一位,编
码不会满 - 位,这就在解压时输出多余字符。
(.)解压
将单个压缩后的字符逐个取出后转化成 型的数再转变成二进制放入缓冲
- 1
- 2
- 3
- 4
- 5
前往页