2

文字をCのトライデータ構造に挿入する基本機能を実装しようとしています。何が間違っているのかを理解しようとしていますが、最後の日かそこらで困惑/立ち往生しています。

私が書いたいくつかのコードを次に示します。

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 は、文字がすでにトライ内にあるかどうかをチェックするブール関数です (トライ構造をトラバースすることにより、つまり、トライ = トライ->兄弟)

任意の助けをいただければ幸いです=]

乾杯！

編集: コードを変更して、insertInOrder が値を返すようにしましたが、insert は void 関数であり、void 関数のままにしなければならないため、ノードをトライのヘッドにさらに挿入する方法がわかりません (つまり、ヘッド->子、頭->子->子など)

4

2 に答える 2

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 に答える
1

insertInOrder 関数の開始時に、新しいノードを割り当てる必要があるかどうかを確認します。次に、必要に応じて新しいノードを割り当てますが、新しいノードのアドレスをローカルに保存し、戻るとすぐに消えます。

insertInOrder 関数は、insert が何か良いことをする TR を返す必要があるのではないでしょうか?

于 2011-05-18T09:28:14.547 に答える