Это мой класс узлов:
class Node:
def __init__(self, initData, initNext):
""" Constructs a new node and initializes it to contain
the given object (initData) and link to the given next node. """
self.data = initData
self.cover = True
self.next = initNext
# Additional attributes
def getData(self):
""" Returns the element """
return self.data
def getNext(self):
""" Returns the next node """
return self.next
def getDisplay(self):
#TODO
if self.cover == True:
return '_'
elif self.cover == False:
return self.data
def setData(self, newData):
""" Sets newData as the element """
self.data = newData
def setNext(self, newNext):
""" Sets newNext as the next node """
self.next = newNext
def setDisplay(self, newDisplay):
#TODO
if newDisplay == self.data:
self.cover = False
elif newDisplay != self.data:
self.cover = True
У меня есть односвязный список, который нужно отсортировать с помощью вставки.У меня есть хорошее понимание сортировки вставки с обычными списками, но не со связанными списками.Я нашел другой пост, и пользователь сказал это:
Давайте подумаем о том, как работает Insertion Sort: он «разделяет» (теоретически) список на три группы: отсортированное подмножество (которое может быть пустым), текущий элемент и несортированное подмножество (которое может быть пустым).Все до текущего элемента отсортировано.Все после текущего элемента может быть или не быть отсортировано.Алгоритм проверяет текущий элемент, сравнивая его со следующим элементом.Помните, что первый элемент после текущего элемента принадлежит несортированному подмножеству.
Предположим, что вы сортируете целые числа в порядке возрастания (поэтому, получив «3,1,5,2,4», вы хотите получить »1,2,3,4,5" ).Вы устанавливаете текущий элемент на первый элемент в списке.Теперь вы начинаете сортировку:
Если следующий элемент больше текущего, вам не нужно сортировать этот элемент.Просто сделайте его «текущим элементом» и продолжайте.
Если следующий элемент меньше текущего элемента, то вам есть над чем поработать.Сначала сохраните следующий элемент где-нибудь, скажем, в указателе с именем temp, а затем «удалите» следующий элемент из списка, сделав current-> next = current-> next-> next.Теперь вам нужно найти правильное место для удаленного предмета.Вы можете сделать это двумя способами:
Либо начните с начала списка, двигаясь вперед, пока не найдете правильную позицию.Как только вы это сделаете, вы вставите элемент туда и продолжите сортировку вставки.Это самое простое решение, если у вас есть односвязный список.Вы идете назад, пока не найдете правильное место для предмета.Как только вы это сделаете, вы вставите элемент туда и продолжите сортировку вставки.Это немного сложнее, но может хорошо работать, если у вас есть двусвязный список.Вы продолжаете этот процесс, пока не достигнете конца списка.Как только вы дойдете до него, вы узнаете, что завершили сортировку вставкой, и список находится в правильном порядке сортировки.
Надеюсь, это поможет.
Ссылка на ответ
Я пытался создать свой код после этого поста, но не знаю, как найти правильное место для элемента, а затем вставить его.Это мой код:
def sort(self):
head = self.linkedList.head
current = head
while current != None:
if current.getNext().getData() > current.getData():
current = current.getNext()
else:
temp = current
current.setNext(current.getNext().getNext())
#I am not sure what to do here
Кто-нибудь может мне помочь?