Listas encadeadas C v6

Prévia do material em texto

1 
ESTRUTURAS DE DADOS 
► Listas encadeadas 
(Linguagem C) 
Prof. Dr. Marcelo Duduchi 
Aux. Docente Lucio Nunes 
Listas lineares 
 Conforme já vimos, uma lista é uma coleção de 
elementos do mesmo tipo dispostos linearmente que 
podem ou não seguir uma determinada organização; 
 Exemplo: [E
1
, E
2
, E
3
, ..., E
n
], onde n ≥ 0; 
 Até aqui usamos alocação sequencial para 
implementá-las, mas a partir de agora usaremos a 
alocação encadeada. 
2 
Listas encadeadas 
 Listas encadeadas são listas lineares em que os 
elementos não necessariamente encontram-se dispostos 
numa área contínua de memória; 
 Como não se encontram numa área continua, é 
necessário ter alguma forma de relacioná-los entre si; 
 A forma utilizada para relacioná-los é incluir em cada 
elemento, além do valor armazenado, uma referência da 
localização do próximo elemento da lista. 
3 
Listas encadeadas simples 
 Cada elemento (nodo) da lista será formado pelo dado 
(data) a armazenar e uma referência (link) para o próximo: 
4 
Nodo 
data link 
Listas encadeadas simples 
 Uma lista encadeada será formada por diversos nodos inter-
relacionados por links e acessada a partir de uma referência 
inicial: 
5 
REFERÊNCIA INICIAL 
C A D E 
lista 
Listas encadeadas simples 
(definição da estrutura) 
6 
typedef struct nodo { 
 char data; 
 struct nodo *link; 
 } *ptr; 
Nodo 
data link 
2 
Listas encadeadas simples 
 Vamos implementar as instruções que criarão a 
lista encadeada abaixo: 
7 
C A D E 
lista 
Listas encadeadas simples 
ptr lista = malloc(sizeof(struct nodo)); 
lista->data = 'C'; 
 
lista->link = malloc(sizeof(struct nodo)); 
lista->link->data = 'A'; 
 
lista->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->data = 'D'; 
 
lista->link->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->link->data = 'E'; 
lista->link->link->link->link = NULL; 
8 
? ? 
lista 
Listas encadeadas simples 
ptr lista = malloc(sizeof(struct nodo)); 
lista->data = 'C'; 
 
lista->link = malloc(sizeof(struct nodo)); 
lista->link->data = 'A'; 
 
lista->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->data = 'D'; 
 
lista->link->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->link->data = 'E'; 
lista->link->link->link->link = NULL; 
9 
C ? 
lista 
Listas encadeadas simples 
ptr lista = malloc(sizeof(struct nodo)); 
lista->data = 'C'; 
 
lista->link = malloc(sizeof(struct nodo)); 
lista->link->data = 'A'; 
 
lista->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->data = 'D'; 
 
lista->link->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->link->data = 'E'; 
lista->link->link->link->link = NULL; 
10 
C ? ? 
lista 
Listas encadeadas simples 
ptr lista = malloc(sizeof(struct nodo)); 
lista->data = 'C'; 
 
lista->link = malloc(sizeof(struct nodo)); 
lista->link->data = 'A'; 
 
lista->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->data = 'D'; 
 
lista->link->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->link->data = 'E'; 
lista->link->link->link->link = NULL; 
11 
C A ? 
lista 
Listas encadeadas simples 
ptr lista = malloc(sizeof(struct nodo)); 
lista->data = 'C'; 
 
lista->link = malloc(sizeof(struct nodo)); 
lista->link->data = 'A'; 
 
lista->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->data = 'D'; 
 
lista->link->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->link->data = 'E'; 
lista->link->link->link->link = NULL; 
12 
C A ? ? 
lista 
3 
Listas encadeadas simples 
ptr lista = malloc(sizeof(struct nodo)); 
lista->data = 'C'; 
 
lista->link = malloc(sizeof(struct nodo)); 
lista->link->data = 'A'; 
 
lista->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->data = 'D'; 
 
lista->link->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->link->data = 'E'; 
lista->link->link->link->link = NULL; 
13 
C A D ? 
lista 
Listas encadeadas simples 
ptr lista = malloc(sizeof(struct nodo)); 
lista->data = 'C'; 
 
lista->link = malloc(sizeof(struct nodo)); 
lista->link->data = 'A'; 
 
lista->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->data = 'D'; 
 
lista->link->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->link->data = 'E'; 
lista->link->link->link->link = NULL; 
14 
C A D ? ? 
lista 
Listas encadeadas simples 
ptr lista = malloc(sizeof(struct nodo)); 
lista->data = 'C'; 
 
