java - 选择排序链接列表

Question

我正在双向链表中实现选择排序。我必须通过查找最小元素并将其插入列表的开头来按姓氏对列表进行排序。但是有一些麻烦，当我运行我的程序时，在 while 循环中的排序方法中出现 NIL 异常。它是整个应用程序，因此您可以根据需要编译并运行它。帮助将不胜感激。谢谢。

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

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

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

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

        public void display() {
            Node current = first;
            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.next;
            }
        }

        public Node findSmallest(Node startNode) {
            Node smallest = startNode;
            while (startNode.next != null) {
                if (smallest.student.surname.compareToIgnoreCase(startNode.next.student.surname) > 1)
                    smallest = startNode.next;
                else startNode = startNode.next;
            }
            return smallest;
        }

        public void Sort() {
            LinkedList newList = new LinkedList();
            Node current = first;

            while (current.next != null) {
                Node smallest = findSmallest(current);
                newList.addLast(smallest.student);
                delNode(smallest);
                current = current.next;

            }
            first = newList.first;
            last = newList.last;
        }

        public void delNode(Node toDel) {
            if (toDel.previous == null) {
                toDel.next.previous = null;
                first = toDel.next;
                return;
            }

            if (toDel.next == null) {
                toDel.previous.next = null;
                last = toDel.previous;
                return;
            }
            toDel.previous.next = toDel.next;
            toDel.next.previous = toDel.previous;
        }

}


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

    static public Student createStudent() {
        Student student = new Student();
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            System.out.println("Enter student's name:");
            student.name = br.readLine();
            System.out.println("Enter surname:");
            student.surname = br.readLine();
            System.out.println("Enter educational type:");
            student.educationType = br.readLine();
        } catch (IOException e) {
            throw new NotImplementedException();
        }
        return student;
    }
}


public class Node {
    public Student student;

    public Node next;
    public Node previous;

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

Answer 1

我没有运行它，所以这只是通过查看你的代码:

1. 这并不是真正的选择排序，因为您正在构建新列表，而不是对旧列表进行排序。

2. delNode() 对于单个元素列表将因 NPE 失败，所以也许这就是问题所在(如果您删除最后一个元素，它也会失败)。

3. 除非不允许，否则请使用哨兵。