当前位置：文档库 › 数据结构实验总结报告

数据结构实验总结报告

一、调试过程中遇到哪些问题？

（1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。

由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。

目前的设计是：

Tree = Identifier(Node,Node)

Node = Identifier | () | Tree

Identifier = ASCII Character

例子：a(b((),f),c(d,e))

这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。

（2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。

②文件结尾要刷新缓冲区，这里容易引发边界错误。

在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。

二、要让演示版压缩程序具有实用性，哪些地方有待改进？

（1）压缩文件的最后一字节问题。

压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。

解决方案：

①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。

②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件，

会造成较大的损耗。

③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。

（2）压缩程序的效率问题。

在编写压缩解压程序时

①编写了屏幕输入输出的版本

②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本

③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口

这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。

（3）程序界面更加人性化。

Usage: huffman [-c file] [-u file] output_file

-c Compress file. e.g. huffman -c test.txt test.huff

-u Uncompress file. e.g. huffman -u test.huff test.txt

目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。

三、调研常用的压缩算法，对这些算法进行比较分析

（一）无损压缩算法

①RLE

RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。

变体1：重复次数+字符

文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。

变体2：特殊字符+重复次数+字符

文本字符串：A A A A A B C C C C B C C C，编码后得到：B B 5 A B B 4 C B B 3 C。编码串的最开始说明特殊字符B，以后B后面跟着的数字就表示出重复的次数。

变体3：把文本每个字节分组成块，每个字符最多重复127 次。每个块以一个特殊字节开头。那个特殊字节的第7 位如果被置位，那么剩下的7位数值就是后面的字符的重复次数。如果第7 位没有被置位，那么剩下7 位就是后面没有被压缩的字符的数量。例如：文本字符串：A A A A A B C D E F F F。编码后得到：85 A 4 B C D E 83 F（85H= 10000101B、4H= 00000100B、83H= 10000011B）

②Huffman

哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。

哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。

③Rice

Rice编码背后的基本思想是尽可能的用较少的位来存储多个字（正像使用哈夫曼编码一样）。实际上，Rice类似静态的哈夫曼编码（例如，编码不是由实际数据内容的统计信息决定，而是由小的值比高的值常见的假定决定）。编码非常简单：将值X用X个‘1’位之后跟一个0位来表示。

对于由大word（例如：16或32位）组成的数据和教低的数据值，Rice编码能够获得较好的压缩比。音频和高动态变化的图像都是这种类型的数据，它们被预处理过（例如delta相邻的采样）。

尽管哈夫曼编码处理这种数据是最优的，却由于几个原因而不适合处理这种数据（例如：32位大小要求16GB的柱状图缓冲区来进行哈夫曼树编码）。因此一个比较动态的方式更适合由大word组成的数据。

④LZ77

在LZ压缩算法的背后是使用RLE算法用先前出现的相同字节序列的引用来替代。