Блог

Главная - Вопросы по программированию - Сортировка списка ссылок

Сортировка списка ссылок

#java #sorting #linked-list

#Ява #сортировка #связанный список

Вопрос:

Я не могу понять, где в коде чего-то не хватает. Почему он сортирует только один раз и помещает, наконец, 50, а остальные элементы такие же, как и раньше. Вот мой Код.

 //TO SORT THE LINKED LIST  static Node sorted(Node head){    Node temp1 = head;  Node temp2 = head;  while(temp1 != null){  while(temp2 != null){  if(temp2.data gt; temp2.next.data){  int temp = temp2.data;  temp2.data = temp2.next.data;  temp2.next.data = temp;  }  temp2 = temp2.next;  }  temp1 = temp1.next;  }  return head;  }

Комментарии:

1. Что это за язык такой?

2. Вы должны использовать более описательные имена переменных, чем просто temp1 и temp2 .

3. Привет, извини, Это Ява. Поэтому я пытаюсь отсортировать свой связанный список 50,40,30,20,10 в порядке возрастания, используя два цикла.

4. Вы использовали свой пошаговый отладчик? Если нет, то почему бы и нет ?

5. (Нет, я НЕ собираюсь предоставлять вам исправления … так что не утруждай себя расспросами. Вместо этого вам нужно самим разобраться в проблемах и самостоятельно разработать решения. Так ты научишься … в этом весь смысл твоего домашнего задания. И, да, научиться использовать отладчик тоже было бы неплохо.)

Ответ №1:

В вашем коде есть две проблемы:

  1. temp2 следует перезапускать с начала списка на каждой итерации внешнего цикла.
  2. temp2.next в конечном итоге будет null , когда temp2.next.data будет проведена оценка. Вам нужно выйти из внутреннего цикла, когда вы достигнете последнего узла, а не когда вы пройдете последний узел. Таким while образом, условие должно быть temp2.next != null

С этими исправлениями это будет работать:

 static Node sorted(Node head){  Node temp1 = head;  while (temp1 != null) {  Node temp2 = head;  while (temp2.next != null) {  if (temp2.data gt; temp2.next.data){  int temp = temp2.data;  temp2.data = temp2.next.data;  temp2.next.data = temp;  }  temp2 = temp2.next;  }  temp1 = temp1.next;  }  return head;  }

Теперь мне еще нужно сделать несколько замечаний:

  1. Вы должны проверить, допустимо ли менять местами данные узлов, вместо того, чтобы менять местами (и переподключать) сами узлы. Если вызывающий метод имеет ссылки на отдельные узлы в списке, он может не ожидать, что эти узлы будут иметь разные значения после сортировки списка. Это может стать неприятным сюрпризом. Многие проблемы с кодом потребуют, чтобы вы не изменяли data элементы узлов, а только их next свойства.
  2. Вы выбрали сортировку по пузырькам в качестве алгоритма сортировки. Это не очень эффективный алгоритм сортировки, и даже его реализацию можно было бы улучшить, остановив внутренний цикл раньше-зная, что конец списка сортируется постепенно, а внешний цикл также может завершиться раньше, когда будет обнаружено, что больше не было выполнено свопов. Но у вас будет более эффективный алгоритм, когда вы перейдете к сортировке слиянием или быстрой сортировке.
  3. Имя функции должно быть sort , так как оно изменяет данный список. Название sorted предполагает, что он не изменяет данный список, но создает новый список, который является его отсортированной версией.
  4. temp1 и temp2 не являются описательными именами переменных. Подумайте о более описательных именах.
  5. Вы написали «Почему он сортирует только один раз и, наконец, помещает 50, а остальные элементы остаются такими, как были раньше»., но данный код не ведет себя так: он сталкивается с исключением.
Метки: