轉換數組的自定義LinkedList類使用遞歸

Question

我使用一個自定義的LinkedList類是這樣的：

public class LinkedList { 
    // Get and Set methods are NOT necessary! 

    private LinkedList next;  
    private final String word; 

    public LinkedList(String word, LinkedList next) { 
     this.word = word; 
     this.next = next; 
    } 

現在我的任務是寫這需要一個字符串數組的方法，和覆羽每個字符串對象變成一個LinkedList WITHOUT循環，所以使用遞歸。這怎麼能沒有循環完成？這對我來說是難以想象的。我從哪開始呢？

編輯：讓我澄清一下這個函數我應該寫只需要一個參數，該參數是一個字符串數組，並返回一個LinkedList ..

Answer 1

也許只是我，但我不喜歡任何提供的解決方案。

public static LinkedList Of(String[] input) { 
     if (input == null || input.length < 1) 
      return null; 
     return LinkedList.Of(input, input.length - 1); 
    } 

    public static LinkedList Of(String[] input, int i) { 
     if (i > 0) 
      return new LinkedList(input[i], LinkedList.Of(input, i - 1)); 
     return new LinkedList(input[i], null); 
    } 

下投票是可怕的，所以這裏是它的正確順序：

/** 
    * Creates linked list from array input. 
    * 
    * @param input 
    *   data array 
    * @return linked list with data 
    */ 
    public static LinkedList Of(String[] input) { 
     // Checks if array has elements. 
     if (input == null || input.length < 1) 
      return null; 
     // Starts creating the array using overload 2. 
     return LinkedList.Of(input, 0); 
    } 

    /** 
    * Creates linked list from array input (overload 2). 
    * 
    * @param input 
    *   data array 
    * @param i 
    *   counter to remember at what element is current 
    * @return linked list with data 
    */ 
    public static LinkedList Of(String[] input, int i) { 
     //Tests if counter is within array elements. 
     if (input.length - 1 > i) 
      // Returns new element with (current element data, reference 
      // to next element). Note that next element will be returned 
      // by this same method (this is why it is recursive). 
      return new LinkedList(input[i], LinkedList.Of(input, i + 1)); 
     //Last element. From here backtracking will begin. 
     return new LinkedList(input[i], null); 
    } 

這是後話了投票：

public String toString() { 
     StringBuilder sb = new StringBuilder(this.word); 
     LinkedList tmp = this; 
     while (tmp.next != null) { 
      sb.append(" > "); 
      tmp = tmp.next; 
      if (tmp.word != null) 
       sb.append(tmp.word); 
     } 
     return sb.toString(); 
    } 

，並測試：

String str = "Neque porro quisquam est qui dolorem ipsum quia " 
      + "dolor sit amet, consectetur, adipisci velit..."; 
    LinkedList ll = LinkedList.Of(str.split("\\s+")); 
    System.out.println(ll); 

Answer 2

我不知道用什麼語言你正在使用，但這裏有一個總體思路：

public LinkedList myfunction(String arr[]) { 
    if(arr.empty == true) 
     return void; 

    //return the array minus the first element 
    String shorterarray[] = substr(arr[],1); 

    //recursively create the next element 
    LinkedList myItem = new LinkedList(arr[0], myfunction(shorterarray[])); 
} 

你必須在做任何語言您使用的是subtring和邊界檢查。

Answer 3

如何：

public static void main(String[] args) { 
    String[] data = new String[] { "1", "2", "3" }; 

    LinkedList head = build(data); 
    while (head != null) { 
     System.out.println(head.word); 
     head = head.next; 
    } 
} 

private static LinkedList build(String[] data) { 
    if (data == null || data.length == 0) { 
     return null; 
    } 

    LinkedList head = new LinkedList(data[0], null); 
    build(head, data, 1); 
    return head; 
} 

private static LinkedList build(LinkedList node, String[] data, int index) { 
    if (index == data.length) { 
     return node; 
    } 

    node.next = build(new LinkedList(data[index], null), data, ++index); 
    return node; 
} 

private static class LinkedList { 
    private final String word; 
    private LinkedList next;  

    public LinkedList(String word, LinkedList next) { 
     this.word = word; 
     this.next = next; 
    } 
} 

要增加，這也可能是值得指出的是遞歸創建集合在實踐中是非常糟糕的 - 它可以很容易地吹出來的堆棧大小。

Answer 4

調用一個帶有三個參數的函數;源數組，數組中的當前位置和目標鏈接列表。

這是否讓你的頭去/你可以從那裏弄清楚？

Answer 5

試試這個：

private LinkedList formlist(LinkedList list, String[] str, int length, int i) { 
    if(i==length) 
     return list; 
    return formlist(new LinkedList (str[i],list),str,length,i+1); 

} 

Answer 6

好的，因爲有一個單一的m使用String []參數的方法。 這裏是一個java示例。 （基於以前的答案，但轉換爲Java）

private LinkedList build(String arr[]) { 
    if(arr.length == 0) 
     return null; 

    //return the array minus the first element 
    String shorterarray[] = Arrays.copyOfRange(arr, 1, arr.length); 

    //recursively create the next element 
    return new LinkedList(arr[0], build(shorterarray)); 
} 

Answer 7

首先，什麼都可以用迭代（循環）你可以用遞歸，反之亦然做（儘管沒有尾調用消除，一些Java的沒有按沒有，遞歸往往比迭代更昂貴）。

當試圖找出如何遞歸地解決問題時，您想弄清楚如何中斷一個或多個看起來像是相同類型的問題但只是較小的問題。列表問題通常意味着當給出一個n元素列表時，您想遞歸處理n -1個元素。您還需要有一個基本案例，以便遞歸將終止。通過列表，基本情況通常是0個元素的列表。

一個數組很像一個列表，但Java數組沒有切片（即：你不能傳遞一個數組的一部分），所以你需要一個輔助方法來知道哪一塊我們關心的數組：

private static LinkedList fromArray(String[] a, int offset) { 

由於您LinkedList類分解成一個單詞，然後在列表（由next指出）的尾部是有意義的，我們也的尾部處理輸入數組。 offset參數讓我們知道我們將要看的數組尾部的多少：這是我們關心的第一個索引。

公共方法只會調用輔助方法給它一個偏移量爲0：

public static LinkedList fromArray(String[] a) { 
    return fromArray(a, 0); 
} 

的偏移量爲0意味着我們關心的元素0（第一個元素）和之後的每一個元素。

因此，現在寫出「幫手」的方法，這是所有真正的工作完成的地方。

首先，將基本情況排除在外。基本情況是我們要轉換的數組部分是空的。如果offset >= a.length就是這種情況。在這種情況下，我們想要返回一個空的LinkedList，實際上這代表了null。那麼在這種情況下return null。

一旦基礎案例得到照顧，請考慮遞歸案例。我們關心的數組中有一個或多個元素。我們創建一個LinkedList來保存這些元素中的第一個，即a[offset]。 （我們關心的第一個元素，就是回想一下，助手只關心從offset開始直到最後的數組部分。）其餘元素可以通過調用自己傳入的相同數組來處理，但遞增offset 1，因爲我們不希望遞歸調用來處理我們已經處理的元素。

Answer 8

enter code here 
    public LinkedList arrayToLinkedList(String[] myArray) 
{ 
     String[] toConvert = myArray; 
     List<String> toConvertList = (List) Arrays.asList(toConvert); 
     LinkedList<String> convertedLinkedList = new LinkedList<String>(toConvertList); 
     return convertedLinkedList; 
}