43
ESTRUTURA DE DADOS Listas Encadeadas Cristina Boeres

ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

  • Upload
    others

  • View
    17

  • Download
    0

Embed Size (px)

Citation preview

Page 1: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

ESTRUTURA DE DADOS

Listas Encadeadas

Cristina Boeres

Page 2: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Lineares

Relembrando

!  listas lineares agrupam informações referentes a um conjunto de elementos que, de alguma forma, se relacionam entre si

!  Uma lista linear ou está vazia, ou possui uma série de elementos

(a1,a2, ....., an) !  onde ai é um componente de algum conjunto

2

Page 3: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas

!  podem crescer e diminuir dinamicamente !  tamanho máximo não precisa ser conhecido a priori

!  Provêem flexibilidade permitindo que os itens sejam rearrumados eficientemente (ainda veremos)

!  Estrutura de dados baseada em tipo recursivo de dados

3

Page 4: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas encadeadas

Tipo recursivo de dados !  um dos campos é um ponteiro para uma estrutura do

mesmo tipo !  definem agregados de crescimento arbitrário !  Exemplo:

struct {

int a;

no* proximo;

} no;

4

Page 5: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

!  Também é um conjunto de itens organizados !  em um vetor ou lista sequencial a organização é

implícita (pela posição) !  alocados em espaços de memória consecutivos

!  em uma lista encadeada a sequência de elementos é especificada explicitamente !  cada elemento contém um ponteiro para o próximo

da lista

Listas Encadeadas 5

A L I S T

Page 6: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

!  Olhando mais em detalhes

Listas Encadeadas 6

A L I S T

A 1024 A

L 2052

esse elemento está alocado no endereço 1024

Page 7: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas

!  Detalhes que devem ser considerados: !  todo elemento possui um ponteiro

!  o ponteiro do último elemento tem que especificar algum tipo de próximo (aponta para si próprio ou NULL)‏

!  para acessar qualquer elemento da lista

!  um ponteiro ou um elemento para o 1º da lista

7

A L I S T

head

Page 8: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas !  algumas operações são mais eficientes do que em lista

sequencial !  exemplo: o último elemento com valor “T” deve ser o primeiro

da lista !  mesmo que a lista seja muito longa, a mudança é realizada

através de 3 operações

8

A L I S T

head

Page 9: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas !  algumas operações são mais eficientes do que em lista

sequencial !  exemplo: o último elemento com valor “T” deve ser o primeiro

da lista !  mesmo que a lista seja muito longa, a mudança é realizada

através de 3 operações 1)  primeiro: localizar o elemento que contém o valor desejado

9

A L I S T

head pt

Page 10: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas !  algumas operações são mais eficientes do que em lista

sequencial !  exemplo: o último elemento com valor “T” deve ser o primeiro

da lista !  mesmo que a lista seja muito longa, a mudança é realizada

através de 3 operações 2)  o ponteiro próximo dele passa a apontar para o primeiro

elemento

10

A L I S T

head pt

Page 11: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas !  algumas operações são mais eficientes do que em lista

sequencial !  exemplo: o último elemento com valor “T” deve ser o primeiro

da lista !  mesmo que a lista seja muito longa, a mudança é realizada

através de 3 operações 3)  o cabeça, passa a apontar para esse elemento

11

A L I S T

head pt

Page 12: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas !  algumas operações são mais eficientes do que em lista

sequencial !  exemplo: o último elemento com valor “T” deve ser o primeiro

da lista !  mesmo que a lista seja muito longa, a mudança é realizada

através de 3 operações 4)  o anterior a esse elemento, aponta para NULL (tem que ser

localizado também)

12

A L I S T

head pt

Page 13: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas

!  Para inserção de um novo elemento que tenha info X: !  aloca-se memória para um elemento !  atualiza-se os ponteiros

!  em lista sequencial seria necessário deslocar todos os elementos a partir do ponto de inserção;

!  apenas 2 links são alterados para esta operação - não importa quão longa é a lista

13

A L I S T

head X

Page 14: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

