Exercícios

Sugestão:  E se cada posição da lista "soubesse" onde está a próxima posição e também a posição anterior?  Nesse caso os itens não tinham de ficar guardados na matriz pela mesma ordem que têm na lista!

Crie um novo módulo lista_double_eficiente e coloque nesse módulo a classe ListaDouble e iterador associado mas fazendo as seguintes alterações:

1.a)  Altere a representação interna da lista de itens dentro da classe ListaDouble de modo a tornar a inserção e remoção de itens mais eficiente.  Sugere-se que a matriz passe a guardar não directamente itens, mas uma estrutura privada da classe que guarda não só o item mas também a posição do próximo item na lista e a posição do item anterior.

1.b)  Altere o método void ListaDouble::insere(Iterador& i, const Item& item) de modo a tirar partido da nova organização dos dados.

1.c)  Altere o método void ListaDouble::remove(Iterador& i) de modo a tirar partido da nova organização dos dados.

1.d)  Altere os restantes métodos da classe ListaDouble de modo a que se adaptem à nova organização dos dados.

1.e)  Altere a classe ListaDouble::Iterador de modo a tirar partido da nova organização dos dados.

1.f)  Teste a nova lista com o mesmo programa que usou na Aula 2!  Obviamente que é necessário modificar a directiva de inclusão do ficheiro de interface do módulo de listas utilizado e fundir o ficheiro objecto do programa com o ficheiro objecto do novo módulo, criando um novo executável.

R:

Apresenta-se a solução completa.  Note-se que o programa de teste foi aumentado para testar um maior número de operações.

lista_double_eficiente.H

#ifndef LISTA_DOUBLE_EFICIENTE_H
#define LISTA_DOUBLE_EFICIENTE_H

#include <cassert>
#include <iostream>

// Uma classe para representar listas de itens do tipo Item (actualmente double):
class ListaDouble {
public:
    // Cria-se um sinónimo para simplificar a tarefa de criar listas com itens de outros tipos:
    typedef double Item;

    // Declaração de uma classe embutida que serve para percorrer e manipular listas.
    class Iterador;

    // A classe de iteração tem acesso irrestrito às listas:
    friend Iterador;

    // Construtor da classe, cria uma lista vazia:
    ListaDouble();

    // Acrescenta item no início da lista:
    void poeInicio(const Item& item);
    // Acrescenta item no fim da lista:
    void poeFim(const Item& item);
    // Insere item imediatamente antes da posição indicada pelo iterador iterador, fazendo
    // com que o iterador continue a referenciar o mesmo item que antes da inserção:
    void insere(Iterador& iterador, const Item& item);

    // Retira o primeiro item da lista:
    void tiraPrimeiro();
    // Retira o último item da lista:
    void tiraUltimo();
    // Remove o item referenciado pelo iterador iterador, ficando o iterador a
    // referenciar o item logo após o item removido:
    void remove(Iterador& iterador);

    // Devolve o primeiro item:
    Item primeiroItem() const;
    Item& primeiroItem();
    // Devolve o último item:
    Item ultimoItem() const;
    Item& ultimoItem();

    // Devolve o comprimento da lista:
    int comprimento() const;
    // Indica se a lista está vazia:
    bool vazia() const;
    // Indica se a lista está cheia:
    bool cheia() const;

    // Devolve um iterador referenciando o primeiro item da lista:
    Iterador primeiro();
    // Devolve um iterador referenciando o último item da lista:
    Iterador ultimo();
    // Devolve um iterador referenciando o item fictício depois do último item da lista:
    Iterador fim();
    // Devolve um iterador referenciando o item fictício antes do primeiro item da lista:
    Iterador inicio();

private:
    // O número máximo de itens na lista:
    static const int limite = 100;

    /*
     A lista é representada por uma cadeia duplemente ligada de elos guardados numa matriz de
     elos.  A matriz de elos contém elos que estão na cadeia duplamente ligada e que portanto
     contêm itens da lista e outros elos que estão livres, e portanto fazem parte de uma cadeia
     simplesmente ligada.  A cadeia duplamente ligada tem guardas (correspondentes aos
     itens fictícios) mas a cadeia simplesmente ligada não tem guardas:
    */
    struct Elo {
        Item item;
        int anterior; // índice na matriz de elos do elo anterior da cadeia.
        int seguinte; // índice na matriz de elos do elo seguinte da cadeia.
    };

