Resolução dos Exercícios da Aula 2

Exercícios

1.  Complete a classe ListaDouble e os iteradores associados e construa um módulo chamado listaDouble para os colocar.  Este módulo deve ser constituído pelos dois ficheiros fonte habituais: o de interface (lista_double.H) e o de implementação (lista_double.C).  Use a função main() acima para criar um programa de teste para esta classe (este programa deve encontrar-se num módulo diferente do usado para concretizar a lista).

R:

lista_double.H

#ifndef LISTA_DOUBLE_H
#define LISTA_DOUBLE_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 i, fazendo com que
    // o iterador continue a referenciar o mesmo item que antes da inserção:
    void insere(Iterador& i, const Item& item);

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

    // 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;

    // Matriz que guarda os itens da lista:
    Item itens[limite];

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

// 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 item referenciado:
    int indice;
};

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

inline ListaDouble::ListaDouble()
    : quantos(0) {
    // Usa-se uma lista de inicializadores.  Neste caso basta dizer que a lista está vazia, i.e.,
    // não tem qualquer item.
}

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

    itens[quantos++] = item;
}

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

    --quantos;
}

inline ListaDouble::Item ListaDouble::primeiroItem() const {
    assert(!vazia());
    return itens[0];
}

inline ListaDouble::Item& ListaDouble::primeiroItem() {
    assert(!vazia());
    return itens[0];
}

inline ListaDouble::Item ListaDouble::ultimoItem() const {
    assert(!vazia());
    return itens[quantos - 1];
}

inline ListaDouble::Item& ListaDouble::ultimoItem() {
    assert(!vazia());
    return itens[quantos - 1];
}

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;
    // ou simplesmente return Iterador(*this);
}

inline ListaDouble::Iterador ListaDouble::ultimo() {
    // Cria-se um iterador para esta lista:
    Iterador iterador(*this);

    // O iterador deve referenciar o último item da lista:
    iterador.indice = comprimento() - 1;

    return iterador;
}

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

    // O iterador deve referenciar o item fictício antes do primeiro item da lista:
    iterador.indice = -1;

    return iterador;
}

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

    // O iterador deve referenciar o item fictício após o último item da lista:
    iterador.indice = comprimento();

    return iterador;
}

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

inline ListaDouble::Iterador::Iterador(ListaDouble& l)
    : lista(l), indice(0) {
}

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

    ++indice;

    return *this;
}

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

    --indice;
    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 se
// 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(0 <= indice && indice < lista.comprimento());

    return lista.itens[indice];
}

// 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_H

lista_double.C
#include "lista_double.H"

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

void ListaDouble::poeInicio(const Item& item)
{
    // Só se pode inserir se ainda houver espaço:
    assert(!cheia());

    // Inserir no início implica rearranjar todos os itens já na lista:
    for(int i = comprimento(); i != 0; --i)
        itens[i] = itens[i - 1];

    // Agora já há espaço:
    itens[0] = item;

    // E convém incrementar o contador de itens...
    ++quantos;
}

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

    --quantos;
    for(int i = 0; i != comprimento(); ++i)
        itens[i] = itens[i + 1];
}

void ListaDouble::insere(Iterador& iterador, const Item& item)
{
    // Só se pode inserir se ainda houver espaço:
    assert(!cheia());

    // Não se pode inserir se o iterador referir o item antes do primeiro:
    assert(iterador.indice != -1);

    // Há que rearranjar todos os itens a partir do referenciado pelo iterador:
    for(int i = comprimento(); i != iterador.indice; --i)
        itens[i] = itens[i - 1];

    // Agora já há espaço (não esquecer de revalidar o iterador!):
    itens[iterador.indice++] = item;

    // Mais um...
    ++quantos;
}

void ListaDouble::remove(const Iterador& iterador)
{
    assert(iterador.indice != -1 && iterador.indice != comprimento());

    --quantos;
    for(int i = iterador.indice; i != comprimento(); ++i)
        itens[i] = itens[i + 1];
}

// 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 << ')';
}

teste.C
#include <iostream>

using namespace std;

#include "lista_double.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;
}

Se lhe sobrar tempo avance para a Aula 3.