Silvan
1486 palavras
6 páginas
Estruturas de DadosListas Generalizadas, Cruzadas
& Matrizes Esparsas
Prof. Ricardo J. G. B. Campello
Créditos
Alguns slides a seguir são adaptações dos originais gentilmente cedidos pela Profa.
Maria Cristina F. de Oliveira.
2
1
Listas
Uma lista (a1, a2, ..., an) pode ser definida como o elemento a1 seguido da lista (a2, ..., an)
A lista (a2, ..., an), por sua vez, pode ser definida como o elemento a2 seguido da lista (a3, ..., an)
E assim sucessivamente até que a lista (an) seja formada por an seguido da lista vazia ()
3
Listas Generalizadas
Até agora consideramos todos os ai do mesmo tipo, sempre como átomos (elementos indivisíveis)
Podemos considerar que cada elemento ai da lista poderia também ser uma lista (chamada sub-lista)
Ex.: L = (a,(b,c),d,(e),( )) a1 a2 a3 a4 a5
L tem 5 elementos:
• a2, a4 e a5 são sub-listas
• a1 e a3 são átomos
4
2
Listas Generalizadas
Definição:
Uma lista generalizada A é uma seqüência finita de n ≥ 0 elementos α1, α2, ..., αn em que αi são átomos ou listas. Os elementos αi, 1 ≤ i ≤ n, que não são átomos, são chamados sub-listas de A.
5
Listas Generalizadas
Elemento pode ser um átomo ou uma sub-lista
Pode ser representado pela seguinte estrutura de nodo:
TAG ELEM
LIG
ELEM: um átomo ou um ponteiro para uma outra lista
LIG: ligação para o próximo elemento da lista
TAG: valor FALSE (ELEM é átomo) ou TRUE (ELEM é ponteiro)
6
3
Exemplos
L1 = (a,(b,c))
L1
F a
T
F b
F b
F c
F f
F c
L2
F a
T
L2 = (a,b,c)
F c
T
L3 = ((a,b),(c,(d,e)),f)
L3
T
F a
F b
F d
F e
7
Listas Generalizadas Compartilhadas
Listas Compartilhadas:
A = (a,(b,c))
A
F a
T
F b
B = (A, A, ())
B
T
F c
T
T
Compartilhamento pode resultar em grande economia de memória. Entretanto, esse tipo de estrutura gera problemas quando desejamos eliminar ou inserir nodos na frente da lista.
8
4