作业 4：深入泛型指针

本次作业用于测试你对话题 4 的理解，你将实现 ls 和 sort 命令的简化版本。你的 ls 命令可以使用多种方式打印出目录中的文件列表。你的 sort 命令将按序打印文件中的行。

本次作业重点关注包含 void* 的泛型编程、函数指针和泛型内存处理，并通过以下几个方面的训练，培养你的技能：

• 理解 C 语言函数指针的目的并学会使用

• 以用户身份使用 void* 泛型接口

• 使用原始内存操作实现 void* 泛型函数

完成作业后，你应该能够熟练地掌握内存管理，并能够使用/实现 void* 泛型接口。最关键的是能够正确地传递/接收变幻莫测的 void* 指针：如何处理一级/多级指针的解引用，需要什么样的类型转换，如何在准确且必要的地方使用 * 和 &。毫无疑问，你应该知道如何确定解引用的级别，并正确应用它。理解并能够推测出错误的后果也很有必要。

为了帮助你评估学习进度，对于每个作业/实验，我们罗列了一些要点，并提供了一些思考问题。在完成作业后，可以使用这些问题进行自我检查。如果你不能很好地回答这些问题，那么还需要进一步努力。

• 为了读取输入，mysort 程序将每一行读入一个临时的栈内存中，该内存大小为最大值，然后将副本复制到大小合适的动态内存中进行持久存储。在类似的案例中，这种栈和堆的配合是一种常见的技术。考虑到栈和堆的特性，解释为什么这种方法是必要的或适当的。

• 函数 strcmp 与比较函数 bsearch 和 qsort 的参数原型大致匹配。粗略的类型转换（例如 scandir 所展示的类型转换）可以用来消除编译器的类型不匹配报警，但这却是一个巨大的错误。作为回调函数的比较函数，strcmp 几乎从来都不是正确的选择。解释一下为什么。

• 阅读 lfind 的 man 手册并描述如何使用 lfind 配合适当的回调来重新实现 strlen 的功能。

内存和指针建议

• 栈与堆。需注意栈分配与堆分配的正确使用以及各自适用的场景。根据一般经验，除非需要动态分配的情况，否则首选栈分配。通常，这两种技术会在程序中一起使用。举个例子，要求动态分配的 C 字符串具有适当的大小，例如字符串“apple”需要 6 个字符的存储空间，不能多也不能少。一个惯用法是分配一个大小为最大值的栈缓冲区来临时存储不确定长度的字符串，一旦确定长度后，再将其复制到大小合适的动态分配的堆缓冲区中。这就是 mysort 的行读取代码运行的逻辑。

• 动态调整大小。 mysort 程序事先并不知道输入中的行数，因此它先进行初始分配并根据需要进行增长。大小翻倍是一项经典技术，你会经常看到，例如上次作业中的 read_line 缓冲区的处理以及 musl_scandir 收集的目录中的文件列表。

• 对分配请求进行防御。在现代系统上，你不太可能耗尽整个堆，但当堆损坏时也可能返回 NULL。无论哪种方式，分配失败都不会带来任何好处，因此最好在情况变得更糟之前停止一切。

• 指针类型应该明确。如果你知道指针的类型，请务必使用其特定类型来声明。仅当指针类型未知或可能变化时才使用 void*。另一方面，声明 void* 指针时，也不要指定特定类型。将 void* 声明为 char* 会误导读者认为该指针是 C 字符串，并可能造成误用，而且编译器不会出现警告。

• 谨慎使用指针运算。尽管可以通过计算基地址的偏移量来访问普通数组元素或结构体字段，但为了可读性和安全性，你应该使用数组下标和结构体字段名称。尽可能在类型系统中工作，发挥强类型的长处。只有当你只能操作原始内存时，才有必要降级使用低级类型转换和指针运算。

