ZAMYLA陈：让我们 一个拼写检查器。 如果你打开​​speller.c，然后你会看到 大部分的功能​​为 检查对一个文本文件 字典是已经为你做。 /拼写检查，传递一个字典文字 文件，然后另一个文本文件， 将检查的文本文件 对字典。 

现在，词典文本文件将包含 有效的话，每行一个。 然后speller.c将调用Load 在字典中的文本文件。 它会调用被调用函数检查 每一个字的输入的文本文件， 打印所有拼写错误的单词。 

Speller.c还将呼吁大小来 决定在单词数 字典和调用卸载 以释放内存。 speller.c也将跟踪如何 多少时间是用来进行这些 过程，但我们会 到后来。 

那么，我们需要做什么？ 我们需要填写dictionary.c。 在dictionary.c，我们有帮手 功能加载，加载了 字典。 功能检查，如果它检查 一个给定的字在字典中。 该函数大小返回数字 在字典中的字。 最后，我们已经卸载，这 从存储器释放字典。 

因此，首先让我们来解决负载。 在字典中的文字每个字 文件，加载将存储在那些话 的词典数据的结构 您的选择，无论是中 哈希表或线索。 我过去无论是在 此穿行。 

首先，让我们来谈谈哈希表。 说你有10台球和 你想存储它们。 你不妨把它们放在一个桶里， 当你需要一个特定的 编号的球，你会采取一 出桶时间的 寻找那个球。 而只有10球，你应该 能够找到你的球在一个合理的 量的时间。 

但是，如果你有20个球？ 现在它可能需要一点时间。 怎么样100？ 1,000？ 现在，这将是容易得多，如果 你有多个桶。 也许有斗球编号为零 经过九个，另一桶 球编号为10至 19，依此类推。 

现在，当您需要寻找特定 球，你可以自动 去一个特定的桶和 搜索通过桶。 如果每个桶中有大约10 球，那么你可以很容易地搜索 通过它。 

现在，因为我们正在处理 字典，一个用于单斗 所有在字典中的单词会 可能是太少桶。 因此，让我们来看看哈希表。 

把它看成是水桶的数组。 并且在这种情况下，该桶 是我们的链表。 我们将分发所有的我们的话 其中在这些多重链表 一个有组织的方式使用哈希函数， 它会告诉我们哪些 斗一个给定的键，一个给定的 字，属于。 

让我们代表这示意性的。 蓝色方框这里包含的价值观和 红色方框指向另一个值 指针对。 我们称这些成对节点。 现在，每个桶，正如我所说 早期，是一个链表。 在链表中，每个节点都有一个值， 以及一个指针，指向 下一个值。 

现在，处理链表， 这是非常重要的，你 不输任何链接。 而另一个事实要记住的是， 最后一个节点，如果它不指向 另一个节点，指向空。 

那么，我们如何代表在C？ 在这里，我们定义我们的结构。 在这种情况下的值是 长度的字符数组。 长度加1，其中长度是 最大长度的任何单词，加1 空终止。 然后我们有一个指针 另一个节点叫做下一步。 

因此，让我们做一个小的链表。 首先，你会想用malloc您的节点， 它在内存中创建空间 您的节点​​类型的大小。 并让另一个节点， 再次mallocing。 

现在，如果你想要一个值赋给一个 字，那么我们可能会说node1上箭头 字等于“你好。”这个箭头操作符 取消引用指针和 访问结构体的变量。 这样，我们就不必同时使用 点和星算。 

于是我有node2上箭头字等于 “世界”。而且，这些值是 居住在我的节点。 为了使链接，我会通过在节点1 旁边的箭头，访问该节点的明星， 该节点的指针，等于节点2， 指向节点1到节点2。 我们在那里有一个链表。 

所以这只是一个链表，但 哈希表是整个阵列 链表。 好了，我们将有相同的节点 如前结构。 但是，如果我们想要一个实际的哈希表， 那么我们可以只让一个节点指针 数组在这里。 例如，大小500。 

现在通知，还有的将是一个贸易 关的大小之间的 哈希表及大小 您的链表。 如果你有一个非常高数 水桶，想象不必跑回来 和向前一行 找到你的水​​桶。 但你也不想少数 水桶，因为那时我们又回到了 如何具有原始问题 太多的球，我们的水桶。 

好了，但那些我们的球去了？ 那么，我们首先需要 有一个球，对不对？ 因此，让我们的malloc为每一个节点 新词，我们有。 节点* new_node等号 的malloc（的sizeof（节点））。 

现在我们有了这个结构，我们 可以扫描中，使用功能 的fscanf，从我们的文件中的字符串，如果 这是一个字典文件，进 new_node箭头字，其中new_node 箭头的话是我们 该单词的目的地。 

