2015-11-01 124 views
0

我在創建此遞歸方法時遇到問題。該方法需要將對象添加到堆棧。遞歸問題

備註: 這是一個路徑查找器項目。

getNextBird()民意調查來自鳥類物體內的鳥類隊列。如果隊列是空的,它將返回null;如果它不是空的,它會返回隊列中的下一隻鳥。

我根本無法使用任何循環。 (如果可以的話,本來很容易。) 堆棧中的最後一個元素必須是Bird「end」。但是,如果代碼工作正常,它應該遞歸地完成。

我的問題是,有一個邊界情況下,支票撞牆getNextBird變爲null(在這種情況下,對象鳥),我想從堆棧中彈出最新的對象。我將得到一個StackOverflow錯誤或一個EmptyCollection錯誤。

private static boolean recurse(Stack<Bird> path, Bird current, Bird end) 
{ 
    Bird bird = null; 
    if (current != null) { 
     bird = current.getNextBird(); 
     if (bird != null) { 
      path.push(current); 
      recurse(path, bird, end); 
      return true; 
     } 
    } 
    return false; 
} 

import java.util.Stack;

public class Solve2 
{ 
    public static void main(String [] args) 
    { 
    // create the maze to solve 
    Maze maze = new Maze(); 

    // create a Stack of Bird objects named path here 
    Stack<Bird> path = new Stack<Bird>(); 

    // call recursive method to solve the maze and print the path 
    recurse(path, maze.getStart(), maze.getEnd()); 
    print(path); 
    } 


    private static boolean recurse(Stack<Bird> path, Bird current, Bird end) 
    { 
     Bird bird = null; 
     if (current != null) { 
      bird = current.getNextBird(); 
      if (bird != null) { 
       path.push(current); 
       recurse(path, bird, end); 
       return true; 
      } else { 
       path.pop(); 
       recurse(path, path.peek(), end); 
       return false; 
      } 
     } 
     return false; 
    } 


    private static void print(Stack<Bird> stack) 
    { 
    // write your code for recursively printing the stack here 
System.out.println(stack.pop()); 
print(stack); 

    } 

} 

鳥類:

public class Bird 
{ 
    public static final int N = 0; 
    public static final int NE = 1; 
    public static final int E = 2; 
    public static final int SE = 3; 
    public static final int S = 4; 
    public static final int SW = 5; 
    public static final int W = 6; 
    public static final int NW = 7; 

    private static final String [] directions = {"N ", "NE", "E ", "SE", "S ", "SW", "W ", "NW"}; 

    private String name; 
    private int direction; 
    private Queue<Bird> queue; 

    public Bird(int row, int column, int direction) 
    { 
    this.name = "Row/Column [" + row + "][" + column + "]"; 
    this.direction = direction; 
    } 

    public void setBirdQueue(Queue<Bird> queue) 
    { 
    this.queue = queue; 
    } 

    public String toString() 
    { 
    return "Location: " + name + ", Direction: " + directions[direction]; 
    } 

    public int getDirection() 
    { 
    return this.direction; 
    } 
    public Bird getNextBird() 
    { 
    // write code to return the next Bird from the queue or null if no Birds left. 
     return queue.poll(); 
    } 
} 

進口java.util.LinkedList中; import java.util.Queue;

public class Maze 
{ 
    private Bird start; 
    private Bird end; 

