Перестановка 2 узлов в deque, python - PullRequest
Новая
       27

Перестановка 2 узлов в deque, python

0 голосов
/ 30 июня 2018

Я пытаюсь поменять местами два несмежных узла. Кроме того, они не являются передними или задними узлами, так что их предыдущий или следующий указатели не равны None. Python не имеет указателей, но я бы сослался на предыдущие и последующие ссылки на узлы узла как на его указатели для удобства. Однако проблема, с которой я сталкиваюсь, заключается в том, что, хотя переключение прошло успешно, предыдущие ссылки на указатели испортились. Здесь l - левый узел, а r - правый узел. 

def _swap(self, l, r):
    assert l is not None and r is not None, "nodes to swap cannot be None"

    temp = l._prev._next
    l._prev._next = r._prev._next
    r._prev._next = temp
    temp = l._next
    l._next = r._next
    r._next = temp
    temp = l._prev
    l._prev = r._prev
    r._prev = temp

    return

список до обмена: 4 5 2 7 1 8
список назад перед свопом: 8 1 7 2 5 4

Я заменяю узел, который содержит 5 как l, и узел, который содержит 7 как r.

список после обмена: 4 7 2 5 1 8
список в обратном порядке после обмена: 8 1 7 4

Я тестировал несколько раз несколькими методами, результат либо одинаковый, либо происходит какая-то бесконечная циклическая ссылка. Я думаю о том, что когда я изменяю следующие указатели, я уже испортил их предыдущие указатели, но не имею конкретного доказательства этого. Любая помощь будет принята с благодарностью. Спасибо.

1 Ответ

0 голосов
/ 30 июня 2018

Вы можете реализовать метод getitem, который будет извлекать значение по индексу, и метод setitem, чтобы обновить узел по индексу. Таким образом, простой метод swap может быть записан путем переназначения значений: 

def check_index(f):
  def wrapper(cls, _val, *args):
    if cls._next is None and _val:
      raise IndexError(f'{_val} exceeds length of deque')
    return f(cls, _val, *args)
  return wrapper

class Deque:
  def __init__(self, _val= None, _previous = None):
     self.value = _val
     self._next, self._previous = None, _previous
  @check_index
  def __getitem__(self, _index):
     return self.value if not _index else self._next[_index-1]
  @check_index
  def __setitem__(self, _index, _val):
     if not _index:
       self.value = _val
     else:
       self._next[_index-1] = _val
  def insert_val(self, _val, _trailing = None):
     if self.value is None:
        self.value = _val
     else:
        if self._next is None:
          self._next = Deque(_val, _trailing)
        else:
          self._next.insert_val(_val, self._next)
  def swap(self, _start, _finish):
    _temp = self[_start]
    self[_start] = self[_finish]
    self[_finish] = _temp
  def __str__(self):
    return f'{self.value}, {str(self._next)}' if self._next is not None else str(self.value)
  def __repr__(self):
     return f'Deque({str(self)})'

d = Deque()
for i in range(10):
  d.insert_val(i)
>>>d
Deque(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
>>>d.swap(2, 6) #swapping the third item with the 7th item
>>>d
Deque(0, 1, 6, 3, 4, 5, 2, 7, 8, 9)
...