《数据结构实习报告.doc

数据结构实习报告 姓名：吴加剑 班级：114102 学号：20101000094 学院：信息工程学院 第一题：软件压缩/解压缩软件 Szip（Huffman算法及应用） 问题：利用哈夫曼编码进行对文件进行重新编码 二．总体分析与设计 设计思想： 存储结构主要是采取动态分配内存的方法用数组进行存储，在进行压缩的时候写进文件的表头是自己定义的结构体，我把码长在0-8之间，8-16之间，16-32之间的分别定义了结构体，这三种结构体都具备data（即ASCII码值），码长，不同的是记录哈夫曼编码的指针类型，根据码长的不同指针类型分别为BYTE类型，WORD类型， unsigned int类型。主要的算法思想是Huffman算法思想和移位，拼接 设计表示：我设计的是先读出需要压缩的文件，然后利用哈弗曼将其重新编码从而达到压缩的目的，解压缩则刚好相反。 详细设计表示： 主要算法框架是：先读一遍文件，统计出每个ASCII码值的频率，并将不为0的频率当作参数来建立Huffman树，然后获得他们的Huffman编码，码长和ASCII值，把码长在0-8之间的写在一起，8-16之间的写在一起，16-32之间的写在一起，然后写进文件，这就是表头。然后再读一遍原文件，一个字节一个字节的读，然后将他们拼成32位写进一个新的文件，这就是压缩后的文件。解码的时候先从压缩的文件中将表头读出来，然后再依次读32位，根据表头信息来进行解码。 三． 编码 首先比较困难的是Huffman传参数的下标，我是从0开始的，而书上的函数代码参数下标是从1开始的，这个问题比较好解决，只要将建Huffman树的函数中有一个地方的数组下标减1就可以了。第二个问题是有很多ASCII码的频率为0，此时需要将它们从数组中删除，下面的一个问题比较难解决，因为想让表头尽可能的小，所以我想分情况，码长在0-8之间的指针用BYTE类型，码长在8-16之间的指针用WORD类型，码长在16-32之间的码长用unsigned int类型，但是一开始写成了通用的结构体，结果码长的指针用的是void型，结果读出来的时候长度不是因指针的长度不同而改变，所以我就改成了用三个不同的结构体，并且分别记录下每个结构体的个数。接下来在压缩拼位时一开始用错了，用成了有符号的，结果发现错了，而且还有一个错误是在右移32位是和我预先设想的不同，所以我将其单独列为了一种情况。接下来就是解码的过程，对我来说，一开始写解码的代码不是很费时间，但是有很多情况没有想全面，结果调程序花了好几天的时间，而且一开始压的时候比原文件都大，始终想不通是为什么，最后才发现是循环的控制条件写错了，我把两个个数弄混了，现在我的程序还有一点点的问题，就是中间解码的时候会有一点乱码，解码时还有一个问题就是最后读最后一次的时候会有不足32位的情况，这时要将多余的位数记下来，否则解码的时候会有多余的字符。 程序及算法分析 使用说明：首先选择数字0或1或2，0代表结束，1代表压缩，2代表解压缩，然后键入文件的地址，再按回车键就行了。 程序运行结果：压缩后的文件在一个文本文档中，而还原后的文件在另一个文件中。 改进思想：可以用重构Huffman树来解码，这样出错的几率就小了， 还有，有的地方控制循环的条件可以缩小一点。 经验与体会：通过做题目一使我对Huffman编码的思想有了具体而深刻的体会，对文件的读写函数更加了解了，也亲自操作了移位与拼接。对指针的运用更加灵活了。 时间复杂度：因为我为了拼接和解码的时候方便些，所以在一开始做了些准备工作，所以循环用的比较多，有的时候是外面一个循环，里面还有一个循环，所以时间复杂度有点高，大部分函数到了n的平方级别。 附录 //哈夫曼编码压缩解压缩程序.cpp #include stdio.h #include string.h #include stdlib.h #include conio.h struct head { unsigned char b; //记录字符在数组中的位置 long count; //字符出现频率（权值） long parent,lch,rch; //定义哈夫曼树指针变量 char bits[256]; //定义存储哈夫曼编码的数组 } header[512],tmp; /*压缩*/ void compress() { char filename[255],outputfile[255],buf[512]; unsigned char c; long i,j,m,n,f; lo