lista->link = malloc(sizeof(struct nodo)); 
lista->link->data = 'A'; 
 
lista->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->data = 'D'; 
 
lista->link->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->link->data = 'E'; 
lista->link->link->link->link = NULL; 
15 
C A D E ? 
lista 
Listas encadeadas simples 
ptr lista = malloc(sizeof(struct nodo)); 
lista->data = 'C'; 
 
lista->link = malloc(sizeof(struct nodo)); 
lista->link->data = 'A'; 
 
lista->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->data = 'D'; 
 
lista->link->link->link = malloc(sizeof(struct nodo)); 
lista->link->link->link->data = 'E'; 
lista->link->link->link->link = NULL; 
16 
C A D E 
lista 
Listas encadeadas simples 
 Vamos implementar as instruções que inserem 
um elemento no início da lista encadeada: 
17 
N 
C A D E 
lista 
Listas encadeadas simples 
void insere(ptr *lista, char elem) { 
 ptr aux = malloc(sizeof(struct nodo)); 
 aux->data = elem; 
 aux->link = *lista; 
 *lista = aux; 
} 
18 
C A D E 
lista 
N 
elem 
lista’ 
4 
Listas encadeadas simples 
void insere(ptr *lista, char elem) { 
 ptr aux = malloc(sizeof(struct nodo)); 
 aux->data = elem; 
 aux->link = *lista; 
 *lista = aux; 
} 
19 
C A D E 
lista 
N 
elem 
? ? 
aux lista’ 
Listas encadeadas simples 
void insere(ptr *lista, char elem) { 
 ptr aux = malloc(sizeof(struct nodo)); 
 aux->data = elem; 
 aux->link = *lista; 
 *lista = aux; 
} 
20 
C A D E 
lista 
N 
elem 
N ? 
aux lista’ 
Listas encadeadas simples 
void insere(ptr *lista, char elem) { 
 ptr aux = malloc(sizeof(struct nodo)); 
 aux->data = elem; 
 aux->link = *lista; 
 *lista = aux; 
} 
21 
C A D E 
lista 
N 
elem 
N 
aux lista’ 
Listas encadeadas simples 
void insere(ptr *lista, char elem) { 
 ptr aux = malloc(sizeof(struct nodo)); 
 aux->data = elem; 
 aux->link = *lista; 
 *lista = aux; 
} 
22 
C A D E 
N 
lista 
N 
elem 
aux lista’ 
Listas encadeadas simples 
 Vamos implementar as instruções que removem 
um elemento do início da lista encadeada: 
23 
C A D E 
lista 
Listas encadeadas simples 
void rem(ptr *lista) { 
 ptr aux; 
 aux = *lista; 
 *lista = aux->link; 
 free(aux); 
} 
24 
C A D E 
lista lista’ 
5 
Listas encadeadas simples 
void rem(ptr *lista) { 
 ptr aux; 
 aux = *lista; 
 *lista = aux->link; 
 free(aux); 
} 
25 
C A D E 
lista aux lista’ 
Listas encadeadas simples 
void rem(ptr *lista) { 
 ptr aux; 
 aux = *lista; 
 *lista = aux->link; 
 free(aux); 
} 
26 
C A D E 
lista aux lista’ 
Listas encadeadas simples 
void rem(ptr *lista) { 
 ptr aux; 
 aux = *lista;*lista = aux->link; 
 free(aux); 
} 
27 
C A D E 
lista aux lista’ 
Listas encadeadas simples 
void rem(ptr *lista) { 
 ptr aux; 
 aux = *lista; 
 *lista = aux->link; 
 free(aux); 
} 
28 
C A D E 
lista aux lista’ 
Listas encadeadas simples 
 Vamos implementar as instruções que exibem 
