双链接节点的矩阵

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; 
} 
}
// link UP
static void linkUp(Node head) { 
// pointer to move right 
Node Rp; 
// pointer to move down 
Node Dp = head; 
Node aux;
// loop till node->down is not NULL 
while (Dp != null) { 
Rp = Dp; 
// loop till node->right is not NULL 
while (Rp != null) { 
aux = Rp.down;
if(aux==null){
}else{
aux.up = Rp;
}
Rp = Rp.right; 
} 
Dp = Dp.down; 
}
}
static void hunter(Node head,int x, int y) { 
Node arr,aba,izq,der;
boolean out = false;
// 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) { 
if(Rp.xpos==x-1 && Rp.ypos==y-1){
Rp.hunter = true;
arr=Rp.up;
if(arr==null){
System.out.println("No link up");
}else{
System.out.println(arr.no);
}
aba=Rp.down;
izq=Rp.left;
der=Rp.right;
System.out.println(" "+izq.no+" "+aba.no+" "+der.no);
out=true;
}
if(out==true){
break;
}
Rp = Rp.right; 
} 
if(out==true){
break;
}
Dp = Dp.down; 
} 
}            
// driver program 
public static void main(String args[]) { 
// 2D matrix 
int arr[][]= new int[11][11];
int no=1;
for(int i=0;i<11;i++){
for(int j=0;j<11;j++){
arr[i][j] = no;
no=no+1;
}
}
int m = 11, n = 11; 
Node head = construct(arr, 0, 0, m, n); 
linkUp(head);
linkLeft(head);
display(head); 
System.out.println("I should get: 38 48 60 50 but i get: ");
hunter(head,5,5);
}
}

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网格应该创建121Nodes，您可以看到问题有多严重，但我检查了一下，您实际上创建了705431！

幸运的是，修复相当简单。创建一个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

我相信这是你所期望的结果。