哈佛 CS50：第 3 周作业（第 7 讲和第 8 讲），第 1 部分

哈佛 CS50 编程基础课程讲座 附加材料：渐近符号、排序和搜索算法 第二部分。C语言中的“标签”

准备

在做题之前，先观看第7-8讲，阅读并深入研究“第三周的补充材料”。他们致力于搜索算法（线性和二进制）、排序（有很多！）以及调试器的工作（使用调试器调试程序的能力是一项极其重要的技能！）。如果讲座和理论一切顺利，您可以轻松回答测试问题：

• 为什么二分查找需要排序数组？
• 为什么冒泡排序估计是O(n2)？
• 为什么插入排序估计是Ω(n)？
• 选择排序如何工作？用三句话（或更少）描述。
• 合并排序可以运行多长时间的上限（最坏情况）是多少？
• GDB 调试器允许您调试程序。如果你更具体地阐述，它到底能让你做什么？

目标

• 了解如何处理包含多个文件的项目
• 学会阅读别人的源代码
• 了解各种算法和递归函数

大多数这些目标实际上不可能进行正式评估。因此，从形式化验证问题的角度来看，没有什么会让你觉得困难的。不过，我们提醒您：只有不断练习才能学会编程！因此，我们鼓励您不仅要解决任务，还要花费额外的时间和精力来实现本周讨论的所有算法。向前！

开始

回想一下，对于第一周和第二周的练习题，您从头开始编写程序并使用mkdir命令创建了自己的pset1和pset2目录。对于第三周的练习作业，您需要下载我们编写的发行版（或我们所说的“发行版”）并向其中添加您自己的代码行。首先，阅读我们的代码并尝试理解它。本周最重要的技能是学习如何阅读别人的代码。因此，登录 cs50.io 并 在终端窗口中运行命令以确保工作区版本是最新的。如果您不小心关闭了终端窗口并且找不到它，请转到“查看”菜单并确保选中“控制台”选项（如果没有选中，请选中）。单击 (+)，在终端窗口框架上的绿色圆圈内，选择New Terminal。 之后，运行命令 并确保您位于工作区目录中（这是您的目录）。之后，运行命令： 将问题书的 ZIP 存档下载到您的工作空间中（wget 是 Linux 下载命令）。如果一切正常，您将在行中看到以下短语： 确保您确实通过运行命令 下载了pset3.zip ： 然后运行 以解压缩该文件。如果现在再次运行ls命令，您还将看到pset3目录。通过运行命令转到它 ，然后再次请求查看该目录的内容： 您将看到该目录中有两个子目录： 已经很有趣了！ update50cd ~/workspacewget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip'pset3.zip' savedlsunzip pset3.zipcd pset3lsfifteen find

搜索

