В прошлой статье мы начали обсуждение связанного списка. Мы увидели, что такое связанный список, а также его преимущества и недостатки. Мы также изучили некоторые из наиболее часто используемых методов связанного списка, такие как обход, вставка, удаление, поиск и подсчет элемента. Наконец, мы увидели, как перевернуть связанный список.
В этой статье мы продолжим с того места, где мы остановились в предыдущей статье, и увидим, как отсортировать связанный список с помощью пузырьковой сортировки и сортировки слиянием, а также как объединить два отсортированных связанных списка.
Прежде чем мы продолжим, необходимо обязательно упомянуть, что вы должны
создать Node и LinkedList которые мы создали в предыдущей статье.
Сортировка связанного списка с помощью пузырьковой сортировки
Есть два способа отсортировать связанный список с помощью пузырьковой сортировки :
- Обмен данными между узлами
- Изменение связей между узлами
В этом разделе мы увидим, как работают оба этих подхода. Мы будем использовать алгоритм пузырьковой сортировки, чтобы сначала отсортировать связанный список путем изменения данных, а затем мы увидим, как мы можем использовать пузырьковую сортировку для изменения ссылок, чтобы отсортировать связанный список.
Сортировка связанного списка по обмену данными
Чтобы отсортировать связанный список путем обмена данными, нам нужно
объявить три переменные p , q и end .
Переменная p будет инициализирована начальным узлом, а end будет
установлен в None .
Важно помнить, что для сортировки списка с n элементами с помощью
пузырьковой сортировки вам потребуется n-1 итераций.
Чтобы реализовать пузырьковую сортировку, нам понадобятся два цикла
while. Внешний цикл while выполняется до тех пор, пока значение
переменной end станет равным self.start_node .
Внутренний цикл while выполняется до тех пор, пока p станет равным
end переменной. Внутри внешнего цикла while значение p будет
установлено на self.start_node который является первым узлом. Внутри
внутреннего цикла while значение q будет установлено p.link который
на самом деле является узлом рядом с q . Затем значения p и q
будут сравниваться, если p больше q p.ref местами, и тогда p
будет указывать на p.ref, который является следующим узлом. Наконец,
end будет присвоено значение p . Этот процесс продолжается до тех
пор, пока связанный список не будет отсортирован.
Давайте разберемся в этом процессе на примере. Предположим, у нас есть следующий список:
8,7,1,6,9
Реализуем наш алгоритм сортировки списка. Посмотрим, что будет происходить на каждой итерации. Цель пузырьковой сортировки заключается в том, что во время каждой итерации наибольшее значение должно быть сдвинуто до конца, поэтому в конце всех итераций список будет автоматически отсортирован.
Перед выполнением цикла значение end устанавливается в None .
На первой итерации p будет установлено на 8, а q будет установлено
на 7 . Поскольку p больше q , значения будут переставлены, и p
станет p.ref . В этот момент связанный список будет выглядеть так:
7,8,1,6,9
Поскольку в этот момент p не равно end , цикл будет продолжен, и
теперь p станет 8, а q станет 1. Поскольку снова p больше q ,
значения снова поменяются местами, и p снова станет p.ref . Список
будет выглядеть так:
7,1,8,6,9
Здесь снова p не равно end , цикл будет продолжен, и теперь p
станет 8, а q станет 6. Поскольку снова p больше q p.ref
местами, и p снова станет p.ref. Список будет выглядеть так:
7,1,6,8,9
Снова p не равно end , цикл будет продолжен, и теперь p станет 8,
а q станет 9. Здесь, поскольку p не больше q , значения не будут
меняться, и p станет p.ref . В этот момент ссылка p будет
указывать на None , а end также указывает на None . Следовательно,
внутренний цикл while будет прерван, а end будет установлен на p .
В следующем наборе итераций цикл будет выполняться до 8, поскольку 9 уже в конце. Процесс продолжается до тех пор, пока список не будет полностью отсортирован.
Код Python для сортировки связанного списка с помощью пузырьковой сортировки путем обмена данными выглядит следующим образом:
def bub_sort_datachange(self):
end = None
while end != self.start_node:
p = self.start_node
while p.ref != end:
q = p.ref
if p.item > q.item:
p.item, q.item = q.item, p.item
p = p.ref
end = p
Добавьте метод bub_sort_dataexchange() в LinkedList который вы
создали в предыдущей статье.
После добавления метода в связанный список создайте любой набор узлов с
помощью функции make_new_list() а затем используйте
bub_sort_dataexchange() для сортировки списка. Вы должны увидеть
отсортированный список при выполнении функции traverse_list() .
Сортировка связанного списка путем изменения ссылок
Пузырьковая сортировка также может использоваться для сортировки
связанного списка путем изменения ссылок вместо изменения данных.
Процесс остается очень похожим на сортировку списка путем обмена
данными, однако в этом случае у нас есть дополнительная переменная r ,
которая всегда будет соответствовать узлу, предшествующему узлу p
Давайте рассмотрим простой пример того, как мы поменяем местами два узла, изменив ссылки. Предположим, у нас есть связанный список со следующими элементами:
10,45,65,35,1
И мы хотим поменять местами 65 и 35. В этот момент p соответствует
узлу 65, а q соответствует узлу 35. Переменная r будет
соответствовать узлу 45 (предшествующему узлу p ). Теперь, если узел
p больше, чем узел q , как здесь, p.ref будет установлен на
q.ref а q.ref будет установлен на p . Точно так же для r.ref
будет установлено значение q . Это поменяет местами узлы 65 и 35.
Следующий метод реализует пузырьковую сортировку для связанного списка путем изменения ссылок:
def bub_sort_linkchange(self):
end = None
while end != self.start_node:
r = p = self.start_node
while p.ref != end:
q = p.ref
if p.item > q.item:
p.ref = q.ref
q.ref = p
if p != self.start_node:
r.ref = q
else:
self.start_node = q
p,q = q,p
r = p
p = p.ref
end = p
Добавьте метод bub_sort_linkchange() в LinkedList который вы создали
в предыдущей статье.
После добавления метода в связанный список создайте любой набор узлов,
используя make_new_list() а затем используйте bub_sort_linkchange()
для сортировки списка. Вы должны увидеть отсортированный список при
выполнении функции traverse_list() .
Объединение отсортированного связного списка
В этом разделе мы увидим, как мы можем объединить два отсортированных связанных списка таким образом, чтобы полученный связанный список также был отсортирован. Для этого есть два подхода. Мы можем создать новый связанный список, который содержит индивидуально отсортированные списки, или мы можем просто изменить ссылки двух связанных списков, чтобы присоединиться к двум отсортированным связанным спискам. Во втором случае нам не нужно создавать новый связанный список.
Давайте сначала посмотрим, как мы можем объединить два связанных списка, создав новый список.
Объединение отсортированных связанных списков путем создания нового списка
Давайте сначала протестируем алгоритм, чтобы увидеть, как мы можем объединить два отсортированных связанных списка с помощью нового списка.
Предположим, у нас есть следующие два отсортированных связанных списка:
list1:
10,45,65,
list2:
5,15,35,68
Это два списка, которые мы хотим объединить. Алгоритм прост. Все, что
нам понадобится, это три переменные p , q и em и пустой список
newlist .
В начале алгоритма p будет указывать на первый элемент list1 тогда
как q укажет на первый элемент list2 . Переменная em будет пустой.
В начале алгоритма у нас будут следующие значения:
p = 10
q = 5
em = none
newlist = none
Затем мы сравним первый элемент list1 с первым элементом list2 ,
другими словами, мы сравним значения p и q и меньшее значение будет
сохранено в переменной em которая станет первым узлом списка новый
список. Значение em будет добавлено в конец newlist .
После первого сравнения у нас будут следующие значения:
p = 10
q = 15
em = 5
newlist = 5
Поскольку q было меньше p , мы сохраняем значение q в em
перемещаемом 'q' на один индекс вправо. Во втором проходе у нас будут
следующие значения:
p = 45
q = 15
em = 10
newlist = 5, 10
Здесь, поскольку p было меньше, мы добавляем значение p в newlist
и устанавливаем em p а затем перемещаем p один индекс вправо. В
следующей итерации мы имеем:
p = 45
q = 35
em = 15
newlist = 5, 10, 15
Аналогичным образом на следующей итерации:
p = 45
q = 68
em = 35
newlist = 5, 10, 15, 35
И на следующей итерации p снова будет меньше q , следовательно:
p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45
Ну наконец то,
p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65
Когда один из списков становится None , все элементы второго списка
добавляются в конец нового списка. Таким образом, окончательный список
будет:
p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68
Скрипт Python для объединения двух отсортированных списков выглядит следующим образом:
def merge_helper(self, list2):
merged_list = LinkedList()
merged_list.start_node = self.merge_by_newlist(self.start_node, list2.start_node)
return merged_list
def merge_by_newlist(self, p, q):
if p.item <= q.item:
startNode = Node(p.item)
p = p.ref
else:
startNode = Node(q.item)
q = q.ref
em = startNode
while p is not None and q is not None:
if p.item <= q.item:
em.ref = Node(p.item)
p = p.ref
else:
em.ref = Node(q.item)
q = q.ref
em = em.ref
while p is not None:
em.ref = Node(p.item)
p = p.ref
em = em.ref
while q is not None:
em.ref = Node(q.item)
q = q.ref
em = em.ref
return startNode
В приведенном выше скрипте у нас есть два метода: merge_helper() и
merge_by_newlist() . Первый метод merge_helper() принимает связанный
список в качестве параметра, а затем передает self класс, который
представляет собой сам связанный список и связанный список, переданный
ему в качестве параметра, merge_by_newlist() .
Метод merge_by_newlist() объединяет два связанных списка, создавая
новый связанный список, и возвращает начальный узел нового связанного
списка. Добавьте эти два метода в класс LinkedList Создайте два новых
связанных списка, отсортируйте их с помощью bub_sort_datachange() или
bub_sort_linkchange() которые вы создали в последнем разделе, а затем
используйте merge_by_newlist() чтобы узнать, можете ли вы объединить
два отсортированных связанных списка или нет.
Объединение отсортированных связанных списков путем перестановки ссылок
В этом подходе новый связанный список не используется для хранения слияния двух отсортированных связанных списков. Скорее, ссылки двух связанных списков изменяются таким образом, что два связанных списка объединяются в отсортированном порядке.
Давайте посмотрим на простой пример того, как мы можем это сделать.
Предположим, у нас есть те же два списка list1 и list2 :
list1:
10,45,65,
list2:
5,15,35,68
Мы хотим объединить их упорядоченным образом, переставив ссылки. Для
этого нам потребуются переменные p , q и em . Изначально они будут
иметь следующие значения:
p = 10
q = 5
em = none
newlist = none
Затем мы сравним первый элемент list1 с первым элементом list2 ,
другими словами, мы сравним значения p и q и меньшее значение будет
сохранено в переменной em которая станет первым узлом списка новый
список.
После первого сравнения у нас будут следующие значения:
p = 10
q = 15
start = 5
em = start
После первой итерации, поскольку q меньше p , начальный узел будет
указывать на q а q станет q.ref . em будет равен начать. em
всегда будет относиться к вновь вставленному узлу в объединенном списке.
p = 45
q = 15
em = 10
Здесь, поскольку p было меньше q , переменная em теперь указывает
на исходное значение p а p становится p.ref .
p = 45
q = 35
em = 15
Здесь, поскольку q было меньше p , em указывает на q а q
становится q.ref .
p = 45
q = 68
em = 35
Точно так же em здесь указывает на q .
p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45
И здесь em указывает на становится p .
p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65
Когда один из списков становится None , элементы из второго списка
просто добавляются в конец.
p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68
Скрипт, содержащий функции для объединения двух списков без создания нового списка, выглядит следующим образом:
def merge_helper2(self, list2):
merged_list = LinkedList()
merged_list.start_node = self.merge_by_linkChange(self.start_node, list2.start_node)
return merged_list
def merge_by_linkChange(self, p, q):
if p.item <= q.item:
startNode = Node(p.item)
p = p.ref
else:
startNode = Node(q.item)
q = q.ref
em = startNode
while p is not None and q is not None:
if p.item <= q.item:
em.ref = Node(p.item)
em = em.ref
p = p.ref
else:
em.ref = Node(q.item)
em = em.ref
q = q.ref
if p is None:
em.ref = q
else:
em.ref = p
return startNode
В приведенном выше скрипте у нас есть два метода: merge_helper2() и
merge_by_linkChange() . Первый метод merge_helper2() принимает
связанный список в качестве параметра, а затем передает собственный
класс, который является самим связанным списком, и связанный список,
переданный ему в качестве параметра, в merge_by_linkChange() , которая
объединяет два связанных путем изменения связывает и возвращает
начальный узел объединенного списка. Добавьте эти два метода в класс
LinkedList Создайте два новых связанных списка, отсортируйте их с
помощью bub_sort_datachange() или bub_sort_linkchange() которые вы
создали в последнем разделе, а затем используйте merge_by_newlist()
чтобы узнать, можете ли вы объединить два отсортированных связанных
списка или нет. Давайте посмотрим на этот процесс в действии.
Создайте новый связанный список, используя следующий скрипт:
new_linked_list1 = LinkedList()
new_linked_list1.make_new_list()
Сценарий запросит у вас количество узлов для входа. Введите столько узлов, сколько хотите, а затем добавьте значения для каждого узла, как показано ниже:
How many nodes do you want to create: 4
Enter the value for the node:12
Enter the value for the node:45
Enter the value for the node:32
Enter the value for the node:61
Затем создайте еще один связанный список, повторяя описанный выше процесс:
new_linked_list2 = LinkedList()
new_linked_list2.make_new_list()
Затем добавьте несколько фиктивных узлов с помощью следующего скрипта:
How many nodes do you want to create: 4
Enter the value for the node:36
Enter the value for the node:41
Enter the value for the node:25
Enter the value for the node:9
Следующим шагом является сортировка обоих списков. Выполните следующий скрипт:
new_linked_list1. bub_sort_datachange()
new_linked_list2. bub_sort_datachange()
Наконец, следующий скрипт объединяет два связанных списка:
list3 = new_linked_list1.merge_helper2(new_linked_list2)
Чтобы проверить, действительно ли списки были объединены, выполните следующий скрипт:
list3.traverse_list()
Результат выглядит так:
9
12
25
32
36
41
45
61
Заключение
В этой статье мы продолжили то, что мы оставили в предыдущей статье . Мы видели, как можно сортировать списки слияния, изменяя данные, а затем мои ссылки. Наконец, мы также изучили различные способы объединения двух отсортированных связанных списков.
В следующей статье мы рассмотрим, как создавать и выполнять операции над двусвязными списками.