选择排序双链表java

我需要使用选择排序对链接列表进行排序。但我不能使用集合。我遇到了找到最小元素和创建排序列表的新版本的麻烦。谢谢。选择排序双链表java

public class LinkedList { 
     public Node first; 
     public Node last; 

     public LinkedList() { 
      first = null; 
      last = null; 
     } 

     public boolean isEmpty() { 
      return first == null; 
     } 

     public void addFirst(Student student) { 
      Node newNode = new Node(student); 
      if (isEmpty()) 
       last = newNode; 
      else 
       first.previous = newNode; 
      newNode.next = first; 
      first = newNode; 
     } 

     public void addLast(Student student) { 
      Node newNode = new Node(student); 
      if (isEmpty()) 
       first = newNode; 
      else 
       last.next = newNode; 
      newNode.previous = last; 
      last = newNode; 
     } 

     public void display() { 
      Node current = last; 
      while (current != null) { 
       System.out.print(current.student.name + "\b"); 
       System.out.print(current.student.surname + "\b"); 
       System.out.println(current.student.educationType); 
       current = current.previous; 
      } 
     }

由于非工作findSmallest方法Sort方法无法正常工作。我尝试通过创建一个新的列表来实现排序，在那里我按照排序的方式放置节点。而且它也不会出去的“While循环，”

 public void Sort() { 
      LinkedList list = new LinkedList(); 
      Node toStart = last; 
      while (toStart!=null){ 
       list.addLast(findSmallest(toStart).student); 
       toStart = toStart.previous; 
      } 


     }

它发出的加入最大元素，如果我手动assign'last“to'smallest”这是可行的。

 public Node findSmallest(Node toStartFrom) { 
      Node current = toStartFrom; 
      Node smallest = toStartFrom; //if i put here `last` it will work correctly 
      while(current != null) { 
       if (smallest.student.name.compareToIgnoreCase(current.student.name) > 0) smallest = current; 
       current = current.previous; 
      } 
      return smallest; 
     } 

    } 

    public class Node { 
     public Student student; 

     public Node next; 
     public Node previous; 

     public Node(Student student) { 
      this.student = student; 
     } 
    } 


    public class Student { 
     public String name; 
     public String surname; 
     public String educationType; 

     static public Student createStudent() { 
     .... 
      return student; 
     } 
    }

来源

2011-10-25 Nikita

定义“不工作”。另外，如果这是一项任务，它应该被标记为家庭作业。 –

是“不工作”以什么方式？ NPE不工作或随机返回不工作或什么？另外，是否有任何理由以相反顺序遍历列表？我觉得node.next会是约定 – SetSlapShot

没有双向链接列表可能会有所帮助，因为那样您的链接就需要更少维护。此外，您可能会遇到findSmallest（）方法的问题，因为您最初将当前和最小设置为同一节点，因此当执行if（smallest.student.name.compareToIgnoreCase（current.student.name）> 0）语句时你正在比较学生的姓名和学生的姓名。例如，如果最小的节点被设置为具有约翰的学生姓名当前被设置为相同的节点，所以当前的学生姓名也是约翰。如果他们是具有相同名称的不同学生，但在您的代码中他们是同一名学生，并且当前和最小指向同一个节点，则不是问题。实际上，如果陈述总是假的，你永远不会执行代码来沿着列表移动电流。这也是为什么当你设置最小=最后时，该方法至少在某些时间起作用。

来源

2011-10-25 03:11:14 gluestick

正如上面所说的，你可以试试

smallest = startnode next =startnode.next while(next != null) compare next with smallest, and assign accordingly next = next.next

应该不会太难把它变成代码

来源

2011-10-25 03:50:32

选择排序双链表java

回答

相关问题