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

用赫夫曼编码完成文件压缩.pptx实验报告
题目：用赫夫曼编码实现文件压缩
班级：理科实验四班 姓名：王渭森 学号：2015201992 完成日期：
一、需求分析
：
1）通信线路中实现信息的最大传送，利用变长编码的方式，可以有效充 分利用带宽，实现信息传送前的压缩。
2).在文件保存时，利用哈夫曼编码的方式，压缩文件,可以实现硬盘存 储最大的信息量。
程序执行的命令包括：
读取文件。
新建并写入文件。
将文件中的字符转换为哈夫曼编码。
将哈夫曼编码八位一组专户为十进制，在通过十进制的 ASCII 码转换 为字符。
翻译过程现将字符转为 01 串，再将 01 串翻译为原来的文件。
测试数据
1）
1
2）
3）
4）
5）
新建一个文件并压缩。 二、概要设计
串的抽象数据类型定义为： 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 存在。
操作结果：由串 S2 复制得串 S1. strlen(SString S)
初始条件：串S 存在。
操作结果：返回S 的元素个数，称为串的长度。
}//ADT String
二叉树的抽象数据类型定义为：
ADT
BinaryTree{
数据对象D：是具有相同特性的元素的集合。 数据关系R：
若D 为空集，则称为空二叉树；
若D 仅含一个数据元素，则 R 为空集，否则 R
= {H}, H 是如
下二元关系：
1）在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无 前驱；
2
3
2） 若D – {root} ≠ Φ，则存在 D – {root} 的一 个划分 Dl Dr ， Dl∩Dr =Φ；
3） 若 Dl≠Φ,则 Dl 中存在惟一的数据元素 x
<root, xl> ∈ H， 且存在 Dl
Dr ≠ Φ,则 Dr 中存在惟一的
<root, xr> ∈
H，且存在 Dr 上的关系Hr <
， 上的关系 Hl < H；若 数 据 元 素 xr ，
H；
4）（Dl，{ Hl、}）是一棵符合本定义的二叉树，称为根 root
Hr、}）是一棵符合本定义的二叉树，称
的 左子树，（Dr，{
为 根 root 的右子树。
基本操作P：
InitBitree(&T)；
操作结果：构造空二叉树。
CreateBitree(&T)；
初始条件：二叉树存在。
操作结果：按输入格式构造二叉树。
Value(T, e)；
初始条件：二叉树存在，e 是T 中某个结点。 操作结果：返回结点e 的值。
Assign(&T, &e, value)；
初始条件：二叉树存在，e 是T 中某个结点。 操作结果：结点e 赋值为 value 。
Parent(T, e)；
初始条件：二叉树存在，e 是T 中某个结点。
操作结果：若e 是T 的非根结点，则返回它的双亲，否则返回“空”。
LeftChild(T, e)；
初始条件：二叉树存在，e 是T 中某个结点。
操作结果：返回 e 的左孩子。若 e 无左孩子，则返回“空”。
RightChild(T, e)；
初始条件：二叉树存在，e 是T 中某个结点。
操作结果：返回e 的右孩子。若 e 无右孩子，则返回“空”。
}ADT BinaryTree
赫夫曼树和赫夫曼编码的存储表示： typedef struct{
char data; int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树
typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码。
函数的调用关系图：
main()->CompressFile()->HuffmanCoding()->Select()
->WriteFile()->CoToCh()
->DeCompressFile()->ChToCo(CName);
->translation()
三、调试分析
文件中字符数目可能非常大，不能用一个整的数组来存，所以需要从文件 中一个字符一个字符来读取处理。
为解决文件中字符出现的不确定性，用数组 character[256]来记录相应 ASCII 的字符出现次数，统计完后，将出现次数非零的字符存在数组 v[]中， 并将它们的权值存在数组 w[]中。
在将赫夫曼编码翻译为字符中，translation（）中函数的变量 ch，在运 算中应该变它的对