java - 如何对链表节点数组进行从高到低排序(基于float值)

Question

我有一个链表节点数组，对应于学生注册的类(class)，我需要将成绩从最高到最低排序。我花了一整天的时间尝试不同的排序算法，但我似乎无法让它正常工作。诚然，我不太擅长排序算法，但这并不是因为缺乏尝试。我第一次尝试合并排序，但失败得很惨，而且我最近的努力也没有奏效。由于它是一个链表节点数组，因此我对如何实现排序感到困惑，因为大多数算法都针对数组或链表，而不是两者。

我遇到的问题:

1.) 多次插入后显示重复节点

2.) 在节点之间交换等级值，而不是交换节点本身

3.) 根本没有显示任何数据。

如果有人能给我指出正确的方向或帮助解释如何正确排序我的节点，我将不胜感激。我已经阅读了几个小时但没有成功。

当我不对节点进行排序时，节点链接良好并显示良好，因此我知道功能运行正常。我的类 Course() 使用包装类 AGradeListNode() 来保存节点插入数组所需的数据。我的代码中包含我最近对节点进行排序的尝试(这不起作用，导致重复)。请不要对我大喊大叫，我真的在努力学习......

public class Course implements Serializable
{
    private String courseName;
    private String classTime;
    private int courseID;
    private Instructor instructor;
    private int numStudents;                     //variable for number of students in the list
    private int hold;                           //used to hold location of node
    protected static final int NUL = -1;        //Constant class var for end of list symbol.
    protected int currentPos;                   //Current position for iteration
    protected int list;                         //Reference to the first node on the list
    protected int free;                         //Reference to the first node on the free list
    protected AGradeListNode[] nodes;           // Array of AListNode holds the linked list

    // set by find method
    protected boolean found;                    // true if element found, else false
    protected int location;                     // node containing element, if found
    protected int previous;                     // node preceding location

    //wrapper class to create nodes for linked list array
    protected class AGradeListNode
    {
        private float grade;
        private Student student;
        private int next;                       //a link to the next node in linked list array

        //displays nodes as neatly formatted string
        @Override
        public String toString()
        {
            return "Student: " + student.getLastName() + ", " + student.getFirstName() + "\n" +
                   "Grade: " + grade + "\n";
        }
    }
//constructor initializes array of nodes with 2 lists: used and free. 
    //contains other data needed for Course object instantiation as well
    public Course(int maxNumStudents, String courseName, String classTime, int courseID, Instructor instructor)
    {
        nodes = new AGradeListNode[maxNumStudents];

        for (int i = 0; i < maxNumStudents; i++)
        {
            nodes[i] = new AGradeListNode();
        }

        //link together the free nodes
        for (int i = 1; i < maxNumStudents; i++)
        {
            nodes[i - 1].next = i;
        }

        nodes[maxNumStudents - 1].next = NUL;

        list = NUL;
        free = 0;
        numStudents = 0;
        currentPos = NUL;

        this.courseName = courseName;
        this.classTime = classTime;
        this.courseID = courseID;
        this.instructor = instructor;
    }
// Returns the index of the next available node from the free list
    // and updates the free list index
    protected int getNode()
    {
        hold = free;
        free = nodes[free].next;
        return hold;
    }