todos os nodos da lista encadeada abaixo: 
29 
C A D E 
lista 
Listas encadeadas simples 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("%c", lista->data); 
 lista = lista->link; 
 } 
} 
30 
C A D E 
lista 
lista’ 
_ 
6 
Listas encadeadas simples 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("%c", lista->data); 
 lista = lista->link; 
 } 
} 
31 
C A D E 
lista 
lista’ 
C_ 
Listas encadeadas simples 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("%c", lista->data); 
 lista = lista->link; 
 } 
} 
32 
C A D E 
lista 
lista’ 
C_ 
Listas encadeadas simples 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("%c", lista->data); 
 lista = lista->link; 
 } 
} 
33 
C A D E 
lista 
lista’ 
CA_ 
Listas encadeadas simples 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("%c", lista->data); 
 lista = lista->link; 
 } 
} 
34 
C A D E 
lista 
lista’ 
CA_ 
Listas encadeadas simples 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("%c", lista->data); 
 lista = lista->link; 
 } 
} 
35 
C A D E 
lista 
lista’ 
CAD_ 
Listas encadeadas simples 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("%c", lista->data); 
 lista = lista->link; 
 } 
} 
36 
C A D E 
lista 
lista’ 
CAD_ 
7 
Listas encadeadas simples 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("%c", lista->data); 
 lista = lista->link; 
 } 
} 
37 
C A D E 
lista 
lista’ 
CADE_ 
Listas encadeadas simples 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("%c", lista->data); 
 lista = lista->link; 
 } 
} 
38 
C A D E 
lista 
lista’ 
CADE_ 
Listas encadeadas simples (exemplo) 
 Agora vamos praticar o que foi aprendido em um 
problema onde listas encadeadas são muito bem 
aproveitadas; 
 Implementaremos uma agenda simples, onde apenas o 
nome e o telefone dos contatos são armazenados. Vale 
lembrar que não sabemos antecipadamente quantos 
contatos serão inseridos. 
39 
Listas encadeadas simples (exemplo) 
 Primeiramente, vamos definir a estrutura que 
representará cada nodo da lista: 
40 
typedef struct nodo { 
 char nome[30], fone[18]; 
 struct nodo *link; 
 } *ptr; 
Listas encadeadas simples (exemplo) 
 Nesta etapa precisamos definir quais serão as 
operações necessárias: 
 Inserir contatos; 
Remover contatos; 
Consultar telefones de contatos; 
Exibir todos os contatos. 
41 
Listas encadeadas simples (exemplo) 
42 
void insere(ptr *lista, char n[ ], char f[ ]) { 
 ptr aux = malloc(sizeof(struct nodo)); 
 strcpy(aux->nome, n); 
 strcpy(aux->fone, f); 
 aux->link = *lista; 
 *lista = aux; 
} 
8 
Listas encadeadas simples (exemplo) 
43 
void rem(ptr *lista, char n[ ]) { 
 ptr a1, a2; 
 if (*lista != NULL) { 
 a1 = *lista; 
 if (strcmp(a1->nome, n) == 0) { 
 *lista = a1->link; 
 free(a1); 
 } 
 else { 
 while (a1->link != NULL && 
 strcmp(a1->link->nome, n)) 
 a1 = a1->link; 
 if (a1->link != NULL) { 
 a2 = a1->link; 
 a1->link = a2->link; 
 free(a2); 
 } 
 } 
 } 
} 
Listas encadeadas simples (exemplo) 
44 
void consulta(ptr lista, char n[ ]) { 
 while (lista != NULL && strcmp(lista->nome, n)) 
 lista = lista->link; 
 if (lista != NULL) 
 printf("Telefone: %s\n", lista->fone); 
} 
Listas encadeadas simples (exemplo) 
45 
void exibe(ptr lista) { 
 while (lista != NULL) { 
 printf("Nome: %s\n", lista->nome); 
 printf("Telefone: %s\n", lista->fone); 
 lista = lista->link; 
 } 
} 
Listas encadeadas simples (pilhas) 
 É muito simples implementar uma pilha 
utilizando alocação dinâmica encadeada; 
 A rotina push insere um nodo no início da lista; 
 Já a rotina pop remove o primeiro nodo da lista; 
 Juntas simulam o comportamento Last In / First 
Out que caracteriza uma pilha. 
46 
Listas encadeadas simples (pilhas) 
47 
int pop(ptr *p) { 
 ptr aux; 
 int n; 
 if (isempty(*p)) { 
 printf("underflow\n"); 
 exit(1); 
 } 
 aux = *p; 
 *p = (*p)->link; 
 n = aux->data; 
 free(aux); 
 return n; 
} 
void push(ptr *p, int elem) { 
 ptr aux = malloc(sizeof(struct nodo)); 
 aux->data = elem; 
 aux->link = *p; 
 *p = aux; 
} 
Listas encadeadas simples (exercício) 
 Implemente as demais rotinas para a 
manipulação de pilhas com alocação dinâmica 
encadeada (create, destroy e top). Lembre-se 
que a rotina isfull não faz sentido neste 
contexto. 
48 
9 
Listas encadeadas simples (filas) 
 Para implementar as rotinas que manipularão 
uma fila com alocação dinâmica encadeada, 
deve-se levar em conta que o tipo fila terá 
dois ponteiros (front e rear) que controlarão o 
início e o final da lista. 
49 
Listas encadeadas simples (exercício) 
 Implemente as rotinas para a manipulação de 
