PRG29003: Etapa 2: A construção da prglib

De MediaWiki do Campus São José
Ir para navegação Ir para pesquisar

Próxima aula

Desde o início do semestre foi usada a biblioteca prglib, que contém implementações das estruturas de dados estudadas. Na primeira etapa da disciplina se enfatizou conhecer e usar essas estruturas de dados. Na segunda etapa o foco está em implementá-las, e o resultado esperado é a implementação da prglib pelas equipes. As versões da prglib a serem criadas devem ser compatíveis com a versão original, de forma que os projetos que foram realizados possam ser recompilados e funcionarem corretamente.


Os arquivos da prglib são:

  • prglib.h: inclui todas as declarações das estruturas de dados
  • libs/fila.h: declara a fila
  • libs/pilha.h: declara a pilha
  • libs/lista.h: declara a lista
  • libs/hash.h: declara a tabela hash
  • libs/arvore.h: declara a árvore de pesquisa binária
  • libs/fila-impl.h: define (implementa) a fila
  • libs/pilha-impl.h: define a pilha
  • libs/lista-impl.h: define a lista
  • libs/hash-impl.h: define a tabela hash
  • libs/arvore-impl.h: define a árvore de pesquisa binária

Os arquivos de declarações praticamente não são modificados em relação à prglib original. O esforço deve se concentrar nos arquivos de implementação, onde de fato serão programados os métodos que contêm os algoritmos dessas estruturas de dados. Para facilitar essa tarefa, a nova prglib é fornecida na forma de um conjunto de arquivos com os esqueletos das estruturas de dados:


O início da implementação se dá pelas estruturas de dados mais simples: fila e pilha. Com elas se pode recompilar o projeto 1.

Filas


De forma geral, uma fila é uma estrutura de dados que funciona como mostrado na figura abaixo:

Prg-queue.png


Filas podem ser implementadas usando um vetor. No entanto, isso somente tem utilidade para filas de pequeno tamanho e cuja capacidade seja conhecida de antemão. Uma forma usual de implementar uma fila com um vetor se chamafila circular, a qual apresenta eficiência no nefileiramento e desenfileiramento de dados.

Uma fila circular possui uma área de memória limitada para armazenamento sequencial dos dados, a qual pode guardar uma quantidade máxima de dados. A fila circular usa essa área de memória, mantendo controle sobre onde está tanto o início quanto o final da fila. Novos dados são adicionados no fim da fila, e dados são retirados sempre do início da fila. O funcionamento da fila circular pode ser exemplificado pela seguinte figura, em que os números 5, 8, 2, 6 e 4 são enfileirados (além do número 5 ser desenfileirado em algum momento):


Prg2-Fila-circular-ex2.png


Deve-se observar que dados são guardados na área de memória, e não mudam de posição. O controle sobre o início e final da fila se faz por meio de dois atributos, chamados convenientemente de inicio e fim. Assim, um novo dado é enfileirado na posição indicada por fim, e em seguida o fim da fila avança para a próxima posição livre. Um dado desenfileirado é retirado da posição indicada por inicio, após o que inicio avança para a próxima posição. Em ambos os casos, se a próxima posição estiver fora da área de memória, então volta-se para sua primeira posição (como mostrado no avanço do fim da fila nos exemplos e) e f)), e por isso esse tipo de fila se chama fila circular, parecendo com a figura a seguir. Desta forma, as operações de enfileiramento e desenfileiramento podem ser implementadas por algoritmos bastante simples e com baixo custo computacional.


Prg-Circular queue.gif
Fila circular: os números são os índices do vetor que contém a fila


Implementação da fila circular

A fila a ser criada deve ser capaz de guardar qualquer tipo de dado, sem necessitar de qualquer modificação em seu código-fonte. Assim, a fila torna-se genérica e reutilizável em outros programas. Há mais de uma abordagem para tornar uma fila (ou qualquer outra estrutura de dados) capaz de guardar qualquer coisa. Nesta disciplina de PRG2 será usada uma abordagem com templates, por sua relativa simplicidade.


A fila utilizada no projeto 1 está definida da seguinte forma: 

#ifndef FILA_H
#define	FILA_H

namespace prglib {

template <typename T> class fila {
public:
    // construtor: cria uma fila capaz de armazenmar até max_itens
    fila(unsigned int max_itens);

    // construtor de cópia: cria uma fila que é uma cópia idêntica de outra fila
    fila(const fila<T>& orig);

    // destrutor: destroi a fila, liberando qualquer memória alocada
    ~fila();

    // enfileira um dado. Dispara uma exceção se fila estiver cheia
    void enfileira(const T & algo);
   
    // desenfileira um dado. Dispara uma exceção se fila estiver vazia
    T desenfileira();

    // retorna uma referência ao dado que está na frente da fila
    T & frente();

    // retorna true se fila estiver vazia
    bool vazia() const;

    // retorna true se fila estiver cheia
    bool cheia() const;

    // retorna a quantidade de dados armazenada na fila
    unsigned int comprimento() const;

    // retorna a capacidade da fila
    unsigned int capacidade() const;

    // operador de atribuição: torna esta fila uma cópia da outra fila
    fila<T>& operator=(const fila<T> & outra);
private:
    // N: quantidade de dados armazenados na fila
    // cap: capacidade da fila
    unsigned int N, cap;

    // buffer: área de memória onde estão armazenados os dados 
    //         implementada como um vetor a ser criado no construtor
    T * buffer;

    // inicio: posição do início da fila no buffer
    // fim: posição do fim da fila no buffer
    unsigned int inicio, fim;
};

} // fim do namespace
#endif	/* FILA_H */

