04.ED.ListasLineares-2-2014-1

Prévia do material em texto

DCC013 
 
Estruturas de Dados 
Listas Lineares - 2 
 Em algumas aplicações, torna-se interessante 
dispor de outras informações sobre a lista, 
como, por exemplo: o número de nós (n), o 
endereço do último nó etc. 
 Nestes casos, a estrutura de dados lista poderia 
ser representada da seguinte forma: 
Listas 
2 
Lista com Descritor 
pri ult 
n 
descritor 
 O conjunto de dados gerais sobre a lista é 
chamado de descritor da lista. 
 O descritor pode ser definido como uma 
estrutura de dados específica e, neste caso, 
deve-se criar um TAD Descritor ou 
simplesmente incluir a definição dos novos 
campos (n, ult) no próprio TAD TListaDesc. 
 Por exemplo: 
Listas 
3 
class TListaDesc 
{ private: 
 No *pri; 
 int n; 
 No *ult; 
 No *it; 
 public: 
 ... restante da classe 
}; 
Lista com Descritor 
Listas 
4 
class TListaDesc 
{ 
 private: 
 No *pri; // ponteiro para o primeiro No da lista 
 int n; // número corrente de Nos da lista 
 No *ult; // ponteiro para o último No da lista 
 No *it; // ponteiro auxiliar para percorrer a lista 
 public: 
 ... 
Lista Simplesmente Encadeada com Descritor 
 TAD TListaDesc: 
pri ult 
n 
Listas 
5 
class TListaDesc 
 ... 
 public: 
 TListaDesc(); 
 float Consulta(); 
 void Atribui(float val); 
 bool Busca(float val); 
 void InserePri(float val);//insere novo No contendo 
 //val no inicio da lista 
 void EliminaPri(); // elimina o primeiro No da lista 
 // 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 
 ~TListaDesc(); 
}; 
Lista Simplesmente Encadeada com Descritor 
 TAD TListaDesc: 
Listas 
6 
Lista Simplesmente Encadeada com Descritor 
 No MI do TAD TListaDesc, as operações abaixo 
não sofrem alterações em relação ao MI do TAD 
TListaSEncad: 
 Operação Consulta: 
 Operação Atribui: 
 Operação Busca: 
 Operações Inicio, ProximoNo e FimDaLista 
 Destrutor 
Listas 
7 
Lista Simplesmente Encadeada com Descritor 
 MI do TAD TListaDesc: 
 Construtor: 
TListaDesc::TListaDesc() 
{ 
 pri = NULL; 
 n = 0; 
 ult = NULL; 
 it = NULL; 
} 
it pri n ult 
0 
Listas 
8 
class TListaDesc 
{ 
 private: 
 No *pri; // ponteiro para o primeiro No da lista 
 int n; // número corrente de Nos da lista 
 No *ult; // ponteiro para o último No da lista 
 No *it; // ponteiro para acessar os Nos da lista 
 public: 
 ... outras operações 
 void InserePri(float val);//insere um novo No contendo 
 //val no início da lista 
 void EliminaPri(); // elimina o primeiro No da lista 
 ... outras operações 
}; 
 As operações de inserção e eliminação de nós 
devem verificar a necessidade ou não de alterar 
também as informações do descritor da lista: 
Listas 
9 
Lista Simplesmente Encadeada com Descritor 
 MI do TAD TListaDesc: 
 Operação InserePri: 
void TListaDesc::InserePri(float val) 
{ // insere No contendo val no início da lista 
 No *p = new No(); // cria No apontado por p 
 p->atribInfo(val); // preenche info com val 
 p->atribProx(pri); // prox recebe atual pri 
 //atualiza o descritor 
 pri = p; 
 n++; 
 if(n == 1) 
 ult = p; 
} 
Listas 
10 
Lista Simplesmente Encadeada com Descritor 
 MI do TAD TListaDesc: Operação EliminaPri: 
void TListaDesc::EliminaPri(){ // elimina primeiro No 
 No *p; 
 if(pri != NULL){ 
 if(it == pri) 
 it = pri->consultaProx(); 
 p = pri; // p aponta para o primeiro No 
 pri = p->consultaProx();//pri passa apontar p/ o 
 //atual segundo nó 
 delete p; // exclui o primeiro nó 
 n--; // atualiza o descritor 
 if(n == 0) 
 ult = NULL;} 
 else 
 Rotina_Erro(2); 
} 
Listas 
11 
Lista Simplesmente Encadeada com Descritor 
 Exercícios: 
 1. Desenvolver uma nova operação do TAD 
TListaDesc para incluir um novo nó depois do nó 
especificado pelo ponteiro de acesso it do TAD. 
 2. Desenvolver uma nova operação do TAD 
