Início / coding / Perguntas / 78899905
Accepted
simply lemon
Asked: 2024-08-22 13:24:10 +0800 CST

Método “add” para lista vinculada em python

  • 772

Estou tentando escrever um método add para lista vinculada em python, mas não está se comportando conforme o esperado.

class linkedlist:
    def __init__(self):
       self.item=None
       self.next=None
    def add(self,val):
       self.next=self
       self.item=val

Isso não funciona. Quando eu crio um objeto:

myobj=linkedlist()
myobj.add(1)
myobj.add(2)
print(myobj.next.item)

dá 2, em vez de 1, como seria de esperar. Onde foi que eu errei?

Tentei consultar É seguro substituir um objeto próprio por outro objeto do mesmo tipo em um método? mas não está ajudando.

python

2 respostas

  1. Eu sugiro que você separe os tipos nodee linkedliste node. A nodetem uma referência ao next node. Embora a linkedlisttenha uma referência a head nodee geralmente a a tail node, adicionar um novo nodeé uma operação constante (ou seja, não requer percorrer toda a lista). Isso torna mais fácil ver que você precisa de uma nova nodeinstância por chamada para add():

    class node:
    def __init__(self, item):
       self.item=item
       self.next=None

class linkedlist:
    def __init__(self):
        self.head = None
        self.tail = None
    def add(self, val):
        n = node(val)
        if self.head:
            self.tail.next = n
        else:
            self.head = n
        self.tail = n

myobj=linkedlist()
myobj.add(1)
myobj.add(2)
myobj.add(3)
print(
        myobj.head.item,
        myobj.head.next.item,
        myobj.head.next.next.item
)

    e aqui está um exemplo de saída:

    1 2 3
    • 3
  2. Best Answer

    Você tem apenas 1 objeto e 2 referências apontando para ele. Você precisa copiar a lista antes de adicioná-la:

    from copy import copy

class linkedlist:
    def __init__(self):
       self.item=None
       self.next=None
    def add(self,val):
       self.next=copy(self)
       self.item=val

myobj=linkedlist()
myobj.add(1)
myobj.add(2)
print(myobj.next.item) # prints 1

    Para esclarecer:

    print(myobj.item, id(myobj))
print(myobj.next.item, id(myobj.next))

    com seu código:

    2 140520931226768
2 140520931226768 # same object!

    Com o meu:

    2 140520931224368
1 140519593761456

    ATUALIZAR:

    Primeiro, suas expectativas estão erradas, você deve obter 3 e 2, que são os valores deixados na lista depois que você estourou a cabeça. Para obter esses resultados, você precisa atualizar o que aaponta. Você poderia fazer isso adicionando return selfno final dos métodos addand pope reatribuindo a:

    from copy import copy

class linkedlist:
    def __init__(self):
       self.item=None
       self.next=None
    def add(self,val):
       self.next=copy(self)
       self.item=val
       return self
    def pop(self):
       self=copy(self.next)
       return self
    
a=linkedlist()
a = a.add(1)
a = a.add(2)
a = a.add(3)
a = a.add(4)
a = a.pop()
print(a.item)
a = a.pop()
print(a.item)

    Mas, na IMO, isso é bastante feio e prefiro usar a abordagem de Allan ...

    • -1

relate perguntas