Я боролся с реализацией очереди приоритетов со структурой связанного списка в Python.У меня есть методы вставки и методы удаления, однако возникают проблемы с методом, который мы должны написать с именем split_alt.
Очередь определена с помощью:
class _PQ_Node:
def __init__(self, value, _next):
"""
-------------------------------------------------------
Initializes a priority queue node that contains a copy of value
and a link to the next node in the priority queue
Use: node = _PQ_Node(value, _next)
-------------------------------------------------------
Parameters:
value - value value for node (?)
_next - another priority queue node (_PQ_Node)
Returns:
a new Priority_Queue object (_PQ_Node)
-------------------------------------------------------
"""
self._value = deepcopy(value)
self._next = _next
class Priority_Queue:
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty priority queue.
Use: pq = Priority_Queue()
-------------------------------------------------------
Returns:
a new Priority_Queue object (Priority_Queue)
-------------------------------------------------------
"""
self._front = None
self._rear = None
self._count = 0
Нам не разрешено ни обновлять какие-либо параметры, передаваемые в методы, ни писать новые методы.
То, что у меня пока есть для split_alt:
def split_alt(self):
"""
-------------------------------------------------------
Splits a priority queue into two with values going to alternating
priority queues. The source priority queue is empty when the method
ends. The order of the values in source is preserved.
Use: target1, target2 = source.split_alt()
-------------------------------------------------------
Returns:
target1 - a priority queue that contains alternating values
from the current queue (Priority_Queue)
target2 - priority queue that contains alternating values
from the current queue (Priority_Queue)
-------------------------------------------------------
"""
target1 = Priority_Queue()
target2 = Priority_Queue()
c = 0
current = self._front
while current:
if c % 2 == 0:
if not target1._front:
target1._front = current
target1._rear = current
t1 = target1._front
target1._count += 1
else:
t1._next = current
target1._rear = current
target1._count += 1
t1 = t1._next
else:
if not target2._front:
target2._front = current
target2._rear = current
t2 = target2._front
target2._count += 1
else:
t2._next = current
target2._rear = current
target2._count += 1
t2 = t2._next
self._front = current._next
current = self._front
c += 1
self._count -= 1
self._front = None
self._rear = None
return target1,target2
Наименьшее значение имеет наивысший приоритет.
Когда я запускаю это, по какой-то причине он всегда вставляет последнее значение в мой список target1 в качестве дубликата.Я в недоумении, почему.Тестирование со списком очередей с приоритетами, например, [11,22,33,44,55,66], например:
Значения Target1: 11 33 55 66
Значения Target2: 22 44 66
Источник:
Опять же, я не уверен, почему 66 добавляется и к target1.
Может кто-нибудь пролить свет на это?
Заранее признателен.