Aula 14 - Listas Encadeadas

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Listas Encadeadas
*
Listas Encadeadas
Vetores nem sempre são estruturas de armazenamento ideais.
Listas Encadeadas
Criamos espaço individualmente para cada elemento que queremos guardar;
Removemos espaço individualmente dos elementos que não queremos mais.
*
Listas Encadeadas
São estruturas de armazenamento de dados;
Correspondem a um conjunto de blocos de dados de mesmas características, que são abstratamente linearizados (ainda que não necessáriamente se apresentem assim na memória); 
Este modo de estruturação de um conjunto de dados, aliado a algoritmos que levem em conta seu potencial, apresenta uma série de vantagens em relação a outros modos de armazenamento.
*
Listas Encadeadas
Uma lista encadeada é uma representação de uma sequência de elementos;
Cada elemento dessa sequência é armazenado em uma célula da lista;
Cada célula contém os dados, e o endereço da célula seguinte;
Vamos supor a partir daqui que o dado armazenado em cada célula é um número inteiro.
*
Ilustração
Ilustração de uma lista encadeada;
proximo
proximo
proximo
proximo
O acesso a uma lista encadeada é o endereço de sua primeira célula.  Se p é o acesso a uma lista, podemos dizer simplesmente que “p é uma lista”;
*
Implementação de uma lista encadeada 
Vamos primeiro criar uma célula;
A estrutura de cada célula de uma lista encadeada pode ser definida da seguinte forma: 
		struct cel { 
			int conteudo; 
			struct cel *proximo; 
		}; 
Por simplicidade podemos apelidar esta nova estrutura de celula:
		typedef struct cel celula;
*
Acesso aos elementos de uma lista
Considere as seguintes declarações:
		celula c;
		celula *p;
‘c’ é uma célula e então:
c.conteudo:  pode armazenar um número inteiro;
c.proximo: pode guardar o endereço de outra célula;
‘p’ é um ponteiro para uma célula e então:
p->conteudo: pode armazenar um número inteiro;
p->proximo:  pode guardar o endereço de outra célula;
O campo próximo da última célula da lista deve valer  NULL;
*
Inserção de um elemento em uma lista
p
Vamos considerar que as inserções na lista em questão serão feitas sempre no início;
Criando a primeira célula da lista ‘p’. 
	Exemplo:
int x;
celula *p = NULL;
*
Inserção de um elemento em uma lista
Vamos considerar que as inserções na lista em questão serão feitas sempre no início;
Criando a primeira célula da lista ‘p’. 
	Exemplo:
p
conteudo
proximo
16
int x;
celula *p = NULL;
...
p = (celula *) malloc(sizeof (celula));
p->conteudo = x; 
p->proximo = NULL;
...
*
Inserção de um elemento em uma lista
Criando uma nova célula depois que a primeira já foi criada;
	Exemplo:
p
conteudo
proximo
16
8
int x;
celula *nova;
...
nova = (celula *) malloc(sizeof (celula));
nova->conteudo = x; 
*
Inserção de um elemento em uma lista
Criando uma nova célula depois que a primeira já foi criada;
	Exemplo:
p
conteudo
proximo
16
8
int x;
celula *nova;
...
nova = (celula *) malloc(sizeof (celula));
nova->conteudo = x; 
nova->proximo = p;
*
Inserção de um elemento em uma lista
Criando uma nova célula depois que a primeira já foi criada; 
	Exemplo:
p
conteudo
proximo
16
conteudo
proximo
8
int x;
celula *nova;
...
nova = (celula *) malloc(sizeof (celula));
nova->conteudo = x;
nova->proximo = p;
 
p = nova;
*
Inserção de um elemento em uma lista
Criando uma nova célula depois que a primeira já foi criada;
	Exemplo:
p
conteudo
proximo
16
conteudo
proximo
8
*
Inserção de um elemento em uma lista
int x;
celula *nova, *p = NULL;
printf("Digite um elemento a ser inserido na lista:");
scanf("%d", &x);
if(p == NULL)
{
		p = (celula *) malloc(sizeof (celula));
		p->conteudo = x; 
		p->proximo = NULL;
}
else
{
		nova = (celula *) malloc(sizeof (celula));
		nova->conteudo = x; 
		nova->proximo = p;
		p = nova;
}
*
Inserção de um elemento em uma lista
Criando a primeira célula da lista ‘p’;
	Exemplo:
p
16
nova = (celula *) malloc(sizeof (celula));
nova->conteudo = x; 
nova->proximo = p;
p = nova;
*
Inserção de um elemento em uma lista
Criando a primeira célula da lista ‘p’;
	Exemplo:
nova = (celula *) malloc(sizeof (celula));
nova->conteudo = x; 
nova->proximo = p;
p = nova;
p
16
*
Inserção de um elemento em uma lista
Criando a primeira célula da lista ‘p’;
	Exemplo:
nova = (celula *) malloc(sizeof (celula));
nova->conteudo = x; 
nova->proximo = p;
p = nova;
16
*
Impressão dos elementos de uma lista
Basta percorrer a lista imprimindo cada elemento;
	Exemplo:
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
Saída:
16
aux = p;
while(aux != NULL)
{
 printf("%d ",aux->conteudo);
*
Impressão dos elementos de uma lista
Basta percorrer a lista imprimindo cada elemento;
	Exemplo:
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
aux = p;
while(aux != NULL)
{
 printf("%d ",aux->conteudo);
 aux = aux->proximo;
}
Saída:
16
8
*
Impressão dos elementos de uma lista
Basta percorrer a lista imprimindo cada elemento;
	Exemplo:
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
aux = p;
while(aux != NULL)
{
 printf("%d ",aux->conteudo);
 aux = aux->proximo;
}
Saída:
16
8 15
*
Impressão dos elementos de uma lista
Basta percorrer a lista imprimindo cada elemento;
	Exemplo:
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
aux = p;
while(aux != NULL)
{
 printf("%d ",aux->conteudo);
 aux = aux->proximo;
}
Saída:
16
8 15 12
*
Impressão dos elementos de uma lista
Basta percorrer a lista imprimindo cada elemento;
	Exemplo:
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
aux
aux = p;
while(aux != NULL)
{
 printf("%d ",aux->conteudo);
 aux = aux->proximo;
}
Saída:
16
8 15 12
*
Impressão dos elementos de uma lista
Basta percorrer a lista imprimindo cada elemento;
celula *aux;
...
if (p == NULL)
	printf("\nA lista esta vazia.\n");
else 
{
	printf("\nConteudo da lista:\n");
 	aux = p;
	while(aux != NULL)
	{
		printf("%d ",aux->conteudo);
		aux = aux->proximo;
	}
}
*
Busca de um elemento em uma lista
Queremos verificar se um inteiro pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista;
	Exemplo: Busca pelo elemento 17;
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
*
Busca de um elemento em uma lista
Queremos verificar se um inteiro pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista: 
	Exemplo: Busca pelo elemento 17.
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
*
Busca de um elemento em uma lista
Queremos verificar se um inteiro pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista: 
	Exemplo: Busca pelo elemento 17.
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
*
Busca de um elemento em uma lista
Queremos verificar se um inteiro pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista: 
	Exemplo: Busca pelo elemento 17.
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
*
Busca de um elemento em uma lista
Queremos verificar se um inteiro pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista: 
	Exemplo: Busca pelo elemento 17.
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
aux
Elemento não encontrado.
*
Busca de um elemento em uma lista
Queremos verificar
se um inteiro pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista: 
	Exemplo: Busca pelo elemento 15.
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
*
Busca de um elemento em uma lista
Queremos verificar se um inteiro pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista: 
	Exemplo: Busca pelo elemento 15.
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
*
Busca de um elemento em uma lista
Queremos verificar se um inteiro pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista: 
	Exemplo: Busca pelo elemento 15.
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
Elemento encontrado.
*
Busca de um elemento em uma lista
Queremos verificar se um inteiro x pertence a uma lista encadeada, ou seja, se é igual ao conteúdo de alguma célula da lista;
	celula *aux;
	...
 	aux = p; 
	while (aux != NULL && aux->conteudo != x) 	aux = aux->proximo;
	if(aux == NULL)
		printf("Elemento não encontrado!\n");
	else
		printf("Elemento encontrado!\n");
*
Remoção de um elemento em uma lista
Removendo o primeiro elemento.
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
celula *aux;
aux = p;
*
Remoção de um elemento em uma lista
Removendo o primeiro elemento.
	
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
celula *aux;
aux = p;
p = p->proximo;
*
Remoção de um elemento em uma lista
Removendo o primeiro elemento.
	
p
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
celula *aux;
aux = p;
p = p->proximo;
free(aux);
...
*
Remoção de um elemento em uma lista
Removendo um elemento qualquer. 
Exemplo: Remoção do elemento 15
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
*
Remoção de um elemento em uma lista
Removendo um elemento qualquer. 
Exemplo: Remoção do elemento 15
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
...
aux1->proximo = aux2->proximo;
*
Remoção de um elemento em uma lista
Removendo um elemento qualquer. 
Exemplo: Remoção do elemento 15
	
p
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
...
aux1->proximo = aux2->proximo;
free(aux2);
*
Remoção de um elemento em uma lista
Removendo um elemento qualquer. 
Exemplo: Remoção do elemento 15
	
p
conteudo
proximo
16
conteudo
proximo
12
conteudo
proximo
8
...
aux1->proximo = aux2->proximo;
free(aux2);
*
Destruição da lista
Libera a memória alocada para os elementos da lista;
	
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
	celula * aux;
	while (p != NULL)
	{
		aux = p;
		p = p->proximo;	
		free(aux);
	}
	
*
Destruição da lista
Libera a memória alocada para os elementos da lista;
	
conteudo
proximo
16
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
	celula * aux;
	while (p != NULL)
	{
		aux = p;
		p = p->proximo;	
		free(aux);
	}
	
*
Destruição da lista
Libera a memória alocada para os elementos da lista;
	
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
	celula * aux;
	while (p != NULL)
	{
		aux = p;
		p = p->proximo;	
		free(aux);
	}
	
*
Destruição da lista
Libera a memória alocada para os elementos da lista;
	
conteudo
proximo
15
conteudo
proximo
12
conteudo
proximo
8
	celula * aux;
	while (p != NULL)
	{
		aux = p;
		p = p->proximo;	
		free(aux);
	}
	
*
Destruição da lista
Libera a memória alocada para os elementos da lista;
	
conteudo
proximo
15
conteudo
proximo
12
	celula * aux;
	while (p != NULL)
	{
		aux = p;
		p = p->proximo;	
		free(aux);
	}
	
*
Destruição da lista
Libera a memória alocada para os elementos da lista;
	
conteudo
proximo
15
conteudo
proximo
12
	celula * aux;
	while (p != NULL)
	{
		aux = p;
		p = p->proximo;	
		free(aux);
	}
	
*
Destruição da lista
Libera a memória alocada para os elementos da lista;
	
conteudo
proximo
12
	celula * aux;
	while (p != NULL)
	{
		aux = p;
		p = p->proximo;	
		free(aux);
	}
	
*
Destruição da lista
Libera a memória alocada para os elementos da lista;
	
conteudo
proximo
12
p
	celula * aux;
	while (p != NULL)
	{
		aux = p;
		p = p->proximo;	
		free(aux);
	}
	
*
Destruição da lista
Libera a memória alocada para os elementos da lista;
	
p
	celula * aux;
	while (p != NULL)
	{
		aux = p;
		p = p->proximo;	
		free(aux);
	}
	
*
Exercícios
Escreva uma função que receba como parâmetro uma lista encadeada e retorne a quantidade de células da lista.
Escreva uma função que receba como parâmetro uma lista encadeada e retorne a soma dos elementos da lista.
Escreva uma função que busca e remove um elemento de uma lista encadeada.
Escreva um programa que contenha uma função que insere um elemento no final (à direita) de uma lista encadeada.