• 优选赋值操作，而不是原始的 memcpy。虽然 memcpy 可用于执行任何类型的赋值，但这并不意味着应该始终使用它。考虑以下三种整数赋值的方法：

  int dst, src;
  void* pDst = &dst;
  void* pSrc = &src;
  
  dst = src;                          // option A
  *(int*)pDst = *(int*)pSrc;          // option B
  memcpy(pDst, pSrc, sizeof(int));    // option C
  

  三个选项都完成了相同的事情（将 4 字节整数从 src 复制到 dst）。选项A，普通的赋值语句是直接、干净、安全的。只要你能够在类型系统中工作，这始终是你的最佳选择。如果你被迫通过 void* 进行操作，则必须考虑选项 B 和 C。选项 B（使用类型转换进行赋值）是你的第二个选择。该选项可读性好、高效且相对安全（给定正确的类型转换）。选项 C 在最低级别运行，没有任何类型安全保障。指针类型或大小的不匹配都是允许的，这会造成严重的破坏。当尝试读/写 void* 的内容时，如果可能，请使用选项 B。仅当你别无选择时，才使用选项 C 的低级内存复制。根据经验：如果 memcpy 的 size 参数是编译时常量（尤其是使用 sizeof 时），则表明你不应该使用 memcpy/memmove。仅当在运行时确定要复制的内存类型/数量时，才需要调用原始字节复制。

• 警惕类型转换。谨慎使用类型转换。你的类型转换破坏了类型系统，并强制编译器毫无怨言地接受它。这种力量伴随着巨大的责任。在使用转换之前，请考虑一下：为什么需要转换？如果不转换会发生什么？有没有更安全的方式来表达我的意图？如何在类型系统内工作而不是忽略它？（即纠正类型不匹配而不是用强制转换来掩盖）。

  你永远不应该转换不变的值（而是修复类型！），转换函数指针也是一个欠考虑的举动（而是修复函数​​原型！）。你也永远不需要将任何内容强制转换为 void*，因为它是通用指针，并且与任何指针类型兼容（这样的强制转换是多余的，且可以删除）。当你需要一些类型转换时，要准确地添加它们，并且仅在必须的地方添加它们。如果你的代码重复使用类型转换的表达式，并且不可避免时，请考虑创建一个辅助函数来封装该表达式，以便在任何地方调用，而不是重复代码。

初始项目

你的个人用户目录下应该已经有 cs102 这个文件夹了，通过下面的命令拷贝初始代码到该目录中：

cp -r /home/cs102-shared/assignments/assign4 ~/cs102

任务 1：探究 scandir

在随后的作业中，你将编写自己版本的 ls 命令。为此，你需要以用户的身份使用 scandir 库函数，该函数用于为给定的路径创建一个目录列表（包含目录内文件名的一个字符串数组）。它还使用两个函数指针：一个是过滤函数，用于控制列表中包含哪些文件；另一个是比较函数，用于控制列表中文件名的顺序。

对 scandir 的理解对于实现 myls 至关重要，所以在使用它之前，我们先看看该函数是如何实现的。打开作业代码中的 scandir.txt 文件，该实现来自 musl 库。这个函数显示出了 C 的内在灵魂：函数指针、动态分配、三级指针，天哪！但是课程进行到此，你对 C 的了解已经足够深入，完全具备能力阅读这样的代码。慢慢来，尝试画图，有不懂的地方就问。

• 查看 man readdir 文档，了解 struct dirent 的定义。一个奇怪的说明是，最后一个结构字段 d_name 是一个字符数组，描述为“未指定大小”。 该数组的大小是自适应的，用于存放指定目录的名称，包括一个终止字符。由此可见，系统默认的文件名称最多支持 255 个字符。

• 破译函数参数的类型。这是粘贴到 cdecl.org 中的内容。画出 scandir 栈帧的内存布局图，包括所有参数和局部变量。跟踪代码时使用该图来查看内存中发生的情况。