    //Frees the node at array position index by linking it into the
    //free list
    protected void freeNode(int index)
    {
        nodes[index].next = free;
        free = index;
    }
//here is where im having issues. I'm attempting to sort the nodes based on
    //grade from high to low. Each grade belongs to a specific student object
    public void addStudentGrade(Student stu, float grade)
    {
        if (isFull())
        {
            return;
        }

        int newNode = getNode();
        nodes[newNode].student = stu;
        nodes[newNode].grade = grade;
        nodes[newNode].next = list;
        list = newNode;
        numStudents++;

        //sorting list, not working :/
        for (int j = 1; j <= numStudents; j++)
        {
            float hold = nodes[j].grade;
            int i = j-1;
            while ((i > -1) && (nodes[i].grade > hold))
            {
                nodes[i+1] = nodes[i];
                i--;
            }
            nodes[i+1] = nodes[j];
        }

        for (int i = 0; i < numStudents; i++)
        {
            System.out.println(nodes[i].toString());
        }
    }

编辑:这是我根据 Andreas 的宝贵意见更新的 addStudentGrade(Student Stu, float Grade) 方法。不过，我的列表仍然没有正确排序。成绩是根据输入的顺序而不是降序/升序进行排序的(老实说，这对我来说都很好，我只想对列表进行排序:/)。如果有人能发现我做错了什么并帮助我，我将非常感激。我已经修改这个方法三天了，我开始变得非常灰心:

//Method used to add student grades to nodes array. After LL node
    //is added, method sorts the used nodes in descending order based
    //off the float value grade
    public void addStudentGrade(Student stu, float grade)
    {
        if (isFull())
        {
            return;
        }

        int newNode = getNode();
        nodes[newNode].student = stu;
        nodes[newNode].grade = grade;
        nodes[newNode].next = list;
        list = newNode;
        numStudents++;

        //storing used nodes in temp Integer array
        Integer[] usedNodes = new Integer[numStudents];

        for (int i = list, j = 0; i != NUL; i = nodes[i].next)
        {
            usedNodes[j++] = i;
        }

        //sorting the temp array using lambda expression and 
        //Arrays.sort. I believe this is where my mistake is
        Arrays.sort(usedNodes, (i1, i2) ->
        {
            return Float.compare(nodes[i2].grade, nodes[i1].grade);
        });

        //rebuilding the linked list after sorting
        list = usedNodes[0];
        for (int i = 1; i < usedNodes.length; i++)
        {
            nodes[usedNodes[i-1]].next = usedNodes[i];
        }

        //printing the nodes to console for verification
        nodes[usedNodes[usedNodes.length - 1]].next = NUL;

        for (int i = 0; i <= numStudents; i++)
        {
            if (nodes[i].student != null)
            {
                System.out.println(nodes[i].toString());
            }
        }
    }

最终编辑:这是我完整的功能类，其中包含的方法未发布在我的原始代码中(我包含了删除、替换和检索学生成绩的其他方法，希望它将来可以帮助其他人) 。现在，它按照应有的方式排序(降序)，并且我不是在插入时排序，而是在调用 printData() 方法期间对列表进行排序。我非常感谢 Andreas 帮助我解决了这个任务，没有你我不可能完成这个任务! (至少在需要的指定时间范围内):

// Returns the index of the next available node from the free list
    // and updates the free list index
    protected int getNode()
    {
        hold = free;
        free = nodes[free].next;
        return hold;
    }

    //Frees the node at array position index by linking it into the
    //free list
    protected void freeNode(int index)
    {
        nodes[index].next = free;
        free = index;
        nodes[free].student = null;
    }

    private void find(int id)
    {
        found = false;
        current = list;
        previous = NUL;
        while (!found || current != NUL )
        {
            if (nodes[current].student.getId() == id)
            {
                found = true;
                location = current;
                return;
            }
            previous = current;
            current = nodes[current].next;
        }
    }

    //Method used to add student grades to nodes array. After LL node
    //is added, method sorts the used nodes in descending order based
    //off the float value grade
    public void addStudentGrade(Student stu, float grade)
    {
        if (isFull())
        {
            return;
        }

        int newNode = getNode();
        nodes[newNode].student = stu;
        nodes[newNode].grade = grade;
        nodes[newNode].next = list;
        list = newNode;
        numStudents++;

        //printing sorted data to console
        printData();
    }

    public boolean removeStudentGrade(int id)
    {
        find(id);
        if (found)
        {
            hold = location;
            if (list == location)
            {
                list = nodes[list].next;   // remove first node
                System.out.println("Removing first node");
            }
            else
            {
                nodes[previous].next = nodes[location].next;
            }
            freeNode(hold);
            numStudents--;
        }
        return found;
    }