!  remoção de um elemento: !  basta alterar o ponteiro do elemento anterior ao

removido !  o conteúdo de X (no exemplo) ainda existe, mas

não é mais acessível pela lista

Listas Encadeadas 14

A L I S T

head X

Page 15: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas

!  Lista Encadeada x Sequencial !  remoção e inserção são mais naturais na lista encadeada

!  outras operações já não são tão naturais

!  Encontrar o k-ésimo elemento da lista

!  em uma lista sequencial - simplesmente acessar a[k]

!  na lista encadeada é necessário percorrer k links.

!  Achar um ítem antes de um dado ítem

15

Page 16: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas

Duplamente encadeada - ponteiros para duas direções !  um ponteiro para o próximo e um para o anterior

16

Simplesmente encadeada - ponteiros em uma direção

Page 17: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas

Inserção e Remoção !  alocação dinâmica de memória

!  aloca() - malloc() ou calloc() do C !  desaloca() ou libera() - free() do C

Exemplo - Gerenciamento de blocos de memória livres !  Rotina que toma conta do espaço livre de memória

!  Ao liberar memória - inserção na lista de bloco livres !  Ao alocar memória - remoção da lista

17

Page 18: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção

!  seja uma lista em que cada elemento armazena: !  um inteiro !  ponteiro para o próximo elemento da lista

!  Problema a resolver: !  inserir um novo elemento sempre no início da lista

18

Page 19: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção

!  seja uma lista em que cada elemento armazena: !  um inteiro !  ponteiro para o próximo elemento da lista

!  Problema a resolver: !  inserir um novo elemento sempre no início da lista

19

head

10 7 32 17 80

Page 20: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção

!  seja uma lista em que cada elemento armazena: !  um inteiro !  ponteiro para o próximo elemento da lista

!  Problema a resolver: !  inserir um novo elemento sempre no início da lista

!  aloca um novo elemento

20

head

10 7 32 17 80

novo

Page 21: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção

!  seja uma lista em que cada elemento armazena: !  um inteiro !  ponteiro para o próximo elemento da lista

!  Problema a resolver: !  inserir um novo elemento sempre no início da lista

!  inicializa campos

21

head

10 7 32 17 80

novo

X

Page 22: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção

!  seja uma lista em que cada elemento armazena: !  um inteiro !  ponteiro para o próximo elemento da lista

!  Problema a resolver: !  inserir um novo elemento sempre no início da lista

!  cabeça passa apontar para o novo primeiro elemento

22

head

10 7 32 17 80

novo

X

Page 23: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção

Estrutura usada struct { int info; tipo_no * prox; } tipo_no; tipo_no * head; head = NULL;

Protótipo da Função Insere(int valor);

23

Page 24: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção

Insere(int valor) { tipo_no * novo;

novo = malloc (sizeof(tipo_no)); if (!novo) return(false); novo->info = valor; novo->prox = head; head = novo; return(true);

}

24

Page 25: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Remoção

!  Problema !  remover o 1º elemento, retornando o valor

armazenado !  Se remover de uma lista vazia? !  E se remover e a lista ficar vazia?

25

Page 26: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Remoção

!  Problema !  remover o 1º elemento, retornando o valor

armazenado !  Se remover de uma lista vazia? !  E se remover e a lista ficar vazia?

!  aponta para o primeiro elemento

26

head

10 7 32 17 80

pt

Page 27: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Remoção

!  Problema !  remover o 1º elemento, retornando o valor

armazenado !  Se remover de uma lista vazia? !  E se remover e a lista ficar vazia?

!  atualiza o novo cabeça

27

head

10 7 32 17 80

pt

Page 28: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Remoção

!  Problema !  remover o 1º elemento, retornando o valor

armazenado !  Se remover de uma lista vazia? !  E se remover e a lista ficar vazia?

!  libera o espaço (antes guarde em uma variável o valor armazenado no elemento)

28

head

7 32 17 80

pt

Page 29: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Remoção