TListaDesc para excluir o nó à direita do nó 
especificado pelo ponteiro de acesso it do TAD. 
 3. Desenvolver procedimentos similares aos 
anteriores, mas realizando as operações na posição 
à esquerda do nó apontado por it. 
Listas 
12 
Lista Simplesmente Encadeada com Descritor 
 Exercícios : 
 4. Desenvolver procedimentos similares aos 
anteriores, mas realizando as operações no final da 
lista. 
 É uma lista (geralmente com descritor) onde 
cada nó possui dois apontadores, sendo um para 
o nó anterior e outro para o nó seguinte 
Listas 
13 
Lista Duplamente Encadeada 
pri ult 
n 
 Portanto, é necessário redefinir o TAD No: 
Listas 
14 
Lista Duplamente Encadeada 
class No 
{ 
 private: 
 No *ant; // ponteiro para o No anterior 
 float info; // informação real do No 
 No *prox; // ponteiro para o próximo No 
 public: 
 No(); 
 void atribAnt(No *p); 
 void atribInfo(float val); 
 void atribProx(No *p); 
 No *consultaAnt(); 
 float consultaInfo(); 
 No *consultaProx(); 
 ~No(); 
}; 
Listas 
15 
No::No() {} 
 
void No::atribAnt(No *p) { ant = p; } 
 
void No::atribInfo(float val){ info = val; } 
 
void No::atribProx(No *p) { prox = p; } 
 
No *No::consultaAnt() { return ant; } 
 
float No::consultaInfo() { return info; } 
 
No *No::consultaProx() { return prox; } 
 
No::~No() {} 
Lista Duplamente Encadeada 
 MI do TAD No (Implementação  No.cpp): 
Listas 
16 
Lista Duplamente Encadeada 
 TAD TListaDEncad = TAD TListaDesc: 
class TListaDEncad 
{ 
 private: 
 No *pri; // ponteiro para o primeiro No da lista 
 int n; // número corrente de Nos da lista 
 No *ult; // ponteiro para o último No da lista 
 No *it; //ponteiro auxiliar para percorrer a lista 
 public: 
 ... 
Listas 
17 
Lista Duplamente Encadeada 
 TAD TListaDEncad = TAD TListaDesc: 
class TListaDEncad 
 ... 
 public: 
 TListaDEncad(); 
 float Consulta(); 
 void Atribui(float val); 
 bool Busca(float val); 
 void InserePri(float val);//insere um novo No contendo 
 //val no início da lista 
 void EliminaPri(); // elimina o primeiro No da lista 
 // 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 
 ~TListaDEncad(); 
}; 
Listas 
18 
Lista Duplamente Encadeada 
 O que muda é a implementação dos métodos de 
inserção e remoção na lista 
class TListaDEncad 
{ 
 private: 
 No *pri; // ponteiro para o primeiro No da lista 
 int n; // número corrente de Nos da lista 
 No *ult; // ponteiro para o último No da lista 
 No *it; // ponteiro auxiliar para percorrer a lista 
 public: 
 ... outras operações 
 void InserePri(float val);//insere um novo No contendo 
 //val no início da lista 
 void EliminaPri(); // elimina o primeiro No da lista 
 ... outras operações 
}; 
Listas 
19 
Lista Duplamente Encadeada 
 MI do TAD TListaDEncad: 
 Operação InserePri: 
void TListaDEncad::InserePri(float val) 
{ // insereNo contendo val no início da lista 
 No *p = new No(); // cria No apontado por p 
 p->atribInfo(val); // preenche info com val 
 p->atribProx(pri); // prox recebe atual pri 
 p->atribAnt(NULL); 
 //atualiza o descritor 
 if(n == 0) 
 ult = p; 
 else 
 pri->atribAnt(p); 
 pri = p; 
 n++; 
} 
Listas 
20 
Lista Duplamente Encadeada 
 MI do TAD TListaDEncad: Operação EliminaPri: 
void TListaDEncad::EliminaPri(){//elimina primeiro No 
 No *p; 
 if(pri != NULL){ 
 if(it == pri) 
 it = pri->consultaProx(); 
 p = pri; // p aponta para o primeiro 
 pri = p->consultaProx();//pri passa a apontar 
 //para o atual segundo 
 delete p; // exclui o primeiro nó 
 n--; 
 if(n == 0) 
 ult = NULL; 
 else 
 pri->atribAnt(NULL);} 
 else 
 Rotina_Erro(2); 
} 
 MI do TAD TListaDEncad: 
 Exercícios: 
 5. Desenvolver as operações de inclusão e exclusão 
no final da lista e à esquerda e à direita do nó 
apontado por it. 
Listas 
21 
Lista Duplamente Encadeada 
 É uma lista duplamente encadeada com os dois 
