5

大学のプロジェクトでTrie (Java)を実装する必要があります。Trie は文字列を追加および削除できる必要があります (フェーズ 1 の場合)。

私はこれを行う方法を理解しようとして毎日（ここ数日間）数時間を費やしてきましたが、毎回惨めに失敗しました。

インターネット上の例と私の教科書 (Adam Drozdek による Java のデータ構造とアルゴリズム) は役に立ちません。

情報

  1. 私が使用しているノードクラス:

    class Node {
    public boolean isLeaf;
}

class internalNode extends Node {
    public String letters;  //letter[0] = '$' always.
    //See image -> if letter[1] = 'A' then children[1] refers to child node "AMMO"
    //See image -> if letter[2] = 'B' then children[2] refers to internal node "#EU"
    public TrieNode[] children = new TrieNode[2];

    public TrieInternalNode(char ch)
    {
        letters = "#" + String.valueOf(ch);//letter[0] = '$' always.
        isLeaf = false;
    }
}

class leafNode extends Node
{
    public String word;
    public TrieLeafNode(String word)
    {
        this.word = new String(word);
        isLeaf = true;
    }
}

  2. そして、ここに私が従う必要がある挿入の疑似コードがあります:(非常にあいまいであることを警告します)

    trieInsert(String K)
{
    i = 0;
    p = the root;
    while (not inserted)
    {
        if the end of word k is reached
            set the end-of-word marker in p to true;
        else if (p.ptrs[K[i]] == 0)
            create a leaf containing K and put its address in p.ptrs[K[i]];
        else if reference p.ptrs[K[i]] refers to a leaf
        {
            K_L = key in leaf p.ptrs[K[i]]
            do
            {
                create a nonleaf and put its address in p.ptrs[K[i]];
                p = the new nonleaf;
            } while (K[i] == K_L[i++]);
        }
        create a leaf containing K and put its address in p.ptrs[K[--i]];
        if the end of word k is reached
            set the end-of-word marker in p to true;
        else
            create a leaf containing K_L and put its address in p.ptrs[K_L[i]];
        else
            p = p.ptrs[K[i++]];
    }
}

  3. 次のメソッドを実装する必要があります。

    public boolean add(String word){...}//adds word to trie structure should return true if successful and false otherwise

public boolean remove(String word){...}//removes word from trie structure should return true if successful and false otherwise

  4. 削除の疑似コードが見つかりませんが、挿入が機能しない場合、削除は役に立ちません。

  5. これは、実装する必要がある Trie がどのように見えるかのイメージです。

ここに画像の説明を入力

  1. このように実装した場合、トライがまだ非効率になることは承知していますが、現時点では心配する必要はありません。

  2. この本は、私がする必要があることと同様の実装を提供しますが、単語の終わりの文字 (「$」) を使用せず、接頭辞なしで子ノードに単語を格納するだけですhttp://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java

制約

  1. Java でトライを実装する必要があります。
  2. Java の組み込みデータ構造をインポートまたは使用することはできません。(つまり、Map、HashMap、ArrayList などはありません)
  3. 配列、Java プリミティブ型、および Java 文字列を使用する場合があります。
  4. Trie は$、単語の終わりを示すために (ドル) 記号を使用する必要があります。（下の画像を参照）

ここに画像の説明を入力

  1. 記号を含む単語$が挿入されると思います。
  2. 本と同じスタイルで Trie it を実装する必要があります。
  3. 単語の大文字と小文字は関係ありません。すべての単語は小文字と見なされます
  4. トライは、単語の終わりの文字と単語に適用可能な文字のみを格納する必要があり、アルファベット全体ではありません (一部の実装のように)。

私は誰かが私のために実装を行うことを期待していません (彼らが横たわっていない限り:P) 私は本当に助けが必要です.

4

1 に答える 1