数据结构实习报告

《数据结构实习报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实习报告姓名：吴加剑班级：114102学号：20101000094学院：信息工程学院第一题：软件压缩/解压缩软件Szip（Huffman算法及应用）一．需求规格说明：问题：利用哈夫曼编码进行对已经存在的文件进行重新编码，也就是压缩，然后再对该文件进行解码，即解压。二．总体分析与设计（1）设计思想：存储结构主要是采取动态分配内存的方法用数组进行存储，在进行压缩的时候写进文件的表头是自己定义的结构体，我把码长在0-8之间，8-16之间，16-32之间的分别定义了结构体，这三种结构体都具备data（即ASCII码值），码

2、长，不同的是记录哈夫曼编码的指针类型，根据码长的不同指针类型分别为BYTE类型，WORD类型，unsignedint类型。主要的算法思想是Huffman算法思想和移位，拼接（2）设计表示：我设计的是先读出需要压缩的文件，然后利用哈弗曼将其重新编码从而达到压缩的目的，解压缩则刚好相反。（3）详细设计表示：主要算法框架是：先读一遍文件，统计出每个ASCII码值的频率，并将不为0的频率当作参数来建立Huffman树，然后获得他们的Huffman编码，码长和ASCII值，把码长在0-8之间的写在一起，8-16之间的写在一起，16-

3、32之间的写在一起，然后写进文件，这就是表头。然后再读一遍原文件，一个字节一个字节的读，然后将他们拼成32位写进一个新的文件，这就是压缩后的文件。解码的时候先从压缩的文件中将表头读出来，然后再依次读32位，根据表头信息来进行解码。三．编码首先比较困难的是Huffman传参数的下标，我是从0开始的，而书上的函数代码参数下标是从1开始的，这个问题比较好解决，只要将建Huffman树的函数中有一个地方的数组下标减1就可以了。第二个问题是有很多ASCII码的频率为0，此时需要将它们从数组中删除，下面的一个问题比较难解决，因为想让表

4、头尽可能的小，所以我想分情况，码长在0-8之间的指针用BYTE类型，码长在8-16之间的指针用WORD类型，码长在16-32之间的码长用unsignedint类型，但是一开始写成了通用的结构体，结果码长的指针用的是void型，结果读出来的时候长度不是因指针的长度不同而改变，所以我就改成了用三个不同的结构体，并且分别记录下每个结构体的个数。接下来在压缩拼位时一开始用错了，用成了有符号的，结果发现错了，而且还有一个错误是在右移32位是和我预先设想的不同，所以我将其单独列为了一种情况。接下来就是解码的过程，对我来说，一开始写解码

5、的代码不是很费时间，但是有很多情况没有想全面，结果调程序花了好几天的时间，而且一开始压的时候比原文件都大，始终想不通是为什么，最后才发现是循环的控制条件写错了，我把两个个数弄混了，现在我的程序还有一点点的问题，就是中间解码的时候会有一点乱码，解码时还有一个问题就是最后读最后一次的时候会有不足32位的情况，这时要将多余的位数记下来，否则解码的时候会有多余的字符。四．程序及算法分析使用说明：首先选择数字0或1或2，0代表结束，1代表压缩，2代表解压缩，然后键入文件的地址，再按回车键就行了。程序运行结果：压缩后的文件在一个文本文

6、档中，而还原后的文件在另一个文件中。改进思想：可以用重构Huffman树来解码，这样出错的几率就小了，还有，有的地方控制循环的条件可以缩小一点。经验与体会：通过做题目一使我对Huffman编码的思想有了具体而深刻的体会，对文件的读写函数更加了解了，也亲自操作了移位与拼接。对指针的运用更加灵活了。时间复杂度：因为我为了拼接和解码的时候方便些，所以在一开始做了些准备工作，所以循环用的比较多，有的时候是外面一个循环，里面还有一个循环，所以时间复杂度有点高，大部分函数到了n的平方级别。五．附录//哈夫曼编码压缩解压缩程序.cpp#

7、include#include#include#includestructhead{unsignedcharb;//记录字符在数组中的位置longcount;//字符出现频率（权值）longparent,lch,rch;//定义哈夫曼树指针变量charbits[256];//定义存储哈夫曼编码的数组}header[512],tmp;/*压缩*/voidcompress(){charfilename[255],outputfile[255],buf[

8、512];unsignedcharc;longi,j,m,n,f;longmin1,pt1,flength,length1,length2;doublediv;FILE*ifp,*ofp;cout<<"请您输入需要压缩的文件：";gets(filename);ifp=fopen(filename,"rb