• 这个三级指针 res 参数相当可怕。这个参数有什么作用呢？为什么需要三级指针？（提示：看一下第 43 行，该行使用了这个参数。那里的代码在做什么？回顾课上讨论的模型，如果主调函数希望通过调用一个函数来修改某个值，那么需要以传地址的方式调用，即指针）。

• 用户在调用这个函数时，如何表明不希望对文件名列表进行过滤？或者不进行排序？

• 变量名 len 和 cnt 的选择对于表明其用途毫无帮助。变量 names 也具有误导性——这是一个字符串数组吗？

• 第 20 行使用了 continue，目前为止这可能是你从未见过的 C 结构。它在这里的目的是什么？虽然这个结构并不经常使用，但是当你遇到它时，有必要知道它的作用。

• 过滤器 sel 的非零结果是否会导致文件名在列表中保留或丢弃？

• 第 23 行几乎重复了我们在实验 3 的 calloc 中查看的一段代码。该测试的目的是什么？删除它会产生什么后果？

• 目录内文件的数量事先是未知的，因此 scandir 使用经典的“按需调整大小”分配策略来分配数组。这段代码看起来应该很熟悉，但有一些细节需要仔细检查：

  • 它在第 24 行调用 realloc，而没有对 malloc 进行初始调用。这样使用为什么也是有效的？（提示：查看 realloc 文档，了解如何处理该特殊情况）

  • 它使用表达式 len * sizeof(*names) 来计算总字节数。如果名称为 NULL，则该表达式似乎间接引用了一个 NULL 指针，但请牢记 sizeof 表达式不会运行，它只是根据表达式的类型（在编译期）确定该类型的大小而已。

  • 大小表达式可以等效地写为 len * sizeof(struct dirent *)。使用 sizeof(*names) 而不显式使用类型名有什么好处？

• 在第 24 行，它将 realloc 的返回值赋值给 tmp，并在 if 之后将指针从 tmp 拷贝到 names。为什么它不直接赋值给 names？

• 第 28~30 行创建了 struct dirent 的堆副本。由于 d_name 字段大小自适应，它会分配大小合适的堆内存并复制内容。

• 第 15 行引入了一个神秘的 errno。阅读 man 3 errno 的更多信息，了解其目的和功能。第 19 行对 errno 做了什么，为什么要引入一个 old_errno？如果发生分配失败的情况，errno 的值是多少？（提示：阅读 malloc 文档的 NOTES 部分）

• 第 42 行有点难以理解，它对传递给 qsort 的函数指针进行了类型转换。尝试在使用和不使用强制转换的情况下编译代码。如果没有转换的情况下，你会收到什么警告/错误？（转换函数指针是一件欠考虑的事情，通常应该避免，但他们选择在这里使用的原因是可以理解的。）

• scandir 过滤器函数接收的参数为 const struct dirent *；比较函数接收的参数为 const struct dirent **。为什么不一致？

• 跟踪 malloc/free 的调用，了解该函数中的内存分配和释放。函数退出后还需要执行哪些释放操作？调用者正确释放该内存的步骤是什么？

完成这一部分是一项重大成就。这段代码中发生了很多事情，你应该为能够剖析如此密集的代码而感到疯狂和自豪！对 scandir 的理解对于实现 myls 至关重要，接下来接受新的挑战吧。

任务 2：实现 myls

你已经多次使用 ls 来查看目录内的文件。现在轮到你来实现这个主力命令行程序的简化版本，这也是一个很好的函数指针练习。

myls 程序的运行方式与标准 ls 类似，但作了许多简化，也包含一些差异。虽然心理上将 myls 看作和标准 ls 相同的程序可能会有所帮助，但请不要错误地尝试对比标准 ls 的更复杂功能的输出结果。下面的列表列举了 myls 所需的功能。如果对 myls 的预期行为有疑问，请观察 samples 目录中示例程序的行为，而不是与标准 ls 进行比较。

