[音乐播放] ROB BOWDEN：你好。 我抢。 而且我们这个解决方案了。 所以在这里我们要实现 一个总表。 我们看到，我们的结构节点 表是要这个样子。 因此，这将有一个char字 数组大小长度+ 1。 不要忘了+1，因为最大 字在字典中是45 字符。 然后，我们将需要一个额外的 字符反斜杠零。 然后我们在每个哈希表 斗将要存储 节点链表。 我们没有做线性探测在这里。 所以为了链接到下一个 在桶的元素，我们需要一个 结构节点*未来。 确定。 所以，这就是一个节点的样子。 现在，这里是声明 我们的哈希表。 这将有16,834桶。 但这个数字其实并不重要。 最后，我们将有 全局变量哈希表大小，这 会作为零开始。 并且它会跟踪如何 许多词都在我们的字典。 因此，让我们来看看负荷。 请注意，负载，它返回一个布尔值。 您将返回true，如果它是成功的 加载，否则返回false。 它需要一个为const char *的字典， 这就是词典 我们要打开。 所以这是第一件事情 我们要做的。 我们要去给fopen的 字典阅读。 而我们将不得不作出 确保它成功了。 所以，如果它返回NULL，那么我们没有 成功打开词典。 我们需要返回false。 但假设它确实成功 开放的，那么我们要读取的 字典。 因此，保持循环，直到我们找到了一些 理由打破这种循环， 我们将拭目以待。 因此，保持循环。 现在我们要 malloc的一个节点。 ，当然，我们需要 宣扬再次检查。 所以，如果mallocing没有成功，那么 我们要卸载的任何节点，我们 碰巧的malloc之前，请关闭 字典和返回false。 但是忽略了，假设我们 成功了，那么我们要使用的fscanf 从读一个字我们 字典到我们的节点。 所以请记住该条目>字是字符 大小茸，加1字缓冲区 那我们要存储的单词英寸 所以的fscanf会返回1，只要 因为它能够成功地 从文件中读一个字。 如果任何一个错误发生，或者我们 到达文件的结尾，它 将不会返回1。 在这种情况下，它不会返回1， 我们终于要摆脱 这个while循环。 所以我们看到，一旦我们成功 读一个字到 入门>字，那么我们也要去那 词使用我们的哈希函数。 让我们来看看 散列函数。 所以，你并不真的需要 要理解这一点。 而实际上我们只是拉着这个散列 从互联网上起作用。 你需要认识到的唯一一件事就是 这需要为const char *字。 所以它采取一个字符串作为输入，并 返回一个unsigned int作为输出。 所以这就是所有的散列函数，它是 需要在输入和给你一个 索引的哈希表。 请注意，我们被NUM_BUCKETS模变， 使返回值 实际上是一个索引哈希表 并没有索引超出了 阵列的界限。 所以，有了该功能，我们将 散列，我们读单词 字典。 然后我们将使用 散列插入 进入哈希表。 现在，哈希表散列是当前 链接表列表中。 而且它很可能 它只是为NULL。 我们要插入我们在入口 开始这个链表中。 所以我们就要有我们目前的 切入点是什么哈希表 目前指向。 然后我们要保存， 在哈希表在 哈希，当前条目。 所以，这两条线插入成功 在本月初的入口 链表的索引处 在哈希表。 一旦我们与该做的，我们知道 我们发现了另一个字的 字典，我们增加了。 因此，我们继续这样做，直到的fscanf 最后在返回的东西非1 这一点请记住， 我们需要自由进入。 所以，在这里我们malloced一个条目。 我们试着读的东西 从字典。 我们没有成功地读 东西从字典中，在 我们需要释放进入这种情况下， 我们从来没有真正投入 哈希表，并最终破裂。 一旦我们突破了，我们需要看到的，好了， 我们没有打出来，因为有 从文件中读取的错误？ 还是我们打出来，因为我们 到达文件的末尾？ 如果有错误，则 我们要返回false。 由于负载没有成功。 而在这个过程中，我们要卸载 所有我们在阅读的话， 关闭字典文件。 假设我们没有成功，那么我们就 仍然需要关闭字典 文件，最后返回true，因为我们 成功加载字典。 这就是它的负载。 所以，现在检查，给定一个哈希表装， 是要这个样子。 因此，检查，它返回一个布尔值，它是 将指示是否通过 以char *的话，是否通过 字符串是在我们的字典。 因此，如果它是在字典中， 如果是在我们的哈希表中， 我们将返回true。 如果不是的话，我们将返回false。 鉴于这种通过在Word中，我们 要哈希的话。 现在认识到的重要一点是 在负载，我们知道，所有的 也就是说，我们要为小写。 但在这里，我们不是那么肯定。 如果我们看一看我们的哈希函数， 我们的哈希函数实际上 是下壳体的每个字符 的话。 所以不管资本化 总之，我们的哈希函数是返回 同样的指数无论 资本化，因为这将有 返回一个完全小写 版的字。 好吧。 这是我们的指数进入 哈希表这个词。 现在，这个for循环是要 遍历链表 这是该索引。 所以请注意，我们初始化入口 指向该索引。 我们将继续 而进入！= NULL。 请记住，更新指针 在我们的链接列表条目=项目>未来。 因此，有我们目前的切入点 在链表中的下一个项目。 因此，对于在该链接的表的每个条目， 我们将使用strcasecmp。 这不是STRCOMP。 因为再次，我们要 做事不区别大小写。 因此我们使用strcasecmp比较 这是通过这个词通过 对词功能 那就是在这个条目。 如果返回零，这意味着有 一个匹配，在这种情况下，我们希望 返回true。 我们成功地找到了 字在我们的哈希表。 如果有不匹配，那么我们 再次要循环，并期待在 下一个条目。 我们将继续循环，同时有 在此链表条目。 如果我们分手会发生什么 出这个for循环？ 这意味着我们没有发现一个条目， 匹配这个词，在这种情况下， 我们返回false，表明我们的 哈希表中没有包含这个词。 ，这是一个检查。 因此，让我们来看看大小。 现在，大小将是非常简单的。 因为记得在负载，每个字 我们发现，我们增加一个全球性的 可变的哈希表大小。 因此，大小功能只是去 返回全局变量。 就是这样。 现在，终于，我们需要卸载 字典曾经的一切的完成。 那么我们如何做到这一点？ 在这里我们要遍历 本表的所有桶。 因此，有NUM_BUCKETS桶。 并为每个链表我们 哈希表，我们将遍历 该链接的表的全部， 释放每个元素。 现在，我们必须要小心。 所以在这里，我们有一个临时变量 这是存储指针指向下一个 元件中的链表。 然后我们将免费 当前元素。 我们需要确保我们做到这一点，因为我们 不能只释放当前元素 然后再试着访问下一个指针， 因为一旦我们释放它， 内存变为无效。 因此，我们需要保持周围的指针 下一个元素，那么我们就可以释放 当前元素，然后我们就可以更新 我们目前的元素指向 下一个元素。 我们将循环而有元素 在此链表。 我们将做到这一点的所有链接 在哈希表中列出。 有一次，我们正在与该做的，我们已经 彻底卸载的哈希表，并 我们就大功告成了。 所以这是不可能的卸载 永远返回false。 而当我们完成后，我们 刚刚返回true。 让我们给这个方案一试。 因此，让我们来看看我们什么 结构节点的样子。 在这里，我们看到，我们就要有一个bool 字和一个结构节点*儿童 支架字母。 所以，你可能是第一件事情 想知道，为什么是字母 编辑定义为27？ 好了，记住，我们将需要 待处理的单引号。 所以这将是有点的 整个程序中的特殊情况。 现在还记得如何在特里 实际工作。 比方说，我们正在索引字 “猫”。然后从字典树的根， 我们要看看孩子 数组，我们要看看 对应于字母索引 C.这样会被索引2。 因此考虑到，那将 给我们一个新的节点。 然后我们将努力从该节点。 所以，有了这个节点，我们再次 去看看孩子们的数组。 而且我们要看看指数为零 对应于猫在A。 这样的话，我们会去到该节点， 并给予该节点我们将 来看看它到底是一个对应 到T和移动到该节点， 最后，我们已经完全看 通过我们的词“猫”。现在bool的 单词应该以指示是否 这个给定的字实际上是一个字。 那么，为什么我们需要这种特殊情况？ 什么样的词以及“灾难” 是在我们的字典，但 单词“猫”是不是？ 所以，看，看单词“猫” 在我们的字典，我们 要成功地去翻 该指数C-A-T的区域节点。 但是，这仅仅是因为灾难 发生在其上创建节点的方法 从C-A-T，一路 字的结尾。 所以布尔字被用来指示是否 这个特殊的位置 实际上表示一个字。 好的。 所以，现在我们知道它特里是什么 会是什么样子，让我们来看看 加载功能。 因此，负载将会返回一个bool 对于我们是否成功 不成功地加载的字典。 这将是字典 我们要加载。 我们是这样做的第一件事就是打开 了那本词典阅读。 我们必须确保 我们没有失败。 因此，如果在字典不 成功打开，它将返回 null，在这种情况下，我们 要返回false。 但假设它成功 开了，那么我们就可以真正阅读 通过字典。 我们将这样的第一件事 想要做的是我们有这个 全局变量的根。 现在根将是一个节点*。 这是我们的字典树的顶部，我们是 将要逐一查看。 所以我们要去的第一件事 想要做的是分配 内存为我们的根。 请注意，我们使用了释放calloc 功能，这是基本相同 作为malloc函数，除了它的 保证返回的东西是 完全归零。 因此，如果我们使用的malloc，我们需要 通过所有的指针我们 节点，并确保 它们都是空。 所以释放calloc会替我们。 现在，就像malloc的，我们需要做 确保分配竟是 成功的。 如果返回null，那么我们 需要关闭或字典 文件并返回false。 所以，假设分配是 成功，我们将使用一个节点* 游标遍历我们的线索。 所以，我们的根永远不会改变， 但我们要使用光标 实际上去从一个节点到另一个节点。 因此，在这个for循环，我们正在阅读 通过字典文件。 而我们使用的是龟etc。 龟etc是要抢单 字符从该文件。 我们要继续抓 虽然我们不到达的字符 该文件的末尾。 有两种情况，我们需要处理。 第一，如果字符 是不是一个新行。 所以我们知道，如果它是一个新行，然后 我们即将进入到一个新词。 但假设它不是一个新行，然后 在这里，我们想弄清楚的 指数我们要索引 在孩子阵列 我们看着面前。 所以，就像我之前说的，我们需要 特殊情况下的单引号。 我们正在使用的三元通知 运营商在这里。 所以，我们要读这个，因为如果 我们读到的字符是一个 单引号，那么我们要设置 指数=“字母”-1，这将 是该指数26。 否则，如果它不是一个单引号，有 我们要设置索引 等于c - 一个。 所以请记住先前对套回， C - 一个是要给我们 C的英文字母位置所以，如果 C是字母A，这将 给我们指数为零。 对于字母B，它会给 我们的索引1，依此类推。 因此，这给了我们中的索引 儿童阵列，我们想要的。 现在，如果该指数是目前在空 子，这意味着，一个节点 目前不存在 从该路径。 因此，我们需要分配 一个节点的路径。 这就是我们在这里做的。 所以，我们要再次使用释放calloc 功能，这样我们就不必 零出所有的指针。 而我们又需要检查 这释放calloc没有失败。 如果释放calloc会失败，那么我们就需要 卸载一切，我们关闭 字典，并返回false。 因此，假如它没有出现故障，则 这将创建一个新的子我们。 然后我们会去那个孩子。 我们的光标会遍历 下到那个孩子。 现在，如果这不是空，首先， 然后将光标可以只遍历 下到那个孩子没有实际 不必分配任何东西。 这是我们第一次发生的情况 分配单词“猫”。和 这意味着当我们去分配 “大灾难”，我们并不需要创建 再次为C-A-T的节点。 他们已经存在。 这是什么东西？ 这是其中c是条件 反斜杠N，其中c是一个新行。 这意味着我们已经成功 完成了一个字。 现在，我们究竟想要做的，当我们 成功地完成了一个字？ 我们将用这个词场 我们的内部结构的节点。 我们要设置为true。 以便表明该节点 表示成功 一句话，一个实际的单词。 现在设置为true。 我们要重设我们的光标点 在特里的开始了。 最后，增加我们的字典 大小，因为我们发现了另一个工作。 所以，我们要继续这样做， 在读取一个字符一个字符， 构建新的节点在我们的线索和 每个字在字典中，直到 我们终于到达C！= EOF，其中 情况下，我们打出来的文件。 现在有下2箱子 我们可能EOF打击。 如果有错误，首先是 读取该文件。 所以，如果有错误，我们 需要做的典型。 卸载一切，接近 该文件，返回false。 假设没有了一个错误，该 只是意味着我们实际上打的结尾 的文件，在这种情况下，我们关闭 文件，并返回true，因为我们 成功载入字典 进入我们的线索。 所以，现在让我们看看检查。 纵观检查功能，我们看到 该检查将要返回一个bool。 如果这个词，它是返回true 传递是在我们的线索。 它，否则返回false。 那么你是如何判断是否 这个词在我们的线索？ 我们在这里看到的是，就像以前一样， 我们将使用游标来遍历 通过我们的线索。 现在，在这里我们要遍历 在我们的整个字。 因此，迭代，我们过去的话， 我们要确定 索引的儿童阵列 对应词支架一所以这 是要完全一样 负载，其中，如果字[I] 是一个撇号，然后我们想 使用索引“字母” - 1。 因为我们确定了 就是我们要去的地方来存储 单引号。 否则我们将使用两个低字 支架一，因此请记住一句话就可以 具有任意大小写。 所以我们要确保我们 用一个事物的小写版本。 然后从'a'到一次减 再次给我们按字母顺序排列 该字符的位置。 所以这将是我们的索引 进入孩子们的数组。 而现在，如果该索引到孩子 数组为null，这意味着我们 不能再继续迭代 下来我们的线索。 如果是这样的话，这个词不能 可能是在我们的线索。 因为如果它是，这将 意味着将有一个路径 下到这个词。 而你永远不会遇到空。 所以遇到空，返回false。 的字不在字典中。 如果它不为null，那么我们 要继续迭代。 所以我们要在那里光标 以指向特定的 节点的索引处。 我们继续在整个这样做 整个单词，假设 我们从不打空。 这意味着我们能够获得通过 整个单词并找到 在我们的尝试的一个节点。 但我们还没有完全完成。 我们不希望只是返回true。 我们要返回游标>字。 由于再次记住，是“猫”不 在我们的字典，和“大灾难” ，那么我们会成功，我们得到 通过字“猫”。但光标 字会是假的，而不是真实的。 所以我们返回游标字来表示 是否该节点实际上是一个字。 就是这样的检查。 因此，让我们看看大小。 所以，大小将是很容易 因为，记得在负载，我们 递增的字典大小 我们遇到的每一个字。 所以，大小只是要 返回字典大小。 就是这样。 所以最后我们已经卸载。 所以卸载，我们将使用 递归函数实际上做 对我们的工作。 因此，我们的功能是要 算得上卸料。 什么是卸载怎么办？ 我们在这里看到的卸料器是要 遍历所有的儿童在 这个特殊的节点。 和如果该子节点不是 null，那么我们要 卸的子节点。 因此，这是你递归卸载 我们所有的孩子。 一旦我们确定我们的孩子 已经卸载，那么我们 可以释放自己，所以 卸载自己。 这将递归工作 卸载整个线索。 然后一旦这样做了， 我们可以只返回true。 卸载不能失败。 我们只是释放的东西。 所以一旦我们完成了解放 一切，返回true。 就是这样。 我的名字是罗布。 这是拼写检查。 [音乐播放]