Aula 3 Lista Dinamica simples

Prévia do material em texto

Aula
Estrutura de dados
Listas dinâmicas simples
Prof. Cenez Araújo de Rezende
Unifor
Universidade de Fortaleza
Fortaleza/CE, Brasil
 
Agenda
- Listas dinâmicas simples
Lista ligada
 
Listas dinâmicas simples
Lista ligada
Aula
 4
Estrutura de dados
Listas dinâmicas simples
● Lista ligada?
– Uma abordagem que permite 
alocação/desalocação dinâmica de endereço de 
memória para cada elemento
– Não há limitação estática de elementos
– Alocação/desalocação sob demanda
● Vantagens
– Evitar gasto de memória com elementos que 
não estão sendo utilizados
– Não necessita gerenciar índices de 
disponibilidade para elementos
 5
Estrutura de dados
Listas dinâmicas simples
● Modelo usado
– Antes de começar, repare nos endereços e 
elementos, bem como chaves
3020
6
3420
3420
10
null
6050
9
3020
Elemento 3420
(Endereço)
Endereço
Aninhado
De 3020,
Consiste no elemento
3420
É o elemento 3020: endereço
Chaves
6, 10 e 9
 6
Estrutura de dados
Listas dinâmicas simples
● Modelo usado
– Antes de começar, repare nos endereços e 
elementos, bem como chaves
3020
6
3420
3420
10
null
6050
9
3020
Aponta para 3020
Aponta para 3420 Não aponta
Pois está nulo
 7
Estrutura de dados
Listas dinâmicas simples
● Lista ligada: como funciona?
– Há um ponteiro início que aponta para o 
primeiro elemento
– Elementos possuem sucessor (o último é null)
– No nosso caso, iremos considerar a ordem, mas 
isso é decisão de projeto
inicio
3020
6
3420
3020
3060
10
null
3290
9
3060
3420
8
3290
 8
Estrutura de dados
Listas dinâmicas simples
● Lista ligada: como funciona?
– Exclusão: o ponteiro aponta para o sucessor do 
próximo. Exemplo, remover 9?
inicio
3020
6
3420
3020
3060
10
null
3290
9
3060
3420
8
3290
 9
Estrutura de dados
Listas dinâmicas simples
● Lista ligada: como funciona?
– Exclusão: o ponteiro aponta para o sucessor do 
próximo. Exemplo, remover 9?
inicio
3020
6
3420
3020
3060
10
null
3420
8
3060
 10
Estrutura de dados
Listas dinâmicas simples
● Lista ligada: como funciona?
– Inclusão: Exemplo, incluir 1
● Inicio aponta para elemento 1, pois é o menor
● Elemento 1 aponta para o antigo primeiro 
elemento, no caso o 6
inicio
3020
6
3420
3020
3060
10
null
3420
8
3060
 11
Estrutura de dados
Listas dinâmicas simples
● Lista ligada: como funciona?
– Inclusão: Exemplo, incluir 1
● Inicio aponta para elemento 1, pois é o menor
● Elemento 1 aponta para o antigo primeiro 
elemento, no caso o 6
inicio
3020
6
3420
3460
3060
10
null
3420
8
3060
3460
1
3020
 12
Estrutura de dados
Listas dinâmicas simples
● Estrutura
inicio
3020
6
3420
3460
3060
10
null
3420
8
3060
3460
1
3020
#include <stdio.h>
#include <malloc.h>
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT inicio;
} LISTA;
 13
#include <stdio.h>
#include <malloc.h>
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct {
KEY chave;
} REGISTRO;
typedef struct aux {
REGISTRO reg;
struct aux* prox;
} ELEMENTO, *PONT;
typedef struct {
PONT inicio;
} LISTA;
Estrutura de dados
Listas dinâmicas simples
● Estrutura
inicio
3020
6
3420
3460
3060
10
null
3420
8
3060
3460
1
3020
 14
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Inicializar a lista
– Quantidade de elementos válidos
– Exibir elementos da lista
– Pesquisar elementos na lista
– Inserir
– Excluir
– Reinicalizar
 15
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Inicializar a lista
● Não temos vetor, portanto basta:
void initialize(LISTA *lista){
lista->inicio = NULL;
}
 16
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Quantidade de elementos
● Não temos nroElem, portanto é necessário 
percorrer a lista, contando válidos
int count(LISTA *lista){
PONT fim = lista->inicio;
int tam = 0;
while(fim!=NULL){
tam++;
fim = fim->prox;
}
return tam;
}
 17
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Exibir elementos
● Percorrer a lista, imprimendo chaves
void print(LISTA *lista){
PONT fim = lista->inicio;
printf("Lista: ");
while(fim!=NULL) {
printf("%i ", fim->reg.chave);
fim = fim->prox;
}
printf("\n");
}
 18
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Pesquisar elementos (Sequencial e ordenado)
● Percorrer a lista, compara chave e retorna 
elemento
PONT busca(LISTA *lista, KEY ch){
PONT ponto = lista->inicio;
while(ponto!=NULL){
if(ponto->reg.chave == ch) return ponto;
ponto = ponto->prox;
}
return NULL;
}
 19
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Inserir elementos
● No caso de inserção ordenada, deve 
encontrar onde o elemento será encaixado na 
lista ligada;
● Alocar memória para novo elemento
● Novo elemento deve apontar para proximo 
elemento (veja que isso é o prox do 
predecessor)
● Predecessor deve apontar para novo elemento
 20
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Inserir - definiremos uma função auxiliar 
chamada buscaAtualAnt, que retorna 2 dados:
–Endereço de elemento se já existir, ou 
NULL se não existir
–Endereço predecessor (existindo ou não)
PONT buscaAtualAnt(LISTA *lista, KEY ch, PONT *ant) {
*ant = NULL;
PONT atual = lista->inicio;
while((atual != NULL) && (atual->reg.chave < ch)) {
*ant = atual;
atual = atual->prox;
}
if((atual != NULL) && (atual->reg.chave == ch)) 
return atual;
return NULL;
}
 21
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Inserir elementos
bool inserirEmOrdem(LISTA *lista, REGISTRO reg){
KEY ch = reg.chave;
PONT ant, i;
i = buscaAtualAnt(lista,ch,&ant);
if(i!=NULL) return false;
i = (PONT) malloc(sizeof(ELEMENTO));
i->reg = reg;
if(ant == NULL) {
i->prox = lista->inicio;
lista->inicio = i;
} else {
i->prox = ant->prox;
ant->prox = i;
}
return true;
}
 22
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Excluir elementos
● Usuário passa a chave
– Se existir: exclui da lista, acertam-se os ponteiros 
e retorna true
– Se não existir: retorna false;
● Necessário conhecer o antecessor do elemento a ser 
excluído
 23
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Excluir elementos
bool excluiElemento(LISTA *lista, KEY ch){
PONT ant, i;
i = buscaAtualAnt(lista,ch,&ant);
if(i==NULL) return false;
if(ant==NULL) lista->inicio = i->prox;
else ant->prox = i->prox;
free(i);
return true;
}
 24
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Reinicializar a lista
● Itera por todos os elementos, onde para cada 
elemento é feita a liberação de memória, com a 
função free()
● O “inicio” deve receber NULL
 25
Estrutura de dados
Listas dinâmicas simples
● Funções a implementar
– Reinicializar a lista
void reinicializar(LISTA *lista){
PONT fim = lista->inicio;
while (fim != NULL){
PONT apagar = fim;
fim = fim->prox;
free(apagar);
}
lista->inicio = NULL;
}
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25