• myls 可以使用零个或多个目录路径作为参数。它可以列出每个路径的文件内容。如果不带参数调用，myls 会打印当前目录 (.) 中的文件列表。

• myls 仅支持目录路径作为参数。如果参数是某个文件或不存在的路径，它应该打印一条错误消息并跳过该参数。你应该调用 error 函数，将错误消息与示例程序进行完全匹配，使用类似的文本“cannot access __”，填写无效参数的名称，以及错误代码 0 和状态代码 0（程序仍然可以继续运行）。

• myls 每行只打印一个文件名。

• 除非使用 -a 标志调用，否则 myls 忽略以 . 开头的文件名。

• myls 在打印目录内同样是目录的名称时，会添加尾部斜杠。注意，符号链接（symbolic link）是一类特殊的文件，不属于目录，可以当作普通文件对待。

• myls 默认按名称顺序打印目录中的文件，名称按字典顺序进行比较（即 strcmp）。如果使用 -z 标志调用，则排序顺序将改为按类型排序（目录在非目录之前）。遇到相同类型的文件，再按名称进行排序。

• myls 不支持除 -a 和 -z 之外的命令行标志

• myls 应调用标准 scandir 函数，而不是重新实现其功能。鉴于 scandir 已经完成了 ls 程序的大部分工作，你只需编写过滤/比较函数，对 scandir 进行一次调用，然后打印结果列表即可。作为补充，man scandir 的文档包含一个简短的示例程序。小提示：该示例程序碰巧以相反的顺序打印条目，这可能不是你想要的。小心不要从文档中直接复制粘贴代码，除非你认真审查过，了解它做了什么并知道如何根据需要进行调整。

注意

本次作业的一个重要限制是，不允许使用 C 标准库中的 versionsort 或 alphasort 函数作为回调函数参数。你应该实现自己的比较函数。

文件 myls.c 为你提供了少量的代码来处理命令行参数。在开始之前，首先阅读并理解给定的代码，弄清楚如何将其合并到你的实现中，最后为你实现的代码以及初始代码添加注释。初始代码旨在帮助你入门，但你完全可以根据需要随意删除/修改这些代码。

你可以使用 typedef 为函数指针类型指定昵称，让代码更简洁。除了可以避免重复原始的语法，还可以更简单地创建该函数指针类型的变量。在文件 mysort.c 中也有该用法的示例。

处理命令行参数也是一项繁琐的工作。 GNU 的扩展 getopt 在一定程度上，有助于简化这个操作。使用 man 3 getopt 了解有关其工作原理的更多信息。使用 getopt 时如何检测并报告无效的选项？

任务 3：探究 bsearch

接下来，你将学习以下代码，以便实现一个通用的二分插入函数，即使用二分搜索高效地将元素插入到一个有序数组中。在稍后的作业中，你将使用它作为 sort 命令实现的一部分。编写一个正确的二分搜索函数本身就相当困难，而实现一个通用的 void* 函数只会增加挑战。如果需要复习二分搜索算法，可以查看 CS101 配套课本。

我们提供了一份来自 bsearch.c (apple.com) 的通用二分搜索 bsearch 的代码。稍后你将修改此实现，作为你自己的 binsert 函数的一部分，因此了解它的工作原理非常重要。请仔细研究！如果你还没有完成实验 4 中有关 void* 的练习，那么现在可以继续巩固这些知识。

void *apple_bsearch(const void *key, const void *base, 
                    size_t nmemb, size_t width, 
                    int (*compar)(const void *, const void *)) {
    for (size_t nremain = nmemb; nremain != 0; nremain >>= 1) {
        void *p = (char *)base + (nremain >> 1) * width;
        int sign = compar(key, p);
        if (sign == 0) {
            return p;
        }
        if (sign > 0) {  /* key > p: move right */
            base = (char *)p + width;
            nremain--;
        }       /* else move left */
    }
    return NULL;
}

