数据结构实习（单链表，法雷序列，二值图像像原分组，压缩）

本文档实现了单链表，通过一次遍历找到单链表中倒数第n个节点，要求不允许使用双向链表；不允许修改原始单链表；可使用额外的辅助空间，但是辅助空间的数目必须最小，不能和n有关。并且给出了测试数据：使用1-1000的整数形成单链表，要求查找倒数第200个元素。 对任意给定的一个自然数n（10≤n≤1000），将分母≤n的不可约的真分数按照升序排列，并且在第一个分数前面加上数0/1，在最后一个分数后面加上数1/1，这个序列被称之为n级法雷序列，，以Fn表示。 例如：F8为：0/1、1/8、1/7、1/6、1/5、1/4、2/7、1/3、3/8、2/5、3/7、1/2、4/7、3/5、5/8、2/3、5/7、3/4、4/5、5/6、6/7、7/8、1/1 要求：给出一个n就能求出由n生成的法雷序列。 存储方式是单链表形式，不允许使用STL容器；程序中为整数操作，不允许出现实数的比较；结果输出到文件中。 利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空 间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩解压缩软件。 一个完整的系统应具有以下功能： （1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果 （包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。 （2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数 据一起写入文件中，形成压缩文件(*.Haf)。 （3）解压缩。打开已有压缩文件(*.Haf)，读取其中的哈夫曼编码，构建哈夫曼树，读取其 中的数据，进行译码后，写入文件，完成解压缩。 （4）程序使用命令行方式运行 压缩命令 ：SZip A Test.Haf 1.doc 解压缩命令：SZip X Test.Haf 2.doc 或 SZip X Test.Haf 用户输入的命令不正确时，给出提示。 （5）使用面向对象的思想编程，压缩/解压缩、哈夫曼构建功能分别构建类实现。