Embed Size (px)
Citation preview
2
Lista LigadaLista Ligada
● Estrutura de dados linear ou dinâmica.
● A lista encadeada ou lista ligada é uma sequencia de elementos (nós), onde cada nó possui:– Um ou mais campos de informações
– Um ponteiro para o próximo nó da lista
6 8 3 12 \
3
Lista LigadaLista Ligada
● Exemplo– Dinâmica
– Linear
6 8 3 12 \
1236 8
4
ListaLista
● Conjunto de operações– Inicializar lista vazia
– Inserir um elemento após o i-ésimo elemento da lista
– Alterar o i-ésimo elemento da lista
– Ordenar a lista em ordem crescente ou decrescente
– Remover o i-ésimo elemento da lista
– Concatenar uma lista em outra lista.
5
Lista EncadeadaLista Encadeada● lista.c#include <stdio.h>#include <stdlib.h>
typedef struct no { int valor; struct no* prox;}No;
x
No
valor prox
6
Lista EncadeadaLista Encadeada
Lista
6 8 3 \
7
Lista EncadeadaLista Encadeada● lista.c
void imprime_lista(No* lista) { while (lista != NULL) { printf("%d\n", lista>valor); lista = lista>prox; }}
8
Lista EncadeadaLista Encadeada
Lista
6 8 3 \
9
Lista EncadeadaLista Encadeada
Lista
6
10
Lista EncadeadaLista Encadeada
Lista
6 8
11
Lista EncadeadaLista Encadeada
Lista
6 8 3 \
12
Lista EncadeadaLista Encadeada● Funçãovoid insere_comeco(No** lista, int valor{ No* no; no = (No*) malloc(sizeof(No));
no>valor = valor; no>prox = *lista;
*lista = no;
imprime_lista(*lista);}
// ...
13
Lista EncadeadaLista Encadeada
void main(){
No* lista;
lista = NULL;
insere_comeco(&lista, 3);insere_comeco(&lista, 8);insere_comeco(&lista, 6);insere_comeco(&lista, 6);
imprime_lista(lista);}
14
Inicializar a ListaInicializar a Lista
X = 3
Lista
15
Inicializar a ListaInicializar a Lista
X = 3
Lista
3 \Lista
16
Inicializar a ListaInicializar a Lista
X = 3
Lista
3 \Lista
Lista
3 \
17
Inserir no início da listaInserir no início da lista
X = 10
Lista
6 8 3 \
18
Inserir no início da listaInserir no início da lista
X = 10
Lista
6
a
8 3 \
Lista
6 8 3 \10
19
Inserir no início da listaInserir no início da lista
a
Lista
6 8 3 \10
b
Lista
6 8 3 \10
20
Inserir no início da listaInserir no início da lista
b
Lista
6 8 3 \10
c
Lista
6 8 3 \10
21
Inserir no final da listaInserir no final da lista
X = 12Lista
6 8 3 \
22
Inserir no final da listaInserir no final da lista
void insere_final(No** lista, int v) {
No *n, *aux; n = (No*) malloc(sizeof(No)); n>valor = v; n>prox = NULL; // Ultimo elemento da lista
if (*lista == NULL) *lista = n; else { aux = *lista; while (aux>prox != NULL) aux = aux>prox; aux>prox = n; }}
23
Inserir no final da listaInserir no final da lista
void main() {
... insere_final(&lista, 12); imprime_lista(lista);
}
24
Inserir no final da listaInserir no final da lista
X = 12Lista
6 8 3 \
25
Inserir no final da listaInserir no final da lista
X = 12Lista
6
a
8 3 \
Lista
6 8 3 \ 12 \
26
Inserir no final da listaInserir no final da lista
a
Lista aux
6 8 3 \ 12 \
b
Lista aux
6 8 3 12 \
27
Inserir no final da listaInserir no final da lista
b
Lista aux
6 8 3 12 \
c
Lista
6 8 3 12 \
28
Remover no início da listaRemover no início da lista
int remove_inicio(No** lista) { No* n; int v;
if (*lista == NULL) return 1;
n = *lista; *lista = n>prox;
v = n>valor; free(n); return v;}
29
Remover no início da listaRemover no início da lista
void main() {
...while (remove_inicio(&lista) != 1)
imprime_lista(l);}
30
Remover no início da listaRemover no início da lista
a
Lista
6 8 3 \
31
Remover no início da listaRemover no início da lista
a
Listan
6 8 3 \
b
6 8 3 \
Lista
X = 6n
32
Remover no início da listaRemover no início da lista
c
8 3 \
ListaX = 6
b
6 8 3 \
Lista
X = 6n
33
Remover no final da listaRemover no final da lista
int remove_final(No** lista) { No *n, *aux; int v;
if (*lista == NULL) return 1; if ((*lista)>prox == NULL) { n = *lista; *lista = NULL; }
//...}
34
Remover no final da listaRemover no final da listaint remove_final(No** lista) {
// ...
else { aux = *lista; /* Para no penúltimo nó */ while (aux>prox>prox != NULL) aux = aux>prox; n = aux>prox; aux>prox = NULL; } v = n>valor; free(n); return v;}
35
Remover no final da listaRemover no final da lista
void main() {
...while (remove_final(&lista) != 1)
imprime_lista(l);}
36
Remover no final da listaRemover no final da lista
aaux
Lista
6 8 3 \
37
Remover no final da listaRemover no final da lista
aaux
Lista
6 8 3 \
b
Lista
6 8 3 \
aux
X = 3
38
Remover no final da listaRemover no final da lista
b
Lista
6 8 3 \
aux
X = 3
c
Lista
6 8 \ X = 3
39
Remover no final da listaRemover no final da lista
aaux
Lista
6 8 3 \
b
Lista
6 8 3 \
aux
X = 3
