2

我一直在尝试在 C 中实现将字符插入到 trie 数据结构中的基本功能。我一直在试图找出我做错了什么，但在最后一天左右我被难住了/卡住了。

这是我写的一些代码：

TR head = NULL;

void initDict () {
  head = NULL;
}

TR newNode (char item) {
  TR temp;
  temp = malloc (sizeof(*temp));
  temp->thisChar = item;
  temp->child = NULL;
  temp->sibling = NULL;
  return temp;
}


TR insertInOrder (char item, TR trie) {
  if (trie == NULL) {
    trie = newNode(item);
  } else if (trie->thisChar < item) {
        insertInOrder(item, trie->sibling);
    } else if (trie->thisChar > item) {
        char temp = trie->thisChar;
        trie->thisChar = item;
        insertInOrder(temp, trie->sibling);
    }
    return trie;
}

void insert (char *word) {
  char letter = *word;
    TR temp = NULL;

    while (*word != '\0') {
        letter = *word;
        if (head == NULL) {
            head = newNode(letter);
            temp = head->child;
            word++;
        } else {
            temp = insertInOrder(letter, temp);
            temp->child = head->child;
            head->child = temp;
            word++;
        }
    }
}

我想不通这个...

PS checkLetter，是一个布尔函数，检查字母是否已经在trie里面（通过遍历trie结构，即trie = trie->sibling）

任何帮助将不胜感激=]

干杯!

编辑：更改了我的代码，以便 insertInOrder 返回一个值，但由于 insert 是一个 void 函数并且必须保持一个 void 函数，我不知道有一种方法可以将节点进一步插入到 trie 的头部（即 head ->孩子，头->孩子->孩子等）

4

2 回答 2

1

在您的 insertInOrder 函数开始时，您检查是否需要分配一个新节点。然后，如果需要，您分配一个新节点，但您将新节点的地址存储在本地，一旦您返回，该地址就会消失。

感觉也许 insertInOrder 函数应该返回一个插入的 TR 有用？

于 2011-05-18T09:28:14.547 回答
1

你可以重新考虑你的插入算法:-)

我不是很好的老师，所以我只是给你解决方案，没有任何好的动机。虽然这没有编译和验证，但可以将其视为伪代码，让您了解我认为更好的算法，它可以处理您似乎错过的一些极端情况，并以不同的方式使用“头”指针来产生更一致的算法：

// 'head' is assumed to be a valid pointer, its 'child' field either NULL or a valid 
// pointer
TR currentNode = head;
while ( *word )
{
    assert(currentNode != NULL);

    if ( currentNode->child == NULL || currentNode->child->thisChar < *word )
    {
        // We need to insert a new node first in the child list
        TR newNode = malloc(sizeof *currentNode);
        newNode->thisChar = *word;
        newNode->sibling = currentNode->child;
        newNode->child = NULL;
        currentNode->child = newNode;
        currentNode = newNode;
    }
    else
    {
        // Find the place to insert next node
        currentNode = currentNode->child;
        while ( currentNode->sibling && currentNode->thisChar < *word )
            currentNode = currentNode->sibling;

        // If the current node already represents current character, we're done
        // Otherwise, insert a new node between the current node and its sibling
        if ( currentNode->thisChar != *word )
        {
            TR newNode = malloc(sizeof *currentNode);
            newNode->thisChar = *word;
            newNode->child = NULL;
            newNode->sibling = currentNode->sibling;
            currentNode->sibling = newNode;
            currentNode = newNode;
        }
    }
    word++;
}
于 2011-05-18T13:54:23.633 回答