C语言数据结构+代码

学院

计算机科学系

数据结构课程设计报告

设计名称： 压缩器/解压器 姓 名： 学 号：

专业班级： 08软件技术（1）班 系 （院）： 计算机科学系 设计时间： 2009~2010学年第二学期 设计地点： 六楼机房

目 录

一 需求分析----------------------------------------------------------------------------------------3 二 概要设计----------------------------------------------------------------------------------------3 三 详细设计----------------------------------------------------------------------------------------6 四 测试与分析-------------------------------------------------------------------------------------10 五 测试结果--------------------------------------------------------------------------------------- 11 六 用户使用说明--------------------------------------------------------------------------------- 13 七 课程总结 -----------------------------------------------------------------------------------13 八 考文献-------------------------------------------------------------------------------------------14

九 附录----------------------------------------------------------------------------------------------

一 、需求分析：

为了节省存储空间，常常需要把文本文件采用压缩编码的方式储存，对于很大的文件来说，节省文件的存储空间就根相当于节省成本，只需要在存储时花费一点额外的运行时间，但在现在计算机的运行速率来说，这点时间不是问题，并且不影存储效果，这次的课程设计利用了lzw(Lemple-Ziv-Welch 由三人创造，故用他们的名字命名)算法来实现。 Lzw压缩算法是一种广泛应用的压缩算法，它不仅用于文本文件压缩，还用于各种图像文件压缩，而且在压缩过程中不使原文件失真，压缩效果好，特别是对一些有大量重复子串的文本文件，压缩效果更好。字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,算是一种无损压缩.

压缩/解压器要完成的主要功能：

用户登录进行选项选择。 对文件进行无损失压缩.

对压缩文件进行解压，并且原文件数据不丢失.

二、概要分析

2.1. 系统功能设计：

经过分析，压缩/解压器可分为四个模块。

A 系统主函数模块 B 压缩模块 Yasu(). C 解压模块 Jieya().

D 菜单选择模块 Menu(). 2 系统功能分析：

2.2 压缩/解压器用到lzw算法，其它基本概念如下：

LZW压缩算法的基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(String Table)。 在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；

而编译表是在编码和解码时都须要用借助的对象。字符(Character)：最基础的数据元素，在文本文件中就是一个字节；

字符串(String)：由几个连续的字符组成； 前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根(Root)：一个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值.

以下是分别对上面几个模块进行分析：

2.3菜单选择：

主要是对不同选择进行响应执行。

主要用到 do while,switch,case等关键字。

2.4压缩模块：

先说明一下lzw的压缩原理：

通过基本概念了解了字符串，先缀，后缀等概念。

压缩原理：

初始化一个编译表，从文本文件读第一个字符记为[ch]1，不做处理，把它作为临时字符串前缀，继续读第二字符，记为[ch]2，如果在编译表有该字符，有两种情况，在编译表有该字符或没有，把该字符和前一个字符合为一个字符串[ch]1[ch]2（一个字符串可以用一个前缀加一个后缀来表示即（前缀，后缀）前缀是一个标号，可以是原始的字符，也可以是一个代表字符串的标号，后缀则是一个字符），把[ch]2作为后缀，如果编译表中有[ch]2的标记，如果该字符在编译表中有对应编码，不做处理，现在编译表中没有该串[ch]1[ch]2，那么为[ch]1[ch]2在编译表添加一个新的标志，同时输出ch[1](前缀)中编译中对应在编号到输出流中，现在ch[1]已经输出去，所以把ch[2]变为前缀。

读取第三个字符ch[3]，形成新的字符串ch[2]ch[3],如果编译表中有ch[2]ch[3],不作处理，继续添加，如果没有，则像第二步一样，在编译表中为其添加标记，同时输出前缀ch[2]，后缀ch[3]变前缀。

读取第四个字符，原理都是前面一样，直到读最后一个字符。

2.5 解压模块

原始数据

A B A B A B A B B B A B A B A A C D A C D A D C A B A A A B A B .....

待解压的数据流为: A B 6 8 B 10 9 A A C D 14 16 D C 8 ....

解压的过程是以一对一对数据来处理的。首先原始数据的位数。

第一步：取第一个和第二个数据，是（A，B），不认得，令6＝（A，B），把前缀A放入输出流中，后缀B变成前缀；

第二步，取第三个数据，现在变为（B，6）。不认得，压缩过程，定义一个新的标志，前缀可以是一个代表子串的标号，但是后缀都是一个单个的数据的，所以这里也不能让后缀是一个字串标号。把6展开，6是A B，那么这里原来的字串就是B A B，其实7＝（B，A），那么7的后缀就是6 代表的字符串的第一个字符。把B放入输出流。

第三步，取第四个数据。由于上一步已经把标号排到7了，7是3位的最大数值，

所以从这一步以后，就应该把字长加一位，所以这里取4位，就是1000，也就是8。现在得到的是（6，8）。不认得，定义7的时候，取的后缀是6的第一个字符，那么这里8的后缀也应该是8的第一个字符， 8的前缀是6，那么8的第一个字符也就是6的第一个字符。也就是 A。所以8＝（6，A），现在把6代表的字符串AB放入输出流，让前缀变为8； 第四步，取第五个数，现在是（8，B），让9＝（8，B），把8＝6A＝AB A放入输出流，前缀为B。

第五步，取第六个，（B，10），同第三步，令10＝（B，10的第一个字符）＝（B，

B），把B放入输出流

最后得到原始数据