Aula 4

1  Resumo da matéria

1.1  Ponteiros e classes

Podem-se definir ponteiros para qualquer tipo, incluindo classes.  Por exemplo:
#include <iostream>
#include <string>

class Aluno {
    std::string nome_;
    int numero_;
public:
    Aluno(std::string no = "", int nu = 0)
        : nome_(no), numero_(nu) {}
    std::string nome() {
        return nome_;
    }
    void nome(std::string no) {
        nome_ = no;
    }
    ...
};

int main() {
    Aluno a("Ambrósio Amaral", 1234);
    Aluno* p = &a;
    std::cout << (*p).nome() << std::endl;
}

Note-se na utilização de parênteses envolvendo *p.  São necessários porque o operador * (conteúdo) tem menor precedência que o operador . (selecção de membro).  Para evitar a notação complicada o C++ fornece um operador com o mesmo efeito:
cout << p->nome() << endl;

1.2  Memória dinâmica

Até agora só se viu como usar variáveis com nomes associados.  Por exemplo, a definição
int i;
cria uma nova variável de nome i e de tipo int atribuindo-lhe um dado espaço na memória.  Mas o C++ permite usar variáveis sem nome e criadas durante a execução do programa, sempre que o programador o desejar.  Essas variáveis são criadas naquilo a que chama a memória livre (free store ou heap).  Para isso, é fundamental o conceito de ponteiro, pois essas variáveis, a que se chama variáveis dinâmicas, não têm nenhum nome associado, sendo por isso necessário usar endereços de memória para as localizar.

1.2.1  Criação de variáveis dinâmicas

Suponha-se que se pretendia criar uma nova variável dinâmica, do tipo int, e guardar o seu endereço num dado ponteiro.  Para isso usa-se o operador new:
int* p;
p = new int;
Depois destas instruções, o ponteiro p passa a conter o endereço de uma variável do tipo int, que pode ser usada como outra qualquer, embora sempre através de uma ponteiro.  Por exemplo:
*p = 20;
cout << *p << endl;
À operação de criação de variáveis dinâmicas dá-se usualmente o nome de "reserva de memória" ou mesmo "alocação de memória", e é implementada através duma interacção apropriada entre a implementação da linguagem e o sistema operativo utilizado.

1.2.2  Destruição de variáveis dinâmicas

A memória é um recurso escasso.  Por isso é regra que as variáveis dinâmicas, quando deixam de ser necessárias, devem ser devolvidas à memória livre.  Para isso usa-se o operador delete:
int* p;
p = new int;
*p = 20;
cout << *p << endl;
delete p;
Para esta operação de devolução da memória de uma variável dinâmica é vulgar utilizar-se a expressão "libertar memória" ou mesmo "dealocar memória".

É um princípio da programação em C++ que todas as variáveis criadas na memória dinâmica devem ser libertadas mais cedo ou mais tarde (de preferência mais cedo...).

1.2.3  Problemas comuns

A utilização de memória dinâmica está sujeita a alguns erros.  De longe os mais frequentes são os que se apresentam abaixo.

Variáveis dinâmicas perdidas

Suponha-se a função:
void f() {
    int* p = new int;
}
Sempre que esta função for chamada é criada uma variável p e inicializada com o endereço duma variável dinâmica criada através do operador new.  Quando a função termina, a variável p é descartada, mas a variável dinâmica mantém-se em memória.  Se se chamar muitas vezes esta função, a memória disponível vai-se reduzindo.  Diz-se que se tem um "fuga de memória" (como num cano roto...).

Outro caso comum é a reserva de memória de que depois se perde a referência por atribuição descuidada ao respectivo ponteiro.  Por exemplo:

int* p = new int;
int i;
p = &i; // e perdeu-se a referência para a variável dinâmica...
É de notar que algumas linguagens, como o Java, possuem uma entidade que, durante a execução do programa, se encarrega de verificar a existência de variáveis dinâmicas para as quais não sobrou qualquer referência (nenhum ponteiro com o seu endereço) e se encarregam de as libertar automaticamente.  O C++ não possui este simpático mecanismo.  Não esquecer nunca que por cada new deve existir um delete!

Dupla destruição

Outro erro frequente é a tentativa de devolução de uma variável dinâmica à memória livre quando esta operação já foi efectuada antes.  Por exemplo:
int* p = new int;
delete p;
delete p; // erro dramático!

Utilização depois da destruição

Despois de libertada uma variável dinâmica, o seu endereço torna-se automaticamente inválido.  Por exemplo:
int* p = new int;
*p = 20;
delete p;
*p = 30; // erro dramático (com sorte o programa aborta).

