1

我现在是罗格斯大学的学生。我以前学过数据结构，现在我被分配了一个程序，该程序必须添加/乘以带有单链表的多项式。这真的很简单，现在我的问题是我必须使用排序技术（分配本身不需要，只是完成它的必要条件），我选择使用归并排序，因为它是最有效的（如果编写得当，也是最简单的） ）。

我可以使用迭代重新编写它，并getMiddleNode通过迭代两次并仅使用计数器来编写方法，但我根本看不出这将如何帮助改进我的代码。老实说，我相信这是任何人都可以在不被允许使用导入的情况下编写的最佳实现。

[CODE]
/**
 * Sorts the polynomial in order of degree from the <strong>highest to the lowest</strong> respectively.
 * <br><br><strong>Note</strong>:<br>Utilizes merge sort technique.
 * 
 * @param p The polynomial to be resorted.
 * @return The front of the node.
 */
private void sort() {
    if (poly == null)
        return;

    poly = sort(poly);
}

/**
 * Recursively splits a node into two parts, left and right. It continues this process until
 * the nodes are paired in two parts and then merges them in descending order.
 * 
 * @param node The node to be split into left and right parts.
 * @return The sorted node.
 */
private static Node sort(Node node) {
    // If the linked list is empty or only has one element it is already sorted.
    if (node == null || node.next == null)
        return node;

    // Find the middle of the linked list.
    Node middle = getMiddle(node), middleNext = middle.next;

    // Split the node in half.
    middle.next = null;

    // Merge the left and right half.
    return merge(sort(node), sort(middleNext));
}

/**
 * Compares the left and right side of each half. 
 * 
 * @param left 
 * @param right
 * @return
 */
private static Node merge(Node left, Node right) {
    if (left == null)
        return right;
    else if (right == null)
        return left;
    System.out.println(left.term +", "+right.term);

    if (left.term.degree < right.term.degree) {
        left.next = merge(left.next, right);
        return left;
    } else {
        right.next = merge(left, right.next);
        return right;
    }
}

/**
 * Iterates the linked list until the middle node is found.
 * 
 * @param node The node to be iterated.
 * @return The middle node of the linked list.
 */
private static Node getMiddle(Node node) {
    if (node == null)
        return null;

    Node slow, fast;
    slow = fast = node;

    // Iterate two nodes concurrently
    while (fast.next != null && fast.next.next != null) {
        // Faster node reaches the end of the linked list two times faster than the slower node.
        // Eliminates the need for a counter and re-iterating.
        slow = slow.next; 
        fast = fast.next.next;
    }

    return slow;
}
[/CODE]

这是我在之前的数据结构课程中基本上学过的代码。我很久以前在笔记中写过，并在我的程序中使用过。我的问题是我的大学会考虑这种剽窃行为吗？我没有想到任何代码，我只是写下文档，表明我了解代码本身是如何工作的。

4

0 回答 0