现在让我们深入研究这些子目录之一。为此，我们将运行命令： cd ~/workspace/pset3/find 如果您在屏幕上显示此文件夹的内容（您可能已经记得如何执行此操作），您应该看到以下内容： 哇 helpers.c helpers.h Makefile find.c generate.c ，有很多文件。不过别担心，我们现在就来对付他们。文件generate.c包含一个程序的代码，该程序使用“伪随机数生成器”（由drand48函数生成）来生成大量随机（实际上是伪随机，计算机无法处理纯随机性！）数字，并一次将它们放在一行中。编译程序： make generate 现在通过运行命令来运行它： ./generate 程序将给您以下消息： Usage: generate n [s] 这意味着程序需要一个或两个命令行参数。使用第一个， n, 是必填项；这个数字表示要创建多少个伪随机数。参数 s 是可选的，如方括号所示。数字 s 可以称为伪随机数生成器的“种子”。通过“种子”我们指的是影响其输出的伪随机数生成器的输入数据。例如，如果您使用 drand48，首先通过调用 srand48（另一个函数，其目的是“播种”drand48），参数为 1，然后然后调用 drand48 三次，drand48 可能会返回 2728，然后是 29785，然后是 54710。如果您使用 drand48 而不是前一个，首先使用参数（例如 2）调用 srand48，然后再次使用 drand48 三次，drand48 可能会返回返回 59797，然后是 10425，然后是 37569。但是，如果您通过再次调用 srand48（参数为 1）来重新看到 drand48，则接下来三次调用 drand48 的结果将再次获得 2728，然后是 29785，然后是 54710！你看，一切的发生都是有原因的。再次运行程序，这次假设n=10，如下所示；您将看到包含 10 个伪随机数的列表。 ./generate 10 让我们使用相同的 n 值第三次运行该程序；您应该会看到另一个包含 10 个数字的列表。现在尝试使用两个参数运行该程序。让我们取 s=0 如下所示。 ./generate 10 0 现在再次运行相同的命令： ./generate 10 0 您甚至无法争论：您再次看到了相同的十位数字的“随机”序列。如果您不更改伪随机数生成器种子，就会发生这种情况。现在让我们看看generate.c程序本身（还记得怎么做吗？）。该文件开头的注释解释了该程序的一般功能。但我们似乎忘记了对代码本身进行评论。仔细阅读代码，不断地阅读，直到理解每一行的含义。然后为我们注释掉这段代码，用描述相应一行或多行代码的目的或功能的短语替换每个 TODO。（注意：unsigned int 是“无符号”int，这意味着它不能为负数）。要获取有关 rand 或 srand 的更多信息 ，请 运行man drand48 ： 坏了：）！提醒一下，make命令会自动编译代码，因此您不必通过手动插入一堆开关来运行 clang 命令。但事实上，make只是简化了我们的输入，但实际上，它的背后隐藏着与我们需要的参数相同的clang。然而，随着程序变得越来越大，make 无法再从上下文中找出如何编译代码。在这种情况下，您必须告诉 make 如何编译程序，特别是当它们涉及使用不同的源文件（例如 .c）时。为了解决这个问题，我们将使用配置文件（Makefile）来告诉 make 到底要做什么。make 命令怎么知道我们应该如何编译生成呢？事实上，团队使用了我们已经编写的配置文件。该文件称为Makefile ，与generate.c位于同一目录中。Makefile 是指定如何从generate.c 创建文件generate 的规则列表。在该文件中，您将特别发现相关行： 第一行告诉 make 应通过调用第二行的命令来创建名为“generate”的“目标”。此外，第一行告诉make，generate依赖于generate.c，这意味着如果该文件已更改，make只会在后续运行中重建generate。这是一个不错的节省时间的技巧，对吧？事实上，如果您没有更改generate.c ，请再次运行以下命令。 您将收到通知，generate 已更新到当前版本。 注意：第二行开头的缩进不是空格序列，而是制表符。不幸的是，make 要求命令前面有制表符，所以要小心不要将它们更改为空格，否则你会遇到奇怪的错误！-Werror标志告诉clang命令man srand48make generategenerate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.cmake generate将警告（不好的）视为错误（甚至更糟），因此您将被迫（以良好的、有教育意义的方式！）纠正它们。现在让我们看看find.c文件。请注意，该程序需要一个命令行参数：“igloo”，它必须在值的“干草堆”中找到。之后，检查代码并通过运行以下命令编译程序。 make find make 基本上给了我们以下信息： clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm 注意！您刚刚编译了一个由一个但两个文件组成的应用程序：helpers.c和find.c。是怎么知道这件事的？要了解这一点，请再次打开 Makefile 以查看其中到底发生了什么。相关行如下。 find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm 我们所说的依赖（冒号后面）的意思是，对find.c、helpers.c或helpers.h的任何更改都将强制 make 在下次出于这些目的调用时重建 find 。现在，通过执行以下操作来运行该程序： ./find 13 此后，系统会要求您提供一定的堆栈（即整数），并一次给它们喂一根吸管。一旦厌倦了输入数字，请按组合键Ctrl-D。该组合将向程序发送一个文件结束（EOF）字符。该符号将强制 CS50 库中的GetInt函数返回常量INT_MAX，而这反过来在find.c中将强制 find 停止键入“stack”。该程序现在将在您提供的大海捞针中寻找针，并且最终会告诉您是否找到了它。简而言之，程序在数组中搜索某些值。至少她应该找到，但问题是她还什么也找不到！但你来救援了！稍后我们将讨论您角色的重要性。事实上，提供干草堆的过程可以自动化，至少可以通过将generate 的输出“合并”到find 作为输入。例如，下面的命令传递 1000 个伪随机数进行查找，然后在这些值中搜索 42。请 ./generate 1000 | ./find 42 注意，当generate 传递原始数据进行查找时，您不会看到生成数字，但会看到 find 正在运行。或者，您可以使用如下命令将generate的输出“重定向”到一个文件： ./generate 1000 > numbers.txt 该文件的内容可以使用以下命令重定向到find的输入： ./find 42 < numbers.txt 让我们再看一下Makefile中的代码，并注意以下行： all: find generate 这意味着您可以通过运行以下命令来构建生成和查找： make all 此外，该行下面的命令与其上面的命令等效，因为 make 默认情况下构建 Makefile 中的第一个条目。 make 如果您能将所有这些练习任务归结为一个命令就好了！可惜！最后，请注意 Makefile 中的最后几行： clean: rm -f *.o a.out core find generate 此条目允许您删除所有以 .o 结尾或称为 core 的文件（我们稍后会解释这一点！），并且还可以简单地运行查找或生成程序通过执行以下行： 如果您想进行 make clean 实验，那么需要注意以下几点：不要将*.c添加到 Makefile 的最后一行！（为什么？）所有以 # 符号开头的行都只是注释。

