使用遞歸在Java中

我需要一個課堂作業寫與指定的方法簽名的方法雙向鏈表找到最小的元素：使用遞歸在Java中

public static <T extends Comparable<T>> T findSmallest(DoubleLinkedListADT<T> list)

的方法必須返回列表中的最小元素，它必須遞歸，我不能修改方法簽名，增長函數不能有超過n像個大O更大

這裏是我到目前爲止（O（nlogn）是不能接受的。）：

public static <T extends Comparable<T>> T findSmallest(DoubleLinkedListADT<T> list) { 

    if(list.isEmpty()){ 
     return null; 
    } 
    ListIterator<T> lit = list.listIterator(); 
    T smallest = lit.next(); 

    return search(lit, smallest); 
} 

private static <T extends Comparable<T>> T search(ListIterator<T> lit, T smallest){ 

    if(lit.hasNext()){ 
     if(smallest.compareTo(lit.next())==1){ 
      smallest = lit.previous(); 
      lit.next(); 
     } 
     search(lit, smallest); 
    } 
    return smallest; 
}

（不要擔心DoubleLinkedListADT，它是一個老師提供的接口。可以將DoubleLinkedList引用分配給DoubleLinkedListADT類型，它是它的子節點。）

這適用於空列表，單個元素列表和兩個元素列表。任何更大的東西都會失敗。我想我只是不理解遞歸，因爲我很困惑，因爲搜索方法中的第一個return語句不是返回到調用findSmallest類中的搜索的事實。它使用搜索中的最後一個返回調用，它使用最小的最小對象引用。

我不是在找別人給我正確的代碼。我想弄清楚爲什麼它在做什麼。

來源

2015-05-01 Khaines0625

放棄任何東西，包括做功課和上大學，去嘗試幾個簡單的遞歸函數來了解它們是如何工作的。 – pjsofts

findSmallest（list）= min（listHead，findSmallest（listTail））希望這個小提示能幫助:-) –

我會考慮的。 – Khaines0625

那麼，你的代碼是複雜的，所有雙鏈接爬行看起來很討厭。這裏是最優雅的解決方案，我能來與整數的列表：

public class Test { 

    public static Integer min(Iterator<Integer> it) { 
     if (it.hasNext()) { 
      return Math.min(it.next(), min(it)); 
     } 
     return Integer.MAX_VALUE; 
    } 

    public static void main(String[] args) { 
     System.out.println(min(Arrays.asList(2, 3, 1, 4, 5).iterator())); 
    } 
}

它適應於任何類型的列表應該很容易。

來源

2015-05-01 20:41:10

這是有道理的。謝謝。我會看看我是否可以爲我工作。 – Khaines0625

使用遞歸在Java中

回答

相關問題