Estrutura de Dados - Listas Encadeadas

1. Prof. Adriano Teixeira de Souza

2. Listas encadeadas ou listas ligadas
representam uma seqüência de objetos na
memória do computador.

Exemplo: Lista de afazeres
1.Comprar uma lâmpada
2.Trocar uma lâmpada queimada
3.Procurar uma conta no quarto
4.Pagar uma conta na internet
5.Desligar o computador
6.Dormir

3. Próxima
ação Ação atual
Na lista de afazeres anterior, uma tarefa
dependia da execução da tarefa anterior

4. 2
1. Comprar
lâmpada
3
2. Trocar
lâmpada
4
3. Procurar
conta
5
4. Pagar
conta
6
5. Desligar
micro
fim 6. Dormir

5. Dormir
Desligar
micro
Pagar
conta
Procurar
conta
Trocar
lâmpada
Como representar a lista anterior em um
programa escrito na Linguagem C?
◦Primeira opção: vetores ou matrizes
Comprar
lâmpada
Tarefa:
Índice: 1 2 3 4 5 6

6. Primeira opção: vetores ou matrizes
◦Como acrescentar “Ligar micro”?
Dormir
Desligar
micro
Pagar
conta
Ligar
micro
Procurar
conta
Trocar
lâmpada
Comprar
lâmpada
Tarefa:
Índice: 1 2 3 4 5 6 7

7. Primeira opção: vetores ou matrizes
◦Os itens da lista são armazenados em posições
contíguas de memória.

◦A lista pode ser percorrida em qualquer direção.

◦A inserção de um novo item pode ser realizada
após o último item com custo constante.

◦A inserção de um novo item no meio da lista requer
um deslocamento de todos os itens localizados
após o ponto de inserção.

◦Retirar um item do início da lista requer um
deslocamento de itens para preencher o espaço
deixado vazio.

8. Segunda opção: ponteiros
◦Estruturas de dados dinâmicas: estruturas de dados
que contém ponteiros para si próprias.
struct lista {
char nome_tarefa[30];
float duracao;
char responsavel[30];
...
struct lista *prox;
};
ponteiro para a
própria estrutura lista

9. Representação gráfica de um elemento da lista:





◦Cada item é encadeado com o seguinte, mediante uma
variável do tipo ponteiro.
◦Permite utilizar posições não contíguas de memória.
◦É possível inserir e retirar elementos sem necessidade de
deslocar os itens seguintes da lista.
campos de informação
próximo nó

10. Cada item em particular de uma lista pode ser
chamado de elemento, nó, célula, ou item.
O apontador para o início da lista também é
tratado como se fosse uma célula (cabeça), para
simplificar as operações sobre a lista.
O símbolo / representa o ponteiro nulo (NULL),
indicando o fim da lista.
3
5
p
2
/ 4

11. Podemos realizar algumas operações sobre
uma lista encadeadas, tais como:
◦Inserir itens;
◦Retirar itens;
◦Buscar itens.

Para manter a lista ordenada, após realizar
alguma dessas operações, será necessário
apenas movimentar alguns ponteiros (de um
a três elementos).

12. Outras operações possíveis:
◦Criar uma lista
◦Destruir uma lista
◦Ordenar uma lista
◦Intercalar duas listas
◦Concatenar duas listas
◦Dividir uma lista em duas
◦Copiar uma lista em outra

13. Prof. Adriano Teixeira de Souza
typedef struct {
float info;
struct No* proximo;
} No;

No* cria (void)
{
return NULL;
}

14. Podemos inserir itens:
◦No início de uma lista
◦No final de uma lista
◦No meio de uma lista

15. p 5 2 / 4
O endereço armazenado no ponteiro p deve
ser alterado para o endereço do item a ser
acrescido à lista.
3

16. Prof. Adriano Teixeira de Souza
No* insere (No* l, float v)
{
No* p = (No*) malloc(sizeof(No));
p->info = v;
p->proximo = l;

return p;
}

17. O endereço armazenado em p será alterado
caso a lista esteja vazia ou
O campo prox do último item será alterado.
/ 3 p
/
3 / 5 p

18. Campo prox do item a ser inserido recebe o
campo prox do item posterior
Campo prox do item antecessor recebe o
endereço do item a ser inserido
2 / 4
5
3 p
lista[5].prox ← lista[2]
lista[3].prox ← 5

19. p 5 2 / 4
O endereço armazenado no ponteiro p deve
ser alterado para o endereço do item que
segue o primeiro item da lista.

20. O campo prox do último item será alterado
caso a lista contenha mais de um item ou
O endereço armazenado em p será alterado
para NULL.
/ 3 p
/
3 / 5 p

21. Item antecessor recebe o campo prox do
item a ser removido
5 2 / 4 3 p
lista[3].prox ← lista[5].prox

22. No* retira (No* l, float v) {//Em qualquer posicao

No* ant = NULL;
No* p = l;

while (p != NULL && p ->info != v) {
ant = p;
p = p->proximo;
}
if (p == NULL)
return l;
if (ant == NULL) {
l = p->proximo;
}else {
ant->proximo = p->proximo;
}
free(p);
return l;
}

23. Prof. Adriano Teixeira de Souza
No* busca (No* l,float v){
No* q;
int i=0;
for (q=l; q!=NULL; q=q ->proximo){
if(q->info == v){
printf("\n\nachou %d\n\n\n",i);
return q;
}
i++;
}
return NULL;
}

24. Prof. Adriano Teixeira de Souza
void imprime (No* l){
No* q;
for (q=l; q!=NULL; q=q ->proximo)
printf("%f\n", q->info);
}

25. Prof. Adriano Teixeira de Souza
void libera (No* l) {
No* q = l;
while (q!=NULL) {
No* t = q->proximo;
free(q);
q = t;
}
}

26. Prof. Adriano Teixeira de Souza
main(){

No* p = cria();
p = insere (p,20.0);
p = insere (p,44.5);
p = insere (p,33.3);
p = insere (p,20.9);
imprime (p);
No* n = busca(p,20.3);//Busca
if (n != NULL){
printf ("Encontrado: %f\n", n->info);
p=retira(p,n->info);
}
printf ("Configuracao da fila:\n");
imprime (p);
libera (p);

system("pause");

}

27. Prof. Adriano Teixeira de Souza
No* insere_ordenado (No* l, float v)
{
No* novo = (No*) malloc(sizeof(No));
novo->info = v;

No* ant = NULL;
No* p = l;

while (p != NULL && p ->info < v) {
ant = p;
p = p->proximo;
}
if (ant == NULL) {
novo->proximo = l;
l = novo;
} else {
novo->proximo = ant->proximo;
ant->proximo = novo;
}
return l;
}