Aula 2 Listas

Prévia do material em texto

Aula
Estrutura de dados
Listas estáticas
Prof. Cenez Araújo de Rezende
Unifor
Universidade de Fortaleza
Fortaleza/CE, Brasil
 
Agenda
- Listas estáticas
* Lineares sequenciais
* Listas ligadas
 
Lineares e sequenciais
Aula
 4
Estrutura de dados
Listas estáticas
● O que é uma lista?
 5
Estrutura de dados
Listas estáticas
● O que é uma lista?
– Estrutura de dados (ED) para guardar e recuperar dados 
(ELEMENTOS)
● Lista linear?
 6
Estrutura de dados
Listas estáticas
● O que é uma lista?
– Estrutura de dados (ED) para guardar e recuperar dados 
(ELEMENTOS). O que é estática?
● Lista linear?
 7
Estrutura de dados
Listas estáticas
● O que é uma lista?
– Estrutura de dados (ED) para guardar e recuperar dados 
(ELEMENTOS). O que é estática?
● Lista linear?
– Uma sequencia de elementos;
– Cada elemento (excluso primeiro/último) é precedido e 
sucedido por outros elementos, os quais se dispõem em 
uma dada ordem (ex: chave ou ordem de inserção).
 8
Estrutura de dados
Listas estáticas
● O que é uma lista?
– Estrutura de dados (ED) para guardar e recuperar dados 
(ELEMENTOS). O que é estática?
● Lista linear?
– Uma sequencia de elementos;
– Cada elemento (excluso primeiro/último) é precedido e 
sucedido por outros elementos, os quais se dispõem em 
uma dada ordem (ex: chave ou ordem de inserção).
● Lista linear sequencial
– Ordem lógica de elementos (visão de usuário) 
equivalente à ordem física (memória)
● Ex. de dados sequenciais: Arranjo (array)
– vetor(unidimensional), matriz (bidimensional)
 9
Estrutura de dados
Listas estáticas
● Como implementar uma lista linear sequencial?
 10
Estrutura de dados
Listas estáticas
● Como implementar uma lista linear sequencial?
– Arranjo de registros?
● Registro contém informações úteis ao usuário 
– Arranjo possui tamanho fixo, bem como número de 
elementos controlados/monitorados por variável inteira
 11
Estrutura de dados
Listas estáticas
● Como implementar uma lista linear sequencial?
– Arranjo de registros?
● Registro contém informações úteis ao usuário 
– Arranjo possui tamanho fixo, bem como número de 
elementos controlados/monitorados por variável inteira
● Modelagem em C #include <stdio.h>
#define MAX 100
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct{
KEY chave;
} REGISTRO;
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 12
Estrutura de dados
Listas estáticas
● Como implementar uma lista linear sequencial?
– Arranjo de registros?
● Registro contém informações úteis ao usuário 
– Arranjo possui tamanho fixo, bem como número de 
elementos controlados/monitorados por variável inteira
● Modelagem em C #include <stdio.h>
#define MAX 100
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct{
KEY chave;
} REGISTRO;
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 13
Estrutura de dados
Listas estáticas
● Como implementar uma lista linear sequencial?
– Arranjo de registros?
● Registro contém informações úteis ao usuário 
– Arranjo possui tamanho fixo, bem como número de 
elementos controlados/monitorados por variável inteira
● Modelagem em C #include <stdio.h>
#define MAX 100
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct{
KEY chave;
} REGISTRO;
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 14
Estrutura de dados
Listas estáticas
● Como implementar uma lista linear sequencial?
– Arranjo de registros?
● Registro contém informações úteis ao usuário 
– Arranjo possui tamanho fixo, bem como número de 
elementos controlados/monitorados por variável inteira
● Modelagem em C #include <stdio.h>
#define MAX 100
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct{
KEY chave;
} REGISTRO;
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 15
Estrutura de dados
Listas estáticas
● Como implementar uma lista linear sequencial?
– Arranjo de registros?
● Registro contém informações úteis ao usuário 
– Arranjo possui tamanho fixo, bem como número de 
elementos controlados/monitorados por variável inteira
● Modelagem em C #include <stdio.h>
#define MAX 100
#define true 1
#define false 0
typedef int bool;
typedef int KEY;
typedef struct{
KEY chave;
} REGISTRO;
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
#include <stdio.h>
#define MAX 100
#define true 1
#define false 0
typedef int bool;
typedef struct {
int A[MAX];
int nroElem;
} LISTA;
Poderia ser assim também
mas vamos trabalhar
com o primeiro, que é mais
genérico e completo
1º 2º
 16
