AEDS COLTEC aula2 listas

Prévia do material em texto

Aula 2: Listas
Professor(a): Virgínia Fernandes Mota
http://www.dcc.ufmg.br/⇠virginiaferm
ALGORITMOS E ESTRUTURAS DE DADOS - SETOR DE INFORMÁTICA
Virgínia Fernandes Mota Aula 2: Listas
Listas Encadeadas
Uma lista encadeada é uma representação de uma sequência
de objetos na memória do computador.
Cada elemento da sequência é armazenado em uma célula da
lista: o primeiro elemento na primeira célula, o segundo na
segunda e assim por diante.
Listas Encadeadas x Vetores: listas são mais flexíveis e mais
baratas (computacionalmente).
Virgínia Fernandes Mota Aula 2: Listas
Listas Encadeadas
Uma lista encadeada (linked list ou lista ligada) é uma sequência
de células; cada célula contém um objeto de algum tipo e o
endereço da célula seguinte.
1 s t r u c t l i s t a {
2 i n t i n f o ;
3 s t r u c t l i s t a ⇤prox ;
4 } ;
5 t y p ed e f s t r u c t l i s t a L i s t a ;
O último elemento sempre apontará para null.
Virgínia Fernandes Mota Aula 2: Listas
Função de Criação
1 /⇤ função de c r i a ç ã o : r e t o r n a uma l i s t a v a z i a ⇤/
2
3 L i s t a ⇤ l s t _ c r i a ( ) {
4 r e t u r n NULL ;
5 }
A lista vazia é representada pelo ponteiro NULL.
Virgínia Fernandes Mota Aula 2: Listas
Função de Inserção
1 /⇤ i n s e r ç ã o no i n í c i o da l i s t a : r e t o r n a a l i s t a a t u a l i z a d a ⇤/
2 L i s t a ⇤ l s t _ i n s e r e ( L i s t a ⇤ l , i n t i ) {
3 L i s t a ⇤novo = ( L i s t a ⇤) ma l l o c ( s i z e o f ( L i s t a ) ) ;
4 novo�>i n f o = i ;
5 novo�>prox = l ;
6 r e t u r n novo ;
7 }
Virgínia Fernandes Mota Aula 2: Listas
Função de Inserção
Exemplo: Criar uma lista inicialmente vazia e inserir nela novos
elementos
1 i n t main ( ) {
2 L i s t a ⇤ l ;
3 l = l s t_ c r i a ( ) ;
4 l = l s t_ i n s e r e ( l , 23) ;
5 l = l s t_ i n s e r e ( l , 42) ;
6 . . .
7
8 r e t u r n 0 ;
9 }
Existe outra maneira de fazer a inserção?
Virgínia Fernandes Mota Aula 2: Listas
Função de Inserção
Sim!
1 vo i d l i s t _ i n s e r e ( L i s t a ⇤⇤ l , i n t i ) {
2 L i s t a ⇤novo = ( L i s t a ⇤) ma l l o c ( s i z e o f ( L i s t a ) ) ;
3 novo�>i n f o = i ;
4 novo�>prox = ⇤ l ;
5 ⇤ l = novo ;
6 }
Dessa forma, uma função main chamaria essa função do seguinte
modo:
Lista *l = lst_cria();
lst_insere(&l, 42);
Virgínia Fernandes Mota Aula 2: Listas
Percorrer e determinar lista vazia
Função que percorre os elementos da lista
1 /⇤ função impr ime : impr ime v a l o r e s dos e l ementos ⇤/
2 vo i d l s t_ impr ime ( L i s t a ⇤ l ) {
3 L i s t a ⇤p ;
4 f o r ( p = l ; p != NULL ; p = p�>prox )
5 p r i n t f ( " i n f o %d " , p�>i n f o ) ;
6 }
Função que verifica se a lista está vazia
1 /⇤ função v a z i a : r e t o r n a 1 se v a z i a ou 0 se não v a z i a ⇤/
2 i n t l s t_ v a z i a ( L i s t a ⇤ l ) {
3 i f ( l == NULL)
4 r e t u r n 1 ;
5 e l s e
6 r e t u r n 0 ;
7
8 //ou somente r e t u r n ( l == NULL) ;
9
10 }
Virgínia Fernandes Mota Aula 2: Listas
Função de Busca
1 /⇤ função busca : busca um elemento na l i s t a ⇤/
2 L i s t a ⇤ l s t_busca ( L i s t a ⇤ l , i n t v ) {
3 L i s t a ⇤p ;
4 f o r ( p = l ; p != NULL ; p�>prox ) {
5 i f ( p�>i n f o == v )
6 r e t u r n p ;
7 }
8
9 r e t u r n NULL ;
10 }
Virgínia Fernandes Mota Aula 2: Listas
nullnullnullnullnullEu
Função para Remoção
Remoção do primeiro elemento da lista
Remoção de um elemento no meio da lista
Virgínia Fernandes Mota Aula 2: Listas
Função para Remoção
1 /⇤ função r e t i r a : r e t i r a e lemento da l i s t a ⇤/
2 L i s t a ⇤ l s t _ r e t i r a ( L i s t a ⇤ l , i n t v ) {
3 L i s t a ⇤ant = NULL ;
4 L i s t a ⇤p = l ;
5
6 wh i l e ( p != NULL && p�>i n f o != v ) {
7 ant = p ;
8 p = p�>prox ;
9 }
10
11 i f ( p == NULL)
12 r e t u r n l ; // e lemento não encont rado , r e t o r n a l i s t a o r i g i n a l
13
14 i f ( ant == NULL)
15 l = p�>prox ; // r e t i r a e lemento do i n í c i o
16 e l s e
17 ant�>prox = p�>prox ; // r e t i r a e l emento do meio
18
19 f r e e ( p ) ;
20
21 r e t u r n l ;
22 }
Virgínia Fernandes Mota Aula 2: Listas
Função para Liberar
1 /⇤ função busca : busca um elemento na l i s t a ⇤/
2 vo i d l s t _ l i b e r a ( L i s t a ⇤ l ) {
3 L i s t a ⇤p = l ;
4 wh i l e ( p != NULL) {
5 L i s t a ⇤ t = p�>prox ;
6 f r e e ( p ) ;
7 p = t ;
8 }
9 }
Virgínia Fernandes Mota Aula 2: Listas
Manutenção lista ordenada
A função de inserção vista anteriormente armazena os
elementos na lista na ordem inversa à ordem de inserção.
Se quisermos manter os elementos da lista em uma
determinada ordem, temos de encontrar a posição correta para
inserir o novo elemento.
Virgínia Fernandes Mota Aula 2: Listas
Manutenção lista ordenada
1 L i s t a ⇤ l s t_ in s e r e_o rdenado ( L i s t a ⇤ l , i n t v ) {
2 L i s t a ⇤novo ;
3 L i s t a ⇤ant = NULL ;
4 L i s t a ⇤p = l ;
5
6 wh i l e ( p != NULL && p�>i n f o < v ) {
7 ant = p ;
8 p = p�>prox ;
9 }
10
11 novo = ( L i s t a ⇤) ma l l o c ( s i z e o f ( L i s t a ) ) ;
12 novo�>i n f o = v ;
13
14 i f ( ant == NULL) {
15 novo�>prox = l ;
16 l = novo ;
17 }
18 e l s e {
19 novo�>prox = ant�>prox ;
20 ant�>prox = novo ;
21 }
22
23 r e t u r n l ;
24 }
Virgínia Fernandes Mota Aula 2: Listas
Listas circulares
Algumas aplicações necessitam representar conjuntos cíclicos.
Exemplo: Manipular figuras geométricas, as arestas que
delimitam uma face podem ser agrupadas por uma estrutura
circular.
Em uma lista circular, o último elemento tem como próximo
ponteiro o primeiro elemento da lista.
Virgínia Fernandes Mota Aula 2: Listas
Listas circulares
1 vo i d l c i r c_ imp r ime ( L i s t a ⇤ l ) {
2 L i s t a ⇤p = l ;
3 i f ( p )
4 do{
5 p r i n t f ( "%d " , p�>i n f o ) ;
6 p = p�>prox ;
7 } wh i l e ( p != l ) ;
8 }
Virgínia Fernandes Mota Aula 2: Listas
Listas duplamente encadeadas
Nas listas encadeadas simples não temos como percorrer os
elementos na ordem inversa de maneira eficiente.
O encadeamento simples também dificulta a retirada de um
elemento.
Na lista duplamente encadeada cada célula contém o endereço
da célula anterior e o da célula seguinte.
Virgínia Fernandes Mota Aula 2: Listas
Listas duplamente encadeadas
1 s t r u c t l i s t a 2 {
2 i n t i n f o ;
3 s t r u c t l i s t a 2 ⇤ant ;
4 s t r u c t l i s t a 2 ⇤prox ;
5 } ;
Virgínia Fernandes Mota Aula 2: Listas
Listas duplamente encadeadas - Inserção
1 /⇤ i n s e r e no i n í c i o da l i s t a ⇤/
2 L i s t a 2 ⇤ l s t 2_ i n s e r e ( L i s t a 2 ⇤ l , i n t v ) {
3 L i s t a 2 ⇤novo = ( L i s t a 2 ⇤) ma l l o c ( s i z e o f ( L i s t a 2 ) ) ;
4 novo�>i n f o = v ;
5 novo�>prox = l ;
6 novo�>ant = NULL ; // i n s e r i n d o no i n í c i o da l i s t a
7 i f ( l != NULL)
8 l�>ant = novo ;
9
10 r e t u r n novo ;
11 }
Virgínia Fernandes Mota Aula 2: Listas
Listas duplamente encadeadas - Busca
1 /⇤ função busca : busca um elemento na l i s t a ⇤/
2
3 L i s t a 2 ⇤ l s t 2_busca ( L i s t a 2 ⇤ l , i n t v ) {
4 L i s t a ⇤p ;
5 f o r ( p = l ; p != NULL ; p = p�>prox )
6 i f ( p�>i n f o == v )
7 r e t u r n p ;
8 r e t u r n NULL ; //não encont rou o e lemento
9 }
Virgínia Fernandes Mota Aula 2: Listas
Listas duplamente encadeadas - Remoção
A função de remoção se torna mais complicada, porém é
possível retirar um elemento tendo apenas o ponteiro para o
mesmo.
p->ant->prox = p->prox;
p->prox->ant = p->ant;
1 /⇤ função r e t i r a : r e t i r a e lemento da l i s t a ⇤/
2 L i s t a 2 ⇤ l s t 2_ r e t i r a ( L i s t a 2 ⇤ l , i n t v ) }
3 L i s t a 2 ⇤p = l s t2_busca ( l , v ) ;
4 i f ( p == NULL)
5 r e t u r n l ; // e lemento não encont rado
6
7 i f ( l == p )
8 l = p�>prox ; // se r e t i r a r o p r im e i r o e lemento da l i st a
9 e l s e
10 p�>ant�>prox = p�>prox ;
11
12 i f ( p�>prox != NULL) // t e s t a se é o ú l t imo e lemento da l i s t a
13 p�>prox�>ant = p�>ant ;
14
15 f r e e ( p ) ;
16
17 r e t u r n l ;
18 }
Virgínia Fernandes Mota Aula 2: Listas
Exercícios
1. Implementar as funções/procedimentos apresentados em sala
para a manipulação de listas encadeadas, listas circulares e listas
duplamente encadeadas. Crie listas.c e listas.h para a manipulação
das listas e main.c para testes. Crie um makefile para compilar o
código.
2. Acrescente uma função para comparar duas listas encadeadas.
3. Problema de Josephus (com 2).
Virgínia Fernandes Mota Aula 2: Listas
Na próxima aula...
Pilhas
Virgínia Fernandes Mota Aula 2: Listas