filas com alocação dinâmica encadeada 
(create, destroy, isempty, store e retrieve). 
Lembre-se que as rotinas isfull e next não 
fazem sentido neste contexto. 
50 
Técnicas de encadeamento 
 Conheceremos agora algumas técnicas de 
encadeamento que tornam a implementação 
de listas encadeadas mais eficiente e simples: 
Lista circular; 
Lista duplamente encadeada; 
Lista com nodos sentinelas. 
51 
Listas encadeadas circulares 
 Uma lista encadeada circular é muito semelhante à uma 
lista encadeada simples, porém seu último nodo aponta 
para o primeiro nodo da lista e não para nulo. 
52 
C A D E 
lista 
Listas duplamente encadeadas 
 Listas duplamente encadeadas são listas lineares em que cada 
elemento possui dois links, um para seu antecessor e outro 
para seu sucessor: 
53 
Nodo 
data link link 
Listas duplamente encadeadas 
 Note que na lista duplamente encadeada: 
o primeiro elemento tem o link à esquerda nulo; 
o último elemento tem o link à direita nulo. 
54 
lista 
C A D E 
10 
Listas com nodos sentinelas 
 Os nodos sentinelas são nodos que ficam no início e/ou final das listas 
encadeadas evitando manipulações em suas extremidades, tornando 
a codificação das rotinas mais simples; 
 No início colocamos um valor menor do que todos (low-value ou LV); 
 No final colocamos o maior valor possível (high-value ou HV). 
55 
LV B C D 
lista 
HV 
Listas encadeadas (exercícios) 
1. Construa uma sub-rotina que remova a 
duplicidade de elementos de uma lista 
ordenada passada como parâmetro; 
2. Construa uma sub-rotina que transforme uma 
lista encadeada simples em uma lista encadeada 
circular. A lista será passada como parâmetro; 
56 
Listas encadeadas (exercícios) 
3. Construa uma sub-rotina que concatene duas listas 
encadeadassimples que serão passadas como 
parâmetros; 
4. Construa uma sub-rotina que retorne a quantidade de 
elementos de uma lista encadeada simples que será 
passada como parâmetro; 
57 
Listas encadeadas (exercícios) 
5. Altere a sub-rotina anterior para que receba 
como parâmetro uma lista encadeada circular e 
retorne sua quantidade de elementos; 
6. Implemente uma sub-rotina recursiva que exiba 
os elementos de uma lista encadeada simples 
passada como parâmetro; 
58 
Listas encadeadas (exercícios) 
7. Construa uma sub-rotina que exiba os elementos de 
uma lista encadeada simples do último ao primeiro. A 
lista será passada como parâmetro; 
8. Construa uma sub-rotina que exiba os elementos de 
duas listas encadeadas ordenadas (passadas como 
parâmetros) intercalados em ordem crescente; 
59 
Listas encadeadas (exercícios) 
9. Construa uma sub-rotina que crie e retorne uma nova lista 
encadeada gerada através da intercalação crescente dos 
elementos de duas listas encadeadas ordenadas passadas 
como parâmetros; 
10. Considere uma coleção de elementos disposta em ordem num 
vetor e outra armazenada em uma lista dinâmica encadeada 
ordenada. Seria viável implementarmos um algoritmo de busca 
binária para as duas coleções? Justifique sua resposta. 
60 
11 
Listas encadeadas (exercícios) 
11. Considerando que as sub-rotinas destroy, isempty e 
next já foram implementadas, codifique a isfull e a store 
para uma fila circular com alocação estática sequencial; 
12. Considerando que as sub-rotinas destroy e isempty já 
foram implementadas, codifique a store para uma fila 
com alocação dinâmica encadeada; 
61 
Listas encadeadas (exercícios) 
13. Com base nos dois últimos exercícios, faça um 
comparativo em relação às velocidades de 
processamento e aos espaços de memória 
requisitados por cada algoritmo; 
14. Implementar um deque (double-ended queue) com 
uma lista encadeada simples; 
62 
Listas encadeadas (exercícios) 
15. Refaça o exercício anterior, porém utilizando uma 
lista duplamente encadeada ao invés de uma 
simples; 
16. Construa uma lista encadeada simples de 
caracteres que tenha um nodo cabeça que 
armazene a quantidade de elementos da lista; 
63 
Listas encadeadas (exercícios) 
17. Implementar uma sub-rotina que ordene em ordem 
crescente uma lista encadeada passada como 
parâmetro. Observe que os ponteiros de cada nodo 
não deverão ser alterados (membro link), apenas o 
conteúdo (membro data). 
64