Estic intentant implementar un Trie molt simple en Java que admet 3 operacions. M’agradaria tenir un mètode insert, un mètode has (és a dir, una paraula determinada en el trie) i un mètode toString per tornar el trie en forma de cadena. Crec que la inserció funciona correctament, però has i toString estan resultant ser difícils. Això és el que tinc fins ahora.Implementación de 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")); } } I el node de 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 ""; } } Així que, bàsicament, a l’crear un trie, 1 TrieNode es crea com l’arrel amb 26 nens. Quan s’intenta inserir, s’invoca a aquest node arrel, que recursivament crea un nou node en la posició correcta, i continua fins que la paraula es completa. Crec que aquest mètode està funcionant correctament.
La meva funció té molt trencada, perquè I té per tenir aquesta declaració de devolució fora dels parèntesis per alguna raó. No puc contenir-dins d’una clàusula else o el compilador es queixa. A part d’això, estic pensant que el mètode hauria de funcionar amb alguns ajustos, però no puc resoldre-ho per la meva vida.
toString és una bèstia que he intentat abordar, però res del que llanci funciona, així que el deixo fins que resolgui el problema. Si tinc funciona, puc trobar una manera de reformatar en una funció toString.
El propòsit d’int val = word.charAt (0) – 64; és perquè cada cadena ingressada ha de ser majúscula (crearé una funció de format de cadena per assegurar això després) perquè el valor int de la primera lletra – 64 sigui la seva posició en la matriu. és a dir, l’índex de matriu 0 és A, llavors A = 64, A – 64 = 0. B = 65, B – 64 = 1, i així successivament.