接下来，我们将要哈希 字使用哈希函数。 散列函数将一个字符串 并返回一个索引。 在这种情况下，索引有 小于的数量 你有水桶。 

现在，散列函数，当你试图 找到一个，并创建一个 你自己，记住他们 必须是确定性的。 这意味着相同的值需要 每次映射到同一个桶 您哈希它。 

这有点像一个图书馆。 当你把一本书的基础上， 作者，你知道哪个货架它应该 去，无论是货架编号 一个，两个或三个。 而这本书将永远属于上 任一货架的一个，两个或三个。 

所以，如果new_node箭头字的 从你的字典中的单词，然后 散列new_node箭头会字 给我们的索引 斗哈希表中。 然后我们将其插入该 由指定的特定链表 回到我们的哈希函数的值。 

让我们看一个例子 插入一个节点到 开始的链表。 如果头是一个节点指针，指示 的一个链接的开始 列表，并new_node表示新 要进入，只是节点 分配头new_node将失去 链接列表的其余部分。 所以，我们不希望这样做。 

相反，我们要确保 我们坚持每 在我们的节目单节点。 所以运行new_node箭头旁边的equals 头，然后头等于new_node 将保留所有的 链接和不会丢失任何。 

但如果你想你的列表是 排序，因为有一个排序的链接 清单可能为更容易 寻找它以后？ 那么，对于这一点，你需要知道的 如何遍历链表。 

遍历一个链表，让我们 一个节点的指针，一个节点*，充当 你的光标，指示哪些 节点你在起 在第一个元素。 循环，直到光标为空，我们可以 进行一定的处理，然后 向前移动光标，当我们需要 使用光标箭头的价值。 

请记住，这是同样的事情 话说明星光标，提领 光标，然后使用 点运算符值。 所以通过将更新光标 光标移动到光标箭头旁边。 

说你确定D变为在 与C和E要插入的节点， 有new_node C点到 节点E，这是下一个光标。 然后C，光标，可以再点 到D这样，你保持一个列表。 小心不要失去你的链接 移动光标箭头旁边到D 的时候了。 

好的。 所以这就是你会如何插入节点， 加载它们，负载话到这些 个节点，并把它们插入 到你的哈希表。 所以，现在让我们来看看尝试。 

在字典树中，每个节点将包含一个 结点的指针，一个用于每个阵列 字母在字母表 加一个单引号。 并且阵列中的每个元素 将指向另一节点。 如果该节点为null，则该信 不会成为下一个字母 在一个序列中的任何一句话，因为每 字指示它是否是最后 字一个字或不是。 

让我们看一个图。 希望事情会 有点清晰。 在此图中，我们看到只有 某些字母及若干子 被列出。 这样你就可以遵循一定的路径， 所有这些路径将导致你 不同的词。 

那么，我们如何代表在C？ 那么，每一个节点现在将不得不 一个布尔值，表示是否 该节点的端 一个给定的字或没有。 然后还会有一个数组 所谓的子节点指针， 有将是他们中的27。 请记住，你也想要 保持你的第一个节点的轨道。 我们要调用根。 

所以这是一个线索的结构。 我们如何代表这 作为一本字典？ 好吧，加载字，每 字典中的单词，你会想 遍历线索。 而在孩子的每个元素 对应于不同的字母。 

因此，在孩子检查值 索引i，其中i代表 信的特定索引 你想插入。 好吧，如果这是null，那么你要 malloc的一个新节点，并有孩子 我指向该节点。 

如果它不为null，那么这意味着， ，鉴于分支，即给定 子，已经存在。 这样的话你只移动到 新的节点，然后继续。 如果你在单词的末尾的 你想在加载 字典，那么你可以设置 你是在为true当前节点。 

因此，让我们来看看插入的一个例子 单词“狐狸”到我们 字典。 假装我们开始 一个空的字典。 第一个字母F，将设 小儿指数五根 儿童数组。 因此，我们插入英寸 

然后字母O将在儿童 指标15，这楼后，再进行X 甚至会低于，分支 关中的O的孩子。 然后，因为X是最后一个字母 这个词的“狐狸”，那么我要去 颜色是绿色，表示 它是字的末尾。 在C语言中，这将被设定为 字布尔值true值。 

现在，如果下一个字，你是 加载中为单词“富”？ 那么，你不需要用malloc任何更多 空间F或为O，因为 那些已经存在。 但在foo中的最后2 O 那一个，你就必须对malloc。 使该新节点，设置 的是字布尔为true。 

