Listas encadeadas - João Araujo

Transcrição

Estruturas de Informação I - Aula 12
Listas encadeadas
João Araujo Ribeiro
[email protected]
Universidade do Estado do Rio de Janeiro
Departamento de Engenharia de Sistemas e Computação
João Araujo Ribeiro (UERJ)
Estruturas de Informação I
EstrInf
1 / 33
Resumo
1
EI12 - Listas Encadeadas
2
EI12 - Pilha como Lista Encadeada
3
EI12 - Fila como Lista Encadeada
4
EI12 - Lista Encadeada Circular
5
EI12 - Lista Duplamente Encadeada
EstrInf
2 / 33
Listas Encadeadas
Vimos anteriormente os diversos tipos de listas possíveis. Neste capítulo
vamos nos aprofundar na programação e uso de listas encadeadas
EstrInf
3 / 33
Lista Simplesmente encadeada
Uma lista simplesmente encadeada é uma coleção de nós que coletivamente
formam uma sequência linear.
EstrInf
4 / 33
Head e Tail
O primeiro nó é conhecido como
Head e o último como Tail.
EstrInf
5 / 33
Inserção no início da lista
EstrInf
6 / 33
Algoritmo de inserção no início
1
2
3
4
5
6
Algoritmo insere_inicio(L, e):
newest = Node(e) {cria um novo nó para armazenar o elemento e}
newest.next = L.head {aponta a próxima referência do novo nó
para o antigo nó head}
L.head = newest {Aponta head para o novo nó}
L.size = L.size + 1 {incrementa o contador de nós}
EstrInf
7 / 33
Inserção no m da lista eencadeada
EstrInf
8 / 33
Algoritmo de inserção no m
1
2
3
4
5
6
Algoritmo insere_fim(L, e):
newest = Node(e) {cria novo nó para armazenar elemento e}
newest.next = None {Faz o próximo apontar para None}
L.tail.next = newest {Faz antigo próximo de tail apontar para o novo nó}
L.tail = newest {faz a variável tail apontar para novo nó}
L.size = L.size + 1 {incrementa o contador de nós}
EstrInf
9 / 33
Remover elemento de lista encadeada
EstrInf
10 / 33
Algoritmo de remoção
1
2
3
4
5
Algorithm remove_primeiro(L):
if L.head is None then
Indica erro: a lista está vazia.
L.head = L.head.next {faz head apontar para o próximo}
L.size = L.size - 1 {decrementa contador}
EstrInf
11 / 33
Removendo último
Infelizmente não podemos remover o último elemento tão facilmente.
Mesmo mantendo um ponteiro para o último elemento, numa lista
encadeada simples devemos começar de head e atravessar a lista
inteiramente para atingir o último elemento. Este problema não haveria se
a lista fosse duplamente encadeada.
EstrInf
12 / 33
Implementando uma pilha como lista encadeada
Como base, implementamos uma classe _Node
1
2
3
4
5
6
class _Node:
"""Classe não publica para armazenar um nó."""
__slots__ = _element , _next
def init (self, element, next):
self._element = element
self._next = next
EstrInf
13 / 33
Pilha como lista encadeada 1/3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class LinkedStack:
"""Implementação LIFO de Pilha usando lista encadeada."""
#-------------------------- Classe Node -------------------------class _Node:
"""Classe não pública para armazenar um nó."""
def __init__(self, element, next): # carrega nó
self._element = element # referência para elemento do usuário
self._next = next # referência para o próximo nó
#------------------------------- métodos da Pilha ----------------------def __init__ (self):
"""Cria pilha vazia."""
self._head = None # referência para head
self._size = 0 # numero de elementos
def __len__ (self):
"""Retorna o número de elementos na pilha."""
return self._size
EstrInf
14 / 33
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def is_empty(self):
"""Retorna True se a pilha está vazia."""
return self._size == 0
def push(self, e):
"""Adiciona element e no topo da pilha."""
self._head = self._Node(e, self._head) # cria novo nó
self._size += 1
def top(self):
"""Retorna (mas não remove) o elemento do topo da pilha.
Levanta exceção Empty se pilha está vazia.
"""
if self.is_empty( ):
raise Empty(Pilha Vazia)
return self._head._element # topo da pilha éa cabeça da lista
EstrInf
15 / 33
38
39
40
41
42
43
44
45
46
47
def pop(self):
"""Remove e retorna o elemento do topo da pilha.
Levanta exceção Empty se pilha está vazia.
"""
raise Empty(Pilha Vazia)
answer = self._head._element
self._head = self._head._next
self._size -= 1
return answer
EstrInf
16 / 33
Fila como lista encadeada 1/3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LinkedQueue:
"""Implementação FIFO de Fila usando lista encadeada."""
#-------------------------- Classe Node -------------------------class _Node:
#------------------------------- métodos da Fila ----------------------def __init__ (self):
"""Cria fila vazia."""
self._head = None
self._tail = None
self._size = 0 # numero de elementos
def __len__ (self):
"""Retorna o número de elementos na fila."""
return self._size
EstrInf
17 / 33
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def is_empty(self):
"""Retorna True se a fila está vazia."""
def first(self):
"""Retorna (mas não remove) o elemento da frente da fila."""
raise Empty(Fila Vazia)
return self._head._element
def dequeue(self):
"""Remove e retorna o elemento do frente da fila.
Levanta exceção Empty se fila está vazia..
"""
EstrInf
18 / 33
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
answer = self._head._element
self._head = self._head._next
self._size -= 1
if self.is_empty( ):# caso especial fila vazia
self._tail = None
return answer
def enqueue(self, e):
"""Adiciona elemento ao fim da fila."""
newest = self._Node(e, None) # nó será o novo tail
self._head = newest # caso especial: previamente vazia
else:
self._tail._next = newest
self._tail = newest
self._size += 1
EstrInf
19 / 33
Lista Encadeada Circular
EstrInf
20 / 33
Lista Encadeada Circular sem início nem m
EstrInf
21 / 33
Fila Circular como lista encadeada 1/3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class CircularQueue:
"""Implementação de Fila como lista encadeada circular."""
class _Node:
"""Classe não publica para armazenar um nó."""
def __init__ (self):
"""Cria fila vazia."""
self._tail = None
self._size = 0
def __len__ (self):
"""Retorna o número de elementos na fila."""
return self._size
def is_empty(self):
EstrInf
22 / 33
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def first(self):
"""Retorna (mas não remove) o elemento da frente da fila."""
head = self._tail._next
return head._element
def dequeue(self):
"""Remove e retorna o elemento do frente da fila.
Levanta exceção Empty se fila está vazia..
"""
oldhead = self._tail._next
if self._size == 1: # remove único elemento
self._tail = None # fila fica vazia
else:
self._tail._next = oldhead._next # bypass antigo head
self._size -= 1
return oldhead._element
EstrInf
23 / 33
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def enqueue(self, e):
"""Adiciona elemento ao fim da fila."""
newest = self._Node(e, None) # nó será o novo tail
newest._next = newest # circular
else:
newest._next = self._tail._next # novo nó aponta para head
self._tail._next = newest # antigo tail aponta para novo nó
self._tail = newest # novo nó se torna tail
self._size += 1
def rotate(self):
"""Roda elemento frontal para fim da fila."""
if self._size > 0:
self._tail = self._tail._next # antigo head vira novo tail
EstrInf
24 / 33
Lista duplamente encadeada
Numa lista duplamente encadeada cada nó mantém uma referência para o
nó imediatamente anterior e outra para o nó imediatamente posterior. (no
exemplo abaixo, usando sentinelas)
EstrInf
25 / 33
Por que usar sentinelas?
Poderíamos implementar a lista duplamente encadeada sem sentinelas, mas
elas simplicam enormemente a inserção e eliminação de nós, pois sempre
existe um nó antes e depois e não precisamos tratar casos especiais, como
anteriormente
EstrInf
26 / 33
Inserindo elemento
EstrInf
27 / 33
Inserindo elemento no início
EstrInf
28 / 33
Removendo elemento
EstrInf
29 / 33
Nó para lista duplamente encadeada
1
2
3
4
5
6
7
8
class _Node:
__slots__ = _element , _prev , _next
def __init__ (self, element, prev, next):
self._prev = prev
self._next = next
EstrInf
30 / 33
lista duplamente encadeada 1/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# coding=UTF-8
class _DoublyLinkedBase:
"""Uma classe base para lista duplamente encadeada."""
class _Node:
__slots__ = _element , _prev , _next
def __init__ (self, element, prev, next):
self._prev = prev
self._next = next
def __init__(self):
"""Cria lista vazia"""
self._header = self._Node(None, None, None)
self._trailer = self._Node(None, None, None)
self._header._next = self._trailer # trailer após header
self._trailer._prev = self._header # header antes de trailer
self._size = 0
def __len__ (self):
"""Retorna o número de elementos na lista."""
EstrInf
31 / 33
Lista duplamente encadeada 2/2
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def is_empty(self):
def _insert_between(self, e, predecessor, successor):
"""Adiciona elemento e entre dois nós existentes e retorna novo nó."
newest = self._Node(e, predecessor, successor)
predecessor._next = newest
successor._prev = newest
self._size += 1
return newest
def _delete_node(self, node):
"""Deleta nó não sentinela e retorna seu elemento."""
predecessor = node._prev
successor = node._next
predecessor._next = successor
successor._prev = predecessor
self._size -= 1
element = node._element
node._prev = node._next = node._element = None
EstrInf
32 / 33
FIM
EstrInf
33 / 33

Listas encadeadas - João Araujo

Transcrição

Documentos relacionados

Editorial

Funções Psicológicas A titude fundam ental

RESTAURANTES DENTRO DA UERJ O Campus Uerj Maracanã

O duelo dos cisnes: a oposição entre o verdadeiro e o falso self The

ALEXANDRA MAZZOCA ANA MARIA MEJOLARO DALLA VALLE

uma introdução à kabbalah

cerimônia de colação de grau

Convocação para 2ª etapa - Prova Objetiva

CONFIGURAAO DE PROXY PARA ACESSO AO CAPES - dinfo

Processos Químicos