    // Matriz que guarda os elos das cadeias (incluindo as duas guardas da cadeia duplamente
    // ligada de itens):
    Elo elos[limite + 2];

    // Contador do número de itens na lista:
    int quantos;

    // Índices das guardas da cadeia duplamente ligada de itens:
    static const int inicial = limite;
    static const int final = limite + 1;

    // Índice do primeiro elo livre da matriz de elos (se não existir nenhum elo livre contém
    // lixo.  É onde começa a cadeia simplesmente ligada dos elos livres:
    int primeiro_livre;

    // Procedimentos auxiliares para inserir e remover um item da cadeia duplamente ligada
    // dos itens:
    void poe(int anterior, int seguinte, const Item& item);
    void tira(int i);

    // Função que retira o primeiro elo da cadeia dos elos livres e devolve o seu índice na matriz.
    // É usada pelo procedimento poe() acima para obter um elo livre onde colocar o novo item
    // da lista:
    int reserva();

    // Procedimento que coloca o elo cujo índice é passado como argumento na cadeia dos elos
    // livres.  É usado pelo procedimento tira() acima quando tira um item da lista (ou
    // melhor, um elo da cadeia duplamente ligada):
    void liberta(int i);
};

// Uma classe para representar iteradores para itens de listas ListaDouble:
class ListaDouble::Iterador {
public:
    // Construtor da classe.  Associa o iterador com a lista lista e põe-no a referenciar o seu
    // primeiro item:
    explicit Iterador(ListaDouble& lista);

    // Incrementação prefixa de iteradores (avança para o próximo item):
    Iterador& operator ++ ();
    // Decrementação prefixa de iteradores (recua para o item anterior):
    Iterador& operator -- ();

    // Incrementação sufixa de iteradores (avança para o próximo item):
    Iterador operator ++ (int);
    // Decrementação sufixa de iteradores (recua para o item anterior):
    Iterador operator -- (int);

    // Devolve o item referenciado pelo iterador:
    Item& item() const;

    // Operadores de igualdade e diferença entre iteradores:
    bool operator == (const Iterador& i) const;
    bool operator != (const Iterador& i) const;

    // A classe ListaDouble tem acesso irrestrito a todos os membros da classe Iterador:
    friend ListaDouble;

private:
    // Referência para a lista a que o iterador está associado:
    ListaDouble& lista;
    // Índice do elo na matriz de elos contendo o item referenciado:
    int indice;
};

// Definição das funções e procedimentos membro inline da classe ListaDouble:

inline int ListaDouble::reserva() {
    const int i = primeiro_livre;
    primeiro_livre = elos[i].seguinte;
    return i;
}

inline void ListaDouble::liberta(int i) {
    elos[i].seguinte = primeiro_livre;
    primeiro_livre = i;
}

// Coloca um novo elo, contendo o item item e retirado da cadeia de elos livres, na cadeia duplamente
// ligada.  O novo elo é colocado entre o elo anterior e o seguinte.
inline void ListaDouble::poe(int anterior, int seguinte, const Item& item) {
    ++quantos;

    const int i = reserva();

    elos[i].item = item;
    elos[i].anterior = anterior;
    elos[i].seguinte = seguinte;
    elos[anterior].seguinte = i;
    elos[seguinte].anterior = i;
}

// Os procedimentos poeInicio(), poeFim() e insere() são todos implementados à
// custa do procedimento membro privado poe():

inline void ListaDouble::poeInicio(const Item& item) {
    assert(!cheia());

    poe(inicial, elos[inicial].seguinte, item);
}

inline void ListaDouble::poeFim(const Item& item) {
    assert(!cheia());

    poe(elos[final].anterior, final, item);
}

