LISTAS
Dilvan Moreira, parcialmente baseado em material
do prof. Ricardo Campello
Lista Linear

Estrutura de representação de informação em que
os elementos são mantidos de forma linear, ou seja,
dispostos um após o outro
 Ex.


listas de nomes, de valores, de pessoas, etc.
Pode ser ordenada ou não
Estruturação de informação em listas ocorre em
vários domínios
 P.
ex. lista telefônica
Lista Linear
Operação Básica em Listas:
 Busca
 por


um elemento através de uma “chave”
Ex. busca na lista telefônica: dado um nome, buscamos o
telefone
Inserção e Remoção de elementos:
 Implementação
 manipulação
depende da organização da lista
distinta de listas ordenadas e não ordenadas
TAD para Lista

Inicializar lista (p. ex. vazia):
 void

Inserir elemento:
 void

Definir(Lista *L);
Inserir(tipo_elem e, Lista *L);
Localizar a posição (na lista) de um elemento dado:
 int
Localizar(tipo_elem e, Lista
*L);
 retorna a posição do elemento na lista retorna um
valor inválido caso ele não esteja na lista
TAD para Lista

Acessar elemento em posição dada:

tipo_elem Buscar(intp, Lista *L);
retorna o elemento da lista na posição fornecida sem alterá-la
 se posição não existir, retorna um valor inválido


Eliminar elemento na posição dada:

int Remover(intp, Lista *L);
Retorna 1 (true) se bem sucedida
 Retorna 0 (false) se posição dada é inválida


Obter número de elementos na lista:

int Tamanho(Lista *L);
TAD para Lista

Apagar a lista:
 void

Apagar(Lista *L);
Destruir a lista:
 void
Destruir(Lista *L);
 lista
não é mais acessível (só para implementações
dinâmicas)

Obter posição seguinte à do último elemento:
 int


Fim(Lista *L);
Verificar se lista está vazia, verificar se está cheia...
...
EDs Estáticas para Listas

Realizações Estáticas (vetores):
 Seqüencial:
 seqüência
de elementos disponíveis de forma consecutiva
 Encadeada:
 seqüência
de elementos disponíveis de forma não
consecutiva
EDs Dinâmicas para Listas

Realizações Dinâmicas (ponteiros e memória):
 Simplesmente
Encadeada:
 Encadeamento
 Duplamente
Encadeada:
 Encadeamento

de ponteiros unidirecional
de ponteiros bidirecional
Cada realização possui vantagens e desvantagens
Lista Estática Sequencial

Implementação a Seguir:
 Exemplo
de Lista Estática Seqüencial em C
 Projetada para Lista Não Ordenada
 Adaptação
