Trie

Learning Goals

  • Learn 更多 关于数据结构
  • Work with a trie

puppies

背景

Imagine you just rescued a dog and you’re deciding on a名字。 You found a file online with a list of 关于 150 of the most popular dog names! You are curious as to whether or not the names you are considering are on this list. Since trie’s are great for data lookups, we’ve given you some (almost!) complete code in trie.c. There is one function, check, which is not yet implemented. Your job is to complete this function.

演示

入门

  1. Log into cs50.dev using your GitHub account.
  2. Click inside the terminal window and execute cd.
  3. Execute wget https://cdn.cs50.net/2022/fall/实验s/5/trie.zip followed by Enter in order to 下载 a zip called trie.zip in your codespace. Take care not to overlook the space between wget and the following URL, or any other character for that matter!
  4. Now execute unzip trie.zip to create 的文件夹中名为 trie.
  5. You 不再 need the ZIP file, so you can execute rm trie.zip and respond with “y” followed by Enter at the prompt.

实现细节

注意 the trie itself is implemented through the creative use of several structs called node. Each node in a trie has an array of (potential) children, with size 26—one potential child for each letter of the alphabet! Adding words to this trie, notice that—for every letter in a word—we 创建一个 new node child whose parent is either the root node (的 first letter) or the 上一页 letter (if not the first letter). On the very last letter, we set the is_word attribute of the child node to true. Now, checking if a word is in our trie is as easy as following each letter of that word through our trie. If we get to the final letter and see that is_word is true, well, that名字 is in our trie!

  • 提示
    • You probably want to start by setting a node pointer, cursor to the root of the trie.
    • Iterate through every letter in the argument word and, as you do, determine the array index that corresponds to that letter.
    • You can use the index for a letter to check if children[index] is a NULL pointer, 意思ing the word does not exist in the trie.
    • If children[index] is in fact a node, you can reset cursor to this node and check 的 下一页 letter in its children nodes.
    • Remember that the lookup should be 不区分大小写. For instance, A and a should correspond to 0, B and b corresponds to 1, etc.

Thought 问题

  • When might you want to use a trie as a data structure? When might you not?

如何测试 Your Code

你的程序应该 behave per the例子below.

trie/ $ ./trie dog_names.txt
Check word: Molly
Found!

trie/ $ ./trie dog_names.txt
Check word: Lucy
Found!

trie/ $ ./trie dog_names.txt
Check word: Prudence
Not Found.

No check50 for this one!

To evaluate that the style of your code, type in the following at the $ prompt.

style50 trie.c

如何提交

No need to 提交! This is a 练习题.