/*
   Note-se que o iterador é passado por referência apesar de não ser alterado.  Será que isto é
   inconsistente?  A verdade é que o iterador só não precisa de ser alterado devido à
   implementação particular do conceito de lista e iterador usado aqui.  Com outra
   implementação (ver resolução da Aula 2), o iterador não poderia ser constante.  A utilização
   de uma referência constante aqui levaria o utilizador da classe a crer que o procedimento
   insere() não altera nunca o iterador, o que só é verdade para esta implementação em
   particular.  Assim, alterar a implementação poderia obrigar a alterar a interface da classe
   (o cabeçalho do procedimento faz parte da interface da classe), com efeitos potencialmente
   desastrosos sobre o código do utilizador da classe.  Moral: a interface deve reflectir os conceitos
   e não a implementação em particular.
*/
inline void ListaDouble::insere(Iterador& iterador, const Item& item)
{
    assert(!cheia());

    // Só se pode inserir se o iterador estiver associado a esta lista!  Mas para o verificar é necessária
    // matéria da próxima aula...

    // Não se pode inserir se o iterador referir o item antes do primeiro (item fictício inicial):
    assert(iterador.indice != inicial);

    poe(elos[iterador.indice].anterior, iterador.indice, item);
    // O iterador mantém-se válido!
}

// Retira o elo i da cadeia duplamente ligada, colocando-o na cadeia simplesmente ligada de elos livres:
inline void ListaDouble::tira(int i) {
    --quantos;

    elos[elos[i].anterior].seguinte = elos[i].seguinte;
    elos[elos[i].seguinte].anterior = elos[i].anterior;

    liberta(i);
}

// Os procedimentos tiraPrimeiro(), tiraUltimo() e remove() são todos implementados
// à custa do procedimento membro privado tira():

inline void ListaDouble::tiraPrimeiro() {
    assert(!vazia());

    tira(elos[inicial].seguinte);
}

inline void ListaDouble::tiraUltimo() {
    assert(!vazia());

    tira(elos[final].anterior);
}

inline void ListaDouble::remove(Iterador& iterador)
{
    assert(iterador.indice != inicial && iterador.indice != final);

    // Só se pode remover se o iterador estiver associado a esta lista!  Mas para o verificar é
    // necessária matéria da próxima aula...

    const int i = elos[iterador.indice].seguinte;
    tira(iterador.indice);

    // Avançar itereador!
    iterador.indice = i;
}

inline ListaDouble::Item ListaDouble::primeiroItem() const {
    assert(!vazia());

    return elos[elos[inicial].seguinte].item;
}

inline ListaDouble::Item& ListaDouble::primeiroItem() {
    assert(!vazia());

    return elos[elos[inicial].seguinte].item;
}

inline ListaDouble::Item ListaDouble::ultimoItem() const {
    assert(!vazia());

    return elos[elos[final].anterior].item;
}

inline ListaDouble::Item& ListaDouble::ultimoItem() {
    assert(!vazia());

    return elos[elos[final].anterior].item;
}

inline int ListaDouble::comprimento() const {
    return quantos;
}

inline bool ListaDouble::vazia() const {
    return comprimento() == 0;
}

inline bool ListaDouble::cheia() const {
    return comprimento() == limite;
}

inline ListaDouble::Iterador ListaDouble::primeiro() {
    // Cria-se um iterador para esta lista, que referencia logo o primeiro item da lista (ver
    // construtor de ListaDouble::Iterador):
    Iterador iterador(*this);

    // Devolve-se o iterador criado:
    return iterador;
}

inline ListaDouble::Iterador ListaDouble::ultimo() {
    Iterador iterador(*this);

    iterador.indice = elos[final].anterior;

    return iterador;
}

inline ListaDouble::Iterador ListaDouble::inicio() {
    Iterador iterador(*this);

    iterador.indice = inicial;

    return iterador;
}

inline ListaDouble::Iterador ListaDouble::fim() {
    Iterador iterador(*this);

    iterador.indice = final;

    return iterador;
}

// Definição das funções e procedimentos membro inline da classe ListaDouble::Iterador:

inline ListaDouble::Iterador::Iterador(ListaDouble& l)
    : lista(l), indice(l.elos[l.inicial].seguinte) {
}