任务 1：搜索

是时候做一些有趣的事情了！请注意，find.c调用search ，这是在helpers.h中声明的函数。不幸的是，我们忘记在helpers.c中完全实现这个函数！（需要注意的是，我们可以将helpers.h和helpers.c的内容放入一个find.c中。但有时最好将程序分成几个文件。特别是如果某些函数（或者更确切地说是实用函数）可能有用对于其他程序。例如CS50库函数。看一下helpers.c，你会发现无论给定值是否在values中，search总是返回false。重写search，使其使用线性搜索，返回true ，如果值在值中，如果值不在值中则返回 false。如果 n 不是正数，请注意立即返回 false。当您准备好检查有效性时，请尝试调用以下命令：由于打印的数字 ./generate 1000 50 | ./find 127 之一当 50 被播种时，generate 是 127，您的代码应该找到针！作为对比，请尝试以下命令：由于 ./generate 1000 50 | ./find 128 128 不在 50 被播种时由generate 生成的数字集中，因此您的代码不必找到“针” 。通过使用一些种子运行生成、分析输出并寻找大海捞针来运行其他测试。注意find.c中main的写法是如果找到“针”则find返回0，否则返回1。你可以检查main在运行其他一些程序后执行时返回的所谓“输出代码”命令 echo $? 。例如，如果您的搜索实现是正确的，如果您运行， ./generate 1000 50 | ./find 127 echo $? 您将看到 0，而 127 是使用种子 50 生成的 1000 个数字之一，因此您编写的搜索应该返回 true。在这种情况下，main（我们编写的）应该返回0（即退出）。如果您给出以下输入 ./generate 1000 50 | ./find 128 echo $? ，您将看到 1，因为 128 不属于生成种子为 50 时输出的 1000 个数字。在这种情况下，search（由您编写）将返回 false，而 main（由我们编写）将返回 false ) 将返回 1 （然后完成工作）。你明白其中的逻辑吗？当一切准备好使用 check50 检查时，运行以下命令： check50 2015.fall.pset3.find helpers.c 顺便说一下，在自己测试代码之前，您不应该习惯使用 check50 来测试代码。毕竟，check50 并不真正存在，因此使用您自己的输入样本运行代码，将实际输出与预期输出进行比较，是您此时可以养成的最佳习惯。这是真的，别上瘾！如果您有兴趣使用 cs50 助手的 find 实现，请运行以下命令： ~cs50/pset3/find

