Trie de la mise en œuvre

Je tente de mettre en œuvre très simple Trie en Java qui prend en charge 3 opérations. Je voudrais avoir une méthode insert, un a la méthode (c'est à dire un certain mot dans le trie), et une méthode toString pour retourner le trie dans la forme d'une chaîne. Je crois que j'ai insertion fonctionne correctement, mais a et toString sont avère difficile. Voici ce que j'ai jusqu'à présent.

Le trie de classe.


public class CaseInsensitiveTrie implements SimpleTrie {

    //root node
    private TrieNode r;

    public CaseInsensitiveTrie() {
        r = new TrieNode();
    }

    public boolean has(String word) throws InvalidArgumentUosException {
        return r.has(word);
    }

    public void insert(String word) throws InvalidArgumentUosException {
        r.insert(word);
    }

    public String toString() {
        return r.toString();
    }

    public static void main(String[] args) {

        CaseInsensitiveTrie t = new CaseInsensitiveTrie();

        System.out.println("Testing some strings");
        t.insert("TEST");
        t.insert("TATTER");
        System.out.println(t.has("TEST"));
    }
}

Et la classe de nœud


public class TrieNode {

    //make child nodes
    private TrieNode[] c;
    //flag for end of word
    private boolean flag = false;

    public TrieNode() {
        c = new TrieNode[26]; //1 for each letter in alphabet
    }

    protected void insert(String word) {
        int val = word.charAt(0) - 64;

        //if the value of the child node at val is null, make a new node
                //there to represent the letter
        if (c[val] == null) {
            c[val] = new TrieNode();
        }

        //if word length > 1, then word is not finished being added.
        //otherwise, set the flag to true so we know a word ends there.
        if (word.length() > 1) {
            c[val].insert(word.substring(1));
        } else {
            c[val].flag = true;
        }
    }

    public boolean has(String word) {
        int val = word.charAt(0) - 64;
        if (c[val]!=null && word.length()>1) {
            c[val].has(word.substring(1));
        } else if (c[val].flag==true && word.length()==1) {
            return true;
        }

        return false;
    }

    public String toString() { 
        return "";
    }
}

Donc en gros, lors de la création d'un Trie, un TrieNode est créé à la racine de avec 26 enfants. Lorsque l'insert est tenté, insérer est appelée sur ce nœud racine, qui de manière récursive crée un nouveau nœud à la position correcte, et continue jusqu'à ce que le mot est complet. Je crois que la méthode fonctionne correctement.

Mon a la fonction est très brisé, parce que je ont avoir que l'instruction de retour à l'extérieur des crochets pour une raison quelconque. Je ne peux pas le contenir à l'intérieur d'une autre clause ou le compilateur se plaint. Autre que cela, je pense que la méthode devrait fonctionner avec certains réglages, mais je ne peux pas le comprendre pour la vie de moi.

toString est une bête, j'ai essayé d'attaquer, mais rien de ce que je jeter à elle fonctionne, donc je vais laisser cela être jusqu'à ce que je résoudre le problème. Si je reçois a travail je pourrai peut-être trouver un moyen de le reformater en une fonction toString.

Le but de l'int val = mot.charAt(0) - 64; est parce que chaque chaîne entrée doit être en majuscule (je vais créer une chaîne de mise en forme de la fonction à assurer par la suite) ainsi, la première lettre de la valeur int - 64 sera sa position dans le tableau. ie tableau d'index 0 est Un, de sorte que A = 64, A - 64 = 0. B = 65, B - 64 = 1, et ainsi de suite.

Au lieu de: int val = word.charAt(0) - 64; vous n': int val = word.charAt(0) - 'A'; !
Est-il une raison pourquoi votre trie est de 26-ary? Pourquoi pensez-vous vous limiter à NOUS lettres majuscules? Ce qui se passe si une des touches d'avoir des espaces ou (Odin interdit) caractères internationaux?
Voici ma mise en œuvre, y compris addWord, getWordNumber, listAllDistinctWords, voir via: github.com/shaogbi/Java/blob/master/datastructure/MyTrie.java

OriginalL'auteur dc. | 2010-02-08

Leave a Reply

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *