双向链接节点矩阵

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 leftstatic 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); 

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

您实际上是在创建网格的多个版本，每个版本都会覆盖right和down链接Nodes已经创建的网格。例如，在构造之后，对于给定的 ，应该是这样的node：

node.right.down == node.down.right

但考虑到网格的构建方式，情况并非如此，当您尝试将它们连接起来时，这会导致问题。考虑到对于 11x11 网格，您应该创建 121 Nodes，您可以看到问题有多严重，但我检查过，您实际上正在创建 705,431！

幸运的是，修复相当简单。创建一个 2d 数组Nodes并将它们直接连接起来：

public static void main(String args[]) { 

   // 2D matrix 

   Node arr[][]= new Node[11][11];

   int m = 11, n = 11; 

   int no=1;

   for(int i=0;i<m;i++){

       for(int j=0;j<n;j++){

         arr[i][j] = new Node();

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

         arr[i][j].xpos = j;

         arr[i][j].ypos = i;

         no=no+1;

       }

   }

   for(int i=0; i<m; i++)

   {

     for(int j=0; j<n; j++)

     {

       arr[i][j].up    = (i>0)   ? arr[i-1][j] : null;

       arr[i][j].left  = (j>0)   ? arr[i][j-1] : null;

       arr[i][j].down  = (i+1<m) ? arr[i+1][j] : null;

       arr[i][j].right = (j+1<n) ? arr[i][j+1] : null;

     }

   }

   Node head = arr[0][0];

   display(head); 

   hunter(head,5,5);

   }

}

产生：

38

 48 60 50

我相信这是您期望的输出。