压缩软件数据结构课程设计.docx

《数据结构》课程设计实验报告题目：压缩软件（选做题）姓名：学号：指导老师：时间：2015.09.06目录一、设计内容和要求3二、算法思想描述3三、程序结构4四、结果与分析5结果5分析9五、收获与体会9设计内容和要求设计内容：压缩软件要求：建立一个文本文件A（可以是C/C++源程序），统计该文件中各字符频率。首先对各字符进行Huffman编码，将该文件翻译成Huffman编码文件B；然后将Huffman编码文件译码成文件C，并对文件A与C进行比较。算法思想描述1.Huffman编码解码思想：Huffman树是一种加权路径长度最短的二叉树。编码时，是根据待编码文件中记录的关键字在文件中出现的频率进行编码，每个关键字都对应一个编码，频率较高则编码较短，频率较低则编码较长。Huffman树解码时，根据记录的关键字的编码对文件进行解码。具体方法为依次选择权值最小的两个关键字作为左右孩子，其和作为父结点的权值，将其父结点代替两个子结点， 再次选择权值最小作为左右孩子，依次进行下去，直到所有的关键字结点都成为叶子结点。根据创建的Huffman树来确定个关键字的01编码，左孩子为0，右孩子为1。2.整体算法描述：首先读入待压缩文件，然后对每种字符出现的频度进行统计，以频率作为建立哈夫曼树的权值。接着建立哈夫曼树，对出现的每种字符进行哈夫曼编码。此时再读入原文件，逐个字节进行编码，将得到的编码流逐个写入文件。译码过程：读入被压缩文件，根据哈夫曼树对文件中的字符逐个译码，将译码结果逐个写入文件。程序结构压缩软件的程序流程图压缩软件的函数功能结构图结果与分析结果界面压缩文件解压文件比较分析1.检查程序的正确性 本程序运行时生成两个文件，文件名分别为A.txt 和C.txt 。当C.txt和原文件的内容大小一致时，说明程序功能已经实现的，在VC的环境下，二者是相同的，仅文件名的差异。2.判断此软件的好坏从代码的简练性着手；从压缩比的高低来判定，哈夫曼编码的唯一性说明这种编码文件的唯一性；收获与体会Huffman树的建立，编码，译码有了更深层次的理解。文件的打开，关闭，读入，输出语句比较熟悉了。对于测试用的数据，比如用来测试的数据的个数可以设为常量，这样方便为之后的测试做修改。通过这次压缩软件的设计，我熟练掌握了对文件的处理，两个程序几乎包含了所有处理文件的基本技巧，包括输入，输出，查找定位，查找文件对话框的使用等等。此外，更加熟练地掌握了huffman编码的算法，通过压缩软件的实现更加透彻地理解了huffman编码的压缩功能。通过学习网上的优秀代码，了解了怎样将编码按照二进制方法写入文件，即用字符移位的方式拼接成完整二进制码：假设原文件第一个字符是A，8位2进制编码后为0110识别编码第一个0，那么我们就可以将其左移一位。下一个是1，应该|1，结同理4位都做完，应该由于字节中的8位并没有全部用完，我们应该继续读下一个字符，根据编码表继续拼完剩下的4位，如果字符的编码不足4位，还要继续读一个字符，如果字符编码超过4位，那么我们将把剩下的位信息拼接到一个新的字节里。一个汉字占两个字节，且最高位是1，如果是以整型数输出的话，每个字节的ASCII值会是负数，所以应该设成为无符号数。在用二进制写入文件时，文件末尾的字符产生错误解压。反复查看后发现由于最后一个字符编码拼接完后不够一个字节的长度，后面自动补零，造成解压错误。于是，加上lastsize记录最后一个字节的有效长度，解压时根据lastsize长度解压最后一个字节，解决了问题。将HuffmanNode对象写入文件时，使用write太慢且程序代码复杂，后重载了、,用来输入输出该对象.且从文件中读入字符用的话，程序会自动把空格符，回车符之类的控制符号去掉，所以用write()方法来写到文件。