• 在实验 1 中，我们阅读了 Joshua Bloch 的文章 Nearly All Binary Searches and Mergesorts are Broken，讨论了实现中点计算的问题。 Apple 的 bsearch 实现是否存在文章中指出的错误？解释下原因。

• 注释 /* else move left */ 似乎注释了一个空的 else 语句块。当符号为负时，搜索如何向左移动呢？

• 对 void* 执行指针算术运算是非法的，因此强制转换为 char*。在实验 4 中，我们研究过 musl_memmove，它将其 void* 参数复制到函数开头的 char* 类型的局部变量中，从而避免了转换的必要。相比之下，Apple 的 bsearch 将其参数保留为 void* 并在每个指针算术运算之前显式强制转换。这种处理背后的依据是 void* 类型传达了该指针的特殊性质，不会误导用户认为该参数是一个普通的 C 字符串。保持它的 void* 属性还意味着，如果你不小心对其执行解引用或指针算术运算，编译器会报警。每次对 void* 的操作都需要显式强制转换，这种故意的类型转换强调了程序员的设计意图。

• 假设变量 void *arr 是数组的基地址，void *found 是搜索到的元素的地址，size_t width 是每个元素的大小（以字节为单位），那么将 found 转换为其相应的数组索引的 C 表达式是什么？

完成这一步是一项巨大的成就。这段代码中发生了很多事情，你应该感到自豪，因为你可以理解这样的库代码了，还能利用它来实现一个通用的二分搜索！有了这些知识储备，你就可以开始编写 binsert，这是 Apple bsearch 的一个变体。

任务 4：实现 binsert

lfind 和 lsearch 是泛型线性搜索函数，阅读 man lsearch 了解更多介绍。lsearch 与 lfind 的区别在于，如果没有找到元素，lsearch 会将搜索关键字添加到数组中。该特性非常方便！

你的下一个任务是编写一个通用函数 binsert，它是 bsearch 的变体，具有相同的功能；对 binsert 的调用将对“键值”执行二分搜索，如果找不到匹配元素，则会将键值插入到有序数组中的正确位置。该函数在作业的最后一个任务中会派上用场，你可以利用其实现自己版本的 sort 命令。以下是 binsert 函数原型：

void *binsert(const void *key, void *base, size_t *p_nelem, 
   size_t width, int (*compar)(const void *, const void *));

以下是该函数操作的详细信息：

• binsert 的参数设计参照了 bsearch 的参数（查看 man bsearch）。唯一的区别是将元素的数量作为指针传递。这是必须的，因为 binsert 将在将新元素插入数组时更新计数。

• 如果 binsert 没有找到匹配的元素，它将把键值插入到数组的正确位置并增加元素的数量。客户端有责任确保数组有足够的空间来容纳新的元素。binsert 不会分配、调整或释放客户端提供的数组内存。

• 该函数返回一个指向匹配的数组成员的指针，如果未找到现有匹配项，则返回指向新添加的成员的指针。

• 你可以将 Apple bsearch 的代码复制/粘贴到 binsert 中作为初始代码。 虽然在 binsert 直接调用 bsearch 可以避免代码重复，但是搜索不到元素时，标准 bsearch 不会提供必要的位置信息，而这些信息在你正确插入新元素时非常重要。如果你调用 bsearch 并得到了否定结果，你就必须进行二次搜索才能找到该位置，这意味着代码冗余和重复执行！所以，把 bsearch 代码拷贝到 binsert 中进行调整，反而可以让该函数只需要执行一次搜索。提示：你可能不需要对提供的代码进行特别大的修改，修改应该不到 10 行。如果你修改了太多的代码，很可能是你对其行为的理解出现了偏差。

• 如果需要移动数组中的元素来腾出空间，你应该使用 memmove，而不是循环逐个移动数组项，memmove 可以一次性移动整个数组！

