在Java中更改对象引用

Question

我试图在Java中实现一个后缀trie。trie有一个根节点，与之相连的是边。但是，当实现诸如constructTrie(T)（在给定字符串T的情况下构造一个trie）或substring(S,T)（检查S是否是T的子字符串）之类的函数时，我会保留一个当前节点cNode，它在整个代码中根据我考虑的节点而变化

我不确定是否正确更改了cNode的值。下面是类Trie

import java.util.*;

class Trie{

    protected Node root = null;

    public Trie(){
        Node n = new Node();
        root = n;
    }

    // Constructs a trie for a given string T
    public void constructTrie(String T){
        ArrayList<String> suffixArray = new ArrayList<String>();
        T += "#"; // Terminator
        int length = T.length();
        // Creates suffix array and removes first letter with every iteration
        for(int i=0; i<length; i++){
            suffixArray.add(T);
            T = T.substring(1); 
        }

        // Goes through suffix array
        for(int i=0; i<length; i++){  
            Node cNode = null; 
            cNode = root; // Current node
            int j = 0;
            // Goes through each letter of an entry in the suffix array
            while(j < (suffixArray.get(i)).length()){ 
                int index = cNode.findEdge((suffixArray.get(i)).charAt(j));
                // If an edge is found at the root with the current letter, update cNode and remove the letter from word
                if(index != -1){
                    cNode = cNode.getEdge(index).getNode(); // Gets node pointed at by edge and sets it as current node
                    String replace = (suffixArray.get(i)).substring(1);
                    suffixArray.set(0, replace); // Erases first letter of suffix
                    j++;
                    System.out.println(i + " " + j +  " " + replace);
                }
                // If an edge is not found at the root, write the whole word
                else{ 
                    for(int k=0; k<(suffixArray.get(i)).length(); k++){
                        Edge e = new Edge((suffixArray.get(i)).charAt(k)); // Creates edge with current letter of current entry of the suffix array
                        Node n = new Node(); // Creates node to be pointed at by edge
                        e.setNode(n);
                        cNode.newEdge(e);
                        cNode = n; // Updates current node
                    }
                    j = (suffixArray.get(i)).length(); // If the word is written, we break from the while and move on to the next suffix array entry
                }
            }
        }
    }

    // Checks if S is a substring of T
    public boolean substring(String S, String T){
        constructTrie(T);
        Node cNode = null;
        cNode = root;

        int index;
        for(int i=0; i<S.length(); i++){
            index = cNode.findEdge(S.charAt(i));
            if(index == -1)
                return false; // Substring was not found because a path was not followed
            cNode = (cNode.getEdge(index)).getNode(); // Reset current node to the next node in the path
        }
        return true; // Substring was found
    }

具体来说，是否允许我将Node root = null设置为类变量，在创建Trie类型的对象时初始化root，并更改cNode，如方法中所示？代码编译时没有错误，但是测试时它并不总是输出正确的响应，例如，测试时，它输出的“es”不是“pest”的子字符串

Answer 1

更新类的方法中的字段会使类不是线程安全的。您的方法有一些副作用，这些副作用可能不是您的类的用户所期望的

考虑：

 Trie t = new Trie("My String");

 boolean startsWithMy = t.substring("My");
 boolean startsWithMyString = t.substring("My String");

如果您正在更新substring方法中的root字段，那么第二次调用将不会执行预期的操作，因为第一次子字符串调用更改了Trie

如果您想创建一个易于使用且副作用最小的可重用类，那么我将按照以下基本模式编写您的类：

public class Trie {
     private final Node root;

     public Trie(String input) {
         // Construct the Trie here and assign it to root:
         this.root = constructTry(input);
     }

     public boolean substring(String part) {
         // Create a local Node variable:
         Node currentNode = root;

         // Navigate the Trie here using currentNode:
         // ...

         return result;
     }
}

您甚至可以添加一个方法（如果需要）来返回Trie的子部分：

public Trie subTrie(String part) {
    // Find the Node here that matches the substring part, and return it.
    // If nothing found, then throw NoSuchElementException or return null.

    Node subNode = findNode(part);

    if (subNode == null) {
        throw new NoSuchElementException("No element starting with: " + part);
    }

    // Constructs a new Trie with a different root node using a 2nd constructor option
    return new Trie(subNode); 
}

Answer 2

您正在通过向根节点添加垃圾来更改其引用。 假设你这样做：

 Trie trie = new Trie();
 trie.substring("es", "pest"); // this returns true. 

但如果你这样做了

 Trie trie = new Trie();
 trie.substring("es", "pest");  
 trie.substring("te", "Master"); 

您对子字符串的第二次调用将在最后一次调用离开的地方进行。您的根已经初始化，并且包含单词“pest”root(p, e, s, t, #)的树。在第二次调用之后，不是像预期的那样使用root(M, a, s, t, e, r, #)，而是使用root(p, e, s, t, #, M, a, r)。这是一个完全不同的词。因此te不是pest#Mar的子串

但如果您根据@john16384实施，您将被迫执行以下操作，以消除副作用：

 Trie trie = new Trie("pest");
 trie.substring("es"); // this returns true. 

 trie = new Trie("Master");
 trie.substring("te") // this returns true. 

这样做总是迫使你从一个干净的根开始。请参见下面的实现：

 class Trie {

protected Node root = null;

public Trie(String T) {
    root = constructTrie(T);
}

// Constructs a trie for a given string T
private Node constructTrie(String T) {
    ArrayList<String> suffixArray = new ArrayList<String>();
    T += "#"; // Terminator
    int length = T.length();
    // Creates suffix array and removes first letter with every iteration
    for (int i = 0; i < length; i++) {
        suffixArray.add(T);
        T = T.substring(1);
    }
    Node localRoot = new Node();
    // Goes through suffix array
    for (int i = 0; i < length; i++) {
        Node cNode = localRoot;
        int j = 0;
        // Goes through each letter of an entry in the suffix array
        while (j < (suffixArray.get(i)).length()) {
            int index = cNode.findEdge((suffixArray.get(i)).charAt(j));
            // If an edge is found at the root with the current letter, update cNode and remove the letter from word
            if (index != -1) {
                cNode = cNode.getEdge(index).getNode(); // Gets node pointed at by edge and sets it as current node
                String replace = (suffixArray.get(i)).substring(1);
                suffixArray.set(0, replace); // Erases first letter of suffix
                j++;
                System.out.println(i + " " + j + " " + replace);
            }
            // If an edge is not found at the root, write the whole word
            else {
                for (int k = 0; k < (suffixArray.get(i)).length(); k++) {
                    Edge e = new Edge((suffixArray.get(i)).charAt(k)); // Creates edge with current letter of current entry of the suffix array
                    Node n = new Node(); // Creates node to be pointed at by edge
                    e.setNode(n);
                    cNode.newEdge(e);
                    cNode = n; // Updates current node
                }
                j = (suffixArray.get(i)).length(); // If the word is written, we break from the while and move on to the next suffix array entry
            }
        }
    }
    return localRoot;
}

// Checks if S is a substring of T
public boolean substring(String S) {
    Node cNode = root;
    int index;
    for (int i = 0; i < S.length(); i++) {
        index = cNode.findEdge(S.charAt(i));
        if (index == -1)
            return false; // Substring was not found because a path was not followed
        cNode = (cNode.getEdge(index)).getNode(); // Reset current node to the next node in the path
    }
    return true; // Substring was found
}
}