数据结构课程设计报告.doc.doc

数据结构课程设计 课程报告 报告题目 Huffman压缩编码 学院名称 信息科学与技术学院 专业名称 软件工程 学生姓名 毕艺翔 学生学号 201413040305 任课教师 李启飞 报告成绩 教务处 制 2015年10月18日 选题的意义与目的 基本任务与要求 基本任务：压缩后的文建立哈夫曼树后，先将哈夫曼树存储到目标文件中，然后再次扫描源文件，对每个字节进行编码并写入到目标文件中，实现文件压缩 解压缩时先从压缩源文件中读取哈夫曼树，然后扫描压缩文件，利用哈夫曼树将变长编码恢复为原来的定长编码，并写入到目标解压文件中 要求: 哈夫曼编码后的变长编码不是8bit的整数倍，请使用位运算实现变长编码的连续输出 程序要有UI界面，压缩和解压缩过程中应显示正确的处理进度 件应比源文件小，解压恢复的文件应和源文件完全一致 选题的意义 掌握线性链表的插入，删除等算法。 掌握Huffman树的概念及构造方法。 掌握二叉树结构及遍历算法。 利用Huffman树及Huffman编码，掌握实现压缩文件的一般原理。 课程设计的目标 一般来讲，课程设计比教学实验更复杂一些，涉及的深度更广些，并更加实用。目的使通过课程设计的综合训练，培养我们实际分析问题，编程和动手能力，最终目标是想通过课程设计的形式，帮助我们系统掌握该门课程的主要内容，更好地完成教学任务。而对于哈夫曼压缩这个项目，我们的目标是能熟练掌握哈夫曼树，并将其运用到压缩和解压上去。同时，我们要尽可能完善压缩界面，做出一个既实用又美观的项目。通过设计的思维能力，促进的综合应用能力的提升 算法分析 哈夫曼树及哈夫曼编码生成步骤： ① 扫描要压缩的文件，对字节出现的频率进行计算统计。 ② 把字节按出现的频率进行排序，组成一个队列。 ③ 把出现频率（权值）最低的两个字节作为叶子节点，它们的权值之和为根节点组成一棵树。 ④ 把上面叶子节点的两个字节从队列中移除，并把它们组成的根节点加入到队列。 ⑤ 把队列重新进行排序。重复步骤 ③④⑤ 直到队列中只有一个节点为止。 ⑥ 把这棵树上的根节点定义为 0 （可自行定义 0 或 1 ）左边为 0 ，右边为 1 。这样就可以得到每个叶子节点的哈夫曼编码了。 例:假设有一段文件ASCTASCTAAAAACCTTT，其中用到4个不同字符Ａ，Ｃ，Ｓ，Ｔ，它们在文件中出现的次数分别为 7 ， 2 ， 4 ， 5 。把 7 ， 2 ， 4 ， 5 当做 4 个叶子的权值用上述方法构造的哈夫曼树如图所示。 在树中令所有左分支取编码为 0 ，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码(哈夫曼编码)，如上图所示。 这些编码拼成的文件01111101001111101000000110110101010不会混淆，因为每个字符的编码均不是其他编码的前缀，这种编码称做前缀编码。 三、压缩和解压缩文件 哈夫曼编码生成以后,所谓的压缩文件不过是将文件中每一个字节读出后用其哈夫曼编码替换,满八位后写入压缩文件,不满八位的读出下一字节凑成八位,这样边读边写,直到文件末尾. 解压缩过程与压缩过程相反,从压缩文件中读一字节(八位)缓存,然后一位一位的解码,直到读到一个哈夫曼编码,用其对应的字节数据替换写入解压文件,这样边读边解码边写,直到文件末尾. 当然写压缩文件内容前,要先写入码表(原文件的编码信息:字节----频率)用于解压缩时还原哈夫曼树及哈夫曼编码。 程序设计与实现 程序结构设计 一、实验题目 哈夫曼编码实现文件压缩 二、实验目的： 1、了解文件的概念。 2、掌握线性链表的插入、删除等算法。 3、掌握Huffman 树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Huffman 树及 Huffman 编码 ，掌握实现文件压缩的一般原理。 三、实验设备与环境：微型计算机、Windows 系列操作系统、Visual C++6.0软件。 四、实验内容：根据ASCII 码文件中各ASCII 字符出现的频率情况创建Huffman 树 ，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。 五、概要设计： 本次实验采用将