para lista ordenada como exercício no final
Lista Estática Sequencial
#define
#define
#define
#define
MAX 100
TRUE 1
FALSE 0
bool int
/* Max. Tamanho da Lista */
typedef struct{
Tipo_1 chave;
Tipo_2 info;
} elem;
/* P. ex. int chave;
*/
/* P. ex. char info[50] */
/* Tipo do Elemento */
typedef struct{
int nelem;
elem A[MAX+1];
} Lista;
/* Tipo da Lista */
Lista L;
/* Exemplo de Declaração*/
Lista Estática Sequencial
void Definir(Lista *L){ /*
O(1)
*/
/* Define uma lista vazia */
L->nelem= 0;
L->A[0].chave = 0;
/* Célula não utilizada */
L->A[0].info[0] = '\0'; /* Célula não utilizada */
}
int Tamanho(Lista *L){
/*
O(1)
*/
/* Retorna o tamanho da Lista (0 caso vazia) */
return L->nelem;
}
Lista Estática Sequencial
int Fim(Lista *L){
/* O(1) */
/* Retorna a posição após o último elemento da
lista */
return (L->nelem + 1);
}
bool Lista_vazia(Lista *L){
/* O(1) */
/* Retorna true se lista vazia, false caso
contrário */
return (L->nelem == 0);
}
bool Lista_cheia(Lista *L){
/* O(1) */
/* Retorna true se lista cheia, false caso
contrário */
return (L->nelem == MAX);
}
Lista Estática Sequencial
bool Inserir(elem* x, int p, Lista *L){
/* Insere elemento x na posição p da Lista L. Se a lista é tal
que L=a1,a2,...,ap,...,an então L=a1,a2,...,ap-1,x,ap+1,...,an.
Se p=Fim(L) então L=a1,a2,...,an,x. Devolve true se sucesso,
false c.c. (L cheia ou não tem posição p). L não ordenada! */
int atual;
if (Lista_cheia(L))
return FALSE; /* lista cheia */
else if (p > Fim(L) || p < 1)
return FALSE; /* posição não existe */
else {
for(atual = L->nelem; atual >= p; atual--)
L->A[atual+1] = L->A[atual];
L->A[p]= *x;
L->nelem++;
return TRUE; /* inserção com sucesso */
}
} /* O(L.nelem) no pior caso. Qual o pior caso? */
Lista Estática Sequencial
int Localizar(elem* x, Lista *L){
/* Retorna a posição de x na Lista. Se x ocorre mais de
uma vez, retorna posição da 1a ocorrência. Se x não
ocorre, retorna 0 */
int atual = 1;
if (!Lista_vazia(L)){
while(atual <= L->nelem){
if(igual(&A[atual], x)) /* iguais ?*/
return atual; /* retorno
sucesso */
else atual++;
}
}
return 0; /* retorno em insucesso ou lista vazia */
}
/* O(L.nelem) no pior caso. Qual o pior caso? */
Lista Estática Sequencial
bool igual(elem* a, elem* b) {
/* Testa igualdade entre elementos por algum critério
particular */
}
return (a->chave==b->chave);
/* O(1) */
elem* Buscar(int p, Lista *L){
/* Retorna elem. da posição p, ou elem. inválido se p é
inválida */
}
if (p >= Fim(L) || p < 1 || Lista_vazia(L))
return x;
/* retorna elemento inválido */
else return &(L->A[p]);
/* O(1) */
Lista Estática Sequencial
bool Remover(int p, Lista *L){
/* Remove o elemento da posição p da Lista. Se L =
a1,a2,...,an então tem-se a1,a2,...,ap-1,ap+1,...,an.
Devolve true se sucesso, false c.c. (L não tem posição p,
inclusive se p = Fim(L)) */
FALSE;
int atual;
if(p >= Fim(L) || p < 1 || Lista_vazia(L)) return
else {
atual++)
for (atual = p+1; atual <= L->nelem;
L->A[atual-1] = L->A[atual];
L->nelem--;
} return TRUE;
} /* O(L.nelem) no pior caso. Qual o pior caso? */
Lista Estática Sequencial em C++