1.2.4  Construtores e destrutores

Construtores

Quando se invoca operador new como até aqui, a variável dinâmica é inicializada usando o construtor por omissão do seu tipo (excepto se este for um dos tipos básicos do C++).  É possível invocar um dos construtores do tipo explicitamente.  Por exemplo:
int* p = new int(10);
Cria uma variável dinâmica inteira, que inicializa com 10, e guarda o seu endereço em p.  Ou, usando a classe Racional definida no semestre passado:
Racional* pr = new Racional(6, 14);
que cria um novo racional, na memória dinâmica, com valor 3/7.

Destrutores

Da mesma forma, também o destrutor do tipo em causa é invocado automaticamente aquando da destruição de uma variável dinâmica.  Por exemplo:
#include <iostream>
class C {
    C() {
        std::cout << "Construtor!" << std::endl;
    }
    ~C() {
        std::cout << "Destrutor!" << std::endl;
    }
};
int main() {
    C* p = new C; // aparece "Construtor!".
    delete p;     // aparece "Destrutor!".
}

1.2.5  Criação de matrizes dinâmicas

Também é possível criar matrizes dinâmicas.  Por exemplo, se se pretender criar uma matriz com dimensão dada pelo utilizador do programa pode-se usar o operador new []:
cout << "Introduza tamanho: " << endl;
int n;
if(cin >> n && n > 0) {
    int* m = new int[n];
    // Utilização de m como outra matriz qualquer:
    for(int i = 0; i != n; i++)
        m[i] = 0;
}
No caso das matrizes o construtor invocado (excepto para tipos básicos do C++, em que não se invoca qualquer construtor) é o construtor por omissão.  Não se pode especificar qualquer outro.

1.2.6  Destruição de matrizes dinâmicas

A devolução duma matriz dinâmica à memória livre faz-se através do operador delete [].  Por exemplo:
Racional* mr = new Racional[100]; // cria matriz com 100 racionais zero (0).
delete[] mr;                      // destroi a matriz.
O operador delete [] invoca automaticamente o destrutor do tipo em causa para cada elemento da matriz dinâmica.  É um erro grave usar o operador delete em vez do operador delete [] para uma matriz dinâmica, mesmo que esta possua apenas um elemento.

1.2.7  Falta de memória

A memória é sempre finita.  Por isso as operações de reserva de memória podem falhar.  Quando tal acontece o operador new invoca uma função especial chamada new_handler (que pode ser substituída pelo utilizador, se necessário).  Esta função por omissão lança uma excepção (um conceito que se estudará mais tarde) chamada bad_alloc e que tem como resultado prático abortar o programa.  A não ser, claro, que a excepção seja explicitamente capturada por código envolvente.  Este assunto será revisitado mais tarde com maior cuidado.

1.2.8  Alguns exemplos

Dada a definição de Aluno na Secção 1.1:
Aluno *p = new Aluno("Ambrósio Amaral", 1234);
cout << p->nome() << endl;
delete p;
Criação de uma matriz com 20 alunos (possível apenas porque a classe tem construtor por omissão):
Aluno *p = new Aluno[20];
p[3].nome("Xisto Ximenes");
delete[] p;

1.3  Listas ligadas

Os ponteiros e a memória dinâmica permitem a definição de conceitos interessantes.  Por exemplo, seja a seguinte classe (aliás, estrutura):
struct No {
    typedef int Item;
    No* seguinte;
    Item item;
    No(No* seg = 0, Item it = Item())
        : seguinte(seg), item(it) {}
};
Note-se que é perfeitamente legal a utilização de ponteiros para uma classe na sua própria definição.  Note-se ainda a utilização do construtor por omissão de Item (no caso int, mas, alterando o typedef, qualquer outra classe)*.

Usando a classe acima e memória dinâmica é possível construir sequências de variáveis dinâmicas, cada uma com o seu inteiro.  Por exemplo, depois das instruções:

No* primeiro = new No(0, 101);
primeiro = new No(primeiro, 45);
primeiro = new No(primeiro, 60);
o ponteiro primeiro contém o endereço de uma variável do tipo No (um nó, para abreviar) com item 60, que contém um ponteiro seguinte para outro nó com item 45 que contém um ponteiro para outro nó com item 101 que contém o ponteiro especial nulo, assinalando o final da sequência.  A esta construção especial de variáveis dinâmicas chama-se uma lista simplesmente ligada.  Se se pretendesse escrever a lista no ecrã poder-se-ia usar:
for(No* no = primeiro; no != 0; no = no->seguinte)
    std::cout << no->item << std::endl;
