需要关于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); 
}