08.LabII.ListaEncadeada

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 Simplesmente Encadeada
 Operações comuns:
 consultar o nó xk;
 atribuir um novo valor ao nó xk;
 inserir um novo nó antes ou depois do nó xk ou em
um dos extremos da lista;
 eliminar o nó xk;
 Obs.: lista é uma estrutura de dados dinâmica,
isto é, o seu comprimento (= número de seus
nós) pode ser alterado em tempo de execução.
Listas
3
 Outras operações:
 concatenar duas listas;
 determinar o comprimento (n) de uma lista;
 localizar o nó que contém um determinado dado;
 partir uma lista em duas ou mais;
 fazer uma cópia de uma lista;
 ordenar os nós de uma lista,
 etc.
Listas
4
Representações de Listas
 Existem várias maneiras de representar uma
lista, devendo ser escolhida a mais adequada
para a aplicação em questão (melhor
desempenho, melhor compatibilidade com o
tipo de memória usada etc.).
 As representações mais comuns são por:
 contiguidade dos nós
 encadeamento dos nós.
Listas
5
Listas Encadeadas
Listas
6
 Serão apresentados os seguintes casos de listas
encadeadas:
 Lista Simplesmente Encadeada
 Lista com Descritor
 Lista Duplamente Encadeada
 Lista Circular
Lista Simplesmente Encadeada
Listas
7
 
Xn-1X2X1 Xn
 Nesta estrutura de dados, um nó deve conter
além de seu valor, uma indicação (ponteiro ou
apontador) para o nó seguinte, representando
uma contiguidade lógica. Esquematicamente:
 Assim, um nó passa a ter a seguinte representação:
informação próximo
X
Listas
8
class No
{
private:
float info; // informação real do No
No* prox; // ponteiro para o próximo No
public:
No() {};
float consultaInfo() { return info; };
No* consultaProx() { return prox; };
void atribInfo(float val) { info = val; };
void atribProx(No *p) { prox = p; };
~No() {};
};
Lista Simplesmente Encadeada
 TAD No (Definição No.h):
Listas
9
class ListaSEncad {
private:
No* pri; // ponteiro para o primeiro No da lista
No* it; // ponteiro auxiliar para percorrer a lista
public:
ListaSEncad();
float Consulta();
void Atribui(float val);
bool Busca(float val);
// operações para percorrer a lista
void Inicio(); // coloca o ponteiro it no início
void ProximoNo(); // avança o ponteiro it
bool FimDaLista(); // verifica se it está no final
void InserePri(float val); // insere no início da lista
void EliminaPri(); // elimina primeiro No
~ListaSEncad();
};
Lista Simplesmente Encadeada
 TAD ListaSEncad:
Listas
10
Lista Simplesmente Encadeada
 MI do TAD ListaSEncad:
 Construtor:
ListaSEncad::ListaSEncad()
{
pri = NULL;
it = NULL;
}
pri
Cria lista vazia
Listas
11
Lista Simplesmente Encadeada
 MI do TAD ListaSEncad:
 Operação Consulta:
float ListaSEncad::Consulta()
{
if(it != NULL)
return it->consultaInfo();
else
{
cout << "Erro: nó inválido!“ << endl;
exit(1);
}
}
Listas
12
Lista Simplesmente Encadeada
 MI do TAD ListaSEncad:
 Operação Atribui:
void ListaSEncad::Atribui(float val)
{
if(it != NULL)
it->atribInfo(val);
else
cout << "Erro: nó inválido!“ << endl;
} pri it
x
Antes
pri it
val
Depois
Listas
13
Lista Simplesmente Encadeada
 MI do TAD ListaSEncad:
 Operação Busca:
bool ListaSEncad::Busca(float val)
{
No* p;
for(p = pri; p != NULL; p = p->consultaProx())
{
if(p->consultaInfo() == val)
return true;
}
return false;
}
pri p
val
Listas
14
Lista Simplesmente Encadeada
 MI do TAD ListaSEncad:
 Operações para percorrer a lista:
void ListaSEncad::Inicio()
{
it = pri;
}
void ListaSEncad::ProximoNo()
{
it = it->consultaProx();
}
bool ListaSEncad::FimDaLista()
{
return (it == NULL);
}
Listas
15
Lista Simplesmente Encadeada
 MI do TAD ListaSEncad:
Destrutor:
ListaSEncad::~ListaSEncad()
{
No* p = pri;
while(p != NULL)
{
No* t = p->consultaProx();
delete p;
p = t;
}
}
Listas
16
Lista Simplesmente Encadeada
 MI do TAD ListaSEncad:
 Operação InserePri:
void ListaSEncad::InserePri(float val)
{ // insere No contendo val no início da lista
No* p = new No(); // cria nó apontado por p
p->atribInfo(val); // preenche info com val
p->atribProx(pri); // prox recebe atual pri
pri = p; // nó apontado por p passa a ser o 1º
}
Listas
17
Lista Simplesmente Encadeada
 MI do TAD ListaSEncad:
 Operação EliminaPri:
void ListaSEncad::EliminaPri()
{ // elimina primeiro No
No* p;
if(pri != NULL){ // se lista não está vazia
p = pri; //p aponta para o nó a ser excluído
// pri passa a apontar para o atual segundo
pri = p->consultaProx();
delete p;} // exclui o 1º nó
}
Listas
18
Lista Simplesmente Encadeada
 Exercícios
1.Desenvolver uma nova operação do MI do TAD
ListaSEncad para remover o nó na lista apontado
pela variável privada it. Após a remoção it aponta
para o nó seguinte, senão será NULL.
Listas
19
Lista Simplesmente Encadeada
 Exercícios
void ListaSEncad::EliminaIt() {
No *p;
if(it != NULL) {
if(it == pri) {
pri = pri->consultaProx();
delete it;
it = pri;
} else {
p = pri;
while(p->consultaProx() != it)
p=p->consultaProx();
p->atribProx(it->consultaProx());
delete it;
it = p->consultaProx();
}
}
}
Listas
20
Lista Simplesmente Encadeada
 Exercícios
2.Desenvolver funções/procedimentos no PA para o TAD
ListaSEncad de float que:
a. imprima os valores de uma lista a partir do primeiro
nó;
b.conte e retorne o número de nós de uma lista;
c. calcule e retorne a média dos valores armazenados
numa lista;
d.concatena duas listas em uma única (retornar a lista
resultante);
e. Partir uma lista em duas a partir de um nó cujo valor
X é dado.
Listas
21
Lista Simplesmente Encadeada
 Exercícios
3. Criar um TAD Lista Encadeada de forma que todos os
nós da lista fiquem sempre em ordem crescente. Dica:
desenvolver uma única operação de inserção na lista
de tal forma que o valor do novo nó mantenha a lista
em ordem crescente. Obs: deve-se remover a
operação Atribui(float val), já que esta
operação pode deixar a lista desordenada.