E se se pretender acrescentar itens ao final da lista ligada?  Poder-se-ia refazer o código para:
No* primeiro = new No(0, 101);
No* ultimo = primeiro;
primeiro = new No(primeiro, 45);
primeiro = new No(primeiro, 60);
ultimo->seguinte = new No(0, 200);
o que levaria a uma lista com os itens 60, 45, 101 e 200.

Suponha-se agora que se pretendia escrever uma função que, dado um ponteiro para um nó duma lista ligada, inserisse depois dele um novo nó com um dado item.  Poder-se-ia escrever:

void insereDepois(No* depois, No::Item item) {
    depois->seguinte = new No(depois->seguinte, item);
}
Mas suponha-se a utilização que se segue:
No* primeiro = new No(0, 101);
No* ultimo = primeiro;
primeiro = new No(primeiro, 45);
primeiro = new No(primeiro, 60);
ultimo->seguinte = new No(0, 200);
ultimo = ultimo->seguinte;
No* no = ultimo;
insereDepois(no, 33);
cout << ultimo->item << endl;
Ao contrário do espectável, o valor escrito no ecrã é 200, e não 33.  Isto porque se inseriu depois do último sem actualizar o ponteiro ultimo.  O problema poderia ser corrigido passando o ponteiro ultimo como referência à função:
void insereDepois(No*& ultimo, No* depois, No::Item item) {
    depois->seguinte = new No(depois->seguinte, item);
    if(ultimo == depois)
        ultimo = depois->seguinte;
}
Suponha-se agora que se pretendia escrever uma função que, dado um ponteiro para um nó duma lista ligada, inserisse antes dele um novo nó com um dado item.  Como os nós não possuem referência para o anterior na lista, poder-se-ia tentar:
void insere(No* depois, No::Item item) {
    depois->seguinte = new No(depois->seguinte, depois->item);
    depois->item = item;
}
Mas ter-se-iam problemas de novo se depois fosse o último da lista.  Seria necessário corrigir como na função insereDepois().

Se se pretender escrever uma função para remover um nó dado tem-se um problema idêntico.  Pode-se usar o truque de remover o elemento seguinte, copiando o respectivo item para o nó que se pretendia remover, mas isso implica que o elemento seguinte teria de existir, o que não é verdade no final da lista!

Como se pode evitar este tipo de problemas?  De duas formas.  Em primeiro lugar podem-se usar referências em ambos os sentidos nos nós, para ter acesso não só ao nó seguinte mas também ao nó anterior.  Isto facilita também o percorrer da lista em sentido inverso.  A listas com estas características chama-se listas duplamente ligadas.  Em segundo lugar, os casos particulares de inserções e remoções no final da lista podem ser evitados arbitrando a existência de dois nós, que não contêm qualquer item, no início (antes do primeiro nó) e no final (depois do último nó) da lista.  A esse dois nós especiais chama-se "guardas".  Se as listas ligadas forem usadas para implementar o conceito de lista e respectivos iteradores, as guardas terão a vantagem adicional de permitir referir os elementos "fictícios" da lista no seu início e no seu fim.

* É possível definir variáveis membro duma classe como ponteiros para essa mesma classe.  Mas não é permitido definir variáveis membro duma classe cujo tipo é essa mesma classe.  Que tamanho (espaço em memória) ocupariam variáveis dessas classe?

1.3.1  Um módulo de listas ligadas

Suponha-se que se pretendia definir um módulo contendo ferramentas básicas para manipulação de listas duplamente ligadas.  Um possível ficheiro de interface (incompleto...) seria o que segue:

Ficheiro de interface (lista_ligada.h)

#ifndef LISTA_LIGADA_H
#define LISTA_LIGADA_H

