Домашняя работа - 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 и данными, поэтому вам следует быть осторожным с этим конструктором MyLinkedList -вероятно, было бы намного проще, если бы он просто читал head = null;.

Также было бы полезно, если бы MyLinked List имел также узел tail, чтобы спасти вас по цепочке до конца, чтобы найти, гдеadd должен поставить новый Node.

После этого, я думаю, проблема в том, что вы не заметили, что вам нужно два цикла: один для прохождения по списку, чтобы отслеживать, где находитсяначинаются несортированные узлы, и один из них находит наименьший из них узел.Вам также нужно написать swap метод для Node, чтобы вы могли написать что-то вроде непроверенного псевдокода , который очень похож на 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;
  }
}

и swapбудет выглядеть примерно так:

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);
}

Обратите внимание еще раз это полностью не проверено и даже не видел компилятор.

Обязательно подумайте об особых случаях, например, когдасписок пуст или содержит только один элемент, и когда в списке остается только один узел, не отсортированный в списке.

---

Я не мог оставить это, не указав, что swap на самом деле многоболее сложный, чем это.Я добавил несколько строк, чтобы исправить указатели в узлах до и после заменяемых узлов.Вам также необходимо учитывать:

• находится ли какой-либо из переставляемых узлов в конце списка, в этом случае head (и tail, если у вас есть один) списка необходимо будет обновить вместо указателей на соседних узлах.Это довольно очевидно.

• Независимо от того, находятся ли подлежащие обмену узлы рядом друг с другом в списке, когда при применении нормального алгоритма вы получаете узлы, указывающие на себя.Это менее очевидно.