排序

线性搜索并不是真正令人印象深刻的东西，但是从第一堂课开始（​​在第七堂课中我们再次重复了这个技巧！）你会记得你可以更快地大海捞针。但首先我们需要对干草堆进行排序。请注意，find.c调用sort ，这是在helpers.h中声明的函数。不幸的是，我们“忘记”在helpers.c中完全实现这个功能！查看 helpers.c，您会发现 sort 立即返回，即使 find 的 main 函数实际上将实际数组传递给它。现在记住数组声明语法。您不仅可以指定该数组的元素类型，还可以在方括号中指定其大小。这就是我们在find.c中对 haystack 所做的事情： int haystack [MAX]; 但是在遍历数组时，您只需指定它的名称。当我们通过 haystack 在find.c中进行排序时，我们的做法完全相同：（ sort (haystack, size); 猜猜为什么我们单独传递该数组的大小？）当我们声明一个采用一维数组作为参数的函数时，我们不需要指定数组的大小。同样，当我们在 helpers.h（和 helpers.c）中声明 sort 时，我们也没有这样做： void sort (int values [] int n); 实现 sort 以便该函数实际上对数字数组从小到大进行排序。它需要的运行时间等于 O(n ² )，其中 n 是数组的大小。正如我们在第三周所了解的那样，您可能想要实现冒泡排序、选择排序或插入排序。然而，值得注意的是：没有“正确”的方法来实现这些算法。有大量的变体。事实上，只要您的实现收敛于 O(n2 ⁾ ，您就可以随时改进它们（如果您认为合适） 。但是，将实验留给函数体，并且为了简化测试，不要更改我们的排序声明。它应该如下所示： void sort (int values [] int n); 由于该函数返回一个 void 值，因此它不应该返回一个排序数组。相反，它必须“破坏性地”对其“运行”的实际数组进行排序，移动其元素。第四周我们将讨论数组是通过引用而不是值传递的。也就是说，sort 不会接收数组的副本，而是接收原始数组本身。虽然您无法更改我们的排序声明，但您始终可以在 helpers.c 中定义自己的函数，然后可以从 sort 调用该函数。自己决定如何最好地测试排序实现。不要忘记 printf 和 GDB 会帮助你！并且不要忘记，您可以通过显式指定生成的种子值来一遍又一遍地创建相同的伪随机数序列。

二分查找，提示

关于find函数 ，您首先需要了解的是我们已经编写了代码（分发）。我们只是填补现有代码中的一些空白。find.c程序请求输入数字（即填充“堆栈”），然后根据用户的请求，使用 helpers.c 中定义的排序和搜索函数在其中搜索“针”。所以，find已经写好了，我们需要写helpers。所以这就是我们需要做的：

1. 实施搜索。如果在堆栈中找到该值，则该函数应返回 true；如果不存在，则返回 false。
2. 实现 sort，一个对值数组进行排序的函数。

最初，搜索是线性实现的。但你可以做得更好。线性搜索算法的运行时间为O(n)。你的任务是编写一个二分搜索算法。其执行时间为O(log n)。然而，它的问题是它需要排序的数据作为输入，否则它将无法工作。你还记得被撕破的书的例子，你可能知道为什么会这样。如果您对元素进行了二分查找，并且没有剩下任何元素（也就是说，这个“堆栈”中根本没有“针”），则需要该函数返回 false。二分搜索可以迭代或递归地实现（David Malan 在第八讲中谈到了递归）。