Recursão e Listas Encadeadas em Python

Prévia do material em texto

Roteiro da Aula 12 
Para entender recursão, você primeiro precisa 
entender recursão. 
 
Agenda 
 
• Dados recursivos 
• Listas Encadeadas 
 
 
 
Dados recursivos 
Recursão aplicada aos dados 
• Auto referenciada, auto similar 
• Cada elemento da estrutura de dados tem, dentro dele, a repetição de uma versão menor da estrutura. 
 
 
Exemplo 
• As bonecas russas (Matroshka) 
• Cebolas 
• Classes contendo referências para si próprias 
 
 
 
Uma classe recursiva 
 
class Contato: 
 def __init__(self, nome, endereco, telefone): 
 self.__nome = nome 
 self.__endereco = endereco 
 self.__telefone = telefone 
 self.__proximo = None 
 
 def __str__(self): 
 return "%s\n%s\n%s\n" % 
 (self.__nome, self.__endereco, self.__telefone) 
 
 # outros métodos 
 
 
Cada contato aponta para outro contato! 
 
 
Se pusermos várias dessas instâncias juntas, temos uma lista encadeada! 
 
__nome 
__telefone 
__proximo 
__endereço 
 
Ver animação em http://www.csanimated.com/animation.php?t=Linked_list 
 
 
 
Uma agenda de contatos 
 
 
class Contato: 
 def __init__(self, nome, endereco, telefone): 
 self.__nome = nome 
 self.__endereco = endereco 
 self.__telefone = telefone 
 self.proximo = None 
 
 def __str__(self): 
 return "\n%s\n%s\n%s\n" % 
 (self.__nome, self.__endereco, self.__telefone) 
 
 # outros métodos... 
 
 
class Agenda: 
 def __init__(self): 
 self.__cabeca = None 
 
 def insereContato(self, contato): 
 contato.proximo = self.__cabeca 
 self.__cabeca = contato 
 
 def imprimeAgenda(self): 
 atual = self.__cabeca 
 while atual != None: 
 print atual 
 atual = atual.proximo 
 
 
 
Criando um novo contato 
 
__nome 
__telefone 
__proximo 
__endereço 
__nome 
__telefone 
__proximo 
__endereço 
__nome 
__telefone 
__proximo 
__endereço 
def criaNovoContato(): 
 nome = raw_input("Nome? (Enter para terminar): ") 
 if nome == "": return None 
 endereco = raw_input("Endereço? ") 
 telefone = raw_input("Telefone? ") 
 novoContato = Contato(nome, endereco, telefone) 
 return novoContato 
 
 
 
Criando uma Agenda e inserindo novos contatos 
 
agenda = Agenda() 
while True: 
 novoContato = criaNovoContato() 
 if novoContato == None: break 
 agenda.insereContato(novoContato) 
 
Em que ordem a lista será criada? 
 
 
 
Imprimindo a lista 
 
agenda.imprimeAgenda() 
 
 
 
Uma pequena modificação 
Vamos usar recursão para percorrer e imprimir os elementos da lista. 
 
class Agenda: 
 def __init__(self): 
 self.__cabeca = None 
 
 def insereContato(self, contato): 
 contato.proximo = self.__cabeca 
 self.__cabeca = contato 
 
 # os contatos na agenda são impressos na ordem contrária da 
 # inserção. Para inverter a ordem de impressão, basta trocar 
 # a ordem das duas últimas linhas desse método. 
 def imprimeAgenda(self, ptr=0): 
 if ptr is None: return 
 if ptr == 0: ptr = self.__cabeca 
 self.imprimeAgenda(ptr.proximo) 
 print ptr 
 
 
Observe que o programador usuário das classes Agenda e Contato (o programador de chapéu vermelho), não 
precisa conhecer detalhes de implementação dessas classes. Se o programador da classe Agenda (o 
programador de chapéu azul) quiser mudar sua implementação e usar um List Python para armazenar os 
contatos ao invés de uma lista encadeada, ele é livre para isso e essa alteração não afetará o código do 
programador de chapéu vermelho (o programador de chapéu vermelho é cliente da interface da classe 
Agenda e não de sua implementação) 
 
class Contato: 
 def __init__(self, nome, endereco, telefone): 
 self.__nome = nome 
 self.__endereco = endereco 
 self.__telefone = telefone 
 self.proximo = None 
 
 def __str__(self): 
 return "\n%s\n%s\n%s\n" % (self.__nome, self.__endereco, 
 self.__telefone) 
 
 # outros métodos... 
 
class Agenda: 
 def __init__(self): 
 self.__contatos = [] 
 
 def insereContato(self, contato): 
 self.__contatos.append(contato) 
 
 def imprimeAgenda(self): 
 for contato in self.__contatos: 
 print contato 
 
#******************************************************* 
#*****************ENCAPSULAMENTO************************ 
#******************************************************* 
def criaNovoContato(): 
 nome = raw_input("Nome? (Enter para terminar): ") 
 if nome == "": return None 
 endereco = raw_input("Endereço? ") 
 telefone = raw_input("Telefone? ") 
 novoContato = Contato(nome, endereco, telefone) 
 return novoContato 
 
agenda = Agenda() 
while True: 
 novoContato = criaNovoContato() 
 if novoContato == None: break 
 agenda.insereContato(novoContato) 
 
agenda.imprimeAgenda()