nós extremos unidos 
Listas 
22 
Lista Circular 
pri ult 
n 
Que modificações devem ser feitas para 
transformar o TAD TListaDEncad em um TAD 
TListaCirc que represente uma lista circular? 
Resposta: NENHUMA 
Listas 
23 
Lista Circular 
 TAD TListaCirc = TAD TListaDEncad: 
class TListaCirc 
{ 
 private: 
 No *pri; // ponteiro para o primeiro No da lista 
 int n; // número corrente de Nos da lista 
 No *ult; // ponteiro para o último No da lista 
 No *it; //ponteiro auxiliar para percorrer a lista 
 public: 
 ... 
Listas 
24 
Lista Circular 
 TAD TListaCirc = TAD TListaDEncad: 
class TListaCirc 
 ... 
 public: 
 TListaDEncad(); 
 float Consulta(); 
 void Atribui(float val); 
 bool Busca(float val); 
 void InserePri(float val);//insere um novo No contendo 
 //val no início da lista 
 void EliminaPri(); // elimina o primeiro No da lista 
 // 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 
 ~TListaDEncad(); 
}; 
 Exercícios: 
 1) Considerando o TAD de uma lista circular, 
desenvolver operações do seu MI para: 
 a) criar uma lista vazia (construtor); 
Listas 
25 
TListaCirc::TListaCirc() 
{ 
 pri = NULL; 
 n = 0; 
 ult = NULL; 
 it = NULL; 
} 
it pri n ult 
0 
 Exercícios: 
 1) Considerando o TAD de uma lista circular, 
desenvolver operações do seu MI para: 
 a) criar uma lista vazia (construtor); 
 b) incluir o primeiro nó; 
Listas 
26 
Listas 
27 
Lista Circular 
 MI do TAD TListaCirc: 
 Operação InserePri: 
void TListaCirc::InserePri(float val) 
{ // insere No contendo val no início da lista 
 No *p = new No(); // cria No apontado por p 
 p->atribInfo(val); // preenche info com val 
 if(n == 0){ 
 p->atribProx(p); // prox recebe p 
 p->atribAnt(p); // ant recebe p 
 ult = p;} 
 else{ 
 p->atribProx(pri); // prox recebe atual pri 
 p->atribAnt(ult); // ant recebe atual ult 
 pri->atribAnt(p); 
 ult->atribProx(p);} 
 pri = p; 
 n++; 
} 
 Exercícios: 
 1) Considerando o TAD de uma lista circular, 
desenvolver operações do seu MI para: 
 a) criar uma lista vazia (construtor); 
 b) incluir o primeiro nó; 
 c) incluir um nó à direita; 
 d) excluir um nó à esquerda; 
 2) Desenvolver uma operação para MI do TAD 
TListCont que leia diversos valores inteiros e 
positivos e insira os valores no final da lista. O 
último valor a ser lido é um FLAG igual a -1. 
Listas 
28 
 Exercícios: 
 3) Idem ao anterior, montando uma lista 
simplesmente encadeada (sem descritor). 
 4) Considerando as listas das questões 2 e 3, 
montar uma operação para cada TAD para, dado 
um valor inteiro val, excluir da lista todos os nós 
cujo valor seja igual a val. 
 5) Desenvolver operações para ordenar os nós das 
listas das questões 2 e 3 em ordem crescente. 
 6) Idem ao anterior, usando um algoritmo de 
ordenação diferente. 
Listas 
29 
 Exercícios: 
 7) Desenvolver uma operação para o TAD 
TListaSEncad que receba uma lista ordenada como 
parâmetro e faça a fusão desta lista com a lista 
encapsulada no TAD, ou seja, a lista encapsulada 
deve passar a conter todos os nós da outra lista, 
porém mantendo a ordenação. Considere que a lista 
encapsulada inicial também já está ordenada. 
Listas 
30 
 Exercícios: 
 8) Apresente a definição de um TAD No modificado 
que guarda como informação um vetor de 5 
posições inteiras. 
 9) Considerando uma lista duplamente encadeada 
com descritor em que cada nó possui o formato do 
TAD No da questão 8, desenvolver uma operação da 
lista para excluir o nó central caso o número de nós 
da lista seja ímpar. 
Listas 
31 
 Exercícios: 
 10) Ainda considerando as questões 8 e 9, crie uma 
nova operação para, caso o número de nós seja par, 
incluir na lista um novo nó contendo um vetor 
passado como parâmetro contendo 5 valores 
inteiros. 
 11) Dada uma lista circular (duplamente encadeada 
com descritor), desenvolver uma operação para 
excluir o nó apontado pelo ponteiro de acesso it. 
Listas 
32