所以，现在让我们将“狗”。狗会 先从根指数3 孩子，因为D有没有 尚未建立。 我们将遵循类似的过程， 之前，创建子狗， 哪来的G被染成绿色，因为 这是一个字的结尾。 

现在，如果我们要插入“做”什么？ 那么，这是狗的一个子串，所以 我们并不需要将malloc了。 但是，我们需要指出，我们已经 达到该字的结束。 所以O将被标记为绿色。 持续这一过程的每一个 词在你的字典中，你已经 在加载它们到任何你 哈希表或您的线索。 

speller.c将通过在字符串 dictionary.c进行检查。 现在，检查函数来操作 在不区分大小写。 这意味着，大写字母和 小写字母和两者的混合 应该都等同于真实的，如果任何 的该组合是在 字典。 您也可以假设字符串 只会包含字母 字符或单引号。 

因此，让我们看看如何可以检查 用哈希表结构。 好吧，如果存在的话，那么它 可以在哈希表中找到。 这样，那么你可以尝试寻找 单词在相关水桶。 

因此，这将斗那个词是？ 好了，你会得到多少，该索引 铲斗，通过散列该字 然后搜索在该链表， 在整个穿越 链表，使用String 比较功能。 

如果链表的末端是 达到了，这意味着你的光标 达到零，那么这个词是不是 在字典中找到。 它不会在任何其他桶。 所以在这里，你可能会看到怎么有可能 是具有两种之间的权衡 排序的链表或无序的。 要么会在需要更多的时间 检查过程中加载或更多的时间。 

你会如何​​检查 一个线索结构？ 我们将向下行进 在特里。 在输入单词的每个字母 我们正在检查，我们去了 对应于孩子元素。 

如果该元素为null，则该方法 有没有子 包含我们输入字，所以 单词拼写错误。 如果它不为空，我们可以移动到 我们是这个词的下一个字母 检查和继续这一进程 直到我们到达终点 的输入字。 然后我们可以检查 如果是的话是真实的。 如果是，那也不错。 这个词是正确的。 但如果没有，即使该子 存在于字典树，单词是 拼写错误。 

当函数大小被调用时，大小 应返回字的数目是 在你的字典中给出 数据结构。 所以，如果你正在使用一个哈希表，你 可以通过每一个 链表中的每一个 斗数着数 话在那里。 如果您使用的是特里，你可以 经过每一个非空 路径在您的线索。 或者你正在加载的字典，而 中，也许你可以保持跟踪如何 您正在加载英寸多的话 

一旦speller.c完成检查 对字典的文本文件，然后 它的完成，所以它调用卸载，其中 你的工作是什么自由 你已经malloced。 所以，如果你使用一个哈希表，那么你 需要特别小心，以避免 通过不释放任何内存泄漏 过早和持有到每 之前你免​​单链接。 

因此，对于在哈希表中的每一个元素 并在链表的每个节点， 你要释放该节点。 你怎么去释放 链表？ 设置您的节点指针光标 头部，以的开头 链表，那么当你的光标 不为空，你可以设置一个临时的 节点指针光标。 然后向前移动光标。 然后你就可以释放该临时 价值，同时仍坚持着 一切之后。 

如果您使用的是特里什么？ 那么做到这一点的最好办法 是从一卸 底部到顶部。 通过旅行到尽可能低的 节点，你可以释放所有指针 孩子，然后原路返回 向上，释放所有的所有元素 孩子阵列，直到 你打你的顶级根节点。 这里就是递归 会派上用场。 

为了确保你可能已经被释放 一切，你已经malloced， 您可以使用Valgrind的。 运行Valgrind的运行你的程序 计数的内存多少字节 你使用，并确保你已经 释放他们，告诉你 在那里你可能有 忘记了自由。 这样运行的，一旦Valgrind的告诉你 并为您提供了继续前进的话 你已经完成卸载。 

现在，一对夫妇的秘诀在你走之前 关闭并开始实施你的 字典。 我建议你​​通过在一个较小的 字典，当你试图测试 出来的东西和调试国内生产总值。 拼写检查器的用法。​​/拼写检查器，一个 可选的字典，然后一个文本。 

默认情况下，它在加载 大字典。 所以，你可能想通过在小 字典，或者甚至让你的 自己的，定制你的字典 和你的文本文件。 

然后最后，我也建议 拿一支笔和纸，画 东西出来之前，期间和之后 你写的所有代码。 只要确保你有 这些指针恰到好处。 

祝你好运。 一旦您完成后，如果你想 挑战大板和 看看你的程序是如何比较快 你的同学'，那么我鼓励 你检查出来。 

就这样，你已经完成了 在拼写检查PSET。 我的名字是Zamyla，这是CS50。