努力寻找 TRIE 中的最小单词

Question

对于我可能犯的任何英语错误提前道歉。我有一个大学学校项目，我必须使用 trie 索引单词并具有多种功能来做多种事情。我正在用 C 编程。我做了一个递归函数来找到 trie 中最大的词并且它正在工作。这是函数：

int BiggestWord(ELEMENT *P)
{
    if (!P) return -1;
    int Alt_max = 0;
    for (int i = 0; i < MAX_VECTOR; i++)
        Alt_max = Biggest(BiggestWord(P->V[i]), Alt_max);
    return 1 + Alt_max;
}

'Biggest'只是一个returns两个值之间的最大值的函数。

现在求最小字函数。我正在考虑如何去做，并尝试检查单词何时结束寻找每个元素后的 'NULL'。这是我的尝试：

int SmallestWord(ELEMENT *P)
{
    if (!P) return -1;
    int Alt_min = 1;
    for (int i = 0; i < MAX_VECTOR; i++)
    {
        if(P->V[i] != NULL)
        {
           SmallestWord(P->V[i]);
           Alt_min++;
        }
    }
    return Alt_min;
}

我找不到让它工作的方法。我还想过尝试在每个单词之后指出单词的结尾，然后尝试遍历 trie 的每个分支并找到最小的单词。这是我第一个半年的编码，我发现在尝试学习它时遇到了一些困难。如果有人可以通过给我提示或尝试给我去哪里的线索来帮助我，我将非常感激，因为这是一个非常重要的项目，我必须完成并做好。

此外，我的数据结构如下：

#define MAX_VECTOR 26 // 我使用的字母表的 26 个字母

typedef struct ELEMENT
{
    int occurrences_word; // this is used for counting number of occurrences of a word
    struct ELEMENT *V[MAX_VECTOR];
} ELEMENT;

typedef struct TRIE
{
    ELEMENT *root_trie;
    int num_words;
} TRIE;

提前感谢所有帮助我的人此致

Answer 1

您可以将您的解决方案重复用于最大（最长 - 对吧？）字。

有 2 个主要区别：

使用 returns 最小而不是最大（最小而不是最大）的函数。您可以使用内置 min/max 函数或实现您自己的函数。
您需要“-1”的特殊情况，表示没有结果。它过去可以正常工作 longest，因为 max 函数会自动跳过它，但这里这个 -1 将立即作为最短的单词返回，所以你需要一个 IF.

代码：

int SmallestWord(ELEMENT *P)
{
  if (!P) return -1;
  int Alt_min = 1000000000;
  for (int i = 0; i < MAX_VECTOR; i++) {
    int candidate = SmallestWord(P->V[i]);
    if (candidate != -1)
      Alt_min = min(candidate, Alt_min);
  }
  return 1 + Alt_min;
}

Answer 2

我看不出有什么优雅的方法可以做到这一点。问题是 -1 表示空指针必须与表示短字的低数区别对待。

她是一个粗略但可行的解决方案：

int SmallestWord(ELEMENT *P)
{
  if (!P) return -1; 

  if(P->occurrences_word != 0) // this is the end of a word
    return 1;

  int Alt_min = -1;      
  for (int i = 0; i < MAX_VECTOR; i++)
    {
      int n = SmallestWord(P->V[i]);
    
      if(n!=-1)
        if(n<Alt_min || Alt_min == -1)
          Alt_min = n;
    }
  return 1 + Alt_min;
}

努力寻找 TRIE 中的最小单词

Struggling with finding the smallest word in a TRIE

c

function

trie