inline ListaDouble::Iterador& ListaDouble::Iterador::operator ++ () {
    assert(indice != lista.final);

    indice = lista.elos[indice].seguinte;

    return *this;
}

inline ListaDouble::Iterador& ListaDouble::Iterador::operator -- () {
    // Decrementar para aquém do item fictício inicial é um erro:
    assert(indice != lista.inicial);

    indice = lista.elos[indice].anterior;
    return *this;
}

inline ListaDouble::Iterador ListaDouble::Iterador::operator ++ (int) {
    ListaDouble::Iterador resultado = *this;
    operator ++ ();
    return resultado;
}

inline ListaDouble::Iterador ListaDouble::Iterador::operator -- (int) {
    ListaDouble::Iterador resultado = *this;
    operator -- ();
    return resultado;
}

// Comparam-se os índices.  Esta implementação não é perfeita.  Em rigor dever-se-ia verificar ambos
// os iteradores estão associados à mesma lista, pois não faz sentido compará-los de outra forma (pense
// como fazê-lo quando tiver aprendido ponteiros).
inline bool ListaDouble::Iterador::operator == (const Iterador& i) const {
    return indice == i.indice;
}

inline bool ListaDouble::Iterador::operator != (const Iterador& i) const {
    return indice != i.indice;
}

inline ListaDouble::Item& ListaDouble::Iterador::item() const {
    // O item só existe se o iterador não se referir a um item fictício:
    assert(indice != inicial && indice != final);

    return lista.elos[indice].item;
}

// Definição de funções e procedimentos não membro e inline:

// Declaração de funções e procedimentos não membro e não inline:

std::ostream& operator << (std::ostream& saida, ListaDouble& l);

#endif // LISTA_DOUBLE_EFICIENTE_H

#include "lista_double_eficiente.H"

// Definição das funções e procedimentos membro não-inline da classe ListaDouble:

ListaDouble::ListaDouble()
    : quantos(0), primeiro_livre(0) {

    // Criar lista de itens vazia (itens fictícios):
    elos[inicial].seguinte = final;
    elos[final].anterior = inicial;

    // Criar lista de nós livres com todos os nós da matriz (excepto guardas):
    for(int i = 0; i != limite - 1; ++i)
        elos[i].seguinte = i + 1;
    // O elemento limite - 1 não precisa de ter seguinte válido!  Porquê?
}

// Definição das funções e procedimentos membro não inline da classe ListaDouble::Iterador:

// Definição de funções e procedimentos não membro e não inline:

// Definição do operador << para escrita de listas num canal. ListaDouble& deveria ser
// const ListaDouble&, mas isso implicaria a definição de uma classe de iterador para listas
// constantes:
std::ostream& operator << (std::ostream& saida, ListaDouble& l)
{
    saida << '(';
    for(ListaDouble::Iterador i = l.primeiro(); i != l.fim(); ++i) {
        saida << i.item();
        if(i != l.ultimo())
            saida << ", ";
    }
    return saida << ')';
}

#include <iostream>

using namespace std;

#include "lista_double_eficiente.H"

// O programa de teste:
int main()
{
    ListaDouble l;

    l.poeFim(1);
    l.poeFim(2);
    l.poeFim(3);
    l.poeFim(4);

    for(ListaDouble::Iterador i = l.primeiro(); i != l.fim(); ++i)
        cout << i.item() << ' ';
    cout << endl;

    for(ListaDouble::Iterador i = l.ultimo(); i != l.inicio(); --i)
        cout << i.item() << ' ';
    cout << endl;

    cout << l << endl;

    ListaDouble::Iterador i = l.primeiro();
    ++i;

    l.insere(i, 10);

    cout << l << endl;

    l.remove(i);

    cout << l << endl;

    l.tiraPrimeiro();
    cout << l << endl;

    l.tiraUltimo();
    cout << l << endl;

    l.tiraPrimeiro();
    cout << l << endl;

    l.tiraUltimo();
    cout << l << endl;

    l.poeInicio(10);
    cout << l << endl;
    l.poeInicio(20);
    cout << l << endl;
    l.poeInicio(30);
    cout << l << endl;
    l.poeInicio(40);
    cout << l << endl;
    l.poeFim(100);
    cout << l << endl;
    l.poeFim(200);
    cout << l << endl;
    l.poeFim(300);
    cout << l << endl;
    l.poeFim(400);
    cout << l << endl;

    ListaDouble::Iterador j = l.ultimo();
    --j;
    --j;
    --j;
    l.remove(j);
    cout << l << endl;
    --j;
    --j;
    l.remove(j);
    cout << l << endl;
    l.insere(j, 1000);
    cout << l << endl;
    l.insere(j, 2000);
    cout << l << endl;
    l.insere(j, 3000);
    cout << l << endl;
    l.insere(j, 4000);
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;
    l.tiraPrimeiro();
    cout << l << endl;

    // A seguir o programa aborta porque tenta tirar um item de uma lista vazia:
    l.tiraUltimo();
    cout << l << endl;
}

