Матрица двусвязных узлов

Question

Я пытаюсь сделать матрицу 11 × 11 узлов с двойным связыванием узлов в Java, но у меня есть проблема, я связал узлы с правым, левым и нижним узлом, но когда я пытаюсь соединиться с восходящим узлом, я простоне могу, и когда я пытаюсь получить, например, node.up, я получаю нулевое значение вместо того, чтобы получить 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 вы должны создать 121 Nodes, но я проверил, и вы на самом деле создаете 705 431!

К счастью, это довольно простое решение.Создайте двумерный массив из 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

Я полагаю, что это результат, который вы ожидали.