/*
  Este módulo não implementa nenhum TAD (Tipo Abstrato de Dados).  Define
  sim um conjunto de ferramentas que implementam listas ligadas.  Assim, todas
  as ferramentas são colocadas num espaço nominativo próprio, para evitar
  colisões de nomes.  Estas ferramentas podem ser úteis para implementar
  outros conceitos que não apenas o de lista.  Por exemplo, os conceitos de pilha,
  fila, conjunto e colecção podem usar internamente listas ligadas.
**/
namespace ListaLigada {
    /*
      Uma classe para representar os nós da lista ligada.  Esta classe (struct,
      na realidade) é uma mera ferramenta para uso na implementação de outros
      conceitos, como o de lista propriamente dita.  Daí que seja uma estrutura,
      i.e., que tenha todos os membros públicos.

      Em todos os procedimentos que lidam com uma lista ligada, dir-se-á que
      inicial e final constituem uma lista (duplamente) ligada sse:
          (a) final é atingível de inicial usando o campo seguinte
           sucessivamente e
          (b) inicial é atingível de final usando o campo anterior
           sucessivamente e
          (c) qualquer que se o nó no intermédio (i.e., diferente de inicial e
             final) atingível de inicial ou de final,
             no->seguinte->anterior = no e
             no->anterior->seguinte = no e
          (d) inicial->anterior = 0 e
          (e) final->seguinte = 0.

      Dir-se-á que a lista ligada está vazia se inicial->seguinte = final,
      i.e., se não existirem nós intermédios.

      Dir-se-á que de e ate constituem um troço de lista ligada sse:
          (a) ate é atingível de de usando o campo seguinte
           sucessivamente e
          (b) de é atingível de ate usando o campo anterior
           sucessivamente e
          (c) qualquer que se o nó no intermédio (i.e., diferente de ate)
           atingível de de ou de ate,
             no->seguinte->anterior = no e
             no->anterior->seguinte = no e
          (d) de->anterior <> 0 (não é guarda inicial).

      Dir-se-á que um nó no pertence a uma lista ligada se no for atingível a
      partir de inicial e for diferente de ambas as guardas.  A definição é
      semelhante para troços de listas ligadas.
    **/
    struct No {
        // Cria-se um sinónimo de int, chamado Item, para simplificar a
        // tarefa de criar listas ligadas com elementos de outros tipos:
        typedef int Item;
        No *anterior;        // ponteiro para o nó anterior.
        No *seguinte;        // ponteiro para o nó seguinte.
        Item item;           // guarda o item propriamente dito.
        /*
          Construtor dum nó.  O nó é construído com referências para o nó
          anterior, para o nó seguinte, e com um dado item.  Os valores por
          omissão são ponteiros nulos (0) para as referências e o valor
          calculado pelo construtor por omissão de um Item (se Item for
          sinónimo de int, por exemplo, o valor é zero).
        **/
        No(No* a = 0, No* s = 0, const Item &it = Item());
    };

    /*
      Definição do construtor inline da classe No.
      PC:
      CO: anterior = a e seguinte = s e item = it
    **/
    inline No::No(No* a, No* s, const Item &it)
        : anterior(a), seguinte(s), item(it) {
    }

    /*
      Procedimento inline que inicializa uma lista ligada criando as suas
      guardas.
      PC:
      CO: inicial e final referem novos nós tais que:
         inicial->anterior = 0 e
         inicial->seguinte = final e
         final->seguinte = 0 e
         final->anterior = inicial
         i.e., inicial e final constituem uma lista ligada vazia.
    **/
    inline void inicia(No*& inicial, No*& final) {
        // A completar...
    }

    /*
      Procedimento que finaliza uma lista ligada, libertando (devolvendo à
      memória livre), todos os seus nós incluindo as guardas.
      PC: inicial e final constituem uma lista ligada.
      CO: todos os nós da ligada foram devolvidos à memória livre.
    **/
    void finaliza(No* inicial, No* final);

    /*
      Procedimento que esvazia uma lista ligada, libertando (devolvendo à
      memória livre), todos os seus nós (excluindo as guardas).
      PC: inicial e final constituem uma lista ligada.
      CO: todos os nós intermédios da lista ligada foram devolvidos à memória
         livre e inicial e final constituem uma lista ligada vazia.
    **/
    void esvazia(No* inicial, No* final);

    /*
      Procedimento inline que retira o nó no da lista ligada representada pelas
      guardas inicial e final.
      PC: inicial e final constituem uma lista ligada à qual no pertence.
      CO: a lista possui os mesmos nós que inicialmente, com excepção de no.
    **/
    inline void remove(No* inicial, No* final, No* no) {
        // A completar...
    }

    /*
      Procedimento inline que insere um novo nó, com item item, antes do nó
      depois da lista ligada representada pelas guardas inicial e final.
      PC: inicial e final constituem uma lista ligada à qual depois
         pertence (ou então depois = final).
      CO: a lista possui os mesmos nós que inicialmente, com excepção de um
         novo nó, antes do nó depois, que contém item.
    **/
    inline void insere(No* inicial, No* final,
                       const No::Item& item, No* depois) {
        // Criar novo nó para o item:
        No* novo = new No(depois->anterior, depois, item);

        // Colocá-lo na lista ligada (a ordem das atribuições é fundamental!):
        depois->anterior->seguinte = novo;
        depois->anterior = novo;
    }