remove () { valor = INEXISTENTE;

if (head != NULL){ valor = head->valor; pt = head; head = head ->prox; free (pt); }else “lista vazia”; return (valor);

}

29

Page 30: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Busca em Listas Encadeadas

!  Problema: !  Buscar um valor em uma lista encadeada onde os

elementos não seguem uma ordenação !  retorna o elemento que contém o valor

procurado, ou NULL, caso não encontre

30

Page 31: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Busca em Listas Encadeadas

!  Problema: !  Buscar um valor em uma lista encadeada onde os

elementos não seguem uma ordenação !  retorna o elemento que contém o valor

procurado, ou NULL, caso não encontre

31

10 7 32 17 80

head valor = 32

Page 32: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Busca Listas Encadeadas

busca_encadeada (valor, ant, pt) { pt = head; ant = head;

while (pt != NULL) && ( pt->info != valor){ ant = pt; pt = pt->prox; }

}

32

10 7 32 17 80

head valor = 32

Page 33: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Busca Listas Encadeadas

!  caso o valor esteja na lista !  pt aponta para o elemento que contém o valor

!  senão estiver na lista !  pt aponta para NULL - o campo prox do último elemento

aponta para NULL

33

10 7 32 17 80

head valor = 11

Page 34: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção

!  Problema: inserir um valor em uma lista encadeada não ordenada, caso não exista !  como não existe ordenação, pode-se inserir no

início da lista

34

Page 35: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção Insere(valor){ pt = head; ant = head;

while (pt != NULL) && ( pt->info != valor){ ant = pt; pt = pt->prox; }

if (pt == NULL){ /* não encontrou o valor na lista */ novo = malloc ();

novo->info = valor; novo->prox = head; head = novo; }

}

35

Page 36: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Inserção Insere(valor){ pt = head; ant = head;

while (pt != NULL) && ( pt->info != valor){ ant = pt; pt = pt->prox; }

if (pt == NULL){ /* não encontrou o valor na lista */ novo = malloc ();

novo->info = valor; novo->prox = head; head = novo; }

}

36

10 7 32 17 80 head

valor = 11

Page 37: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Remoção

!  Problema: remover o elemento que armazena um dado valor em uma lista encadeada não ordenada, caso exista

37

Page 38: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Remoção

!  Problema: remover o elemento que armazena um dado valor em uma lista encadeada não ordenada, caso exista !  procurar pelo elemento !  retirá-lo se encontrar

38

Page 39: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Remoção remove_enc(valor)‏ { pt = head; ant = head;

while (pt != NULL) && ( pt->info != valor){ ant = pt; pt = pt->prox; } if (pt != NULL){ ant->prox = pt->prox; if (ant == pt) head = pt->prox; free (pt); }else “não encontrado”;

}

39

Page 40: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas - Remoção remove_enc(valor)‏ { pt = head; ant = head;

while (pt != NULL) && ( pt->info != valor){ ant = pt; pt = pt->prox; } if (pt != NULL){ ant->prox = pt->prox; if (ant == pt) head = pt->prox; free (pt); }else “não encontrado”;

}

40

Page 41: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Busca em uma lista ordenada

busca_enc_ord (valor, ant, pt)‏ {

ant = head; pt = head; while ((pt != NULL) && (pt->info < valor)){ ant = pt; pt = pt->prox; }

}

41

Page 42: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Pensar

!  Fazer um programa que: !  Le números inteiros positivos

a) Calcular média destes números

b) Calcular mínimo e máximo destes números

c) Listar os N maiores

!  Sejam x e y dois polinômios. Calcule a soma de x e y e armazene em z

42

Page 43: ESTRUTURA DE DADOSboeres/slides_ed/ed_ListasEncadeadas.pdf · Lista Encadeada x Sequencial ! remoção e inserção são mais naturais na lista encadeada ! outras operações já

Listas Encadeadas

Exercício Prático !  Implementar os procedimentos de inserção e remoção

em uma lista encadeada desordenada !  Dado uma lista encadeada, localizar o n-ésimo elemento

43