    public Maze() 
    { 
    // construct the diagrammed maze 
    int MAX_ROW = 5; 
    int MAX_COL = 7; 
    Bird [][] maze = new Bird[MAX_ROW][MAX_COL]; 

    // row 0 
    maze[0][0] = new Bird(0, 0, Bird.S); 
    maze[0][1] = new Bird(0, 1, Bird.SW); 
    maze[0][2] = new Bird(0, 2, Bird.S); 
    maze[0][3] = new Bird(0, 3, Bird.SE); 
    maze[0][4] = new Bird(0, 4, Bird.SW); 
    maze[0][5] = new Bird(0, 5, Bird.SW); 
    maze[0][6] = new Bird(0, 6, Bird.SW); 

    // row 1 
    maze[1][0] = new Bird(1, 0, Bird.S); 
    maze[1][1] = new Bird(1, 1, Bird.W); 
    maze[1][2] = new Bird(1, 2, Bird.SW); 
    maze[1][3] = new Bird(1, 3, Bird.S); 
    maze[1][4] = new Bird(1, 4, Bird.N); 
    maze[1][5] = new Bird(1, 5, Bird.S); 
    maze[1][6] = new Bird(1, 6, Bird.W); 

    // row 2 
    maze[2][0] = new Bird(2, 0, Bird.NE); 
    maze[2][1] = new Bird(2, 1, Bird.NW); 
    maze[2][2] = new Bird(2, 2, Bird.N); 
    maze[2][3] = new Bird(2, 3, Bird.W); 
    maze[2][4] = new Bird(2, 4, Bird.SE); 
    maze[2][5] = new Bird(2, 5, Bird.NE); 
    maze[2][6] = new Bird(2, 6, Bird.E); 

    // row 3 
    maze[3][0] = new Bird(3, 0, Bird.SE); 
    maze[3][1] = new Bird(3, 1, Bird.NE); 
    maze[3][2] = new Bird(3, 2, Bird.E); 
    maze[3][3] = new Bird(3, 3, Bird.NW); 
    maze[3][4] = new Bird(3, 4, Bird.NW); 
    maze[3][5] = new Bird(3, 5, Bird.E); 
    maze[3][6] = new Bird(3, 6, Bird.W); 

    // row 4 
    maze[4][0] = new Bird(4, 0, Bird.N); 
    maze[4][1] = new Bird(4, 1, Bird.NE); 
    maze[4][2] = new Bird(4, 2, Bird.N); 
    maze[4][3] = new Bird(4, 3, Bird.N); 
    maze[4][4] = new Bird(4, 4, Bird.NE); 
    maze[4][5] = new Bird(4, 5, Bird.W); 
    maze[4][6] = new Bird(4, 6, Bird.N); 

    start = maze[2][0]; 
    end = maze[2][6]; 

    // write your code here 
    /*snipped the logic for adding the birds in the queue, but I do know that this part is 100% functional on my end*/ 
    } 

    public Bird getStart() 
    { 
    return this.start; 
    } 

    public Bird getEnd() 
    { 
    return this.end; 
    } 

} 
+0

什麼是禽流數據結構?以及你的輸入數據是什麼。也許你已經創建了某種循環,並且一次又一次地去同一只鳥?......如果你在中間添加System.out.println(鳥)會很有用。 – Rumoku

+0

您能否提供堆棧跟蹤和邊界案例? –

+0

@mst它不會一遍又一遍地循環同一只鳥。 –

回答

2

好了,有一件事我看到你已經通過在遞歸參數end但從未使用過。

遞歸的一個關鍵是有一個控制語句這將導致遞歸中斷和返回正確的事情或什麼都沒有。您隨機返回true和false(或者可能存在邏輯),它不會爲您的執行路徑添加任何值。

所以,讓我們做一個不同的方式:

  1. ,除非你需要它,讓你有當您打印只彈出不要在壓棧任何東西。你需要推入的第一隻鳥是最後一隻鳥匹配表達(current == end)
  2. 如果這隻鳥沒有返回前一隻鳥的東西,表明路徑被阻塞。現在爲了與此匹配,在步驟1中,如果(current == end)返回了前一隻鳥的某個物體,表明找到了最後一隻鳥,並將其連同第一隻鳥中的每隻鳥都傳給它。

僞代碼:

recursive(stack, current, end) 
{ 
    if(current == end){ 
     stack.push(current); //push the final bird 
     return true; //indication that final is found 
    } 
    else if(current.getNext() != null){ 
     result = recurse(stack, current.getNext(), end); //recurse 
     if(result == true) 
      stack.push(current); // using indication from the chain 

     return result; 
    } 

    return false; 
} 
+0

這是真的,你是對的!但我的問題是我如何推進,並彈出堆棧。因爲該方法中堆棧不應該變空,所以應該只刪除不需要的鳥類物體。 –

+0

是什麼讓鳥不需要? –

+0

因此,如果鳥類隊列中的下一隻鳥(它位於每個鳥類物體內部,並且使用getNextBird調用),在沒有達到最終鳥類的情況下變爲null,則該特定鳥類物體將從堆棧中移除。此外,代碼中使用的包裝的鍵盤快捷鍵是什麼? –