课程设计解压缩数据结构报告

为了节省空间，常常需要把文本文件采用压缩编码的方式，对于很大的文件来说，节省文件的空间就根相当于节省成本，只需要在时花费一点额外的运行时间，lzw(Lemple-Ziv-Welch由三人创造，故用他们的名字命名)算法来实现。的文本文件，压缩效果更好。字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,算是一种无损压缩.压缩/解压器要完成的主要功能：用户登录进行选项选择。对文件进行无损失压缩.对压缩文件进行解压，并且原文件数据不丢失.2.1.经过分析，压缩/解压器可分为四个模块。A系统主函数模块 2系统功能分析：压缩/解压器用到lzw算法，其它基本概念如下：LZW压缩算法的基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(StringTable)。在编码时，数据流是输入对象（文本文件的据序列，编码流就是输出对象（经过压缩运算的编码数据；在时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和时都须要用借助的对象。字符(Character)：最基础的数据元素，在文本文件中就是一个字节；字符串(String)：由几个连续的字符组成；前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根(Root)：一个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值.以下是分别对上面几个模块进行分析：菜单选择：主要是对不同选择进行响应执行。主要用到dowhile,switch,case等关键字。压缩模块：先说明一下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]变前缀。第符，原理都是前面一样，直到读最后一个字符。ABABABABBBABABAA DACDADCABAAABA待解压的数据流为AB68B109AACD1416DC8（A，B6＝（A，BB变成前缀；（B67（BA76B放入输出流。7了，73位的最大数值，（6，8就是A8＝（6，A6代表的字符串AB8；（8B9（8BB。（B，10B 2.5Lzwlzw是动态生成编译表，所以本人认为解压过程就否是是否在编是否添加当前字符到编译lzwCLEARend8位，能表示的基本单个字255标志，就要用清除标志CLEARendCLEAR一般比单个字符最大标1endCLEAR18位基本标志的清除标志CLEARend256，257258开始。40964096，就要将当前前缀和当前码输入代码流，并向代码流中加入一个清除码，初始化串表，继续有一个字符串，是由A、B、C、D符构成的，那么就可以用0123来表示，ABADCABAAAAB位，定义A最在标志：p(BASSCII256voidhashinit(void)//voidhashinsert(Elementelement)//structElement//hash{intkey;intcode;Elementhashfind(intkey,Element&element)//表的查找fclose(fp1);//文件关闭FILE： ([.c.]k { {}{}

} lzw2551个字符作为当前字符，把这个当前字符和前缀同时输出，N3N42重新执行。2重新执行。6N2 { { CharStream;//输出[code]所对 [codecode]所对应的字符 }{}

}VC++VC++后读文件就有问题了，读文件时会提示文件读写错误，最scanf函数输入文件名。读入一个新的字符，就要去查找起来的数据。1

五、原始数据中，只包括4个字符(Character),A,B,C,D,符可以用一个2bit的数表示，4AB,5CC，上面的字符串可以替代表示为:45A4CDDAA5DB,这样是不是就比LZW码能有效利用字符出现频率冗余度进