哈夫曼编码与译码课程设计报告.doc

课程名称: 数据结构课程设计 学 院: 管理学院 专业班级: 10信息管理与信息系统(2)班 姓 名: 王高智 学 号： 3110004891 指导老师: 丁天翔 2012年06月18日 目录 哈夫曼编码与译码 2 一、 问题及功能分析 2 (一) 要求： 2 (二) 分析： 2 二、 详细设计 2 (一) 读取信息 2 (二) 统计文本信息 2 (三) 设计编码和译码方案 3 (四) 计算压缩比 3 (五) 整体流程 3 三、 程序实现 3 (一) 汇总 3 (二) 具体实现代码 3 1. com.gauze.Main 3 2. com.gauze.charstatistics.CharData 4 3. com.gauze.charstatistics.CharDataMapActor 6 4. com.gauze.charstatistics.CharReader 9 5. com.gauze.util.HaffmanNode 10 6. com.gauze.util.HaffmanTree 11 四、 调试分析 14 (一) 统计英文文本： 14 (二) 统计含有中英文文本 15 (三) 查询只含有字符串“AAAABBBCDDBBAAA”的文本（课本示例）： 16 手机信息管理 17 一、 问题及功能分析 17 (一) 功能要求： 17 (二) 性能要求： 17 (三) 分析： 17 二、 详细设计 20 (一) 持久层 20 (二) 逻辑层 21 (三) 展示层 23 三、 程序实现 27 四、 调试分析 42 (一) 通讯录管理 42 (二) 通话记录 47 (三) 信箱管理 53 五、 课设总结 59 哈夫曼编码与译码 问题及功能分析 要求： 从某文本文件中统计其中字符使用频率（由英语字母构成），建立对应的哈夫曼树，设计哈夫曼编码与译码方案，计算压缩比。 分析： 读取并统计文本信息（统计每个字符的使用次数并计算使用频率） ( 根据统计的信息设计编码方案 ( 译码 ( 计算压缩比。 详细设计 读取信息 使用java.io.BufferedReader类读取文本字符。 统计文本信息 需要统计的信息为字符的出现次数和文本的字符总数。 字符总数：每读取一个字符，字符总数加1； 字符出现次数： 特征： 每个字符对应的次数随着读取的进行可能会发生改变，属于动态变量； 不允许出现两个存储到相同的字符信息对象； 当读取到新的字符时，需要添加新的存储字符信息的对象； 每读取到一个字符，需要对所有已经读取的字符进行查找更新数据，查找频繁。 分析：因为不允许存储重复的对象，因此应该采用Set集合进行存储，由于查找更新数据比较频繁，为提高效率，应该采用Hash散列存储结构，综上可得出结论：采用HashSet结构存储数据效率最高。 设计编码和译码方案 根据统计的信息：权值（频率）进行编码和译码。 计算压缩比 计算压缩前和压缩后的文件字节总数只比。 整体流程 程序实现 汇总 类 类型 描述 com.gauze.Main class 主方法 com.gauze.charstatistics.CharData class 存储字符信息 com.gauze.charstatistics.CharDataMapActor class 操作字符信息 com.gauze.charstatistics.CharReader class 读取字符 com.gauze.util.HaffmanNode class 哈夫曼树节点类 com.gauze.util.HaffmanTree class 哈夫曼数类 具体实现代码 com.gauze.Main package com.gauze; import java.io.FileNotFoundException; import com.gauze.charstatistics.CharDataMapActor; import com.gauze.charstatistics.CharReader; public class Main { /** * @param args */ public static void main(String[] args) { try { CharReader reader = new CharReader(./中文.txt); CharDataMapActor map = ne