歸併不給正確的輸出

Question

我有兩個類：

public class List { 
    public Node _head; 
} 

和：

public class Node { 
    public String _word; 
    public Node _next; 
} 

我在「名單」的構造函數，它得到一個字符串作爲參數，並把每一個字一個單獨的節點，就像這樣：

public List(String text) { 
    if (text.length() == 0) 
     _head = null; 
    createList(text); 
} 

private void createList(String text) { 
    int lastIndex=0; 
    String temp;   
    for (int i=0;i<text.length();i++) { 
     if (text.charAt(i)==' '|| i==text.length()-1) { 
      if (i == 0) { // Space in the begining 
       lastIndex=1; 
       continue; 
      } 
      if (i == text.length()-1) { // If we reached to the last char of the string 

       if (text.charAt(i) == ' ') { // If it's a space, don't include it 
        temp = text.substring(lastIndex,i); 
       } else { 
        temp = text.substring(lastIndex,i+1); 
       } 
      } else { 
       temp = text.substring(lastIndex,i); 
      } 
      addToBegining(temp); 
      lastIndex=i+1; 
     } 
    } 
} 

無論如何，當我試圖使用一個合併的鏈表上，我不能設法得到它活像國王。

這是排序代碼：

public Node merge_sort(Node h) { 
    if (h == null || h._next == null) { return h; } 
    Node middle = getMiddle(h);  //get the middle of the list 
    Node sHalf = middle._next; middle._next = null; //split the list into two halfs 

    return merge(merge_sort(h), merge_sort(sHalf)); //recurse on that 
} 

public Node merge(Node a, Node b) { 
    Node dummyHead, curr; 
    dummyHead = new Node(); 
    curr = dummyHead; 
    while (a !=null && b!= null) { 
     if (a._word.compareTo(b._word) <= 0) { 
      curr._next = a; 
      a = a._next; 
     } else { 
      curr._next = b; 
      b = b._next; 
     } 
     curr = curr._next; 
    } 
    curr._next = (a == null) ? b : a; 
    return dummyHead._next; 
} 

public Node getMiddle(Node h) { 
    if (h == null) { return h; } 
    Node slow, fast; 
    slow = fast = h; 
    while (fast._next != null && fast._next._next != null) { 
     slow = slow._next; 
     fast = fast._next._next; 
    } 
    return slow; 
} 

任何想法有什麼不對？ 我試圖做一個新的TextList與字符串「你好新世界有一個黎明」和輸出是：「有世界」..

Answer 1

請改變如下。我想你忘了將curr節點分配到if-else之後的適當值。

public Node merge(Node a, Node b) 
    { 
     Node dummyHead, curr; 
     dummyHead = new Node(); 
     curr = dummyHead; 
     while (a != null && b != null) 
     { 
      if (a._word.compareTo(b._word) <= 0) 
      { 
       curr._next = a; 
       curr = a; 
       a = a._next; 
      } 
      else 
      { 
       curr._next = b; 
       curr = b; 
       b = b._next; 
      } 
      curr = curr._next; 
     } 
     curr._next = (a == null) ? b : a; 
     return dummyHead._next; 
    } 

Answer 2

合併排序不適合鏈接列表，因爲您需要訪問列表的中間元素（將列表劃分爲2個子列表）。通過鏈接列表，您只能訪問列表的第一個元素（單鏈表）。

嘗試使用它是不可行的，因爲每次分割列表時都必須首先找到中間元素的鏈接。最好嘗試使用插入排序或快速排序鏈接列表的第一個元素作爲關鍵點。

編輯： 昨天，我從我的電話回覆，無法分析您的代碼。

今天我測試了你的代碼。

我用字"ant", "lion", "pig", "rat", "bat", "tiger", "cat", "dog"創建輸入列表並使用merge_sort()方法。 它的輸出是很好的排序列表。

唯一的交替給你的代碼我所做的，就是將構造函數來Node()類

Node() { 
    _word = ""; 
    _next = null; 
} 

Node (String word) { 
    _word = word; 
} 

但這只是對我來說，更容易創建新的節點。

你能告訴你如何測試你的輸出列表嗎？

EDIT2： 我沒有檢查你的代碼，你說，它的工作原理，從字符串分隔單詞）

EDIT3： 您的合併方法也有其他的問題，但是這個人是最主要的一個。

想想看，你的merge()方法的工作，當你嘗試合併2列表： A = { 「蟻族」， 「蝙蝠」， 「狗」} B = { 「貓」， 「獅子」， 「鼠」 }

而循環迭代：

1. CURR = { 「螞蟻」} A = { 「球棒」， 「狗」} b = { 「貓」， 「獅子」， 「鼠」}

2. curr = {「ant」，「bat」} a = {「dog」} b = {「cat」，「lion」，「rat」}

3. CURR = { 「螞蟻」， 「球棒」， 「貓」} A = { 「狗」} B = { 「獅子」， 「鼠」}

4. CURR = { 「螞蟻」，「蝙蝠」， 「貓」， 「狗」} A = {} b = { 「獅子」， 「鼠」}

5. 一個== NULL，while循環終止

接下來發生了什麼？ 您的方法只分配一次來自列表b的下一個元素並退出。從b中鬆開第二個元素（「老鼠」）。

我稍微改變你的代碼，getMiddle()方法是一樣的你：

public Node mergeSort(Node h) { 
    if (h._next != null) { // check for recursion if in list left at least 2 elements 
     Node middle = getMiddle(h); 
     Node sHalf = middle._next; middle._next = null; 
     return merge(mergeSort(h), mergeSort(sHalf)); 
    } 
    else { // if only 1 element then no need to sort 
     return h; 
    } 
} 

public Node merge(Node a, Node b) { 
    Node dummyHead = new Node(); 
    Node curr = dummyHead; 
    while (a !=null && b!= null) { 
     if (a._word.compareTo(b._word) <= 0) { 
      curr._next= a; 
      a = a._next; 
     } else { 
      curr._next = b; 
      b = b._next;    
     } 
     curr = curr._next; 
    } 
    // if list a still has some elements, insert them to the end of the curr 
    while(a != null) { 
     curr._next = a; 
     a = a._next; 
     curr = curr._next; 
    } 
    // if list b still has some elements, insert them to the end of the curr 
    while(b != null) { 
     curr._next = b; 
     b = b._next; 
     curr = curr._next; 
    } 
    return dummyHead._next; 
}