java - 在 Java 中更改对象引用

Question

我正在尝试用 Java 实现后缀特里树。一个特里树有一个根节点，并且连接到它的是边缘。但是，当实现诸如 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

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

考虑:

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

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

如果您正在更新子字符串方法中的 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); 
}