用赫夫曼编码完成文件压缩.pdfVIP

实验报告 题目：用赫夫曼编码实现文件压缩 班级：理科实验四班 姓名：王渭森 学号：2015201992 完成日期：2016.6.10 一、需求分析 1.现实需求： 1）通信线路中实现信息的最大传送，利用变长编码的方式，可以有效充 分利用带宽，实现信息传送前的压缩。 2).在文件保存时，利用哈夫曼编码的方式，压缩文件,可以实现硬盘存 储最大的信息量。 2.程序执行的命令包括： 1）读取文件。 2）新建并写入文件。 3）将文件中的字符转换为哈夫曼编码。 4）将哈夫曼编码八位一组专户为十进制，在通过十进制的ASCII 码转换 为字符。 5）翻译过程现将字符转为01 串，再将01 串翻译为原来的文件。 3.测试数据 1） 2） 3） 4） 5） 新建一个文件并压缩。 二、概要设计 1.串的抽象数据类型定义为： ADT String{ 数据对象：D={ai|ai ∈CharacterSet,i=1,2,...,n,n=0} 数据关系：R1={ai-1,ai|ai-1,ai∈D,i=1,2,...,n} 基本操作： strcpy(String S1,String S2) 初始条件：串S2 存在。 1 操作结果：由串S2 复制得串S1. strlen(SString S) 初始条件：串S 存在。 操作结果：返回S 的元素个数，称为串的长度。 }//ADT String 2.二叉树的抽象数据类型定义为： ADT BinaryTree{ 数据对象D：是具有相同特性的元素的集合。 数据关系R： 若D 为空集，则称为空二叉树； 若D 仅含一个数据元素，则R 为空集，否则R = {H}, H 是如 下二元关系： 1）在D 中存在唯一的称为根的数据元素root，它在关系H 下无 前驱； 2） 若D – {root} ≠ Φ，则存在D – {root} 的一 个划分Dl Dr ， Dl ∩Dr =Φ； 3） 若Dl≠Φ,则Dl 中存在惟一的数据元素 x ， root, xl ∈ H， 且存在 Dl 上的关系 Hl H ；若 Dr ≠ Φ,则Dr 中存在惟一的 数 据 元 素 xr ， root, xr ∈ H，且存在Dr 上的关系Hr H； 4）（Dl，{ Hl、}）是一棵符合本定义的二叉树，称为根root 的 左子树，（Dr，{ Hr、}）是一棵符合本定义的二叉树，称 为 根root 的右子树。 基本操作P： InitBitree(T)； 操作结果：构造空二叉树。 CreateBitree(T)； 初始条件：二叉树存在。 操作结果：按输入格式构造二叉树。 Value(T, e