Блог

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

  //getData() returns the data in that Node
 //getLink() returns the link to the next Node
 //setLink() sets the link of the Node 
 //top is the reference to the first node

public void ordInsert(int newItem) {

 IntNode prev = null;
 IntNode next = top;
 while(next!=null amp;amp; next.getData()<newItem){
   prev = next;
   next = next.getLink();
 }
 IntNode newNode = new IntNode(newItem,next);
 if(prev==null)
   top = newNode;
 else
   prev.setLink(newNode);
}
  

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

   public void inSort(){

     IntNode next = top;

     if(next != null){

       ordInsert(next.getData());
       top.setLink(next.getLink());
       inSort();
     }

   return;
 }
  

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

  Input: 3000 400 40 120 70 
 Expected Output : 40 70 120 400 3000
  

Отслеживание бесконечной рекурсии

Проблема, с которой вы столкнулись сейчас, заключается в том, что узел, сортируемый в списке, не удаляется.

Давайте посмотрим на приведенный вами пример ввода:

 Input: 3000 400 40 120 70
  

В начале top указывает на 3000 узел. В inSort , next устанавливается в точку, где top указывает, и 3000 является значением, которое нужно вставить.

При вызове ordInsert начальное условие

 while(next!=null amp;amp; next.getData()<newItem)
  

никогда не является истинным, потому что next.getData() всегда равно newItem (это тот самый объект, который вы пытаетесь повторно вставить!). Как следствие, top узел воссоздается и вставляется вверху и top , следовательно, устанавливается на точку там. Таким образом, список теперь:

 3000 3000 400 40 120 70
  

с top указанием на первый элемент.

Поскольку next это ссылка на тот же объект, что и top , top ссылка s теперь устанавливается на 3000 следующий за ней. И вы оказываетесь в той же ситуации, что и раньше, только списку предшествует другой элемент.

Повторный вызов inSort() будет повторять этот процесс бесконечно, чтобы получить результат

 3000 3000 ... 3000 400 40 120 70
  

Проблемы

• Вставляемые элементы не удаляются, что приводит к расширению списка
• Сброс top in inSort делает недействительной предпосылку для цикла while в ordInsert .

Предлагаемое решение

Метод ordInsert работает только в том случае, если список, в который вставляется новый элемент, уже отсортирован. Итак, стратегия должна быть:

 1. Detach element at index 0
2. Sort remaining list
3. insert detached element into sorted list
  

Таким образом, сначала сохраните ссылку на начало списка, затем переместите top маркер к следующему элементу и установите отдельный (предыдущий верхний) элемент, на который будет указывать null . Это не отменит предпосылку цикла while, поскольку top все еще ссылается на начало списка (элемент с индексом 0 был удален из списка).

Затем выполните вызов inSort() теперь сокращенного списка. После успешного вызова используйте ordInsert() для вставки отдельного элемента. Лучше заставить его работать с IntNode , чем создавать совершенно новый элемент.

Чтобы рекурсия сработала, подтвердите, что top ссылается на начало списка (сокращенный [после отсоединения] или расширенный [после повторной вставки]), чтобы для любого шага рекурсии состояние программы было допустимым. И следите за базовым вариантом, когда top == null .

В inSort условие остановки является if(next == null) . next является top и top является заголовком списка (не последним узлом). Следовательно, рекурсия никогда не останавливается.

Кроме того, вместо сортировки существующего связанного списка вы вставляете новые данные, код бесконечно дублирует узлы.