Бесконечный цикл односвязных списков при совместном использовании элементов между списками в Python - PullRequest
Новая
       7

Бесконечный цикл односвязных списков при совместном использовании элементов между списками в Python

0 голосов
/ 12 мая 2018

Я реализовал связанный список с помощью Python 3.6, сам связанный список работает хорошо, но проблема заключается в том, что когда я пытаюсь создать следующий пример: 

3 -> 1 -> 5 -> 9 ->
                   7 -> 2
          4 -> 6 ->

Это означает, что у меня есть 2 связанных списка и вВ определенный момент они разделяют одни и те же элементы (7,2), код моего связанного списка следующий: 

class Element:    
    def __init__(self,value):
        self.next = None 
        self.value = value

class LinkedList:
    def __init__(self,head=None):
        self.head = head

    def append(self,new_element):
        current = self.head
        if current:
            while current.next:
                current = current.next
            current.next = new_element
        else:   
            self.head = new_element

    def print_linked(self):
        current = self.head
        while current:
            print(current.value, end=" ")
            current = current.next

e1 = Element(3)
e2 = Element(1)
e3 = Element(5)
e4 = Element(9)

e1p = Element(4)
e2p = Element(6)

e1s = Element(7)
e2s = Element(2)

# Start setting up a LinkedList
ll = LinkedList(e1)
ll.append(e2)
ll.append(e3)
ll.append(e4)
ll.append(e1s)
ll.append(e2s)

l2 = LinkedList(e1p)
l2.append(e2p)
l2.append(e1s)
l2.append(e2s)

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

3 1 5 9 7 2 2 2 2 2 2 2 [...]

Я что-то упустил?Помощь приветствуется.Спасибо

1 Ответ

0 голосов
/ 12 мая 2018

Давайте рассмотрим это: 

ll.append(e2)
ll.append(e3)
ll.append(e4)
ll.append(e1s)
ll.append(e2s)

После того, как этот код запустит внутреннее состояние последнего элемента (e2s), оно указывает на никуда.

Но тогда: 

l2.append(e2p)
l2.append(e1s)
l2.append(e2s)

Это заставляет последний элемент указывать на себя (l2.append(e2s) добавляется без учета циклов).Вы перебираете весь список и добавляете элемент , даже если он уже существует .

Поскольку состояние является внутренним для узлов (Element), у вас, вероятно, есть два варианта:

  1. Не делить состояние (сделать копию)
  2. Проверить выход узла и не допустить его повторения в списке

Вы можете поднятьошибка в случае дублирования элементов: 

def append(self,new_element):
    current = self.head
    if current is new_element:
        raise ValueError('can not duplicate node %s on list' % new_element)
    if current:
        while current.next:
            current = current.next
        current.next = new_element
    else:   
        self.head = new_element
...