需要關於Java代碼的幫助

Question

我對鏈接列表有點問題。我使用隨機類中的隨機對象生成40個隨機整數，並將它們附加到鏈表中。這也使用指定的種子。一切正常完美減去這一個錯誤。在控制檯/輸出中打印的第一件事是隨機生成的40個整數的鏈表。然後我嘗試使用遞減的插入排序來排序列表，這是我認爲我的錯誤在於的地方。我在「遞減插入排序算法」的嘗試是在isdRecI和isdRecII方法中完成的，這些方法是遞歸的（小心這個程序的大部分是遞歸的，所以如果你不熟悉遞歸小心）。排序完成後，我想按降序重新打印鏈接列表。請儘量保持簡單，如果你喜歡我的代碼風格，因爲我有點Java初學者，請不要過於複雜。正如你可以看到，如果你編譯我的代碼，你會看到排序後的打印副本。我的代碼列在下面。我也理解鏈表和插入排序的概念，但我有一段艱難的時間讓代碼以我想要的方式輸出。請隨時修改我的方法。感謝您的時間和貢獻。

public class Node 
{ 

private int data = 0; 
Node next; 

public Node (int datax) //constructor 
{ 
    data = datax; 
    next = null; 
} 

public int getData() // get the data value 
{ 
    return data; 
} 

public void setData(int datax) // sets the data value 
{ 
    data = datax ; 
} 

public void print() // print node data on one line. 
{ 
    System.out.print(data + " "); 
} 

public Node getNext() 
{ 
    return (next); 
} 

public void setNext(Node nextx) 
{ 
    next = nextx; 
} 
} 

import java.util.Random; 

public class MySort 

{ 
Node head; 


/* 
* This method appends iteratively to the end of the linked list 
*/ 
public void appendIter(int datax) 
{ 
    Node newNode = new Node(datax); 
    Node rightpointer = head; 
    if (rightpointer == null) 
    { 
     head = newNode; 
     return; 
    } 
    else 
    { 
     while (rightpointer.getNext() != null) 
     { 
      rightpointer = rightpointer.getNext(); 
     } 
     rightpointer.setNext(newNode); 

    } 
} 

/* 
* This method passes the data to isdRecI 
*/ 

     public void isRecI(MySort unsortedList) 
    { 
     isRecII(head); 
    } 

    public void isRecII(Node unsortedPointer) 
    { 
     int data; 
     if(unsortedPointer == null) 
     { 
      return; 
     } 
     data = unsortedPointer.getData(); 
     isdRecI(data); 
     isRecII(unsortedPointer.getNext()); 
    } 


    /* 
    * This method sorts the data using insert sort and sorts in decreasing order 
    * 
    */ 
    public void isdRecI(int dx) 
    { 
     head = isdRecII(head, dx); 
    } 

    public Node isdRecII(Node hp, int dx) 
    { 
     Node nxp; 
     /* 
     if(hp == null) 
     { 
      nxp = new Node(dx); // commented out for testing purposes please uncomment if you need 
      return nxp; 
     } 
     */ 
     if(dx >= hp.getData())  
     { 
      nxp = new Node(dx); 
      nxp.setNext(hp); 
      return nxp; 
     } 
     hp.setNext(isdRecII(hp.getNext(),dx)); 
     return hp; 
    } 

    /* 
    * This method is an iterative print method for the linked list 
    */ 
    public void print() 
    { 
     System.out.println("print list start: "); 
     Node nextrightpointer = head; 
     while (nextrightpointer != null) 
     { 
      nextrightpointer.print(); 
      nextrightpointer = nextrightpointer.getNext(); 
     } 
     System.out.println("print list end"); 
    } 


    public static void main(String[] args) 
{ 
    MySort SortObject = new MySort(); 
    Random random = new Random(12345); 

    for(int i=0; i < 40;i++) 
     { 
      SortObject.appendIter(random.nextInt(200)); 
     } 

     SortObject.print(); 
     SortObject.isRecI(SortObject); 
     System.out.println(); 
     SortObject.print(); 

} 
} 

另外包括輸出：

打印清單開始： 51 80 41 28 55 84 175 2 101 189 117 142 190 6 12 184 187 103 132 175 1 151 192 116 28 181 25 143 71 39 129 197 101 25 103 155 152 31 10 108打印列表端

（後排序//這不打印只是FYI）

打印清單開始： 197 192 190 189 187 184 181 175 175 155 152 151 143 142 132 129 117 116 108 103 103 101 10 1 84 80 71 55 51 51 80 41 41 39 31 28 28 28 55 84 175 25 25 12 10 6 2 2 101 189 117 142 190 6 12 184 187 103 132 175 1 1 151 192 116 28 181 25 143 71 39 129 197 101 25 103 155 152 31 10 108打印列表結束

Answer 1

你試圖實現什麼樣的排序算法？我建議您查看一個標準的排序算法（例如bubblesort，mergesort），然後開始工作。從你的描述看來，你只是想出了你自己的排序算法（不推薦）。 Java還內置了幫助您對數據進行排序的機制。例如，您可以覆蓋Node類的compareTo方法，並在列表中調用Collections.sort()。

Answer 2

你的問題是，「頭」是指未排序的列表，但在isdRecI方法中，它被視爲如同描述排序列表一樣。 isdRecI所做的第一件事是向列表中添加一個新節點 - 因此列表現在包含原始未排序列表以及一個新節點。

Answer 3

1）你有太多的遞歸函數。一個主要功能和一個幫手應該就足夠了。 2）您打電話給列表中添加一個新的值而不刪除它。我會嘗試修改遞歸函數併發布我所得到的結果。

這是我得到的新代碼。由於您沒有實施雙鏈表，我必須做一些奶酪才能添加/刪除。

public void isRecI(Node unsortedList) 
{ 
    int data; 
    if(unsortedList == null) 
    { 
     return; 
    } 
    Node prev = unsortedList; 
    unsortedList = unsortedList.getNext(); //first element is in order 
    while(unsortedList != null){ 
     reHelper(head , null , unsortedList , prev); 
     prev = unsortedList; 
     unsortedList = unsortedList.getNext(); 
    } 
} 

public void reHelper(Node inOrder , Node orderPrev , Node toInsert , Node insertPrev){ 
    if(inOrder == toInsert)return; 
    if(inOrder.getData() < toInsert.getData()){ 
     insertPrev.setNext(toInsert.getNext()); //remove from list 
     toInsert.setNext(inOrder);// first part of add to list 
     if(orderPrev == null){ 
      head = toInsert; // make head 
     } 
     else{ 
      orderPrev.setNext(toInsert);// finish add to list 
     } 
     return; 
    } 
    reHelper(inOrder.getNext() , inOrder , toInsert , insertPrev); 
}