c - 在C中的O(N)中搜索Trie

您如何遍历C中O（n）时间的特里。我想到做一个for循环，如果匹配到一个字母，则通过1级搜索根链表，然后搜索该链表，但会给我n ^ 2次有什么办法可以加快速度吗？

谢谢！

最佳答案

“ O（n）”中使用的“ n”是什么？如果n表示搜索字符串中的字符数，则可以在O（n）时间执行以下代码。

/* structure of Trie node */
struct trieNode {
   char *value;
   childNode children();
   int childCount;
}

/* structure for childnode in a Trie node. Whichi contains 'key' and pointer to child node */
struct childNode {
   char key;
   trieNode *node;
}


/* setup Trie and search string. (not real code) */
trieNode root=createTrinode(...) ; /* Setup Trie of your problem. */
char* searchString = inputSearchString(...); /* get string for search */

int i;
trieNode curNode;

curNode = root;
for i=0 to len(searchString)-1
{
    curNode = findChildren(curNode,searchString(i)); /* findChildren function returns childnode of first argument, whose key is equal to second argument.  (Code of findChildren is omitted) */
}

/* curNode is the traversed leaf node by  searchStrin */

for循环的索引为0到n（searchString的长度）-1，因此此代码可能执行jn O（n）次。

此代码不考虑给定Trie中不包含serach-string的情况。

关于c - 在C中的O(N)中搜索Trie，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26209020/