java - 作业 - Java - 在我创建的双链表上进行选择排序

Question

我的任务是创建我自己的链表类(我不能使用Java的LinkedList类)并通过交换指针而不是数据来实现选择排序。

我创建了一个双链接的 MyLinkedList 类，但我在使用排序方法时遇到了问题。我已经尝试了很多方法，但没有任何效果 - 甚至没有任何可以在这里发布以进行更正的内容。 (我确实知道我需要至少使用一个临时节点。)它必须是一种选择排序。

我不一定要找人为我编码；我希望有人可以帮助我设计一种算法，然后我可以自己将其转化为代码。非常感谢任何帮助。

以下是我实现 MyLinkedList 类和关联的 Node 类的方法:

public class MyLinkedList
{
    private Node head;
    private int count;

    public MyLinkedList()
    {
        head = new Node(null);
        count = 0;
    }

    public void add(String line)
    {
        Node temp = new Node(line);
        Node current = head;

        while (current.getNext() != null)
        {
            current = current.getNext();
        }

        temp.setLine (line);  // not sure this is how to do it
        current.setNext(temp);
        temp.setPrev(current);
        count++;
    }

    public void displayList()
    {
        Node current = head;

        for (int i = 0; i < count; i++)
        {
            current = current.getNext();
            System.out.println(current.getLine());
        }
    }

    public void sortList()
    {       
        Node start = head;
        Node index = start;
        Node min = start;

        Node temp1, temp2;

        while (start.getNext() != null)
        {
            index = index.getNext();

            if (index.getLine().compareTo(min.getLine()) < 0)
            {
                min = index;
            }

            //swap - HELP, PLEASE :-)
            {
                // Algorithm???
            }
        }
    }

    public int size()
    {
        return count;
    }


    private class Node
    {
        String textLine;
        Node next;
        Node prev;

        public Node()
        {
            textLine = null;
            next = null;
            prev = null;
        }

        public Node (String line)
        {
            textLine = (line);
            next = null;
            prev = null;
        }

        public Node (String line, Node node1, Node node2)
        {
            textLine = line;
            prev = node1;
            next = node2;
        }

        public String getLine()
        {
            return textLine;
        }

        public Node getNext()
        {
            return next;
        }

        public Node getPrev()
        {
            return prev;
        }

        public void setLine(String line)
        {
            textLine = line;
        }

        public void setNext(Node nextNode)
        {
            next = nextNode;
        }

        public void setPrev(Node prevNode)
        {
            prev = prevNode;
        }
    }
}

Answer 1

如果空的 MyLinked List 中有一个节点，即使它只是一个带有 null prev, 的节点，也可能会造成困惑next 和 data，因此您需要小心 MyLinkedList 构造函数 - 如果它只是简单地读取 head = null;，可能会容易得多。

如果 MyLinked List 也有一个 tail 节点，它会很有用，这样您就可以沿着链到末尾查找 add 应该放置一个新的 Node。

之后，我认为问题是您没有注意到您需要两个循环:一个循环遍历列表以跟踪未排序节点的起始位置，另一个循环则从中找到最小的节点。您还需要为 Node 编写一个 swap 方法，以便您可以编写类似这样的未经测试的伪代码，它恰好看起来很像 Java

for (index = head; index != null; index = index.getNext()) {
  min = index;
  for (test = min.getNext(); test != null; test = test.getNext) {
    if (test.getLine().compareTo(min.getLine()) < 0)
        min = test;
  }
  if (min != index) {
    swap(index, min);
    index = min;
  }
}

交换看起来大致如下

public void swap(Node other)
{
  Node temp;

  temp = next;
  next = other.getNext();
  other.setNext(temp);

  temp = prev;
  prev = other.getPrev();
  other.setPrev(temp);

  other.getNext().setPrev(this);
  other.getPrev().setNext(this);

  this.getNext().setPrev(other);
  this.getPrev().setNext(other);
}

再次注意这完全未经测试，甚至没有见过编译器。

请务必考虑特殊情况，例如当列表为空或其中只有一个元素时，以及当列表中只剩下一个未排序的节点时。

---

我不能不指出交换实际上比这复杂得多。我添加了几行来纠正要交换的节点之前和之后的节点中的指针。您还需要考虑:

• 交换的任一节点是否位于列表末尾，在这种情况下，交换的 head(以及 tail，如果有的话)需要更新列表而不是相邻节点中的指针。这是相当明显的。

• 要交换的节点是否在列表中彼此相邻，如果应用普通算法，您会得到指向自身的节点。这不太明显。