数据结构课程设计报告-------LZW压缩与解压学院:计算机学院专业:计算机科学与技术班级:2013级1班姓名:傅娴雅学号:201300130014目录一、问题描述二、设计三、测试结果四、分析与探究五、总结六、附录一、问题描述(1)系统功能1.在一个文本文件上实现LZW压缩和解压缩,其中每个字符就是该文本的8位ASCII码2.在实现LZW过程中需要仔细考虑在编译表中找到匹配或找不到匹配,需要注意匹配算法的时间、空间开销3.*应用LZW算法实现256色灰度BMP图像文件的压缩和解压缩(2)输入要求用MFC做出了图形化界面,不再需要命令行输入,故输入只需在编辑框输入正确的地址或者直接选择。(3)输出要求消息框提示操作成功,能生成压缩或者解压缩之后的文件。(4)界面设计用MFC生成相应界面,能对压缩或者解压缩操作进行选择,减少界面的冗余度。(5)测试设计找一篇3000字的文章放于txt文件中,测试程序能否压缩成功及压缩的速率。同时利用压缩的文件进行解压缩。照一张256色灰度BMP图像,进行相应的压缩与解压缩过程二、设计(1)系统设计LZW压缩算法是一种新颖的压缩方法,由Lemple-Ziv-Welch三人共同创造,用他们的名字命名。它采用了一种先进的串表压缩,将每个第一次出现的串放在一个串表中,用一个数字来表示串,压缩文件只存贮数字,则不存贮串,从而使图象文件的压缩效率得到较大的提高。奇妙的是,不管是在压缩还是在解压缩的过程中都能正确的建立这个串表,压缩或解压缩完成后,这个串表又被丢弃。词典编码主要利用数据本身包含许多重复的字符串的特性,用一些简单的代号代替那些重复出现的字符串,从而实现压缩,实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。实用的词典编码算法的核心就是如何动态地形成词典,以及如何选择输出格式以减小冗余。在本次实验中所用到的LZW(Lempel-ZivWalch)压缩编码方法。LZW的核心思想是用短的编码代替字符串。它不对输入的字符串做任何分析,只是将收到的每一个新字符串添加到一张字符串表中。当已经出现的字符串再次出现,即用一个短的编码代替该字符串,这就实现了压缩。(2)数据结构预算法设计此次实验中采用链表散列的存储方式,牺牲空间以换取时间。采用二进制形式输入,除数设为4096,对前256位初始化,空间用完时丢弃,在后面进行解压过程中重建。A.压缩算法:•1.从输入流中读入一个字符,作为当前串的后缀。•2.如果当前串在字典中,就用当前串的编码作前缀,转到第1步。•3.如果当前串不在字典中,就把当前串放到字典中,并把前缀放到输出流,后缀变前缀,转到第1步。•4.当输入流读完了后,串中应该还剩一个前缀,把它放到输出流,结束。解压缩算法与压缩算法类似三、测试结果(1)测试过程(2)测试问题能够实现文本的压缩与解压缩,且压缩过程速度较快,bmp图像的压缩过程也能实现,但是解压缩过程并不能实现。四.分析与探究(1)测试结果分析借助MFC使得程序可视化程度较高,程序运行速度较快,然而最终没能完成所要求的图形的压缩与解压缩过程,程序面向的对象相对来说较为狭窄。(2)思考在网上有查到可以利用树结构来存储,可能会进一步减小程序的时间复杂度。然而没有能够很明白这种结构,最终还是采用了课本上提供的算法思想五.总结在课本上找得到这个问题的解决方法,然而按照课本上的程序,在进行压缩和解压缩的步骤分开,使得整个方法变得特别的冗余,利用MFC进行第一次修改之后在一定程度上有所改善,在最后一次进行修改之后终于达到了想要的效果。总而言之,这是一次特别好的开发经历,其中各种波折让我对于数据结构的选择,等等一些列问题有了新的认知。五.附录以下是MFC中自己建的类1.对字符进行操作#includestdafx.h#includestdio.h#includememory.h#includeassert.h#includelzwtable.h#includelzwcode.h/*CDecodeBitArray*/CDecodeBitArray::CDecodeBitArray(DWORDdwInitWidth)//widthinbit{m_pbBits=NULL;m_dwWidthInByte=0;m_dwTail=m_dwHead=0;if(dwInitWidth)InitBits(dwInitWidth);}CDecodeBitArray::~CDecodeBitArray(){ClearBits();}voidCDecodeBitArray::ClearBits(void){if(m_pbBits)deletem_pbBits;m_dwTail=m_dwHead=0;m_dwWidthInByte=0;}voidCDecodeBitArray::InitBits(DWORDdwInitWidth){//newClearBits();DWORDdwLength=dwInitWidth/8;dwLength+=(dwInitWidth%8)?1:0;m_pbBits=newBYTE[dwLength];m_dwHead=m_dwTail=0;m_dwWidthInByte=dwLength;}voidCDecodeBitArray::InitBytes(DWORDdwInitWidth){//newInitBits(dwInitWidth*8);}DWORDCDecodeBitArray::GetLeftBytes(void){DWORDdwLeftBytes;DWORDdwLeftBits=GetLeftBits();dwLeftBytes=dwLeftBits/8;dwLeftBytes+=(dwLeftBits%8)?1:0;returndwLeftBytes;}WORDCDecodeBitArray::RemoveBits(intiWidth){WORDwGet=0;for(inti=iWidth-1;i=0;i--){if(RemoveFirstBit())SET_BIT_1(wGet,i);}returnwGet;}WORDCDecodeBitArray::RemoveFirstBit(void){BYTE*pbFirstByte=m_pbBits+m_dwHead/8;BYTEbFirstByte=*pbFirstByte;WORDwGet=(CHECK_BIT_1(bFirstByte,7-m_dwHead%8))?1:0;m_dwHead++;returnwGet;}BOOLCDecodeBitArray::AddBytes(BYTE*pbAdd,intiLength){if(m_pbBits==NULL)returnFALSE;Resort();memcpy(m_pbBits+m_dwTail/8,pbAdd,iLength);m_dwTail+=8*(DWORD)iLength;returnTRUE;}voidCDecodeBitArray::Resort(void){//becausem_dwTail%8alwaysequal0if(m_dwHead8)return;if(m_dwTail==m_dwHead){m_dwTail=m_dwHead=0;return;}DWORDdwLength=GetLeftBytes();DWORDdwHead=m_dwHead%8;DWORDdwMove=m_dwHead-dwHead;memcpy(m_pbBits,m_pbBits+(m_dwHead/8),(int)dwLength);m_dwHead=dwHead;m_dwTail-=dwMove;}/*classCEncodeBitArray*/CEncodeBitArray::CEncodeBitArray(DWORDdwInitWidth){if(dwInitWidth==0)m_pbBits=NULL;elseInitBits(dwInitWidth);}CEncodeBitArray::~CEncodeBitArray(){ClearBits();}BOOLCEncodeBitArray::InitBits(DWORDdwInitWidth){ClearBits();assert(dwInitWidth);m_dwWidthInByte=dwInitWidth/8;m_dwWidthInByte+=(dwInitWidth%8)?1:0;m_pbBits=newBYTE[m_dwWidthInByte];m_dwTail=0;returnTRUE;}voidCEncodeBitArray::ClearBits(void){if(m_pbBits)deletem_pbBits;m_pbBits=NULL;}BOOLCEncodeBitArray::AddBits(WORDwAdd,intiWidth){if(m_pbBits==NULL)returnFALSE;for(inti=iWidth-1;i=0;i--){BYTE*pbByte=m_pbBits+m_dwTail/8;if(CHECK_BIT_1(wAdd,i))SET_BIT_1(*pbByte,7-m_dwTail%8);elseSET_BIT_0(*pbByte,7-m_dwTail%8);m_dwTail++;}returnTRUE;}DWORDCEncodeBitArray::GetBytesWidth(void){DWORDdwBytes=m_dwTail/8;dwBytes+=(m_dwTail%8)?1:0;returndwBytes;}intCEncodeBitArray::RemoveBytes(BYTE*pbGet,intiWant){if(m_pbBits==NULL)return-1;intiTotal=(int)GetBytesWidth();if(iWantiTotal)iWant=iTotal;if(pbGet!=NULL)memcpy(pbGet,m_pbBits,iWant);memcpy(m_pbBits,m_pbBits+iWant,iTotal-iWant);intiTail=(int)m_dwTail;iTail-=iWant*8;if(iTail0)iTail=0;m_dwTail=iTail;returniWant;}BOOLCLZWDecode::BeginLZWDecode(constDWORDdwLength,//thecompressedlengthFUN_LZWDECODEGETNEXTBYTESpfunLZWGetNextBytes,FUN_LZWDECODEPUTNEXTBYTEpfunLZWPutNextByte,WORDwBuffer,FUN_LZWDECODEDBYTESpfunLZWDecodedBytes,DWORDdwBytesOnce){m_dwDecodedByte=0;//printf(enterdecodepressakey\n);BYTE*pbNewData=newBYTE[4000],*pbOutData=newBYTE[4000];BYTE*pbBuffer=newBYTE[wBuffer];BYTEbFirst;m_LZWTable.InitLZWTable();intiBitWidth=9;m_iTotalEntry=LZW_BEGIN_ENTRY;BYTE*pbDecodedData;WORDwOld,wLastLen;m_baContain.InitBits((wBuffer+20)*8);intiR=0;DWORDdwRead=0;while(1){if(m_baContain.GetLeftBytes()5){WORDwGetBytes=wBuffer;if((DWORD)wGetBytes+dwReaddwLength)