    /*
      Procedimento inline que transfere todos os nós intermédios de uma lista
      para outra.
      PC: inicial e final constituem uma lista ligada (destino) e
         inicial2 e final2 constituem uma lista ligada (origem) e as listas
         são distintas.
      CO: a lista de destino contém no seu final todos os nós que constavam da
         lista de origem, pela mesma ordem, e a lista de origem está vazia.
    **/
    inline void transfere(No* inicial, No* final,
                          No* inicial2, No* final2) {
        // A completar...
    }

    /*
      Procedimento que copia nós de um troço de lista ligada (de de até ate
      exclusivé) para o final da lista ligada representada pelas guardas inicial
      e final.
      PC: inicial e final constituem uma lista ligada (destino) e
         de e ate constituem um troço de lista ligada (origem) que pode fazer
         parte da lista de destino.
      CO: a lista de destino contém no seu final novos nós contendo cópias dos
         itens no troço de origem (pela mesma ordem) desde de inclusivé a
         ate exclusivé.
    **/
    void concatena(No* inicial, No* final, No* de, No* ate);

    /*
      Procedimento que procura a primeira ocorrência de um item na lista ligada
      representada pelas guardas inicial e final.  Devolve um ponteiro para
      o nó encontrado ou, se não o encontrou, para a guarda final.
      PC: inicial e final constituem uma lista ligada.
      CO: se item consta de algum dos nós intermédios da lista ligada, o valor
      devolvido é um ponteiro para o primeiro desse nós (o mais próximo de
      inicial), se não o valor devolvido é final.
    **/
    No* procura(No* inicial, No* final,
                const No::Item& item);

    /*
      Procedimento que procura a última ocorrência de um item na lista ligada
      representada pelas guardas inicial e final.  Devolve um ponteiro para
      o nó encontrado ou, se não o encontrou, para a guarda inicial.
      PC: inicial e final constituem uma lista ligada.
      CO: se item consta de algum dos nós intermédios da lista ligada, o valor
      devolvido é um ponteiro para o último desse nós (o mais próximo de
      final), se não o valor devolvido é inicial.
    **/
    No* procuraUltimo(No* inicial, No* final,
                      const No::Item& item);
}

#endif // LISTA_LIGADA_H

Note-se que não se verificam as PC das funções com assert.  Seria boa ideia fazê-lo?

O respectivo ficheiro de implementação (incompleto...) seria como se segue:

Ficheiro de implementação (lista_ligada.cpp)

#include "lista_ligada.h"

// Definição de funções e procedimentos não 'inline' do módulo:

using ListaLigada::No;  // para evitar ListaLigada::No.

void ListaLigada::concatena(No* inicial, No* final,
                            No* de, No* ate) {
    /*
      Se ate = final, uma implementação imediatista fica em ciclo infinito, pois
      ate afasta-se de de à medida que novos nós são inseridos!  Daí a condição
      de paragem mais complicada nesse caso:
    **/
    if(ate == final) {
        No* ultimo = ate->anterior;
        // Inserem-se sucessivamente os itens da lista l:
        for(; de != ultimo->seguinte; de = de->seguinte)
            insere(inicial, final, de->item, final);
    } else
        // Idem:
        for(; de != ate; de = de->seguinte)
            insere(inicial, final, de->item, final);
}

void ListaLigada::finaliza(No* inicial, No* final) {
    // A completar...
}

void ListaLigada::esvazia(No* inicial, No* final) {
    No* no = inicial->seguinte;
    while(no != final) {
        No* seguinte = no->seguinte;
        delete no;
        no = seguinte;
    }
    inicial->seguinte = final;
    final->anterior = inicial;
}

No* ListaLigada::procura(No* inicial, No* final,
                         const No::Item& item) {
    // A completar...
}

No* ListaLigada::procuraUltimo(No* inicial, No* final,
                               const No::Item& item) {
    No* no = final->anterior;
    while(no != inicial && no->item != item)
        no = no->anterior;
    return no;
}

1.4  Leitura recomendada

Recomenda-se a leitura dos Capítulos 4 e 5 de [2].

2  Exercícios

1.  Complete as funções do módulo das listas ligadas.  Complete uma de cada vez, escrevendo um programa de teste para as testar.  Experimente casos patológicos (mas que cumpram as pré-condições) tais como concatenar uma lista com ela própria.

3  Referências

[1]  Bjarne Stroustrup, "The C++ Programming Language", 3ª edição, Addison-Wesley, Reading, Massachusetts, 1997. *

[2]  Michael Main e Walter Savitch, "Data Structures and Other Objects Using C++", Addison-Wesley, Reading Massachusetts, 1997. #

* Existe um exemplar na biblioteca do ISCTE.

# Existem 10 exemplares na biblioteca do ISCTE.