07.LabII.ListaContigua

Prévia do material em texto

Laboratório de Programação II
Departamento de Ciência da Computação
UFJF
Aula de hoje
•TAD Lista Contígua
•Uma lista é uma estrutura linear, composta de
um conjunto de n ≥ 0 elementos x1, x2, ..., xn,
chamados nós, organizados de forma a manter
a relação entre eles.
•Existem várias maneiras de representar uma
lista, devendo ser escolhida a de melhor
desempenho para a aplicação em questão.
•As representações mais comuns são por:
–Lista contígua
–Lista encadeada
Lista
TAD Lista
•Dados
–Elementos x1, x2, ..., xn (nós)
•Operações
–Cria lista
–Destrói lista
–Acessa nó
–Insere nó (início, fim, meio)
–Elimina nó
–Busca nó
–etc
•A forma mais simples de representar uma lista
de elementos é usando um array com uma
capacidade máxima.
•Representação por contiguidade dos nós:
–Também chamada de alocação sequencial
–Contígua porque os elementos da lista estão
armazenados sequencialmente na memória,um
após o outro.
–Esquematicamente:
Lista Contígua
Lista Contígua
•Exemplo de lista com capacidade para 10 nós
TAD ListaContigua em C++
•As listas podem armazenar elementos de
qualquer tipo de dados, isto é, podem ser do
tipo int, float, double, bool ou até
mesmo algum tipo definido pelo programador.
•Vamos mostrar um exemplo de uma lista para
armazenar elementos do tipo float em C++.
TAD ListaContigua em C++
class TListCont
{
private:
int m; // capacidade máxima de elementos do vetor
int ultimo; // índice do ultimo no da lista
float *x; // vetor que armazena a lista
public:
TListCont(int tam);
float consulta(int k);
void atribui(int k, float val);
void insereK(int k, float val);//insere antes de x
k
void insereUlt(float val); // insere ultimo no
void eliminaK(int k); // elimina no antes de x
k
void eliminaUlt(); // elimina ultimo no
~TListCont();
};
TAD ListaContigua em C++
TListCont::TListCont(int tam)
{
m = tam;
ultimo = -1;
x = new float[m];
}
TListCont::~TListCont()
{
delete [] x;
}
TAD ListaContigua em C++
float TListCont::consulta(int k)
{
if(k >= 0 && k <= ultimo)
return x[k];
else
{
cout << "Indice invalido!" << endl;
exit(1);
}
}
TAD ListaContigua em C++
void TListCont::atribui(int k, float val)
{
if(k >= 0 && k <= ultimo)
x[k] = val;
else
{
cout << "Indice invalido!" << endl;
exit(2);
}
}
TAD ListaContigua em C++
void TListCont::insereK(int k, float val)
{ // insere no contendo val antes do no x
k
if(ultimo == m-1){
cout << "Vetor Cheio!" << endl;
exit(3);}
if(k >= 0 && k <= ultimo){
for(int i = ultimo; i >= k; i--)
x[i+1] = X[i];
x[k] = val;
ultimo = ultimo + 1;
}
else {
cout << "Indice invalido!" << endl;
exit(4);
}
}
TAD ListaContigua em C++
void TListCont::insereUlt(float val);
{// insere no contendo val como ultimo no da lista
if(ultimo == m-1)
{
cout << "Vetor Cheio!" << endl;
exit(3);
}
ultimo = ultimo + 1;
x[ultimo] = val;
}
TAD ListaContigua em C++
void TListCont::eliminaK(int k)
{ // elimina no antes do no x
k
if(k >= 0 && k <= ultimo){
for(int i = k; i <= ultimo-1; i++)
x[i] = x[i+1];
ultimo = ultimo - 1;
}
else
{
cout << "Indice invalido!" << endl;
exit(5);
}
}
TAD ListaContigua em C++
void TListCont::eliminaUlt()
{ // elimina o ultimo no da lista
if(ultimo == -1)
{
cout << "Lista Vazia!" << endl;
exit(6);
}
ultimo = ultimo - 1;
}
Exercícios
1. Implemente operações para:
‒ Imprimir a lista
‒ Buscar um elemento na lista: retornar o índice do
elemento caso ele esteja presente ou -1 caso
contrário
‒ Retornar o número de nós de uma lista
‒ Ordenar a lista
Exercícios
2. Faça um PA que crie 3 listas contíguas L1, L2 e
L3. Inicialize L1 com 50 valores quaisquer até
que a lista esteja cheia. Em seguida, retire a
primeira metade de L1 e guarde em L2. Faça
o mesmo com a segunda metade, mas
guarde em L3. Imprima L2 e L3.
Obs.: Utilize apenas as operações de inserção e
remoção do TAD TListCont.
Exercícios
3. Modifique o TAD TListCont para armazenar
pontos (TAD TPonto2D) ao invés de
elementos inteiros. Faça um PA que imprima
uma tabela de distâncias entre todos os
pontos.