Estrutura de Dados Lista Simplismente Encadeada

Prévia do material em texto

Estrutura de Dados
Lista Simplesmente Encadeada
2
Tópicos Principais
• Motivação
• Listas encadeadas
• Operações
• Criar
• Inserir 
• Remover 
• Listar
• Alterar
• Encontrar maior
• Encontrar menor 
• Contar elementos
• Buscar sucessor e predecessor. 
Estruturas de dados
• Conjunto de dados que representam informações:
• Números
• Dados de um Funcionário
• Dados de um NPC
• Seus dados estão organizados de forma linear
Motivação
• Vetor
– ocupa um espaço contíguo de memória;
– permite acesso randômico aos elementos;
– deve ser dimensionado com um número máximo de
elementos;
– A ordem é linear e determinada pelos seus índices.
VETOR
4Estática
5
Motivação
• Estruturas de dados dinâmicas:
– crescem (ou decrescem) à medida que elementos
são inseridos (ou removidos).
– Exemplo:
• listas encadeadas:
• amplamente usadas para implementar outras estruturas de
dados
Estruturas de dados dinâmicas:
• As estruturas dinâmicas possuem elementos encadeados 
linearmente e cada elemento poderá ser inserido e removido em 
tempo de execução.
• O elemento é inserido e removido fisicamente na memória.
Listas
• As listas podem ser 
• Homogênea 
• Quando o elemento possui um tipo primitivo da linguagem;
• Heterogênea
• Quando o elemento possui um registro. Ou seja, quando o elemento pode armazenar 
um registro em sua estrutura.
Lista Estática Homogênea
1 2 25 30
0 1 2 3 4 5 6
int vetor[7]
inicio fim
1
Representação Gráfica (um elemento)
Representação Gráfica
Lista Estática Heterogênea
João
20
1.95
Maria
35
1.70
Valmir
40
1.80
0 1 2 3 4 5 6
struct ELEMENTO
{
char nome[30];
int idade;
float altura; 
};
inicio fim
João
20
1.95
Representação Gráfica (um elemento)
Representação Gráfica
Elemento lista[7];
Listas Dinâmicas Homogênea
1 2 30
NULLinicio fim
1
Representação Gráfica (um elemento)
Elemento*inicio
Elemento*fim
Declaração da Lista
Listas Dinâmicas Heterogênea
João
20
1,80
NULLinicio fim
Representação Gráfica (um elemento)
Elemento *inicio
Elemento *fim
Declaração da Lista
maria
30
1,60
Vanessa
20
1,70
struct PESSOA
{
char nome[30];
int idade;
float altura;
}
struct ELEMENTO
{
Pessoa p;
Elemento *prox;
};
João
20
1,80
Listas Encadeadas
• Lista encadeada:
– sequência encadeada de elementos, chamados de nós da lista
– nó da lista é representado por dois campos:
• a informação armazenada e
• o ponteiro para o próximo elemento da lista
– a lista é representada por um ponteiro para o primeiro nó
– o ponteiro do último elemento é NULL
Info1 Info2 Info3
lst
InfoN
. . .
NULL
12
struct
int
ELEMENTO{ 
info;
...void* prox;
Estrutura com ponteiro para ela mesma
info
ELEMENTO* prox;
};
13
Representação de um nó
info
int info
struct ELEMENTO *prox;
Exemplo: Lista de inteiros
struct
int
ELEMENTO{ 
info;
ELEMENTO * prox;
};
1. Lista é uma estrutura auto-referenciada, pois o 
campo prox é um ponteiro para uma próxima 
estrutura do mesmo tipo.
2. uma lista encadeada é representada pelo ponteiro 
para seu primeiro elemento, do tipo Elemento*
15
Exemplo:
Lista de Inteiros
Elemento *inicio;
Elemento *fim;
Elemento *aux;
Elemento *anterior;
16
struct
int
ELEMENTO{ 
info;
ELEMENTO * prox;
};
Controladores da lista
São ponteiros Globais
Declaração dos ponteiros
Listas Encadeadas de inteiros: Criação
de criação:// função
Cria uma lista vazia, representada pelo ponteiro NULL
NULL
17
void criar_lista()
{
inicio = NULL;
fim = NULL
}
Listas encadeadas de inteiros:
Inserção Início
• aloca memória para armazenar o elemento
/* inserção no início
void inserirInicio_lista (int val)
{
Elemento* novo = new Elemento;
novo->info = val;
if(inicio == NULL)
{
inicio = novo;
fim = novo;
fim->prox = NULL;
}
else
{
novo->prox = inicio;
inicio=novo;
}
}
• encadeia o elemento no início da lista existente
18
Listas encadeadas de inteiros:
Inserção Fim
• aloca memória para armazenar o elemento
/* inserção no fim
void inserirFim_lista (int val)
{
Elemento* novo = (Elemento*) malloc(sizeof(Elemento));
novo->info = val;
if(inicio == NULL)
{
inicio = novo;
fim = novo;
fim->prox = NULL;
}
else
{
fim->prox = novo;
fim = novo;
fim->prox = NULL;
}
}
• encadeia o elemento no final da lista existente
19
Listas Encadeadas: exemplo
• cria uma lista inicialmente vazia e insere novos elementos
int main()
{
criar_lista();
inserirFim_lista(5);
inserirFim_lista(4);
inserirInicioLista(10);
system(“pause”);
return 0;
}
5
fim
4
20
10
inicio
Listas Encadeadas: Teste de vazia
• Retorna 1 se a lista estiver vazia ou 0 se não estiver vazia
/* função vazia:
21
retorna 1 se vazia ou 0 se não vazia */
()int verif_listaVazia
{
if(inicio == NULL)
return true;
else
return false;
}
Listas Encadeadas: impressão
• Imprime os valores dos elementos armazenados
p
Info1 Info2 Info3
inicio
InfoN
. . .
p
p
p p
22
void listar()
{
if(verif_listaVazia()) //verificando se a lista esta vazia 
{
cout << “A lista esta vazia!\n”;
}
else //iterando na lista enquanto não acha
{ //o final que é NULL
cout << “consultando a lista!\n”;
aux = inicio;
while(aux != NULL)
{
cout << aux->prox << endl;
aux = aux->prox;
}
}
} fim
Listas Encadeadas: remover um elemento
• recebe como entrada a lista e o valor do elemento a retirar
• atualiza o valor da lista, se o elemento removido for o
primeiro
Info1 Info2 Info3
inicio
Info1 Info2 Info3
• caso contrário, apenas remove o elemento da lista
inicio
23
fim
fim
Remover Inicio
1 2 30
NULLinicio fim
Desenvolver o Algoritmo
inicio = aux->prox;
delete aux;
aux = inicio;
Remover Fim
1 2 30
NULLinicio fim
Desenvolver o Algoritmo
anterior->prox = NULL;
fim = anterior;
delete aux;
aux = NULL;
Remover Meio
1 2 30
NULLinicio fim
Desenvolver o Algoritmo
anterior->prox = aux->prox;
delete aux;
aux = anterior -> prox;
void remover_lista(int val)
{
int achou;
if(verif_listaVazia())
{
printf(“A lista esta vazia!\n”);
}
else
{
aux = inicio;
anterior = NULL;
achou = 0;
while(aux != NULL)
{
if(aux->info == valor)
{
achou = achou+1;
if(aux == inicio)
{
inicio = aux->prox;
delete(aux);
aux = inicio;
}
else if(aux == fim)
{
anterior->prox = NULL;
fim = anterior;
delete(aux);
aux = NULL;
}
else
{
anterior->prox = aux->prox;
delete(aux);
aux = anterior -> prox;
}
}
else
{
anterior = aux;
aux = aux->prox;
}
}
if(achou == 0)
{
cout <<“O numero não foi encontrado!\n”;
}
else if(achou == 1)
{
cout <<“O numero foi removido uma vez!\n”;
}
else
{
cout << “O numero foi removido ” << achou << “ vezes!\n”;
}
} 
}
32
Listas Encadeadas: Libera a lista
• destrói a lista, liberando todos os elementos alocados
void liberar_lista()
{
if(verif_listaVazia())
{
cout << “A lista esta vazia!\n”;
}
else
{
aux = inicio;
while(aux != NULL)
{
inicio=inicio->prox;
free(aux);
aux = inicio;
}
cout << “A lista foi esvaziada!\n”;
}
}