Como ficaria essa implementação em C++?
Seria muito diferente?
Lista Estática Sequencial Orig.
#define
#define
#define
#define
MAX 100
TRUE 1
FALSE 0
bool int
typedef struct{
char info[50];
} elem;
/* Max. Tamanho da Lista */
/* P. ex. char info[50] */
/* Tipo do Elemento */
typedef struct{
int nelem;
tipo_elem A[MAX+1];
} Lista;
/* Tipo da Lista */
Lista L;
/* Exemplo de Declaração*/
Lista Estática Sequencial em C++
#define
#define
#define
#define
MAX 100
TRUE 1
FALSE 0
bool int
/* Max. Tamanho da Lista */
class Elem {
char info[50];
/* P. ex. char info[50] */
…
}
/* Tipo do Elemento */
class List {
int nelem;
tipo_elem A[MAX+1];
…
}
/* Tipo da Lista */
Lista Estática Sequencial Orig.
void Definir(Lista *L){ /*
O(1)
*/
/* Define uma lista vazia */
L->nelem= 0;
L->A[0].info[0] = '\0'; /* Célula não utilizada */
}
int Tamanho(Lista *L){
/*
O(1)
*/
/* Retorna o tamanho da Lista (0 caso vazia) */
return L->nelem;
}
Lista Estática Sequencial em C++
void Lista::Lista(){ /*
O(1)
*/
/* Define uma lista vazia */
nelem= 0;
A[0].info[0] = '\0'; /* Célula não utilizada */
}
int Lista::Tamanho(){
/*
O(1)
*/
/* Retorna o tamanho da Lista (0 caso vazia) */
return nelem;
}
Lista Estática Sequencial Orig.
int Fim(Lista *L){
/* O(1) */
/* Retorna a posição após o último elemento da
lista */
return (L->nelem + 1);
}
bool Lista_vazia(Lista *L){
/* O(1) */
/* Retorna true se lista vazia, false caso
contrário */
return (L->nelem == 0);
}
bool Lista_cheia(Lista *L){
/* O(1) */
/* Retorna true se lista cheia, false caso
contrário */
return (L->nelem == MAX);
}
Lista Estática Sequencial C++
int List::Fim(){
/* O(1) */
/* Retorna a posição após o último elemento da
lista */
return (nelem + 1);
}
bool List::Lista_vazia(){
/* O(1) */
/* Retorna true se lista vazia, false caso
contrário */
return (nelem == 0);
}
bool List::Lista_cheia(){
/* O(1) */
/* Retorna true se lista cheia, false caso
contrário */
return (nelem == MAX);
}
Lista Estática Sequencial Orig.
bool Inserir(elem* x, int p, Lista *L){
/* Insere elemento x na posição p da Lista L. Se a lista é tal
que L=a1,a2,...,ap,...,an então L=a1,a2,...,ap-1,x,ap+1,...,an.
Se p=Fim(L) então L=a1,a2,...,an,x. Devolve true se sucesso,
false c.c. (L cheia ou não tem posição p). L não ordenada! */
int atual;
if (Lista_cheia(L))
return FALSE; /* lista cheia */
else if (p > Fim(L) || p < 1)
return FALSE; /* posição não existe */
else {
for(atual = L->nelem; atual >= p; atual--)
L->A[atual+1] = L->A[atual];
L->A[p] = *x;
L->nelem++;
return TRUE; /* inserção com sucesso */
}
} /* O(L.nelem) no pior caso. Qual o pior caso? */
Lista Estática Sequencial C++
bool List::Inserir(Elem* x, int p){
/* Insere elemento x na posição p da Lista L. Se a lista é tal
que L=a1,a2,...,ap,...,an então L=a1,a2,...,ap-1,x,ap+1,...,an.
Se p=Fim(L) então L=a1,a2,...,an,x. Devolve true se sucesso,
false c.c. (L cheia ou não tem posição p). L não ordenada! */
int atual;
if (Lista_cheia())
return FALSE; /* lista cheia */
else if (p > Fim() || p < 1)
return FALSE; /* posição não existe */
else {
for(atual = nelem; atual >= p; atual--)
A[atual+1] = A[atual];
A[p] = *x;
nelem++;
return TRUE; /* inserção com sucesso */
}
} /* O(L.nelem) no pior caso. Qual o pior caso? */
Lista Estática Sequencial Orig
int Localizar(elem* x, Lista *L){
/* Retorna a posição de x na Lista. Se x ocorre mais de uma vez,
retorna posição da 1a ocorrência. Se x não ocorre, retorna 0 */
int atual = 1;
if (!Lista_vazia(L)){
while(atual <= L->nelem){
if(igual(&L->A[atual], x))
return atual; /* retorno em sucesso
*/
else atual++;
}
}
return 0; /* retorno em insucesso ou lista vazia */
}
/* O(L.nelem) no pior caso. Qual o pior caso? */
Lista Estática Sequencial C++
int List::Localizar(Elem* x){
/* Retorna a posição de x na Lista. Se x ocorre mais de uma vez,
retorna posição da 1a ocorrência. Se x não ocorre, retorna 0 */
int atual = 1;
if (!Lista_vazia()){
while(atual <= nelem){
if(A[atual].Igual(x))
return atual; /* retorno em sucesso
*/
else atual++;
}
}
return 0; /* retorno em insucesso ou lista vazia */
}
/* O(L.nelem) no pior caso. Qual o pior caso? */
Lista Estática Sequencial Orig
bool igual(elem* a, elem* b) {
/* Testa igualdade entre elementos por algum critério
particular */
}
return (strcmp(a->chave,b->chave)==0);
/* O(1) */
elem* Buscar(int p, Lista *L){
/* Retorna elem. da posição p, ou elem. inválido se p é
inválida */
}
if (p >= Fim(L) || p < 1 || Lista_vazia(L))
return x;
/* retorna elemento inválido */
else return L->A[p];
/* O(1) */
Lista Estática Sequencial C++
bool Elem::igual(elem* b) {
/* Testa igualdade entre elementos por algum critério
particular */
}
return (strcmp(info,b->info)==0);
/* O(1) */
Elem* List::Buscar(int p){
/* Retorna elem. da posição p, ou elem. inválido se p é
inválida */
}
if (p >= Fim() || p < 1 || Lista_vazia())
return null;
/* retorna inválido */
else return &A[p];
/* O(1) */
Lista Estática Sequencial Orig
bool Remover(int p, Lista *L){
/* Remove o elemento da posição p da Lista. Se L =
a1,a2,...,an então tem-se a1,a2,...,ap-1,ap+1,...,an.
Devolve true se sucesso, false c.c. (L não tem posição p,
inclusive se p = Fim(L)) */
FALSE;
int atual;
if(p >= Fim(L) || p < 1 || Lista_vazia(L)) return
else {
atual++)
for (atual = p+1; atual <= L->nelem;
L->A[atual-1] = L->A[atual];
L->nelem--;
} return TRUE;
} /* O(L.nelem) no pior caso. Qual o pior caso? */
Lista Estática Sequencial C++
bool List::Remover(int p){
/* Remove o elemento da posição p da Lista. Se L =
a1,a2,...,an então tem-se a1,a2,...,ap-1,ap+1,...,an.
Devolve true se sucesso, false c.c. (L não tem posição p,
inclusive se p = Fim(L)) */
FALSE;
int atual;
if(p >= Fim() || p < 1 || Lista_vazia()) return
else {
for (atual = p+1; atual <= nelem; atual++)
A[atual-1] = A[atual];
nelem--;
} return TRUE;
} /* O(L.nelem) no pior caso. Qual o pior caso? */
.
Checando
1.
2.
3.
4.
Modifique a operação Remover do TAD Lista Estática Seqüencial
para que esta retorne o elemento removido e não um valor lógico.
Modifique a operação Localizar do TAD Lista Estática Seqüencial
para que esta receba apenas a chave do elemento procurado e
não o elemento todo.
Modifique a operação Localizar do TAD Lista Estática Seqüencial
para que esta retorne um ponteiro para uma cópia do elemento
localizado, cópia esta alocada dinamicamente em memória.
Retorne NULL se o elemento não existir na lista.
Implemente o TAD Lista Estática Seqüencial em C, de forma
modular, com módulos separados de interface (arquivo .h) e
implementação (arquivo .c), e faça alguns testes.aula
Checando
Modifique a oImplemente uma nova operação de
inserção para o TAD Lista Estática Seqüencial para
substituir aquela que foi apresentada anteriormente
nesses slides (Inserir). Essa nova operação deve inserir
o novo elemento de forma a manter sempre a lista
ordenadapelas chaves dos seus elementos.
5.
5.
OBS: Como a lista deve ser mantida ordenada, essa
operação deve determinar a posição de inserção
automaticamente, não recebê-la como parâmetro. Nesse
exercício, faça isso percorrendo um a um os elementos da
lista a partir do início (depois vide exercício 7).
Checando
Considerando que a operação de inserção utilizada
no TAD Lista Estática Seqüencial é aquela
implementada no exercício 5, reimplemente também a
operação Localizar do TAD para que esta faça uso
do fato da lista estar ordenada para realizar uma
busca muito mais eficiente (binária) pelo elemento
desejado.
6.
6.
7.
Qual o tempo de execução assintótico (BIG-O) de pior
caso da operação acima ? Qual o pior caso? Justifique.
Estando a nova operação de localização via busca
binária do exercício 6 disponível, é possível utilizá-la
para simplificar a implementação da operação de
inserção ordenada do exercício 5? Explique.
Bibliografia



N. Ziviani, Projeto de Algoritmos, Thomson, 2a.
Edição, 2004
A. M. Tenembaum et al., Data Structures Using C,
Prentice-Hall, 1990
J. L. Szwarcfiter & L. Markenzon, Estruturas de
Dados e seus Algoritmos, LTC, 1994
Perguntas?