Перемещение узла в конце цепочки узлов

Question

У меня есть функция, где я должен переместить существующий код, например

def print_chain_and_ids(chain): 
    current = chain 
    while current != None: 
     print(id(current), current.get_data()) 
     current = current.get_next() 

a = Node('first') 
b = Node('middle') 
c = Node('last') 
a.set_next(b) 
b.set_next(c) 

print_chain_and_ids(a) 
move_node_to_end(a, 'middle')  

print_chain_and_ids(a) 

так что теперь цепь идет:

a ----> b ----> c

с узлом c в конце цепи.

Если бы я хотел, чтобы переместить узел b до конца цепи так далее:

a ----> c ----> b

так, что она не изменяет значение последнего узла, а просто перемещает его вокруг. У меня есть класс узлов, готовый:

class Node: 
    def __init__(self, init_data): 
     self.data = init_data 
     self.next = None 

    def get_data(self): 
     return self.data 

    def get_next(self): 
     return self.next 

    def set_data(self, new_data): 
     self.data = new_data 

    def set_next(self, new_next): 
     self.next = new_next 

    def __str__(self): 
     return str(self.data) 

Я хотел знать, как я буду заниматься этим.

Я хочу сделать, чтобы сделать функцию, которая принимает два входа, первый узел цепочки, а также значение, которое перемещается в последнее положение цепочки. Итак:

def node_to_end(first_node, value_to_move): 
    ..... 

Здесь я должен изменить положение узлов. Таким образом, значение для перемещения переходит к последней позиции.

a = Node('blue') 
b = Node('red') 
c = Node('green') 

a.set_next(b) 
b.set_next(c) 

, который приведет к blue red green

node_to_end(a, 'red') 

бы создать цепочку

blue green red

Спасибо за любую помощь.

Answer 1

Ваша цепочка узлов очень похожа на так называемый односвязный список.С этими узлами обычно удаляются узлы, отслеживая предыдущий узел при прохождении по списку, таким образом, когда целевой узел будет найден, вы узнаете, какой из них (если он есть) появился перед ним. Наличие этой части информации позволяет легко изменять список.

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

class Node: 
    def __init__(self, init_data): 
     self.data = init_data 
     self.next = None 

    def get_data(self): 
     return self.data 

    def get_next(self): 
     return self.next 

    def set_data(self, new_data): 
     self.data = new_data 

    def set_next(self, new_next): 
     self.next = new_next 

    def __str__(self): 
     return str(self.data) 

def move_to_end(start, target): 
    """Move target node from the chain beginning with start to end.""" 
    previous = None 
    current = start 
    while current: 
     if current.get_next() is target: 
      previous = current 
      break 
     current = current.get_next() 

    if previous: # target found in chain? 
     previous.set_next(target.get_next()) # remove it 
     # and move it to the end 
     current = target 
     while current: 
      if not current.get_next(): # last node in chain? 
       target.set_next(None) 
       current.set_next(target) 
       break 
      current = current.get_next() 

def print_node_chain(start): 
    """Utility to print out a node chain starting from given node.""" 
    values = [] 
    current = start 
    while current: 
     values.append(str(current)) 
     current = current.get_next() 

    print(' ----> '.join(values) + ' ----> None') 

a = Node('blue') 
b = Node('red') 
c = Node('green') 

a.set_next(b) 
b.set_next(c) 

print_node_chain(a) 
move_to_end(a, b) 
print_node_chain(a) 

Выход:

blue ----> red ----> green ----> None 
blue ----> green ----> red ----> None 

Answer 2

Ну, это потребует некоторых вычислений. Давайте предположим, что общий случай:

е _я-1 - > е _я - > е _{я + 1} - > ... - > е _п

Теперь мы хотим для перемещения e _i до последней позиции:

е _я-1 - > е _{я + 1} - > ... - > е _п - > е _я

Итак, вопрос: что должно измениться?Основываясь на общем случае, есть три указатели, которые должны изменить:

• е _я-1 теперь указывает на е _{я + 1};
• e _i теперь указывает на ничто (None); и
• е _п теперь указывает на е _я.

Теперь, так как связанный список не двусвязного: узел не имеет никакого отношения к предыдущему узлу, единственное, что мы можем сделать, чтобы получить предыдущий элемент, является итерация от корня, пока мы не найдем элемент:

def get_prev_element(root,node): 
    while root.get_next() is not node: 
     root = root.get_next() 

После того, как мы имеем предыдущий элемент, мы можем позволить ему ссылку на следующий элемент:

previous.set_next(node.get_next()) 

Но теперь нам еще нужно выяснить, что такое последний элемент. И угадайте, что мы делаем это снова, по переборе, мы можем, однако начать с нашего собственного узла:

def get_last(node): 
    while node.get_next() is not None: 
     node = node.get_next() 
    return node 

Теперь мы устанавливаем next последнего узла, к нашему собственному узлу:

last.set_next(node) 

и, наконец, мы устанавливаем наши собственные рядом с None:

node.set_next(None) 

Теперь группируя все это вместе, мы можем определить метод на узле:

class Node: 

    # ... 

    def get_previous(self,root): 
     previous = root 
     while previous.get_next() is not self: 
      previous = previous.get_next() 
     return previous 

    def get_last(self): 
     last = self 
     while last.get_next() is not None: 
      last = last.get_next() 
     return last 

    def move_last(self,root): 
     previous = self.get_previous(root) 
     previous.set_next(self.get_next()) 
     last = self.get_last() 
     last.set_next(self) 
     self.set_next(None) 

Обратите внимание, что, поскольку связанный список не Двусвязные, вы должны будете дать ему корневой элемент.

---

Интермеццо: даны у вас есть ссылки на a, b и c. Конечно, нет причин для расчета предыдущего и последнего: вы знаете, что a является предыдущим и что c является последним. Таким образом, в этом случае код просто:

a.set_next(c) 
c.set_next(b) 
b.set_next(None) 

---

Этот код не работает, если корневой элемент сам узел. Я оставляю это как упражнение, чтобы изменить код, чтобы он работал правильно. Это не очень сложно.