[python-brasil] Remover elemento - lista encadeada
cairoaorocha
Bom dia,
Eu acompanho a lista a um tempo, mas nunca havia postado. Meu nome é
Cairo Rocha, sou estudante do 4º período em ciencias da computação e
escolhi Python para me auxiliar nos meus trabalhos a partir desse
período(quando for permitido escolha de linguagem).
Foi me passado um trabalho de revisão sobre listas encadeadas, quando
paguei Estruturas de Dados fiz em C++ mas agora pretendo fazer esse
pequeno exercicio em Python.
Minha dúvida é na parte de remoção de um elemento, quando eu realoco
os ponteiros, como faço pra remover o elemento desejado(em C free, em
C++ delete) ?
| Antes de enviar um e-mail para o grupo leia: |
| http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar |
| E se você é usuário do BOL lembre-se de cadastrar o |
| e-mail do grupo na lista branca do seu sistema anti-spam. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
__,_._,___
Bruno Gola
Opa,
2008/8/17 cairoaorocha <cairoaorocha@gmail.com>:
> Minha dúvida é na parte de remoção de um elemento, quando eu realoco
> os ponteiros, como faço pra remover o elemento desejado(em C free, em
> C++ delete) ?
Ficou muito vaga sua dúvida.
Geralmente quando você quer "liberar" a memoria utilizada por um
elemento basta não referencia-lo que o GC faz a sua parte. Para isso
você pode usar o del.
>>> a = "xxxxxx"
>>> del a
Mas, seria legal voce mandar sua implementação ou especificar melhor o
problema :-D
[]'s,
--
Bruno Fialho Marques Gola <brunogola@gmail.com>
http://www.brunogola.com.br
Cel: (11) 9294-5883
__,_._,___
Joao S. O. Bueno
On Sunday 17 August 2008, cairoaorocha wrote:
> Bom dia,
>
> Eu acompanho a lista a um tempo, mas nunca havia postado. Meu nome
> é Cairo Rocha, sou estudante do 4º período em ciencias da
> computação e escolhi Python para me auxiliar nos meus trabalhos a
> partir desse período(quando for permitido escolha de linguagem).
>
> Foi me passado um trabalho de revisão sobre listas encadeadas,
> quando paguei Estruturas de Dados fiz em C++ mas agora pretendo
> fazer esse pequeno exercicio em Python.
>
> Minha dúvida é na parte de remoção de um elemento, quando eu
> realoco os ponteiros, como faço pra remover o elemento desejado(em
> C free, em C++ delete) ?
>
Oi Caio -
Ao contrário das coisas teóricas importantes que você tem que aprender
nessa disciplina, Python é uma linguagem apra alta-produtvidade e de
alto nível.
Você deve ter percebido como as lisats ligadas são elementos
importantes na implantação memso de programas simples, que dirá de
coisas que exijam funcionalidades mais complexas.
Uma vez que as listas são algo tão básico, as mesmsas já vem
totalmente implementadas em python - com funcionalidades que
provavelemnte vão bem além das que você está vendo agora.
Assim, para apagar um elemneto de uma lisat, em python, basta o
statement:
del <número do item>
Como voc ê pode ver, não será muito educativo para voce entender como
ponteiros funcionam e toda a lógica por baixo do capô aí.
Se você já fez o exercício em C, para um exercio de algum valor em
python, acho que o interessante seria você emular a memoria física do
computador - com um objeto buffer ou array (módulo array, classe
array) - e implementar uma lista ligada que use estruturas de dados
em bytes e ponteiros (com "endereços" que seriam índices dentro da
array. ) (para montar estruturas de dados com campos em bytes, como
os struct do C, use o mõdulo struct)
Dessa forma, você teria oportunidade para entender bem o que são
ponteiros mesmo - uma vez que teria que, idealmente, implementar
inclusive uma versão simplificada de controle de memória, que em
geral cabe ao sistema operacional.
>
> ------------------------------------
>
> ,----------------------------------------------------------.
>
> | Antes de enviar um e-mail para o grupo leia: |
> | http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar |
> | E se você é usuário do BOL lembre-se de cadastrar o |
> | e-mail do grupo na lista branca do seu sistema anti-spam. |
>
> `----------------------------------------------------------´Links
> do Yahoo! Grupos
>
__,_._,___
Rodrigo Bernardo Pimentel
On Mon, Aug 18 2008 at 03:20:32PM BRT, Bruno Gola <brunogola@gmail.com> wrote:
> 2008/8/17 cairoaorocha <cairoaorocha@gmail.com>:
> > Minha dúvida é na parte de remoção de um elemento, quando eu realoco
> > os ponteiros, como faço pra remover o elemento desejado(em C free, em
> > C++ delete) ?
>
> Ficou muito vaga sua dúvida.
>
> Geralmente quando você quer "liberar" a memoria utilizada por um
> elemento basta não referencia-lo que o GC faz a sua parte. Para isso
> você pode usar o del.
Se a sua implementação estiver arrumadinha, nem precisa disso. Se você usa
uma estrutura do tipo:
class Node:
def __init__(self, value, next):
self.value = value
self.next = next
Pra excluir um nó da lista, você faz:
anterior.next = anterior.next.next
e pronto. Se não há mais referências ao nó "excluido", o garbage collector
toma conta dele.
rbp
--
Rodrigo Bernardo Pimentel <rbp@isnomore.net> | GPG: <0x0DB14978>
__,_._,___
cairoaorocha
> Se a sua implementação estiver arrumadinha, nem precisa disso. Se
você usa
> uma estrutura do tipo:
>
> class Node:
> def __init__(self, value, next):
> self.value = value
> self.next = next
>
> Pra excluir um nó da lista, você faz:
>
> anterior.next = anterior.next.next
>
> e pronto. Se não há mais referências ao nó "excluido", o garbage
collector
> toma conta dele.
>
>
>
> rbp
> --
> Rodrigo Bernardo Pimentel <rbp@...> | GPG: <0x0DB14978>
>
Era essa parte que eu estava interessado. Obrigado.
Eu já fiz toda estruturas de dados em C para entender a manipulação de
ponteiros, esse trabalho é de Projeto e Analise de Algoritmos, e é
apenas uma revisão, mas como eu quis fazer em Python fiquei com essa
dúvida. Não posso utilizar as listas de Python, pois tenho que criar
meu próprio TAD.
Obrigado a todos que responderam, estudarei com cuidado as respostas.
Abraços.
Cairo Rocha.
| Antes de enviar um e-mail para o grupo leia: |
| http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar |
| E se você é usuário do BOL lembre-se de cadastrar o |
| e-mail do grupo na lista branca do seu sistema anti-spam. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
__,_._,___
Luciano Ramalho
2008/8/18 cairoaorocha <cairoaorocha@gmail.com>:
> Era essa parte que eu estava interessado. Obrigado.
>
> Eu já fiz toda estruturas de dados em C para entender a manipulação de
> ponteiros, esse trabalho é de Projeto e Analise de Algoritmos, e é
> apenas uma revisão, mas como eu quis fazer em Python fiquei com essa
> dúvida. Não posso utilizar as listas de Python, pois tenho que criar
> meu próprio TAD.
>
> Obrigado a todos que responderam, estudarei com cuidado as respostas.
>
> Abraços.
> Cairo Rocha.
Cairo, existe um excelente livro (online) introdutório de computação
com estruturas de dados em Python em português: chama-se "Aprenda
Computação com Python"
O capítulo 8 é sobre listas:
http://pensarpython.incubadora.fapesp.br/portal/livro/capitulo_08.rst/
[ ]s
Luciano
__,_._,___
Paul Eipper
Em 18/08/08, cairoaorocha<cairoaorocha@gmail.com> escreveu:
> Eu já fiz toda estruturas de dados em C para entender a manipulação de
> ponteiros, esse trabalho é de Projeto e Analise de Algoritmos, e é
> apenas uma revisão, mas como eu quis fazer em Python fiquei com essa
> dúvida. Não posso utilizar as listas de Python, pois tenho que criar
> meu próprio TAD.
>
> Obrigado a todos que responderam, estudarei com cuidado as respostas.
Fiz a implementação de uma lista encadeada em Python para a faculdade
também, está neste link, se quiser dar uma olhada:
http://www.inf.ufsc.br/~lkraider/2007-1/py/lista/
elemento.py é o Node da lista (é, fiz o código em pt_BR :)
lista.py contém 3 classes, uma da lista base, outra de interface de
mais alto nível para uso da lista (assim dava pra eu trocar a lista
"backend" sem precisar alterar a API de uso na interface), e outra
para as exceções, heh
testa_lista.py são os testes unitários usados ao desenvolver a lista
lista_view.py é uma interface simples em glade+kiwi para apresentar a
lista funcionando :P
--
Paul Eipper
__,_._,___
cairoaorocha
Respondendo a todos:
Minha dúvida foi sanada, era sobre o Garbage Collector mesmo.
A disciplina que eu estou pagando é Analise e Projeto de algoritmos,
esse é um trabalho introdutório, e como fiz estruturas de dados toda
em C++, escolhi fazer em Python.
Já li essa apostila "Pensando como um computólogo", inclusive me
baseei nela. Sobre os conceitos de ponteiro, acho que já os tenho bem
fixado.
Sobre a lista encadeada simples ela está redondinha, agora surge outro
problema: a lista encadeada dupla não consigo remover um elemento que
não for o 'cabeça'. Segue o código: http://paste.la/3286
Peço ajuda mais uma vez, e desde já, obrigado a todos.
| Antes de enviar um e-mail para o grupo leia: |
| http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar |
| E se você é usuário do BOL lembre-se de cadastrar o |
| e-mail do grupo na lista branca do seu sistema anti-spam. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
__,_._,___
Paul Eipper
Em 19/08/08, cairoaorocha<cairoaorocha@gmail.com> escreveu:
> Sobre a lista encadeada simples ela está redondinha, agora surge outro
> problema: a lista encadeada dupla não consigo remover um elemento que
> não for o 'cabeça'. Segue o código: http://paste.la/3286
Acho que fica mais ou menos assim:
if noExclui:
if noExclui == self.cabeca:
self.cabeca = self.cabeca.prox
else:
noFrente = noExclui.prox
noTras = noExclui.ant
if noFrente:
noFrente.ant = noTras
if noTras:
noTras.prox = noFrente
Só precisa ligar os nós que eram o ant e prox do noExclui entre si.
--
Paul Eipper
| Antes de enviar um e-mail para o grupo leia: |
| http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar |
| E se você é usuário do BOL lembre-se de cadastrar o |
| e-mail do grupo na lista branca do seu sistema anti-spam. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
__,_._,___
Rodrigo Bernardo Pimentel
On Tue, Aug 19 2008 at 08:29:42AM BRT, cairoaorocha <cairoaorocha@gmail.com> wrote:
> Sobre a lista encadeada simples ela está redondinha, agora surge outro
> problema: a lista encadeada dupla não consigo remover um elemento que
> não for o 'cabeça'. Segue o código: http://paste.la/3286
Bom, ali seu problema é de lógica, não exatamente de Python. Dê uma olhada
(linhas 44-48 do seu código):
if noExclui == self.cabeca:
self.cabeca = self.cabeca.prox
else:
noExclui.ant = noExclui.prox
Pensa bem... Você quer *excluir* noExclui e fazer com que o anterior a
noExclui aponte para o proximo a noExclui (e vice-versa, já que a lista é
duplamente ligada). O que você está fazendo é mudar quem o noExclui acha que
é seu antecessor (o que realmente não faz sentido). Desenhe a cadeia de nós,
que ajuda :)
rbp
--
Rodrigo Bernardo Pimentel <rbp@isnomore.net> | GPG: <0x0DB14978>
| Antes de enviar um e-mail para o grupo leia: |
| http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar |
| E se você é usuário do BOL lembre-se de cadastrar o |
| e-mail do grupo na lista branca do seu sistema anti-spam. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
__,_._,___
Carlos da Silva Santos
2008/8/19 cairoaorocha <cairoaorocha@gmail.com>:
> Respondendo a todos:
>
> Minha dúvida foi sanada, era sobre o Garbage Collector mesmo.
>
> A disciplina que eu estou pagando é Analise e Projeto de algoritmos,
> esse é um trabalho introdutório, e como fiz estruturas de dados toda
> em C++, escolhi fazer em Python.
>
> Já li essa apostila "Pensando como um computólogo", inclusive me
> baseei nela. Sobre os conceitos de ponteiro, acho que já os tenho bem
> fixado.
>
> Sobre a lista encadeada simples ela está redondinha, agora surge outro
> problema: a lista encadeada dupla não consigo remover um elemento que
> não for o 'cabeça'. Segue o código: http://paste.la/3286
>
> Peço ajuda mais uma vez, e desde já, obrigado a todos.
Existe um livro online de estruturas de dados e algoritmos em python em:
http://www.brpreiss.com/books/opus7/
Pode servir para tirar algumas dúvidas.
[]s
Carlos
>
>
| Antes de enviar um e-mail para o grupo leia: |
| http://www.pythonbrasil.com.br/moin.cgi/AntesDePerguntar |
| E se você é usuário do BOL lembre-se de cadastrar o |
| e-mail do grupo na lista branca do seu sistema anti-spam. |
`-----------------------------------------------------------´
Alterar configurações via web (Requer Yahoo! ID)
Alterar configurações via e-mail: Alterar recebimento para lista diária de mensagens | Alterar formato para o tradicional
Visite seu Grupo | Termos de uso do Yahoo! Grupos | Sair do grupo
__,_._,___
cairoaorocha
Consegui fazendo assim:
noExclui.ant.prox = noExclui.prox
if noExclui.prox: # Quando for o ultimo, no.prox é nulo
noExclui.prox.ant = noExclui.ant
Realmente era problema de lógica.
Abraços.
--- Em python-brasil@yahoogrupos.com.br, "Carlos da Silva Santos"
<carlos.s.santos@...> escreveu
>
> 2008/8/19 cairoaorocha <cairoaorocha@...>:
> > Respondendo a todos:
> >
> > Minha dúvida foi sanada, era sobre o Garbage Collector mesmo.
> >
> > A disciplina que eu estou pagando é Analise e Projeto de algoritmos,
> > esse é um trabalho introdutório, e como fiz estruturas de dados toda
> > em C++, escolhi fazer em Python.
> >
> > Já li essa apostila "Pensando como um computólogo", inclusive me
> > baseei nela. Sobre os conceitos de ponteiro, acho que já os tenho bem
> > fixado.
> >
> > Sobre a lista encadeada simples ela está redondinha, agora surge outro
> > problema: a lista encadeada dupla não consigo remover um elemento que
> > não for o 'cabeça'. Segue o código: http://paste.la/3286
> >
> > Peço ajuda mais uma vez, e desde já, obrigado a todos.
>
> Existe um livro online de estruturas de dados e algoritmos em python em:
> http://www.brpreiss.com/books/opus7/
>
> Pode servir para tirar algumas dúvidas.
>
> []s
> Carlos
>
> >
> >
>
__,_._,___