将你的实现写入 util.c 文件中。你可以单独编写并测试该函数，然后在稍后编写 mysort 程序时使用该函数。你可以使用我们提供的 test_binsert.c 程序测试你的 binsert 函数。 test_binsert 程序与 sanitycheck 集成，方便你进行测试。注意：除了 -i 和 -s 标志之外，test_binsert 不支持带有负数或以 - 开头的字符串的输入。有关如何使用它的更多信息，请参阅 test_binsert.c 文件。

在继续下一个任务之前，你是否彻底测试了 binsert 的实现？增量开发是开发过程的一个重要部分，你可以单独实现一个个小模块，彻底测试它们，然后在确定它们的正确性后再进行整合。这样的好处是，如果某一步遇到了错误，你可以确信错误来源就是你最近修改的代码，缩小排查的范围。mysort 建立在这段代码的基础上，因此在继续之前，请确保对其正确性充满信心。

任务 5：实现 mysort

对于作业的最后部分，你将实现你自己的 sort 命令，称为 mysort，它将使用 binsert 函数作为底层实现。sort 是另一个过滤器命令，类似 uniq 和 tail，你在上次作业中已经实现了它们的简化版本。标准 sort 命令逐行读取输入，然后按指定顺序打印出各行。它支持各种命令行标志控制排序的行为。以下是 sort 的使用示例：

$ cat samples/colors
red
green
green
red
blue
blue
blue
red

$ sort samples/colors 
blue
blue
blue
green
green
red
red
red

$ sort -u -r samples/colors 
red
green
blue

mysort 程序的运行方式与标准 sort 类似，但有许多简化和一些差异。虽然心理上将 mysort 看作和标准 sort 相同的程序可能会有所帮助，但请不要错误地尝试对比标准 sort 的更复杂功能的输出结果。如果对 mysort 的预期行为有疑问，请观察 samples 目录中示例程序的行为，而不是与标准 sort 进行比较。

以下是 mysort 所需的功能：

• mysort 读取一个文件：指定文件（由参数指定）或标准输入（参数未指定）。

• mysort 的默认排序顺序是字典顺序（字母顺序）。

• 如果使用 -l 标志调用，则排序顺序是按行的长度递增。

• 如果使用 -n 标志调用，则排序顺序按字符串数值（将 atoi 应用于每一行并比较数字）。

• 如果是重复行，即根据排序规则，比较结果相等的行，则可以按任意顺序输出。

• 如果使用 -r 标志调用，则排序顺序将相反。（提示：对输入进行常规排序，只需更改打印时的顺序即可）

• 如果使用 -u 标志调用，则丢弃重复的行。排序后的输出只包含输入中互不相同的行。根据排序顺序来确定哪些行是重复的（例如，如果按长度排序，则长度相同的两行被视为重复）。

• mysort 的标志可以单独使用或组合使用。如果同时使用 -l 和 -n，则命令行上最后一个标志将用作排序顺序。

• 除了 -l -n -r -u 之外，mysort 不支持其他任何命令行标志。

在底层实现中，mysort 应该具有以下行为：

• mysort 使用 fgets 将一行内容读取到栈数组中。该栈数组的大小应设置为最大大小（参阅 MAX_LINE_LEN 常量，预估一个较大的值）。对于超过最大长度的输入行，我们不会对其进行任何测试。你还可以假设所有输入行都以换行符结束，这可以避免在输入的最后一行出现特殊情况。

• 读取要存储的行后，应将其复制到适当大小的动态堆内存中进行存储。此时，函数 strdup 会很方便。

• mysort 应该能够处理任意行数的输入。如此大的行数组对于栈内存来说可能太大了，因此这个数组必须是在堆内存上分配的。由于无法提前确定行数，所以 mysort 应该将数组分配为一个最小初始数量（请参阅 MIN_NLINES 常量），然后每次填满时，将其大小加倍。

• mysort 的 -u 选项必须重复调用 binsert 函数。这里要求对所有重复行仅存储一次，而不是存储所有的行，再将重复的删除。另外，此处不应该调用 qsort。