Exercícios propostos

Faça um programa de teste em que se dá o número e o nome de um aluno.  Depois o programa pergunta se quer dar a nota de trabalho.  Se o utilizador disser que sim o programa lê esta nota.  E da mesma forma para as outras duas notas.  No fim o programa indica que o aluno já tem nota final e qual ela é.

1.b)  Refaça a lista de 2. para conter itens do tipo Aluno.  Assinale nos ficheiros de interface (.H) e implementação (.C) do módulo das listas todas as modificações que teve que fazer.  Faça um programa de teste semelhante ao da alínea 1.

2.  Considere a classe ListaDouble concretizada em 1.  Pretende-se fazer um iterador que permita percorrer a lista de forma ordenada.  Isto é, começa por se obter um iterador referenciando o item de menor valor que está na lista (ou o primeiro deles se houver mais que um igual).  Depois, ao incrementar o iterador, deve-se obter o iterador para o item seguinte por ordem crescente dos seus valores.  Para resolver este execício siga os passos abaixo:

2.a)  Faça uma classe embutida IteradorMenor que permita percorrer todos os itens com o menor valor da lista.

A classe ListaDouble deve ser equipada de uma função membro IteradorMenor menor() que devolva um iterador para o primeiro dos itens com o menor valor na lista.  Se a lista estiver vazia o iterador deve-se referir ao item fictício final (depois do último).  A procura deste item é trivial, dados os algoritmos desenvolvidos no primeiro semestre.

A incrementação de um IteradorMenor faz o seguinte: vai desde o item referenciado pelo iterador antes da incrementação até ao fim da lista à procura de um item com valor igual.  Se o encontrou, o novo valor do iterador deve-se referir a esse item.  Caso contrário o iterador deve-se referir ao item fictício final.

Faça um programa de teste que lê uma série de números para um lista e escreve os menores.

2.b)  Transforme a classe IteradorMenor na classe (embutida) IteradorOrdenado.  A inicialização deste iterador faz-se como a do IteradorMenor.  O avanço também, excepto que, se não encontrar um item de valor igual, deve colocar o iterador a referenciar o primeiro item da lista com valor imediatamente acima.  Se não existir, aí sim, deve referenciar o elemento fictício final.

Faça um programa de teste que lê uma série de números para uma lista e os escreve de forma ordenada.  O ciclo de escrita dos valores deve ser:

ListaDouble l;
... // leitura de valores.
// Escrita ordenada:
for(ListaDouble::IteradorOrdenado i = l.menor(); i != l.fim(); ++i)
    cout << l.item() << endl;

iterador_ordenado.H

#ifndef ITERADOR_ORDENADO_H
#define ITERADOR_ORDENADO_H

#include "lista_aluno.H"

class IteradorOrdenado {
public:
    typedef ListaAluno Lista;
    typedef Lista::Item Item;

    IteradorOrdenado(Lista& l);
    Item& operator * () const;
    IteradorOrdenado& operator ++ ();
    IteradorOrdenado& operator -- ();
    IteradorOrdenado operator ++ (int);
    IteradorOrdenado operator -- (int);
    bool operator == (IteradorOrdenado const& i) const;
    bool operator != (IteradorOrdenado const& i) const;
    bool operator == (Lista::Iterador const& i) const;
    bool operator != (Lista::Iterador const& i) const;

private:
    Lista* lista;
    Lista::Iterador iterador;
};

