双向链接节点矩阵

Question

我正在尝试在 Java 中创建一个 11 x 11 的节点矩阵双向链接节点，但我有一个问题，我将节点链接到右、左和下节点，但是当我尝试链接到上节点时，我就是不能例如，当我尝试获取 node.up 时，我得到了一个 null 而不是得到一个 int（我应该得到）。

无论如何，这是我的代码，希望有人可以帮助我。我猜错误可能在void linkUp().

public class CazadorPresa {

// node of linked list 

static class Node { 

    int no; 

    Node right; 

    Node down;  

    Node left;

    Node up;

    int xpos,ypos;

    public boolean hunter,prey,crossed,blocked;

}; 

// returns head pointer of linked list 

// constructed from 2D matrix 

static Node construct(int arr[][], int i, int j, int m, int n) { 

    // return if i or j is out of bounds 

    if (i > n - 1 || j > m - 1) 

        return null; 

    // create a new node for current i and j 

    // and recursively allocate its down and 

    // right pointers 

    Node temp = new Node();

    temp.no = arr[i][j]; 

    temp.xpos = j;

    temp.ypos = i;

    temp.blocked = false;

    temp.crossed = false;

    temp.hunter = false;

    temp.prey = false;

    temp.right = construct(arr, i, j + 1, m, n); 

    temp.down = construct(arr, i + 1, j, m, n); 

    return temp;

} 

// utility function for displaying 

// linked list data 

static void display(Node head) { 

    // pointer to move right 

    Node Rp; 

    // pointer to move down 

    Node Dp = head; 

    // loop till node->down is not NULL 

    while (Dp != null) { 

        Rp = Dp; 

        // loop till node->right is not NULL 

        while (Rp != null) { 

            System.out.print(Rp.no + " "); 

            Rp = Rp.right; 

        } 

        System.out.println(); 

        Dp = Dp.down; 

    } 

} 

// link left

static void linkLeft(Node head) { 

    Node Rp; 

    Node Dp = head; 

    Node auxL= head; 

    // loop till node->down is not NULL 

    while (Dp != null) { 

        Rp = Dp; 

        // loop till node->right is not NULL 

        while (Rp != null) { 

            if(Rp==Dp){

            }else{

                Rp.left = auxL;

                auxL = Rp;

            }

            Rp = Rp.right;    

        } 

        Dp = Dp.down; 

    } 

}

Answer 1

问题在于使用递归来构造Nodes. 当你这样做时：temp.right = construct(arr, i, j + 1, m, n);&nbsp;temp.down = construct(arr, i + 1, j, m, n);&nbsp;您实际上是在创建网格的多个版本，每个版本都会覆盖right和down链接Nodes已经创建的网格。例如，在构造之后，对于给定的 ，应该是这样的node：node.right.down == node.down.right但考虑到网格的构建方式，情况并非如此，当您尝试将它们连接起来时，这会导致问题。考虑到对于 11x11 网格，您应该创建 121 Nodes，您可以看到问题有多严重，但我检查过，您实际上正在创建 705,431！幸运的是，修复相当简单。创建一个 2d 数组Nodes并将它们直接连接起来：public static void main(String args[]) {&nbsp;&nbsp; &nbsp;// 2D matrix&nbsp;&nbsp; &nbsp;Node arr[][]= new Node[11][11];&nbsp; &nbsp;int m = 11, n = 11;&nbsp;&nbsp; &nbsp;int no=1;&nbsp; &nbsp;for(int i=0;i<m;i++){&nbsp; &nbsp; &nbsp; &nbsp;for(int j=0;j<n;j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;arr[i][j] = new Node();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;arr[i][j].no = no;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;arr[i][j].xpos = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;arr[i][j].ypos = i;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;no=no+1;&nbsp; &nbsp; &nbsp; &nbsp;}&nbsp; &nbsp;}&nbsp; &nbsp;for(int i=0; i<m; i++)&nbsp; &nbsp;{&nbsp; &nbsp; &nbsp;for(int j=0; j<n; j++)&nbsp; &nbsp; &nbsp;{&nbsp; &nbsp; &nbsp; &nbsp;arr[i][j].up&nbsp; &nbsp; = (i>0)&nbsp; &nbsp;? arr[i-1][j] : null;&nbsp; &nbsp; &nbsp; &nbsp;arr[i][j].left&nbsp; = (j>0)&nbsp; &nbsp;? arr[i][j-1] : null;&nbsp; &nbsp; &nbsp; &nbsp;arr[i][j].down&nbsp; = (i+1<m) ? arr[i+1][j] : null;&nbsp; &nbsp; &nbsp; &nbsp;arr[i][j].right = (j+1<n) ? arr[i][j+1] : null;&nbsp; &nbsp; &nbsp;}&nbsp; &nbsp;}&nbsp; &nbsp;Node head = arr[0][0];&nbsp; &nbsp;display(head);&nbsp;&nbsp; &nbsp;hunter(head,5,5);&nbsp; &nbsp;}}产生：38&nbsp;48 60 50我相信这是您期望的输出。