Arquivo libs/fila.h

A implementação dos métodos da fila deve ser feita no arquivo libs/fila-impl.h.


A implementação da fila pode ser testada com este pequeno programa: 

#include<iostream>
#include <prglib.h>

using namespace std;
using prglib::fila;

int main() {
  fila<int> f1(10); // cria uma fila chamada "f1", com capacidade 10

  // enfileira os números 5, 8, 2 e 4 na fila "f1"
  f1.enfileira(5);
  f1.enfileira(8);
  f1.enfileira(2);
  f1.enfileira(4);

  // desenfileira um por um dos dados da fila, mostrando-os na tela, até
  // que a fila fique vazia
  while (! f1.vazia()) cout << "Dado: " << f1.desenfileira() << endl;

  return 0;
}

Programa de teste da fila

Atividade

  1. Inicie a implementação de sua fila. Entenda os atributos da fila, e como eles são usados para armazenar os dados. Veja também as operações típicas da fila, e pense em como implementá-las segundo o modelo de uma fila circular.
  2. Teste sua fila com o programa exemplo.
  3. E se a fila tivesse capacidade auto-expansível, ou mesmo ilimitada ? O que mudaria na sua implementação ? Experimente definir uma nova fila que tivesse essas característica.

A implementação da pilha

Pilhas são estruturas do tipo LIFO (Last In First Out - último a entrar, primeiro a sair). Apenas duas operações são possíveis de modificar pilhas:

* Push: empilha um novo dado (acrescenta-o ao topo da pilha).
* Pop: desempilha um dado (retira-o do topo da pilha)
*Top: acessa o dado do topo da pilha		 Prg-pilha.jpg


Pilhas podem ser implementadas usando vetores. Abaixo mostra-se uma possível implementação com vetores: 

template <typename T> class pilha {
 public:
  // construtor: deve-se informar a capacidade da pilha
  pilha(unsigned int umaCapacidade);
 
  // construtor de cópia: cria uma pilha que é cópia de outra
  pilha(const pilha<T>& outra);
 
  // destrutor da pilha
  ~pilha();
 
  // operador de atribuição: torna esta pilha uma cópia de outra pilha
  pilha<T> & operator=(const pilha<T> & outra);
 
  // operações da pilha
 
  virtual void push(const T & dado); // empilha um dado
 
  T pop(); // desempilha um dado
 
  virtual const T& top() const; // retorna o dado do topo da pilha, sem retirá-lo
 
  bool vazia() const;
  bool cheia() const;
  unsigned int comprimento() const;
  void esvazia();
  unsigned int capacidade() const;
 
 private:
  // Topo da pilha (corresponde também à qtde de dados na pilha)
  unsigned int topo;

  // Capacidade da pilha (quantos dados cabem nela)
  unsigned int cap;

  // a área de memória onde são armazenados os dados (um vetor)
  T * buffer;
};
#endif

libs/pilha.h

A implementação dos métodos da pilha deve ser feita no arquivo libs/pilha-impl.h.


O programa abaixo pode ser usado para testar a implementação da sua pilha: 

#include <iostream>
#include <prglib.h>
 
const int CAPACIDADE=6;
 
using namespace std;
using prglib::pilha;

int main() {
  pilha<int> q(CAPACIDADE);
 
  q.push(5);
  q.push(8);
  q.push(4);
  q.push(2);
  q.push(3);
 
  cout << "Empilhou 5, 8, 4, 2, 3" << endl;
 
  while (! q.vazia()) {
    cout << "Topo da pilha=" << q.top();
    cout << "... desempilhou " << q.pop() << endl;
  }
 
  return 0;
}

Atividades

  1. Inicie a implementação de sua pilha. Entenda os atributos da pilha, como eles são usados para armazenar os dados. Veja também as operações típicas da pilha, e pense em como implementá-las segundo o modelo de uma pilha de capacidade limitada.
  2. Teste sua pilha com o programa exemplo.
  3. Verifique sua implementação da fila usando este verificador no Moodle.
  4. Verifique sua implementação da pilha usando este verificador no Moodle.
  5. Recompile seu projeto 1 com sua fila e sua pilha, e verifique se ele funciona igual à versão com a prglib original.
Disponível em “https://wiki.sj.ifsc.edu.br/index.php?title=PRG29003:_Etapa_2:_A_construção_da_prglib&oldid=162320”