Sto cercando di implementare un trie molto semplice in Java che ammette 3 operazioni. Mi piacerebbe avere un metodo di inserimento, un metodo ha (cioè una parola determinata nel trie) e un metodo di tosting per restituire il trie a forma di catena. Penso che l’inserimento funzioni correttamente, ma ha e la toutring è difficile. Questo è quello che ho finora. Trie
la classe trie.
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")); } } e il nodo di classe
public class TrieNode { //make child nodes private TrieNode c; //flag for end of word private boolean flag = false; public TrieNode() { c = new TrieNode; //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 == null) { c = 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.insert(word.substring(1)); } else { c.flag = true; } } public boolean has(String word) { int val = word.charAt(0) - 64; if (c!=null && word.length()>1) { c.has(word.substring(1)); } else if (c.flag==true && word.length()==1) { return true; } return false; } public String toString() { return ""; } } Così, fondamentalmente, quando si crea un trie, un trineo viene creato come radice con 26 bambini. Quando si tenta di inserire, viene invocato a quel nodo root, che crea ricorsivamente un nuovo nodo nella posizione corretta e continua fino a completare la parola. Penso che il metodo funzioni correttamente.
La mia funzione è molto rotta, perché devo avere quella dichiarazione di ritorno al di fuori delle parentesi per qualche motivo. Non posso contenerlo all’interno di una clausola else o il compilatore si lamenta. A parte questo, sto pensando che il metodo dovrebbe funzionare con alcuni aggiustamenti, ma non posso risolverlo a causa della mia vita.
Tosting è una bestia che ho provato ad affrontare, ma niente di ciò che è Gruppi funziona, quindi cosa lascio finché non risolve il problema. Se lo faccio funzioni, posso trovare un modo per riformattarlo in una funzione di tosting.
lo scopo di int val = word.charat (0) – 64; È perché ogni catena ammessa deve essere maiuscola (creerò una funzione di formattazione stringa per assicurarti questo) in modo che il valore int della prima lettera – 64 sia la sua posizione nella matrice. Cioè, la velocità della matrice 0 è A, quindi A = 64, A – 64 = 0. B = 65, B – 64 = 1, e così via.