Java 用递归填充 3D 链表

Question

我在尝试填充 3D 链表时出现堆栈溢出。我不明白为什么它没有在指定的范围内停止，它只是永远运行。这可能是一个简单的错误，我只是不明白。

编辑：好的，我现在已经更新了代码并删除了那个愚蠢的错误，但是它仍然没有完全按预期运行。它似乎确实在生成 10x10x10 列表，但是它的运行是无限的。用 (10, 10, 10) 初始化，它应该创建 10000 个对象并停止。我只是想创建一个列表来表示 3d 坐标平面，每个整数坐标都是一个节点，可通过方向指针北、南、东、西、上或下访问。

感谢任何帮助

public class Main {


    public static void main(String[] args) {
        NodeController3D con = new NodeController3D(6,6, 6);

    }

}
public class Node3D {

//    public Node3D(Node3D... nodes) {
//        if (nodes.length != 5) {
//            throw new RuntimeException();
//        }
//        this.nodes = nodes;
//    }

    public Node3D[] nodes;
    public int x, y, z;


    public Node3D north() {
        return nodes[0];
    }

    public Node3D south() {
        return nodes[1];
    }

    public Node3D east() {
        return nodes[2];
    }

    public Node3D west() {
        return nodes[3];
    }

    public Node3D up() {
        return nodes[4];
    }

    public Node3D down() {
        return nodes[5];
    }
}

public class NodeController3D {

    public NodeController3D(int length, int width, int height) {
        HEAD = new Node3D();
        pnc(HEAD, length, width, height);
    }

    private void pnc(Node3D node, int xMax, int yMax, int zMax) {
        if(node.nodes == null) {
            node.nodes = new Node3D[5];
        }

        if (node.x < xMax) {
            Node3D newNode = node.nodes[2] = new Node3D();
            newNode.x = node.x + 1;
            newNode.y = node.y;
            newNode.z = node.z;
            System.out.println(newNode.x + ", " + newNode.y + ", " + newNode.z);

            pnc(newNode, xMax, yMax, zMax);
        }
        if (node.y < yMax) {
            Node3D newNode = node.nodes[0] = new Node3D();
            newNode.x = node.x;
            newNode.y = node.y + 1;
            newNode.z = node.z;

            pnc(newNode, xMax, yMax, zMax);
        }
        if (node.z < zMax) {
            Node3D newNode = node.nodes[4] = new Node3D();
            newNode.x = node.x;
            newNode.y = node.y;
            newNode.z = node.z + 1;

            pnc(newNode, xMax, yMax, zMax);
        }
    }

//    public NodeController3D(int radius) {
//
//    }

    public final Node3D HEAD;
}

编辑：好的，我现在已经更新了代码并删除了那个愚蠢的错误，但是它仍然没有完全按预期运行。它似乎确实在生成 10x10x10 列表，但是它的运行是无限的。用 (10, 10, 10) 初始化，它应该创建 10000 个对象并停止。我只是想创建一个列表来表示 3d 坐标平面，每个整数坐标都是一个节点，可通过方向指针访问。

Answer 1

您正在运行进入无限递归。

所以发生了什么。

您正在创建一个新的 Array。

if(node.nodes == null) {
   node.nodes = new Node3D[5];
}

您继续使用 Node3D 作为 newNode 变量。发生这种情况是因为 node.x<xMax 将为真。 -> Node3D newNode = node.nodes[2] = new Node3D();。

你现在递归调用 pnc，newNode。

那么现在发生的事情，node.y<yMax 将是真实的。现在您重新分配新节点。 Node3D newNode = node.nodes[0] = new Node3D();。并再次递归调用 pnc 。但是你运行现在遇到了麻烦。因为它是一个新的 Node3D，您的 node.x<xMax 将再次为真，并且这两个步骤将再次发生并无限期发生，直到您遇到上述错误。

要修复此错误，您可能需要将 node.x 和 node.y 复制到新创建的变量中。

通过改变赋值可以跳出无限递归

if (node.x < xMax) {
    if (node.nodes[2] == null) {
        node.nodes[2] = new Node3D();
    }
    Node3D newNode = node.nodes[2];
    newNode.x = node.x + 1;
    newNode.y = node.y;
    newNode.z = node.z;

    pnc(newNode, xMax, yMax, zMax);
}
if (node.y < yMax) {
    if (node.nodes[0] == null) {
        node.nodes[0] = new Node3D();
    }
    Node3D newNode = node.nodes[0];
    newNode.x = node.x;
    newNode.y = node.y + 1;
    newNode.z = node.z;

    pnc(newNode, xMax, yMax, zMax);
}
if (node.z < zMax) {
    if (node.nodes[4] == null) {
        node.nodes[4] = new Node3D();
    }
    Node3D newNode = node.nodes[4];
    newNode.x = node.x;
    newNode.y = node.y;
    newNode.z = node.z + 1;

    pnc(newNode, xMax, yMax, zMax);
}

但是因为我不知道你试图用你数组中这些特定索引处的这个特定元素来实现什么，这对你来说可能是一个错误的解决方案。

Answer 2

每当您创建一个新的 Node3D 时，变量 x、y 和 z 都不会被初始化，因此如果访问它们，它们将评估为 0。

在 pnc 方法中，总是会出现 x < xMax、y < yMax 或 z < zMax 的情况，因为它们都设置为 1。

一个好的做法是尽可能将变量设为私有和最终：

class Node3D {
    private final Node3D[] nodes;
    private final int x;
    private final int y;
    private final int z;

    public Node3D(int x, int y, int z) {
        this.nodes = new Node3D[6];
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

这将防止将来出现此类错误。您可以为变量创建 getter 方法。如果您确实需要重新分配 x、y 或 z 的值，您可以改为创建一个新的 Node3D，以便该对象可以保持不可变。

Answer 3

您以多种方式导航到 3D 网格中的节点。例如，您从 (1,0,0) 和 (0,1,0) 都去了 (1,1,0)，为同一坐标创建了副本。这样，您创建的节点数等于每个节点 cube paths 的总和。

另一种方法是填充节点的立方体，并为每个节点提供对它们所在立方体的引用。然后当您需要向北时，只需让立方体 return 向右节点，使用当前节点的坐标。您可以使用 Apache 的 MultiKeyMap 作为网格：

class Node3D {
    private static int instances = 0;
    public final int x;
    public final int y;
    public final int z;
    public final int number;
    public final MultiKeyMap<Integer, Node3D> gridMap;

    public Node3D(MultiKeyMap<Integer, Node3D> gridMap, int x, int y, int z) {
        this.gridMap = gridMap;
        this.x = x;
        this.y = y;
        this.z = z;
        this.number = instances++;
    }

    //Add/alter these methods according to your orientation
    //Returns null if no value is present, you might want to handle this
    public Node3D getNorthNode() {
        return gridMap.get(this.x + 1, this.y, this.z);
    }

    //Other getters omitted

    @Override
    public String toString() {
        return "Node3D#" + number + "[" + x + ", " + y + ", " + z + "]";
    }
}

现在可以按如下方式进行初始化：

    MultiKeyMap<Integer, Node3D> gridMap = new MultiKeyMap<>();
    for(int x = 0; x < xMax; x++) {
        for(int y = 0; y < yMax; y++) {
            for(int z = 0; z < zMax; z++) {
                gridMap.put(x, y, z, new Node3D(gridMap, x, y, z));
            }
        }
    }

    System.out.println(gridMap.get(4, 4, 4).getNorthNode());

Java 用递归填充 3D 链表

Java populating a 3D linked list with recursion

java

list

recursion

nodelist