Estrutura de dados
Listas estáticas
● Funções gerenciais utilizadas na ED
– initialize
– count
– print
– search
– add
– delete
– clear
 17
Estrutura de dados
Listas estáticas
● Initialize
– Define os valores iniciais de variáveis
● Arranjo por padrão já inicia vazio
● nroElem=0
● Qual usar?
void initializa(LISTA lista){ 
lista.nroElem = 0; 
}
void initializa(LISTA *lista){ 
lista->nroElem = 0; 
}
void initializa(LISTA *lista){ 
(*lista).nroElem = 0; 
}
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 18
Estrutura de dados
Listas estáticas
● Count
– Retorna nroElem
● Qual usar?
int count(LISTA lista){ 
return lista.nroElem; 
}
int count(LISTA *lista){ 
return lista->nroElem; 
}
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 19
Estrutura de dados
Listas estáticas
● Print
– Itera o arranjo e imprime dados dos elementos (por 
exemplo a chave)
void print(LISTA *lista){
int i;
printf("Lista: [ ");
for(i=0;i<lista->nroElem; i++)
printf("%d ", lista->A[i].chave);
printf("]\n");
}
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
typedef struct{
KEY chave;
} REGISTRO;
 20
Estrutura de dados
Listas estáticas
● Search
– Função recebe uma chave: caso exista, retorna 
indexação da chave na lista; ou -1 caso contrário.
int search(LISTA *lista, KEY chave){
int i = 0;
while (i < lista->nroElem){
if(chave == lista->A[i].chave) return i;
else i++;
}
return -1;
}
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 21
Estrutura de dados
Listas estáticas
● Add
– Ordenada, começo, fim, indexado?
– Indexado
● Registro e índice são passados como parâmetros, 
visando a inserção na lista na posição do índice
bool add(LISTA *lista, REGISTRO reg, int i){
int j;
if((lista->nroElem==MAX) || (i<0) || (i>lista->nroElem))
return false;
for(j=lista->nroElem; j>i ; j--) 
lista->A[j] = lista->A[j-1];
lista->A[i] = reg;
lista->nroElem++;
return true;
}
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 22
Estrutura de dados
Listas estáticas
● Add
● Inserir o 18 na posição 3?
bool add(LISTA *lista, REGISTRO reg, int i){
int j;
if((lista->nroElem==MAX) || (i<0) || (i>lista->nroElem))
return false;
for(j=lista->nroElem; j>i ; j--) 
lista->A[j] = lista->A[j-1];
lista->A[i] = reg;
lista->nroElem++;
return true;
}
10 5 30 40 ? ?
4
A
nroElem
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 23
Estrutura de dados
Listas estáticas
● Add
● Inserir o 18 na posição 3?
10 5 30 40 40 ?
4
A
nroElem
bool add(LISTA *lista, REGISTRO reg, int i){
int j;
if((lista->nroElem==MAX) || (i<0) || (i>lista->nroElem))
return false;
for(j=lista->nroElem; j>i ; j--) 
lista->A[j] = lista->A[j-1];
lista->A[i] = reg;
lista->nroElem++;
return true;
}
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 24
Estrutura de dados
Listasestáticas
● Add
● Inserir o 18 na posição 3?
10 5 30 18 40 ?
5
A
nroElem
bool add(LISTA *lista, REGISTRO reg, int i){
int j;
if((lista->nroElem==MAX) || (i<0) || (i>lista->nroElem))
return false;
for(j=lista->nroElem; j>i ; j--) 
lista->A[j] = lista->A[j-1];
lista->A[i] = reg;
lista->nroElem++;
return true;
}
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 25
Estrutura de dados
Listas estáticas
● Delete
– Dada uma chave, verificar se o elemento existe
● Se existir, excluir
– Elementos posteriores são deslocados uma 
posição à esquerda
– Ex: [A,B,C,D,...]→[A,B,D,…]), onde C foi 
excluído
● Diminuir nroElem em 1 e retornar True
 26
Estrutura de dados
Listas estáticas
● Delete
bool delete(LISTA *lista, KEY chave, ){
int pos, j;
pos = search(lista,chave);
if(pos==-1) return false;
for(j=pos; j<lista->nroElem-1;j++)
lista->A[j] = lista->A[j+1];
lista->nroElem--;
return true;
}
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
 27
Estrutura de dados
Listas estáticas
● Clear
void clear(LISTA *lista){
lista->nroElem = 0;
}
typedef struct {
REGISTRO A[MAX];
int nroElem;
} LISTA;
	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
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27