    //updates student grade from nodes array based on student id
    public void updateStudentGrade(int id, float newGrade)
    {
        find(id);
        if (found)
        {
            hold = location;
            nodes[hold].grade = newGrade;
        }
        else
        {
            System.out.println("Student ID not found. Please check data entry and try again.");
        }
    }

    //Method that searches array for student by id #. if found,
    //students grade is returned. if not, -1 is returned
    public float findStudentGrade(int id)
    {
        find(id);
        if (found)
        {
            hold = location;
            return nodes[hold].grade;
        }
        else
        {
            System.out.println("Student ID not found. Please check data entry and try again.");
        }
        return -1;
    }

    //method that sorts student's grades for a specific course in descending order
    private void sort()
    {
        //storing used nodes in temp Integer array which will be used
        //to compare and sort the grade values of each node
        Integer[] usedNodes = new Integer[numStudents];

        for (int i = list, j = 0; i != NUL; i = nodes[i].next)
        {
            usedNodes[j++] = i;
        }

        //sorting the temp array in descending order using custom
        //comparator and Arrays.sort from Java.util.Arrays.
        Arrays.sort(usedNodes, (i1, i2) ->
        {
            return Float.compare(nodes[i2].grade, nodes[i1].grade);
        });

        //rebuilding the linked list after sorting
        list = usedNodes[0];
        for (int i = 1; i < usedNodes.length; i++)
        {
            nodes[usedNodes[i-1]].next = usedNodes[i];
        }
        nodes[usedNodes[usedNodes.length - 1]].next = NUL;
    }
//Determines whether this list is full
    public boolean isFull()
    {
        return (free == NUL);
    }

    //prints grades for a specific course. Calls sort()
    //method before printing
    public void printData()
    {
        current = list;
        while (current != NUL)
        {
            sort();
            System.out.println(nodes[current].toString());
            previous = current;
            current = nodes[current].next;
        }
    }

Answer 1

已更新原始答案假设您只是想在事后对列表进行排序，但仔细观察，您似乎想要插入排序，其中具有相同成绩的学生应按插入顺序排列。

为此，需要替换 addStudentGrade() 方法的大部分内容。您不是“排序”，而是搜索“插入点”，然后在其中添加新节点。

为了展示这一点，我将代码缩减为 MCVE (最小、完整和可验证的示例)。您可以在 IDEONE 上查看完整代码.

public void addStudentGrade(Object stu, float grade) {
    // Search for insertion point (i.e. between prevIdx and nextIdx)
    int prevIdx = NUL;
    int nextIdx = list;
    while (nextIdx != NUL && nodes[nextIdx].grade >= grade) {
        prevIdx = nextIdx;
        nextIdx = nodes[nextIdx].next;
    }

    // Initialize and insert new node
    int newIdx = getNode();
    nodes[newIdx].student = stu;
    nodes[newIdx].grade = grade;
    nodes[newIdx].next = nextIdx;
    if (prevIdx == NUL)
        list = newIdx;
    else
        nodes[prevIdx].next = newIdx;
}

<小时/>

原始答案

这是一个非常奇怪的类，它有一个基于索引的链表到一个固定大小的节点数组中。

我建议，要对非自由节点进行排序，首先将这些节点收集到数组中，或者更确切地说是它们的节点索引。由于您知道有多少个正在使用的节点，即 numStudents，因此创建一个该大小的新数组，然后用正在使用的节点的索引填充它。请注意，数组必须是 Integer[]，而不是 int[]，因此可以提供自定义比较器来进行排序:

Integer[] inuse = new Integer[numStudents];
for (int i = list, j = 0; i != NUL; i = nodes[i].next)
    inuse[j++] = i;

然后使用自定义比较器对它们进行排序，例如使用 Java 8 lambda:

Arrays.sort(inuse, (i1, i2) -> {
    return Float.compare(nodes[i2].grade, nodes[i1].grade); // descending
});

现在它们已经排序，您需要重新构建链表:

list = inuse[0];
for (int j = 1; j < inuse.length; j++)
    nodes[inuse[j - 1]].next = inuse[j];
nodes[inuse[inuse.length - 1]].next = NUL;

我相信应该可以做到。