• 如果在没有 -u 标志的情况下执行，mysort 应该只调用一次 qsort 并且不会调用 binsert。

重要提示：在实现过程中，如果你需要存储某一行，则仅应在堆上存储。另外，如果不需要存储该行并在稍后进行打印，则不应在堆上分配内存。如果你的内存使用量明显高于示例程序，则可能是因为这个原因。

这可能看起来与之前的作业相似，你最初可能会倾向于复制粘贴之前的代码，但最终应该意识到此实现中存在着一些显着的差异。与上一个作业不同，本次作业需要使用不同的策略来读取未知大小的文本——先将其分配在栈上，然后仅在知道完整大小后才使用堆内存进行分配，因为此时才能准确分配你需要的内存大小来存储数据。

不同的方法各有利弊。对于本次作业，你可能会采取上一份作业使用的方法，由于没有使用栈内存进行预先存储，在堆上分配的空间将略多于所需的大小。而本次作业推荐的策略，将使用大量栈空间来存储初始字符串，最终的结果是你可以精准地分配所需的堆内存大小。我们希望通过这两次作业，能够让你充分练习这两种有效的开发模式。

文件 mysort.c 为你提供了少量的代码来处理命令行参数。在开始之前，首先阅读并理解给定的代码，弄清楚如何将其合并到你的实现中，最后为你实现的代码以及初始代码添加注释。初始代码旨在帮助你入门，但你完全可以根据需要随意删除/修改这些代码。

mysort 的一个核心目标是如何在不重复代码或使代码过于复杂的情况下，优雅地处理排序选项的组合。特别注意，4 个命令行标志都可以独立地打开，总共有 24 种不同组合。如果你考虑不周，最终可能会从每个组合中创建一个不同的情况，以至于多出 16 倍的代码量。相反，如果你能够统一共同的操作，只在个别差异的地方添加代码来处理，那么可以少走很多弯路。你可能需要不断迭代来解决很多细节，但如果用心去做，最终你将会得到一个非常令人满意的结果！加油吧！

最后，强烈建议你阅读：Engineering a Sort Function。这篇文章是关于 qsort 库函数的思想和工程实践的精彩读物。Jon Bentley 和 Doug McIlroy 是前贝尔实验室的两位名人堂成员，他们写的任何东西都值得一读！

如何使用 sanitycheck 检测较长输出

最后一个测试使用一份很长的数字文件进行排序。如果通过测试，则不会打印整个输出，但如果输出不匹配，那么它将打印整个差异信息，这可能很烦人。

除了在终端中滚动查看输出结果，一个更方便的技巧是使用管道 > 将测试结果保存到一个文件中。

需要注意的是，由于输出的格式和颜色问题，文件中可能会显示一些奇怪的字符。解决方法是，可以使用以下命令，使用正确的格式打开文件：less -R outputfile.txt。

$ sanitycheck > outputfile.txt 
$ less -R outputfile.txt

测试与提交

作为作业的一部分，你应该尽可能完善 custom_tests 中的测试案例，至少添加 3 到 5 个。为了更好的可读性，也建议你为代码和测试用例编写注释或文档。这些注释用于说明每个测试的初衷，以及这些测试之间的相互关系。

作业提交方式参考作业 0，可以使用 submit 提交你的代码。为了追求完美，一些加分项值得你去注意：

• 编译是否干净，有无警告等编译错误？

• 默认测试是否全部通过？

• 自定义测试案例是否全面？

对于代码实现部分：

• 有没有其他地方，还可以使用位运算进行改写？

• 算法是否高效？还记得如何分析算法复杂度吗？

• 代码风格及可读性是否注意过？有没有进行函数拆分，提取出一些更通用的代码？

• 有没有尝试编写文档？一份好的代码就如同一篇优美的散文，不多一字，也不少一字。加油！