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放入输出流

最后得到原始数据

2.5 w压缩过程的算法流程图

2.5 解压模块

Lzw解压原理：

通过上面压缩原理，大概可以知道了解到压缩过程就是不找子串，旧的子串不作处理，新的子旧就为其添加新的标记，交输出前缀到输出流。

解压其实就是压缩的逆过程，因为lzw是动态生成编译表，所以本人认为解压过程就相对难解理一些，下面说明一下解压过程：

否 是 否 大 于 是 基本标志

是否在 是 后缀变前缀 编译表

否

前缀+后缀（当前字符）

输出 后缀变前缀 读入字符（直到文件结束） 开始 赋给后缀 遍历编译表 添加当前字符到编译

三、祥细设计

3.1 lzw压缩的实现：

压缩的基本原理在概要分析已经讲述过，在这里主要是把每个步聚祥细的说一编，并且把此模块的主要功能实现过程与核心代码解释一遍。

以下是具体过程：

在讲之前，还要说明几个名词以及它们的作用，为了区别编译表中串值与单个字符，要用到清除标志CLEAR和结束标志end ,比如说，基本标志有8位，能表示的基本单个字符范围就是256（0-255），如果超过256，就要有新的标志，为了区别原来的标志与新的标志，就要用清除标志CLEAR和结束标志end，清除标志CLEAR一般比单个字符最大标志大1，而结束标志end又比清除标志CLEAR大1，所以8位基本标志的清除标志CLEAR和结束标志end 分别为256，257。如果有新的标志就从258开始。

LZW压缩码长度最长是12bits。超过这个长度将要重新开始编码解码。

事实上压缩一个文件时，常常要对串表进行多次初始化，往往一文件中出现的第一次出现的基 本字符串个数会超过4096个，在压缩过程中只要字符串的长度超过了4096，就要将当前前缀和当前码 输入代码流，并向代码流中加入一个清除码，初始化串表，继续按上述方法进行压缩。

例 如：

有一个字符串，是由A、B、C、D四个字符构成的，那么就可以用0 1 2 3 来表示，两位就够了。

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

首先要扩充一位，变成3位，定义 Clear＝4，End＝5。那么以后的标号就从6开始。 缩过程中要用的主要字段与函数：

A 最在标志：p (p<=65535)

B ASSCII代码的数量 256 表的基本标志 C void hashinit(void)//表初始化

D void hashinsert(Element element)//表的插入 E struct Element//hash表中的元素

{ int key; int code; Element *next; }*table[MAX];//表

F hashfind(int key,Element &element)//表的查找 fclose(fp1);// 文件关闭 fclose(fp2);

同时还在用到文件的输入输出： FILE *fp1,*fp2;

用到的文件读写函数： fwrite(file1,20,1,fp2);

ch=fgetc(fp1);

下面是压缩过程的具体过程： ：

Initialize String Table;

[.c.] = Empty;

[.c.]k = First Character in CharStream; while ([.c.]k != EOF ) {

if ( [.c.]k is in the StringTable) {

[.c.] = [.c.]k; } else

{

add [.c.]k to the StringTable;

Output the Index of [.c.] in the StringTable to the

CodeStream; [.c.] = k; }

[.c.]k = Next Character in CharStream;

}

Output the Index of [.c.] in the StringTable to the CodeStream;

3.2 lzw解压过程：

在解压前先说明一下，读出一个字符时，如果小于基本标志（前面压缩的定义为0-255），就直接输出》

如果大基本标志（258，有清除与结束标志），并在编译表中存在代码值时，就到编译表找到中它对应的字符，并输出。

如果没找到，就把前缀的第1个字符作为当前字符，把这个当前字符和前缀同时输出，并且把他们存储在编译表中》

以下是具体的解压步骤：

1、 读取第一个字符，输出它，并且把它赋给前缀。

2、 读取下一个字符，如果没有结束，把它赋给当前字符，同时判断是否大于基本标志N。

3、 如果大于N，有两种情况：在编译表中或不在。

4、 没在编译表中，把前缀与后缀组成的当前字符的第一个字符输出 ，并把当前字符存储到编译表中，同时把当前字符赋给前缀，回到2重新执行。

5、 在编译表中，遍历编译表的所有标记所对应的字符，并且输出它，把当前字符赋给前缀，并回到2重新执行。

6、 如果小于N，输出当前字符，并且把当前字符赋给前缀，回到2重新执行。 7、 直到最后一个字符，输出标记同时结束。

下面是压缩过程的该心过程：

Initialize String Table;

[code] = First Code in the CodeStream;

Output the String for [code] to the CharStream; [old] = [code];

[code] = Next Code in the CodeStream; while ([code] != EOF )

{

if ( [code] is in the StringTable)

{

Output the String for [code] to the CharStream; // 输出[code]所对

应的字符串 [...] = translation for [old]; //[old]所对应的字符串

k = first character of translation for [code]; // [code]所对应的字符

串的第一个字符

add [...]k to the StringTable; [old] = [code];

}

else {

[...] = translation for [old]; k = first character of [...];

Output [...]k to CharStream; add [...]k to the StringTable; [old] = [code]; }

[code] }

= Next Code in the CodeStream;

四、测试与分析

4.1

1. 在压缩时没有错误，但解压时总会有一个字符没有解压正确，也不知原因，最后改用VC++就没事了，但改成用VC++后读文件就有问题了，读文件时会提示文件读写错误，最后没有用到scanf函数输入文件名。

2. 在解压时怎么样才能知道当前的字符串是已经遇见过的？如果是遇见过的，它的标号是多少呢？显而易见，必须把已经遇见过并且标了好的字符串以某种方式储存起来，每次读入一个新的字符，就要去查找储存起来的数据。

五、测试结果：

1、 主界面：

2、解压界面：

压缩界面：

六、用户使用手册

1、程序的运行环境是XP SP3系统，内存2GB。

2、编译环境是VC++6.0,通过创建工程后编译、连接即可运行

3、程序运行中的操作是通过提示菜单的方式运行，输入相应的操作数即可进行相应目录进行操作

4、登录后可以按相关提示进行文件的压缩与解压。

七、总结与体会

1. 通过这次的课程设计，我对程序的模块化设计有更深一层的识认，

原始数据中，只包括4个字符(Character),A,B,C,D,四个字符可以用一个2bit的数表示，0-A,1-B,2-C,3-D,从最直观的角度看，原始字符串存在重复字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以替代表示为:45A4CDDAA5DB,这样是不是就比原数据短了一些呢！

它采用了一种先进的串表压缩不，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢弃。

LZW码能有效利用字符出现频率冗余度进行压缩，且字典是自适应生成的，但通常不能有效地利用位置冗余度。除了用于图像数据处理以外，LZW压缩技术还被用于文本程序等数据压缩领域。对于数据流中连续重复出现的字节和字串，LZW压缩技术具有很高的压缩比。对于任意宽度和像素位长度的图像，都具有稳定的压缩过程。压缩和解压缩速度较快。

八、参考文献

《数据结构(C语言版)》电子工业出版社 肖宏启 清华大学，数据结构（C语言版） 黄国瑜、叶乃菁编著

本文来源：https://www.bwwdw.com/article/l1to.html