#include "iterador_ordenado_impl.H"

#endif // ITERADOR_ORDENADO_H

inline IteradorOrdenado::Item& IteradorOrdenado::operator * () const {
    return *iterador;
}

inline IteradorOrdenado IteradorOrdenado::operator ++ (int) {
    IteradorOrdenado i = *this;
    operator ++ ();
    return i;
}

inline IteradorOrdenado IteradorOrdenado::operator -- (int) {
    IteradorOrdenado i = *this;
    operator -- ();
    return i;
}

inline bool IteradorOrdenado::operator == (IteradorOrdenado const& i) const {
    return iterador == i.iterador;
}

inline bool IteradorOrdenado::operator != (IteradorOrdenado const& i) const {
    return iterador != i.iterador;
}

inline bool IteradorOrdenado::operator == (Lista::Iterador const& i) const {
    return iterador == i;
}

inline bool IteradorOrdenado::operator != (Lista::Iterador const& i) const {
    return iterador != i;
}

#include "iterador_ordenado.H"

IteradorOrdenado::IteradorOrdenado(Lista& l)
    : lista(&l), iterador(l)
{
    for(Lista::Iterador i = l.primeiro(); i != l.fim(); ++i)
        if(*i < *iterador)
            iterador = i;
}

IteradorOrdenado& IteradorOrdenado::operator ++ ()
{
    assert(iterador != lista->fim());

    // Procura seguinte igual:
    Lista::Iterador i = iterador;
    for(++i; i != lista->fim() && *i != *iterador; ++i)
        ;
    if(i == lista->fim()) {
        // Não há seguinte igual...

        // Procura primeiro maior:
        for(i = lista->primeiro(); i != lista->fim() && *i <= *iterador;)
            ++i;

        if(i != lista->fim()) {
            // Se há um maior, procurar o primeiro menor dos maiores:
            Lista::Iterador j = i;
            for(++j; j != lista->fim(); ++j)
                if(*j > *iterador && *j < *i)
                    i = j;
        }
    }
    iterador = i;
    return *this;
}

IteradorOrdenado& IteradorOrdenado::operator -- ()
{
    assert(iterador != lista->inicio());

    // Procura anterior igual:
    Lista::Iterador i = iterador;
    for(--i; i != lista->fim() && *i != *iterador; --i)
        ;
    if(i == lista->inicio()) {
        // Não há anterior igual...

        // Procura último menor:
        for(i = lista->ultimo(); i != lista->inicio() && *i >= *iterador;
            --i)
            ;

        if(i != lista->inicio()) {
            // Se há um menor, procurar o último maior dos menores:
            Lista::Iterador j = i;
            for(--j; j != lista->inicio(); --j)
                if(*j < *iterador && *j > *i)
                    i = j;
        }
    }
    iterador = i;
    return *this;
}

#include "aluno.H"
#include "lista_aluno.H"
#include "iterador_ordenado.H"

int main()
{
    ListaAluno l;
    l.poeFim(Aluno("Zeca", 10));
    l.poeFim(Aluno("Maria", 20));
    l.poeFim(Aluno("Zeca", 1));
    l.poeFim(Aluno("Maria", 40));
    l.poeFim(Aluno("João", 40));
    for(IteradorOrdenado i(l); i != l.fim(); ++i)
        cout << *i << endl;
}

teste_ordena: teste_ordena.o iterador_ordenado.o lista_aluno.o

lista_aluno.o: lista_aluno.H lista_aluno_impl.H

teste_ordena.o: teste_ordena.C lista_aluno.H lista_aluno_impl.H aluno.H \
                aluno_impl.H iterador_ordenado.H iterador_ordenado_impl.H

iterador_ordenado.o: iterador_ordenado.C iterador_ordenado.H \
                     iterador_ordenado_impl.H lista_aluno.H \
                     lista_aluno_impl.H aluno.H

3.b)  Modifique para ordenar pelo nome.