CS50计算机科学入门第5周作业 Speller 笔记，仅作个人用途。

目录

作业介绍

在 speller.c 文件中，学生需要编写一个程序，该程序的目的是在将磁盘上的单词字典加载到内存中后对文件进行拼写检查。

同时，这个字典是在一个叫做 dictionary.c 的文件中实现的。其中的函数原型不在 dictionary.c 中定义，而是在 dictionary.h 中。这样 speller.c 和 dictionary.c 都可以 #include 这个文件。

DICTIONARY.H

dictionary.h #include 了一个叫做 stdbool.h 的文件，它定义了 bool 本身。

学生还要注意 #define 的使用，这是一个 预处理器指令 ，定义了一个名为 LENGTH 的常数（constant），其值为 45 。常数无法在代码中被改变， clang 会在你自己的代码中用 45 替换掉所有提到的 LENGTH 。换句话说，常数并非一个变量，而是一个“查找和替换”。

最后，学生要注意五个函数的原型： check 、 hash 、 load 、 size 和 unload 。其中 check 、 hash 和 load 使用指针作为参数（有*符号）。

DICTIONARY.C

在 dictionary.c 的顶部定义了一个叫做 node 的结构（struct），它代表了哈希表中的一个节点。

一个全局指针数组（global pointer array） table 也被声明，它将代表你用来跟踪字典中的单词的哈希表。这个数组包含 26 （暂时） 个节点指针，以便于下面描述的默认哈希函数相匹配。这个数字能够被改变，取决于学生自己想如何实现哈希。

注意到程序的代码里只有一个基于单词首字母的样本算法来实现哈希。学生该做的便是尽可能巧妙地重新实现这些函数。

SPELLER.C

speller.c 不需要被编辑。通过一个叫做 getrusage 的函数，程序将对学生的 check 、 load 、 size 和 unload 的实现进行“基准测试”，也就是对执行进行计时。

还需要注意的是程序如何逐字逐句地传递要检查的某个文件的内容。最终，程序会报告该文件中的每个拼写错误，以及一系列的统计数据。

作业目的

学生的目的是尽可能有效地使用哈希表来实现 load 、 hash 、 size 、 check 和 unload ，并使每个函数运行所需的时间都达到最小。

规则

  1. speller.c 和 Makefile 不能被修改
  2. dictionary.c 可以被修改，但五个函数的声明无法被修改
  3. 可以在 dictionary.c 中添加新的函数和变量
  4. dictionary.c 中 N 的值可以被修改
  5. dictionary.h 可以被修改，但五个函数的声明无法被修改
  6. check 的实现必须是不区分大小写的。如果“foo”在 dictionary 中，那么 check 应该在任何字母大写的情况下返回 true
  7. check 的检查实现应该只对实际在 dictionary 中的单词返回 true
  8. 可以假设传递给程序的任何字典的结构与作业提供的完全一样：按字母顺序从上到下排序、每行一个词、每行以 \n 结尾。也可以假定字典至少包含一个词、没有一个词的长度超过 LENGTH 、没有一个词会出现一次以上、每个词只包含小写字母、可能还有单引号，以及没有一个词以单引号开头
  9. 可以假设 check 仅让包含字母字符和单引号的单词通过
  10. 程序可能只接受文本和可选的字典作为输入。学生可能倾向于对默认字典进行预处理，以便得出一个理想的哈希函数，但学生不能为了获得该优势而将任何这种预处理的输出保存在磁盘上以及程序后续运行时重新将其载入内存
  11. 必须不泄露任何内存，一定要用 valgrind 检查泄露
  12. 学生所写的哈希函数最终应该是学生自己的，而非在网上搜索的