Estrutura de Dados e Algoritmos
e
Programação e Computadores II
Aula 4: Listas Estáticas e Dinâmicas
Listas
„
„
„
Estáticas: com Vetores
Dinâmicas: Listas Ligadas (com
ponteiros)
Variáveis e Métodos de Controle:
Classes
1
Listas
„
„
Uma lista é uma estrutura que armazena
elementos de forma alinhada, ou seja, com
elementos dispostos um após o outro.
Exemplos
„
„
„
„
Lista Telefônica
Lista de clientes de uma agência bancária
Lista de setores de disco a serem acessados
por um sistema operacional
Lista de pacotes a serem transmitidos em um
nó de uma rede de comutação de pacotes.
Listas
„
Operações Realizadas com Listas
„
„
„
„
„
„
„
„
„
Criar uma lista vazia
Verificar se uma lista está vazia
Obter o tamanho da uma lista
Obter/modificar o valor do elemento de uma determinada
posição na lista
Obter a posição de elemento cujo valor é dado
Inserir um novo elemento após (ou antes) de uma
determinada posição na lista
Remover um elemento de uma determinada posição na lista
Exibir os elementos de uma lista
Concatenar duas listas
2
Listas
„
Formas de Representação
„
Estática (com vetores)
„
„
pode ser representado por um vetor na
memória principal ou um arquivo seqüencial
em disco
Atenção: aqui trabalharemos apenas com
vetores
Listas
„
Dinâmicas (com ponteiros)
„
esta estrutura é tida como uma seqüência de
elementos encadeados por ponteiros, ou seja,
cada elemento deve conter, além do dado
propriamente dito, uma referência para o
próximo elemento da lista.
3
Listas com Classes
„
„
„
„
„
Listas necessitam de variáveis de controle
para armazenar suas informações.
Inicialmente, tamanho da lista e elementos
da lista. (Futuramente existirão outras.)
Listas também necessitam de métodos de
controle, como os citados anteriormente.
Variáveis + Métodos = Classes
Principalmente devido aos rótulos de
permissão das classes, que protege variáveis
e métodos de uso interno da classe.
Listas com Classes
class Lista {
int n;
// Número de elementos da lista.
tipo dados;
// Elementos (vetor ou ponteiro).
public:
Lista();
// Criar a lista (vazia).
bool Empty(); // Verificar se está vazia.
int Length(); // Obter o tamanho da lista.
void SetValues (int pos, tipo elem);
~Lista();
// Remover a lista.
};
4
Listas Estáticas
„
Características
„
„
„
„
os elementos na lista estão armazenados
fisicamente em posições consecutivas;
a inserção de um elemento na posição a(i) causa
o deslocamento a direita do elemento de a(i) ao
último;
a eliminação do elemento a(i) requer o
deslocamento à esquerda do a(i+1) ao último;
o vetor alocado possui um tamanho.
Listas Estáticas
class Lista {
int n;
// Número de elementos da lista.
tipo dados[]; // Vetor de elementos.
public:
Lista();
// Criar a lista (vazia).
bool Empty(); // Verificar se está vazia.
int Length(); // Obter o tamanho da lista.
void SetValues (int pos, tipo elem);
~Lista();
// Remover a lista.
};
5
Listas Estáticas
„
Operações simples utilizando lista
seqüencial
1. Criar a lista
void Lista (int tamanho) {
n = 0;
max = tamanho; // não definida antes.
dados = new tipo[tamanho];
}
2. Verificar se a lista está vazia
bool Empty () {
return (n == 0);
}
Listas Estáticas
3.
Verificar se uma lista está cheia
bool Full () {
return (n == MAX);
}
4.
Obter o tamanho de uma lista
int Length () {
return (n);
}
5.
Obter o i-ésimo elemento de uma lista
int elemento (int pos, tipo *elem) {
if ((pos > n) || (pos <= 0))
return (0);
*elem = dados[pos-1];
return (1);
}
6
Listas Estáticas
„
Pronto, a parte dos professores já foi feita,
agora é a vez dos alunos:
6. Pesquisar um dado elemento, retornando a sua
posição
int posicao (tipo elem) {
7. Inserção de um elemento em uma determinada
posição
int inserir (int pos, tipo elem){
8. Remoção do elemento de uma determinada
posição
int remover (int pos, tipo elem){
Listas Estáticas
6. Pesquisar um dado elemento, retornando
a sua posição
int posicao (tipo elem) {
for (int i = 0; i < n; i++)
if (dados[i] == elem)
return (i+1);
return (0);
}
7
Listas Estáticas
7. Inserção de um elemento em uma determinada
posição
int inserir (int pos, tipo elem){
int i;
if ((n == MAX)) || (pos > n + 1) )
return (0);
for (i = n; i >= pos; i--)
dados[i] = dados[i-1];
dados[pos-1] = elem;
n++;
return (1);
}
Atenção: esta não é a melhor solução pois não foi
considerada a alocação de um vetor maior
quando o existente já estiver cheio.
Listas Estáticas
8. Remoção do elemento de uma determinada
posição
int remover (int pos, tipo *elem){
int i;
if ((pos > n) || (pos <= 0))
return (0);
*elem = dados[pos-1];
for (i = pos; i <= n-1; i++)
dados[i-1] = dados[i];
n--;
return (1);
}
8
Listas Dinâmicas
„
Características:
1. deve exestir um ponteiro que aponte para o
primeiro elemento da lista (início da lista);
2. cada elemento, ou nó, da lista aponta para o
próximo sucessivamente (daí o nome listas
ligadas)
3. o último elemento deve apontar para NULL (ou
NIL), indicando o final da lista.
Listas Dinâmicas
„
Representação Gráfica:
„
„
Ponteiro
para o
primeiro
dados
Lista Vazia
Lista com 1 elemento
dados
„
Lista com 2 elementos
NULL
Elemento
da Lista
Ponteiro
para o
próximo
dados
„
Lista com N elementos
dados
9
Listas Dinâmicas
class Lista {
int n;
// Número de elementos da lista.
struct No {
tipo elem; // Elemento armazenado.
struct No *prox; // Ponteiro para o próximo.
} tipoNo;
tipoNo *dados;
// Ponteiro para o primeiro.
public:
Lista();
// Criar a lista (vazia).
bool Empty(); // Verificar se está vazia.
int Length(); // Obter o tamanho da lista.
void SetValues (int pos, tipo elem);
~Lista();
// Remover a lista.
};
Listas Dinâmicas
„
Operações simples
1. Criar a lista
void Lista (int tamanho) {
n = 0;
dados = NULL;
}
2. Verificar se a lista está vazia
bool Empty () {
return (n == 0);
}
3. Verificar se uma lista está cheia: não é
pertinente
10
Listas Dinâmicas
4.
Obter o tamanho de uma lista
int Length () {
return (n);
}
5.
Obter o i-ésimo elemento de uma lista
int elemento (int pos, tipo *elem) {
if ((pos > n) || (pos <= 0))
return (0);
tipoNo *p = dados;
for (int i = 1; i < pos; i++)
p = p->prox;
*elem = p->elem;
return (1);
}
Listas Dinâmicas
6. Pesquisar um dado elemento, retornando a sua
posição
int posicao (tipo elem) {
int i = 0;
tipoNo *p = dados;
while (p != NULL) {
i++;
if (p->elem = elem)
return i;
p = p->prox;
}
return (0);
}
11
Listas Dinâmicas
7. Inserção de um elemento no início
int inserir_inicio (tipo elem){
tipoNo *p;
p = new tipoNo;
p->elem = elem;
p->prox = dados;
dados x
dados = p;
n++;
return (1);
p
}
Listas Dinâmicas
8. Remoção do último elemento
int remover_ultimo (tipo *elem){
if (n == 0) // Lista vazia.
return 0;
int i = 1;
tipoNo *p = dados, *q;
if (n == 1) // Lista com 1 Elemento.
dados = NULL;
// continua o else no próximo slide
12
Listas Dinâmicas
else {
// Lista com N Elementos.
while (p->prox != NULL) {
q = p;
p = p->prox;
i++;
}
q->prox = NULL;
}
*elem = p->elem;
delete p;
n--;
return (i);
}
Listas Dinâmicas
„
Outras funções para serem feitas:
9.
10.
11.
12.
13.
14.
Inserção de um elemento no final;
Remoção do primeiro elemento;
Inserção de elemento em determinada posição;
Remoção de elemento em determinada posição;
Liberar a lista (destrutor);
e inúmeras outras.
13