PRG2-2017-2

Programação 2: Diário de Aula 2017-2

• Lista de presença

Professor: Marcelo Maia Sobral
Encontros: 5a feira/13:30, 6a feira/15:40
Atendimento paralelo: 6a de 8:30 às 9:30 h / 6a de 13:30 às 14:30 h

• Plano de Ensino
• Monitoria de Programação

Referências complementares

• Introdução C++
• Modularização em programas C/C++ (arquivos de cabeçalho e implementação
• Apostila sobre listas encadeadas (Unicamp)
• Estruturas de dados disponíveis dentro do kernel Linux (cap. 6 do livro Linux Kernel Development, 3rd ed., de Robert Love, 2010)
• Curso de linguagem C da UFMG
• Slides sobre linguagem C do prof. Emerson R. Mello
• Guia básico do depurador GDB
• Misra-C: diretrizes para uso da linguagem C em sistemas críticos
• "Variáveis globais são ruins" ...
  • Uma discussão sobre isso em um forum de programadores
• Separation of Concerns (Separação de interesses): uma boa introdução sobre decomposição de problemas em partes e modularidade em software.
• Dicionário de Algoritmos e Estruturas de Dados
• Um interessante texto sobre linguagens de programação
• Controle do terminal de texto

Cursos e videos online

• Data structures (Coursera)
• Estruturas de dados: medindo e otimizando o desempenho (Coursera)
• Videos sobre estruturas de dados (em inglês e com legendas)
• Introduction to Data Structures (edX)
• Foundations of Data Structures (edX)
• Implementation of Data Structures (edX)

Avaliações

As avaliações são de três tipos:

1. Projetos: feitos em equipes de até dois alunos, são desenvolvidos ao longo da disciplina.
2. Provas práticas: feitas individualmente, são realizadas em laboratório. Os resultados dessas provas ajustam os conceitos dos projetos (podem confirmá-los, aumentá-los, reduzi-los ou mesmo anulá-los).

Aluno	Projeto 1	Projeto 2	Prova 1	Projeto3	Projeto 4	Prova 2	Proj. Lib	Prova3	FINAL	Faltas até 23/10 (máx: 18/semestre)
Ameliza	5	7	-2			anula (3 incompletas: 7 pontos)/-2 (19 pontos)				0
Ana Paula	8	9	-2	8	6	anula (1 incompleta: 6 pontos)/0*				0
Andre Luiz	0*	0*	anula	0*	0*	anula/0*				10
Diego	9	10	+2	10	9	+2 (3 completas: 39 pontos)				14
Felipe	10	10	mantém	10	9	+2 (3 completas: 34 pontos)				6
Gabriel	9	10	anula	8		anula/0*				13
Gustavo	9	10	+2	10	9	0*/0*				19
Guilherme	5	7	-2			anula (1 incompleta: 2 pontos)/mantém (23 pontos)				2
João Pedro	0*	0*	anula			anula/0*				2
Luiza	6	7	mantém	8	8	mantém (2 completas: 22 pontos)				4
Renan	8	9	+2	8	6	mantém (2 completas: 20 pontos)				0
Stefanie	5	7	anula			anula/0*				9
Yara	9	10	+2	8		anula/-2 (19 pontos)				2

Obs:

• 0* = não fez a avaliação.
• (?) = a confirmar
• (--) = nota reduzida em 1 ponto por atraso

Softwares

• g++: o compilador da linguagem C++ que usaremos
• gdb: um debugger para ajudar a encontrar erros em programas
• make: um programa para automatizar a compilação de programas
• Netbeans IDE (versão C/C++)
  • Cópia do instalador no servidor do Ifsc
  • OBS: instale o Netbeans executando este comando em um terminal:

    bash netbeans-8.2-cpp-linux-x64.sh
    

  • OBS 2: você precisará ter a máquina virtual Java instalada em seu computador. Você pode obtê-la aqui.
• Code::Blocks - outro IDE C/C++

27/07: Apresentação e introdução ao projeto

• Introdução C++

Programas precisam armazenar e organizar dados de forma eficiente, o que depende do tipo de problema a ser resolvido, da quantidade de dados a serem manipulados, e da forma com que dados são representados. Para isso existe o conceito de estruturas de dados, que são justamente formas de armazenar e organizar dados. Algumas estruturas de dados corriqueiras são:

• Filas
• Pilhas
• Listas
• Tabelas de dispersão (hash)
• Árvores

... porém há muitas outras (faça uma pesquisa se ficou curioso).

Em PRG2 serão estudadas as estruturas de dados acima listadas, as quais são de uso comum em programas em geral. O estudo será orientado a pequenos projetos, com a intenção de mostrar possíveis usos dessas estruturas.

• Projeto 1: (fila e pilha)
• Projeto 2: (lista)
• Projeto 3: (árvore)
• Projeto 4: (tabela hash)

O estudo dessas estruturas será dividido em duas etapas:

1. Uso das estruturas de dados: as estruturas de dados são apresentadas, destacando-se suas características, operações e aplicações. Os projetos serão desenvolvidos usando estruturas de dados já existentes.
2. Implementação das estruturas de dados: As estruturas de dados serão implementadas, de forma a funcionarem como as estruturas usadas na etapa 1. Como resultado, cada equipe terá ao final criado uma biblioteca de programação contendo suas estruturas de dados. Os projetos criados na etapa 1 devem ser compilados e funcionar usando essa biblioteca, sem necessitar qualquer modificação.

Introdução a C++

• Introdução a C++ (USP)
• Introdução a C++ (UFRGS)
• Introdução a C++ (UFRJ)

A linguagem de programação a ser usada se chama C++. Como indica o nome, essa linguagem é uma extensão à linguagem C, de forma a aderir ao paradigma de orientação a objetos. Como esse assunto será visto em profundidade na 4a fase, na disciplina de POO (Programação Orientada a Objetos), faremos um uso mais superficial dessa linguagem. Quer dizer, usaremos algumas de suas construções, mas não nos deteremos em seus aspectos teóricos. O objetivo de usar C++ é introduzir essa linguagem, que será usada em próximas disciplinas.

• Uma breve apresentação da linguagem C++

Mas o que tem de especial a linguagem C++ ? Muita coisa, se comparada à linguagem C. Veja este exemplo sobre string em ambas linguagens:

Linguagem C	Linguagem C++
#include <stdio.h> #include <string.h> int main() { char nome[32], sobrenome[32]; char nomeCompleto[64]; printf("Nome: "); scanf("%32s", nome); printf("Sobrenome: "); scanf("%32s", sobrenome); strcpy(nomeCompleto, nome); strcat(nomeCompleto, " "); strcat(nomeCompleto, sobrenome); printf("Nome completo: %s\n", nomeCompleto); return 0; }	#include <iostream> #include <string> using namespace std; int main() { string nome, sobrenome, nomeCompleto; cout << "Nome: "; cin >> nome; cout << "Sobrenome: "; cin >> sobrenome; nomeCompleto = nome + " " + sobrenome; cout << "Nome completo: " << nomeCompleto << endl; }

Obs: para compilar o programa C++, grave-o em um arquivo com extensão .cpp ou .cc e compile-o assim (supondo que o arquivo se chame main.cpp):

g++ -std=c++11 -o exemplo main.cpp

Esse exemplo mostra algumas diferenças entre as linguagens:

• strings em C++ são representadas por variáveis do tipo string. Valores string podem ser concatenados com o operador +.
• A leitura de dados do console (entrada padrão) se faz por meio da variável predefinida cin (console input). Essa variável cin funciona como um arquivo somente leitura, e é similar a stdin da biblioteca C padrão. No exemplo, a leitura formatada se faz por meio do operador >> (operador leitura). Outras formas de ler dados serão vistas mais adiante na disciplina.
• A escrita de dados no console (saída padrão) se faz por meio da variável predefinida cout (console output). Essa variável também funciona como um arquivo, porém somente escrita, e é similar a stdout da biblioteca C padrão. A escrita formatada de dados se faz por meio do operador << (operador escrita). Outras formas de escrever dados serão vistas mais adiante.

Esses e outros detalhes diferem entre as linguagens C e C++, mas a principal diferença entre elas reside no paradigma de programação com que foram concebidas. A linguagem C segue o paradigma de programação estruturada, e C++ segue o paradigma de orientação a objetos. Em C++, um programa é pensado como um conjunto de objetos que se relacionam com o objetivo de apresentar a solução imaginada.

• Mais sobre objetos

Para ter um primeiro contato com classes e objetos, vamos criar alguns pequenos programas.

Um exemplo com números complexos

Números complexos são compostos por uma parte real e outra imaginária. Eles possuem grande aplicação na Física e Engenharias, incluindo em Telecomunicações (como vocês verão). No entanto, as linguagens de programação não costumam definir um tipo de dados para números complexos (Python é uma exceção !).

O primeiro exemplo sobre classes e objetos visa criar números complexos. Para o propósito do exemplo, um número complexo tem partes real e imaginária do tipo double, e apresenta operações para calcular o módulo e ângulo para forma polar.

Linguagem C

Linguagem C++

#include <math.h> struct Complexo { double r, i; }; double modulo(struct Complexo * z) { return sqrt(z->r*z->r + z->i*z->i); } double angulo(struct Complexo * z) { return atan(z->i / z->r); }

#include <math.h> class Complexo { // os atributos de um número complexo: suas partes real e imaginária private: double r, i; // partes real e imaginária public: // construtor: método para criação de um número complexo Complexo(double rr, double ii) { r = rr; i = ii; } // métodos para obter cópias dos valores dos atributos do número complexo double real() const { return r;} double imaginario() const { return i;} // métodos para obter módulo e ângulo da forma polar double modulo() const { return sqrt(r*r + i*i); } double angulo() const { return atan(i/r); } };

Uma vez tendo declarado a classe Complexo, podem-se criar objetos dessa classe e usá-los em programas:

Linguagem C	Linguagem C++
#include <stdio.h> #include "complexo.h" int main() { struct Complexo z = {1, 1}; printf("Parte real: %lg\n", z.r); printf("Parte imaginaria: %lg\n", z.i); printf("Forma polar: modulo=%lg, angulo=%lg\n", modulo(&z), angulo(&z)); }	#include <iostream> #include "complexo.h" using namespace std; int main() { Complexo z(1,1); // "z" é um objeto da classe Complexo cout << "Parte real: " << z.real() << endl; cout << "Parte imaginaria: " << z.imaginario() << endl; cout << "Forma polar: modulo=" << z.modulo(); cout << ", angulo=" << z.angulo() << endl; }

Compile os exemplos e execute-os para vê-los em funcionamento. Em seguida, experimente fazer pequenas modificações na versão em C++. Por exemplo, tente acessar diretamente os atributos do objeto z (tente acessar z.r ou z.i).

O exemplo é muito simples, e pode-se questionar o que se ganha escrevendo-o usando classe e objetos. Essa questão poderá ser retomada quando os programas forem um pouco maiores ou mais complexos ... O próximo exemplo também é simples, mas possui alguns requisitos a mais. Afinal, ele faz alguma coisa aparentemente útil ;-)

Uso do NetBeans

Na disciplina recomenda-se usar o ambiente integrado de desenvolvimento (IDE - Integrated Development Environment) NetBeans. Esse software auxilia na escrita de programas, pois integra um editor de texto, um gerenciador de projetos, compilador e depurador, além de ajuda on-line e outras facilidades. Os exemplos durante a disciplina serão disponibilizados como projetos do NetBeans, mas não é obrigado utilizá-lo - pode-se trabalhar diretamente com um editor de textos (ex: gedit) e o compilador C++ (g++) e depurador (gdb), porém isso é um pouco mais trabalhoso ...

Para instalar o NetBeans siga estes passos:

1. Certifique-se de que possui a máquina virtual Java instalada. Execute este comando em um terminal:

   $ java -version
   java version "1.8.0_121"
   Java(TM) SE Runtime Environment (build 1.8.0_121-b16)
   Java HotSpot(TM) 64-Bit Server VM (build 25.51-b03, mixed mode)
   $
   

2. Se não tiver o Java instalado, faça o seguinte:
   • Faça o download do instalador, escolhendo a versão adequada para o seu Linux (deve ser um arquivo .tar.gz para a versão do seu sistema operacional, se 32 ou 64 bits).
   • Descompacte o arquivo do instalador dentro do seu diretório pessoal. Note que deve aparecer uma pasta chamada jre1.8.0.121 ou algo parecido).
   • Inclua esta linha ao arquivo .profile que existe em sua pasta pessoal, substituindo a versão do Java se necessário (use um editor de texto, como o gedit):

     export PATH=${PATH}:${HOME}/jre1.8.0.121/bin
     

   • Saia da sua conta (encerre a sessão), e em seguida entre novamente.
3. Faça o download do instalador do Netbeans:
   • Instalador do Netbeans 8.2 no servidor de Tele
   • Instalador do Netbeans 8.2 no site oficial
4. Execute o instalador em um terminal de texto. Supondo que o download foi realizado na pasta Download:

   $ bash Download/netbeans-8.2-cpp-linux-x64.sh
   

5. Siga as instruções de instalação.

Exercícios

Resolva os três primeiros exercícios existentes na página da disciplina do Moodle.

OBS: para se inscrever no Moodle, faça o login com seu usuário e senha do Portal do Aluno. Em seguida, solicite a autoinscrição, fornecendo a chave de inscrição mr.robot quando pedida.

O que foi usado da C e C++ para resolver os exercícios:

• classe string, e seus métodos:
  • size para saber seu comprimento
  • [/ operador []] para acessar um caractere de uma certa posição.
  • front: para acessar o primeiro caractere
  • back: para acessar o último caractere
  • pop_back: para remover o último caractere
  • erase: para remover caracteres a partir de uma certa posição
• função toupper (para converter caractere para maiúsculo)
• argumentos de linha de comando: parâmetros argc e argv da função main

28/07: Introdução a C++

• Introdução a C++

Hoje continua-se a introdução a linguagem C++ de forma a explorar classes e objetos.

Jogo da Forca

• Jogo da Forca (wikipedia)

O jogo da Forca é um jogo em que se tenta adivinhar uma palavra letra a letra. Um jogador escolhe uma palavra, e informa quantas letras ela possui. Outro jogador tenta descobrir a palavra, informando sucessivamente letras que imagina pertencer à palavra. Cada letra que não exista na palavra implica uma penalidade, acrescentando uma parte do corpo à forca, como ilustrado na figura a seguir. Se o corpo na forca ficar completo, o desafiador perde a partida.

Esse jogo pode ser facilmente implementado como um programa. Basicamente ele trata de manipulação de string e caracteres.

O jogo da Forca em linguagem C++

• Introdução a string em C++

A tarefa desta aula anterior envolve implementar o jogo da Forca em linguagem C++. A versão em C++ pode explorar os recursos dessa linguagem, tais como classes e objetos (principalmente string). Um bom ponto de partida é primeiro definir um protótipo que seja o mais simples posśivel, porém que contenha as características essenciais do jogo.

#include <iostream>
#include <string>

using namespace std;

int main() {
    string palavra = "abacaxi"; // a palavra a ser descoberta
    string incompleta = "_______"; // a parte da palavra que já está revelada
    int tentativas = 7; // a quantidade de erros que podem ser cometidos

    // abaixo deve-se escrever o algoritmo do jogo ...
}

Um início de implementação do jogo da Forca em C++

Uma solução para o jogo da Forca

TAREFA para dia 03/08

Implemente o jogo da Forca em linguagem C++. Sua implementação pode ser testada nesta atividade no Moodle.

03/08: Introdução a C++: exercícios

• Introdução a C++

Continuação dos exercícios da aula anterior. E mais alguns ... ver no Moodle.

04/08: Projeto 1: um enumerador de arquivos

Os discos de um computador contêm usualmente milhares de arquivos, contando arquivos de sistema e de usuários. Por exemplo, o diretório pessoal do professor em seu computador no IFSC têm pouco mais de 254 mil arquivos, e o seu computador como um todo possui 636274 arquivos. Essa grande quantidade de arquivos está distribuída em muitos subdiretórios (??? no caso do computador pessoal do professor). A listagem ou enumeração de arquivos a partir de um dado subdiretório pode ser útil em algumas situações, tais como backups e buscas de arquivos, e para isso tornam-se necessários programas utilitários especializados.

O projeto 1 tem como objetivo a criação de um programa enumerador de arquivos. Esse programa deve listar os arquivos abaixo de um dado subdiretório de acordo com alguns critérios:

• extensão (ex: pdf, doc, txt, html, ...)
• tipo (arquivo regular, programa, diretório, link simbólico, ...)

A listagem deve ser feita a partir de um subdiretório, sendo realizada de forma recursiva. Isso significa que a busca deve ser feita também dentro dos subdiretórios ali contidos, independente da quantidade de resultados.

O enumerador de arquivos deve ser implementado usando a classe Diretorio. Objetos dessa classe possibilitam listar diretórios, obtendo descrições dos arquivos e subdiretórios ali contidos. A declaração dessa classe pode ser vista a seguir:

A classe Diretório

#ifndef DIRETORIO_H #define DIRETORIO_H #include <sys/types.h> #include <dirent.h> #include "tipos.h" // classe que representa diretórios class Diretorio { public: // construtores // cria um diretório associado ao diretório atual Diretorio(); // cria um diretório com caminho "pathname". Se caminho // não existir, ou não puder ser acessado, dispara uma // exceção de valor inteiro Diretorio(const string & pathname); // cria um diretório com caminho "pathname". Se caminho // não existir ou não puder ser acessado, e block for false, // dispara uma exceção de valor inteiro. // se block for true, tenta criar o diretório (se não // conseguir, dispara a exceção) Diretorio(const string & pathname, bool criar); Diretorio(const Diretorio& orig); // destrutor virtual ~Diretorio(); // operador de atribuição Diretorio& operator=(const Diretorio & orig); // muda de diretório void muda(const string & pathname); // retorna a quantidade de entradas neste diretório unsigned int entradas() const; // retorna o caminho deste diretório string caminho() const { return path;} // retorna o caminho absoluto deste diretório string caminho_absoluto() const; // métodos para listar um diretório // inicia a listagem: deve ser invocado em primeiro lugar // se diretório não existir, ou não puder ser acessado, // dispara uma exceção de valor inteiro void inicia_listagem(); // obtém próxima entrada de diretório // se não houver iniciado a listagem, ou listagem // chegou ao fim, dispara uma exceção de valor inteiro Entrada proximo(); // testa se listagem chegou ao fim bool fim_listagem() const; private: // atributos da classe: cada objeto desta classe // possui estes três atributos string path; DIR * dir; dirent * dent; }; arquivo Diretorio.h

A estrutura do enumerador pode ser visualizada nesta figura. Ela mostra que o programa pode ser entendido como uma composição de quatro partes (ou módulos). Cada módulo é responsável por uma funcionalidade específica, e isso foi pensado para simplificar a resolução do projeto. Os módulos Diretorio e Prglib já foram fornecidos. O primeiro fornece a classe Diretorio, necessária para listar e navegar por diretórios. A segunda oferece uma implementação de algumas estruturas de dados que podem ser úteis na solução.

Os arquivos contendo as declarações e implementações desses módulos, incluindo exemplos de como utilizá-los, estão disponíveis em um arquivo de projeto Netbeans:

• Arquivo de projeto Netbeans para o Enumerador

Pode-se importar esse arquivo de projeto no Netbeans por meio do ítem de menu Arqivo->Importar. De forma alternativa, podem-se compilá-los diretamente na linha de comando:

1. Descompacte o arquivo de projeto
2. Entre no diretório do projeto. Ex:

   cd Enumerador
   

3. Compile o programa exemplo:

   make
   

4. Execute o programa exemplo, que está em dist/Debug/GNU-Linux/. Ex:

   dist/Debug/GNU-Linux/enumerador
   

O início do projeto 1 começa com uma demonstração dos módulos que já estão prontos.

Atividade

1. Use a classe Diretorio para listar um diretório qualquer. Mostre os nomes dos arquivos e subdiretórios ali existentes.
2. Modifique o programa anterior para listar cada um dos subdiretórios encontrados.
3. Modifique o programa para identificar os arquivos que possuem um determinado nome.
4. Modifique o programa para identificar os arquivos que possuem uma determinada extensão.

A localização de arquivos e subdiretórios

A enumeração de arquivos implica percorrer todos os subdiretórios abaixo do diretório inicial. Os subdiretórios se relacionam em uma estrutura chamada árvore, como mostrado na figura a seguir. A busca por arquivos em um subdiretório deve ser feita por algum algoritmo que consiga visitar cada subdiretório e conferir se ali tem o arquivo procurado. Essa busca pode ser feita um nível por vez (busca em largura), ou visistando uma ramificação por completo a cada vez (busca em profundidade). Por exemplo, na figura a seguir, a busca em largura a partir do subdiretório /home implica visitar esses subdiretórios: /home, /home/jane, /home/will, /home/zeb, /home/will/work, /home/will/play. A busca em profundidade seguiria esta ordem: /home, /home/jane, /home/will, /home/will/work, /home/will/play, /home/zeb.

Sendo assim:

• Como se poderia implementar um algoritmo de busca em largura ?
• Como se poderia implementar um algoritmo de busca em profundidade ?

10 e 11/08: Projeto 1: uso de filas e pilhas para percorrer os diretórios

A busca de arquivos pelos subdiretórios pode ser feita usando algoritmos de busca em profundidade e busca em largura. O primeiro tipo pode ser implementado usando uma fila, e o segundo usando uma pilha. A aula de hoje introduz essas estruturas de dados.

Filas

• Uma aplicação de filas em roteadores

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

A declaração da Fila na biblioteca Prglib é esta:

template <typename T> class fila : public std::queue<T> {
public:
    fila(unsigned int N);
    fila(const fila<T>& orig);
    virtual ~fila();
    fila<T>& operator=(const fila<T> & outra);
    void enfileira(const T & algo);
    T desenfileira();
    const T & frente() const;
    bool vazia() const;
    bool cheia() const;
    unsigned int comprimento() const;
    unsigned int capacidade() const;
private:
    unsigned int N;
};

Arquivo libs/fila.h

... e um exemplo de uso é mostrado a seguir:

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

using namespace std;

int main() {
  // uma fila com capacidade de armazenar 20 inteiros
  prglib::fila<int> numeros(20);

  // uma fila com capacidade de armazenar 20 string
  prglib::fila<string> coisas(20);

  numeros.enfileira(6);
  numeros.enfileira(8);
  numeros.enfileira(10);
  numeros.enfileira(12);

  coisas.enfileira("banana");
  coisas.enfileira("graviola");
  coisas.enfileira("sapoti");
  coisas.enfileira("siriguela");
  coisas.enfileira("caju");

  cout << "Fila de numeros tem comprimento=" << numeros.comprimento() << endl;
  cout << "Fila de string tem comprimento=" << coisas.comprimento() << endl;

  while (not numeros.vazia()) {
    cout << "Numero: " << numeros.desenfileira() << endl;
  }

  while (not coisas.vazia()) {
    cout << "String: " << coisas.desenfileira() << endl;
  }
}

Exercícios

1. Resolva os seguintes exercícios sobre filas:
   • Enfileirador de caracteres
   • Fila de substrings
   • Filtro de fila
   • Concatenador de filas

Pilhas

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

A declaração da Pilha na biblioteca Prglib é esta:

template <typename T> class pilha : public std::stack<T> {
 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:
  unsigned int N;
};

Arquivo libs/pilha.h

... e um exemplo de uso é mostrado a seguir:

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

using namespace std;

int main() {
  // uma pilha com capacidade de armazenar 20 inteiros
  prglib::pilha<int> numeros(20);

  numeros.push(6);
  numeros.push(8);
  numeros.push(10);
  numeros.push(12);

  cout << "Pilha de numeros tem comprimento=" << numeros.comprimento() << endl;

  while (not numeros.vazia()) {
    cout << "Topo da pilha: " << numeros.top() << endl;
    cout << "... desempilhou: " << numeros.pop() << endl;
  }

}

Atividade

1. Resolva os exercícios sobre uso de pilhas e filas que estão no tópico Etapa 1 no Moodle.

Dica para o exercício sobre linhas de um arquivo

#include <fstream> #include <string> using namespace std; int main(int argc, char * argv[]) { // abre o arquivo cujo nome é dado por argv[1] ifstream arq(argv[1]); // se arquivo não foi aberto (algum erro ?) // mostra um alerta e termina o programa if (not arq.is_open()) { cout << "arquivo invalido" << endl; return 0; } // Este laço lê todas as linhas do arquivo // Cada repetição do laço corresponde a uma nova linha lida string linha; while (getline(arq, linha)) { // faz algo com a linha } return 0; }

17/08: Projeto 1: Algoritmos de busca do localizador

Na aula anterior se apresentaram os algoritmos de busca em largura e de busca em profundidade. O localizador deve ser implementado usando ambos algoritmos, para investigar se existe diferença em seus desempenhos (ex: o tempo total de busca).

Algoritmo para busca em largura

parâmetros de entrada: caminho: caminho do subdiretório onde se inicia a busca nome: nome ou parte do nome a serem procurados resultado: conjunto de arquivos ou subdiretório que satisfazem o critério de busca Início: Cria uma fila "q" capaz de armazenar string enfileira "caminho" em "q" enquanto fila "q" não estiver vazia faça desenfileira um caminho de "q" para cada entrada existente no caminho desenfileirado faça se entrada for um subdiretório, enfileire-o em "q" se entrada contiver "nome", acrescente-a ao resultado fimPara fimEnquanto devolva o resultado contendo as entradas que satisfizeram o critério de busca Fim

Algoritmo para busca em profundidade

parâmetros de entrada: caminho: caminho do subdiretório onde se inicia a busca nome: nome ou parte do nome a serem procurados resultado: conjunto de arquivos ou subdiretório que satisfazem o critério de busca Início: Cria uma pilha "p" capaz de armazenar string empilha "caminho" em "p" enquanto pilha "p" não estiver vazia faça desempilhe um caminho de "p" para cada entrada existente no caminho desempilhado faça se entrada for um subdiretório, empilhe-a em "p" se entrada contiver "nome", acrescente-a ao resultado fimPara fimEnquanto devolva o resultado contendo as entradas que satisfizeram o critério de busca Fim

Atividade

1. Implemente os algoritmos de busca em largura e em profundidade
2. Compare os tempos de execução de suas implementações desses algoritmos. DICA: execute seu programa com o utilitário time. Ex (se estiver usando o Netbeans):

   time dist/Debug/GNU-Linux/enumerador
   

18/08: Projeto 1: conclusão

A aula de hoje está à disposição para esclarecimento de dúvidas sobre o projeto 1.

Exemplo de uso de argumentos de linha de comando
#include <iostream> using namespace std; int main(int argc, char * argv[]) { cout << "Quantidade de argumentos: " << argc << endl; for (int i=0; i < argc; i++) { cout << "argv[" << i << "]=" << argv[i] << endl; } return 0; }

Processamento dos argumentos de linha de comando

O processamento dos argumentos de linha de comando precisou ser implementado por cada equipe. Deve ter ficado evidente que esse tipo de processamento pode ser necessário em diferentes programas, e que boa parte dele pode ser generalizada. De fato existem bibliotecas que oferecem recursos para realizar o processamento dos argumentos:

• getopt: função da biblioteca C padrão
• Biblioteca Program_options: biblioteca composta por classes e funções (parte da suite C++ boost)
  • Um tutorial sobre como usar o processamento de argumentos com a biblioteca boost
  • Uma comparação entre getopt e boost (com exemplos)

Ambas opções acima são bastante utilizadas e completas. No entanto, por se pretenderem genéricas, apresentam alguns detalhes a serem bem compreendidos para que possam ser utilizadas (veja os manuais). Uma alternativa é esta pequena classe que processa os argumentos de forma simplificada:

• Argparse

A classe Argparse é capaz de processar argumentos com opções curtas e longas, com ou sem valores complementares. Algumas definições podem esclarecer isso:

• Opção curta: informada com uma única letra e precedida por um hífen. Ex: -f
• Opção longa: informada com duas ou mais letras e precedida por dois hífens. Ex: --tipo
• Opção com valor complementar: a opção pede um valor. Ex: -p /home, --tipo arquivo
• Opção sem valor complementar: nenhum valor deve ser acrescentado à opção. Ex: -b, --path.

Valores complementares de opções são sempre do tipo string. Opções sem valor complementar, chamadas de flag, possuem valor bool (true se opção aparece na linha de comando, false caso contrário).

A classe Argparse possui esta interface:

class Argparse {
public:
    Argparse();
    Argparse(const Argparse& orig);
    virtual ~Argparse();

    // Métodos para adicionar uma opção do tipo flag. Tal tipo de opção
    // não requer um valor a ser informado na linha de comando.
    // Ela é do tipo bool: se aparece na linha de comando seu valor é true,    
    // e, caso não apareça, seu valor é false.
    void add_flag(char shortoption);
    void add_flag(const string & longoption);
    
    // Métodos para adicionar uma opção do tipo flag com um valor
    // predefinido
    void add_flag(char shortoption, bool defval);
    void add_flag(const string & longoption, bool defval);
    
    
    // Métodos para adicionar uma opção comum. Tal tipo de opção
    // requer um valor a ser informado na linha de comando.
    // Ela é do tipo string: se aparece na linha de comando, a string que a sucede
    // se torna seu valor. Caso essa opção não apareça, seu valor é uma string vazia.
    void add_option(char shortoption);
    void add_option(const string & longoption);
    
    // Métodos para adicionar uma opção comum com um valor
    // predefinido    
    void add_option(char shortoption, const string & defval);
    void add_option(const string & longoption, const string & defval);
    
    // Métodos para obter o valor de uma opção comum
    string get_option(char shortoption) const;
    string get_option(const string & longoption) const;
    string operator[](const string & longoption) const;
    string operator[](char shortoption) const;

    // Métodos para obter o valor de uma opção do tipo flag
    bool get_flag(char shortoption) const ;
    bool get_flag(const string & longoption) const;
    
    // Método para obter os argumentos que não foram processados como
    // opções.
    string get_extra() const { return extra;}
    
    // Método para analisar os argumentos de linha de comando e extrair
    // as opções e seus valores contidos nesses argumentos. O vetor argv
    // corresponde ao parâmetro argv da função main. A análise das opções
    // é efetuada a partir da segunda posição do vetor (argv[1]).
    int parse(char * argv[]);
};

O programa a seguir ilustra o uso de Argparse, supondo um programa que tenhas as opções sem valor complementar -L, -P, e as opções com valor complementar -e, -p, --type.

#include <cstdlib>
#include <iostream>
#include "Argparse.h"

using namespace std;

/*
 * 
 */
int main(int argc, char** argv) {
    Argparse args;
      
    /* Demonstração do analisador de argumentos de linha de comando
     
     As opções contidas nessa demonstração são:
     
     -e EXTENSÃO 
     --type TIPO
     -p CAMINHO
     -L
     -P
     * 
     * Assim, o programa pode ser executado com qualquer combinação dessas opções,
     * as quais podem aparecer em qualquer ordem na linha de comando.
     */

    args.add_option('e');
    args.add_flag('L');
    args.add_flag('P', true);
    args.add_option('p');
    args.add_option("type", "file");
    
    int n = args.parse(argv);
    
    cout << "Identificou " << n << " opções" << endl;

    cout << "ext=" << args['e'] << endl;
    cout << "alg: largura=" << args.get_flag('L');
    cout << ", profundidade=" << args.get_flag('P') << endl;    
    cout << "path=" << args['p'] << endl;
    cout << "tipo=" << args["type"] << endl;
    cout << "extra=" << args.get_extra() << endl;
          
    return 0;
}

Entrega do projeto

• Prazo de entrega: 27/08/2017, 23:59 h
• Entrega feita no Moodle
• Pode ser feito por equipes de no máximo 03 alunos (ideal ser feito em dupla)
• Os critérios de avaliação podem ser visto na descrição da tarefa no Moodle

24/08: Projeto 2: um programa para acessar dados de IDH

O Índice de Desenvolvimento Humano (IDH) é um indicador desenvolvido pela ONU para identificar condições de vida, bem-estar e desenvolvimento humano em países e suas regiões. Isso possibilita enumerar os países de acordo com esse índice, como pode ser visto aqui:

• Lista de países por IDH

No caso do Brasil existe o IDHM, que adapta a metodologia de cálculo do IDH para os municípios. Os indicadores são:

• IDHM: IDH do município
• IDHM_E: IDH do município para educação
• IDHM_L: IDH do município para longevidade
• IDHM_R: IDH do município para renda

O projeto 2 propõe criar um programa que faça buscas de dados em uma tabela de IDHM. Essas buscas podem considerar diferentes dimensões, tais como ano de cálculo do IDHM, o IDHM em si ou seus subíndices, e inclusive a melhorias nesses índices ao longo do tempo. O programa deve usar como fonte de dados este arquivo CSV, que contém uma tabela de IDHM:

• Tabela de IDHM (compactado com bzip2)

Nesse arquivo, cada linha corresponde aos dados de um município separados por vírgulas. As colunas representam, nesta ordem: ANO,UF,Codmun6,Codmun7,Município,IDHM,IDHM_E,IDHM_L,IDHM_R. Um exemplo de uma linha do arquivo é apresentada a seguir:

1991,11,110001,1100015,ALTA FLORESTA D'OESTE,0.329,0.112,0.617,0.516

As buscas no arquivo envolvem trabalhar com conjuntos de dados, os quais devem poder ser acessados de forma arbitrária. Assim, filas e pilhas não servem para armazená-los no programa. Uma nova estrutura de dados se faz necessária para tornar mais fácil essa tarefa. Mas antes de estudá-la, deve-se entender como os dados do arquivo CSV podem ser lidos.

Atividade

• Arquivo de projeto do Netbeans para projeto 2

1. Modele a representação em software de cada registro do arquivo de IDHM. Um registro corresponde aos dados de um município contidos em uma linha. A representação em software pode ser um tipo de dados ou uma classe. Ex:

   struct IDHM {
     string municipio;
     int ano;
     int uf;
     float idhm;
     float idhm_e;
     float idhm_l;
     float idhm_r;
   };
   

   ... ou:

   struct IDHM {
     string municipio;
     int ano;
     int uf;
     float idhm;
     float idhm_e;
     float idhm_l;
     float idhm_r;
   
     // construtor sem parâmetros: não inicializa os campos
     IDHM() {
       // aqui nada precisa ser feito ... fica assim vazio mesmo
     }
   
     // construtor que inicializa os campos com os valores contidos na linha do tipo CSV
     IDHM(const string & linha) {
       // aqui deve-se implementar o processamento da linha,
       // para extrair os valores nela contidos, convertê-los e copiá-los
       // para os campos correspondentes desta struct
     }
   };
   

2. Escreva um programa capaz de ler as linhas do arquivo de IDHM e as transforme em valores do tipo de dados ou objetos da classe criados no ítem 1. Dica: você pode usar a função separa desenvolvida como exercício no Moodle.

25/08: Projeto 2: introdução a listas

• Um video introdutório da Khan Academy

Uma lista encadeada é uma estrutura de dados em que os dados são armazenados dinamicamente em memória, de forma a se organizarem em uma sequência. Cada dado é armazenado em um elemento da lista denominado nodo, que funciona como uma caixa onde se guarda esse dado. Assim, para cada dado armazenado na lista existe um nodo. Cada nodo possui uma referência ao próximo nodo da lista, formando uma sequência parecida com os vagões de um trem. A figura abaixo ilustra uma lista encadeada:

Uma lista possui algumas características:

• Os nodos são criados dinamicamente, à medida que for necessário. Assim, a quantidade total de memória usada para a lista depende da quantidade de dados nela armazenados (compare isso com um vetor ou matriz).
• A lista não precisa ocupar uma área de memória contígua: como nodos são alocados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos nodos em memória e sua ordem na lista (novamente compare isso com um vetor ou matriz).
• Não é possível indexar os nodos, por isso para acessar um nodo deve-se obrigatoriamente procurá-lo a partir do início ou fim da lista, seguindo cada nodo até chegar àquele procurado.
• Para adicionar um nodo, basta modificar a referência do nodo que o antecede na lista. Assim, não é necessário "empurrar" os nodos seguintes para frente (como seria o caso de um vetor).
• Para remover um nodo é a mesma coisa: basta modificar a referência de seu nodo antecessor. Assim, não é necessário "deslocar pra trás" os nodos seguintes (como seria o caso de um vetor).

As operações elementares de uma lista definem como dados podem ser adicionados, obtidos e removidos da lista, e também que informações sobre a lista podem ser obtidas. São elas:

• anexa: adiciona um dado ao final da lista
• insere: adiciona um dado em uma determinada posição da lista
• remove: remove um dado de uma determinada posição da lista
• obtem: obtém um dado de uma determinada posição da lista
• comprimento: obtém o comprimento da lista
• esvazia: esvazia a lista (remove todos os dados)

A biblioteca Prglib possui uma lista,cuja declaração é apresentada a seguir:

A lista encadeada da biblioteca Prglib

/* * File: lista.h * Author: msobral * * Created on 11 de Agosto de 2016, 08:56 */ #ifndef LISTA2_H #define LISTA2_H #include <cstddef> #include <ostream> #include <string> #include <list> #include <algorithm> #include <random> #include <memory> using std::shared_ptr; namespace prglib { template <typename T> class lista { public: //construtor: não precisa de parâmetros para criar uma nova lista lista(); // construtor de cópia lista(const lista &outra); // destrutor virtual ~lista(); // insere "algo" no inicio da lista void insere(const T & algo); // adiciona "algo" no final da lista void anexa(const T & algo); // insere "algo" em uma posição específica da lista void insere(const T & algo, int posicao); void insereOrdenado(const T & algo); // remove o dado que está na "posicao" na lista, e retorna // uma cópia desse dado virtual T remove(int posicao); // remove todos os dados que forem equivalentes a "algo" void retira(const T & algo); // estas duas operações são idênticas: retorna // uma referência ao dado que está na "posicao" na lista T& obtem(int posicao) const; T& operator[](int pos) const; // atribuição: torna esta lista idêntica à outra lista virtual lista& operator=(const lista<T> & outra); // compara duas listas: são iguais se tiverem mesmo comprimento // E todos os dados armazenados forem iguais e na mesma ordem bool operator==(const lista<T> & outra) const; // Retorna uma referência a um dado que seja equivalente a "algo" T& procura(const T &algo) const; // Procura todos os dados equivalentes a "algo", e os // anexa a "lista". Retorna uma referência a "lista". shared_ptr<lista<T>> procuraMuitos(const T &algo) const; lista<T> & procuraMuitos(const T &algo, lista<T> & lista) const; // retorna a quantidade de dados armazenados na lista int comprimento() const; // retorna true se lista estiver vazia bool vazia() const; // Esvazia a lista void esvazia(); // apresenta o conteúdo da lista no stream "out" void escrevaSe(std::ostream & out) const; void escrevaSe(std::ostream & out, const std::string & delim) const; // ordena a lista void ordena(); // iteração do início pro fim void inicia(); T & proximo(); bool fim() const; // ... e do fim pro início void iniciaPeloFim(); T & anterior(); bool inicio() const; // inverte a ordem nos nodos na lista void inverte(); // embaralha os dados de uma lista void embaralha(); // obtém uma sublista lista<T> * sublista(unsigned int pos1, unsigned int pos2) const; lista<T> & sublista(unsigned int pos1, unsigned int pos2, lista<T> & outra) const; };

Abaixo segue um exemplo de uso de algumas operações de uma lista:

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   main.cpp
 * Author: msobral
 *
 * Created on 20 de Fevereiro de 2017, 17:32
 */

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

using namespace std;
using prglib::lista;

int main(int argc, char** argv) {
    // cria uma lista de string
    lista<string> nomes;
    
    // anexa três dados ao final da lista
    nomes.anexa("manuel");
    nomes.anexa("maria");
    nomes.anexa("bilica");
    
    // mostra comprimento e conteúdo da lista
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
    
    // insere dado no início da lista
    nomes.insere("maneca");
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;

    // insere dado na posição 2 da lista
    nomes.insere("joaquim", 2);
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;

    // remove dado do início da lista
    nomes.remove(0);
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
    
    // remove dado da posição 2 da lista
    nomes.remove(2);
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
    
    // esvazia a lista
    nomes.esvazia();
    cout << "Comprimento: " << nomes.comprimento() << ", dados: ";
    nomes.escrevaSe(cout, ",");
    cout << endl;
        
    // ao final, lista é automaticamente destruída, e a memória utilizada
    // é liberada
    return 0;
}

Atividade

1. Faça os exercícios sobre listas que estão no Moodle, para se familiarizar com listas

31/08: Projeto 2: outras operações da lista

A lista encadeada da Prglib ofere outras operações além daquelas para adicionar, obter e remover dados. Duas outras operações são de grande utilidade:

• iteração: possibilita obter sucessivamente de forma eficiente os dados da lista;
• ordenamento: ordena os dados de forma eficiente

Iteração

Quando se necessitam acessar em sequência todos (ou uma boa parte) dos dados de uma lista, a melhor forma é por meio da operação de iteração. A lista é capaz de ser iterada por meio dos métodos inicia, proximo e fim. Esses métodos são usados em conjunto para acessar cada dado da lista sucessivamente, a partir do início da lista. O exemplo a seguir mostra como usá-los:

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

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração
  numeros.inicia();

  // enquanto não chegar ao fim da lista, continua a iteração
  while (not numeros.fim()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.proximo();

    cout << "Numero: " << algo << endl;
  }
}

Essa forma de percorrer os dados de uma lista é muito mais eficiente do que acessar os dados a partir de suas posições (usando o método obtem ou o operador []). Para ter uma ideia, percorrer uma lista com 10 dados é 10 vezes mais rápido com iteração. Se a lista tiver 100 dados, a iteração é 100 vezes mais rápida. Se a lista tiver 1000 dados, a uteração é 1000 vezes mais rápida, e assim por diante. O tempo que se leva para percorrer todos os dados com iteração é proporcional à quantidade de dados, porém se for usado o método obtem (ou operador []), o tempo necessário é proporcional ao quadrado da quantidade de dados.

A iteração pode ser feita também em sentido contrário se forem usados os métodos iniciaPeloFim, anterior, e inicio:

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

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração pelo fim da lista
  numeros.iniciaPeloFim();

  // enquanto não chegar ao início da lista, continua a iteração
  while (not numeros.inicio()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.anterior();

    cout << "Numero: " << algo << endl;
  }
}

Ordenamento da lista

A lista possui o método ordena, que ordena seus dados. O ordenamento é feito por um algoritmo com razoável eficiência, e isso é importante porque esse tipo de operação tem custo computacional considerável (pode ser proporcional ao quadrado da quantidade de dados se não for bem feito). O único requisito para ordenar uma lista é que os dados armazenados possuam uma relação de precedência. Em outras palavras, que possam ser comparados com operador < (menor que). O exemplo a seguir mostra o ordenamento de uma lista:

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

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // ordena a lista
  numeros.ordena();

  numeros.escrevaSe(cout);

  cout << endl;
}

01/09: Projeto 2: conclusão

Na apresentação do projeto 2, modelou-se cada informação do IDHM na forma de um novo tipo de dados:

struct IDHM {
  string municipio;
  int ano;
  int uf;
  float idhm;
  float idhm_e;
  float idhm_l;
  float idhm_r;
 
  // construtor sem parâmetros: não inicializa os campos
  IDHM() {}
 
  // construtor que inicializa os campos com os valores contidos na linha do tipo CSV
  IDHM(const string & linha) {
    // coisas ...
  }
};

struct IDHM

Com base nessa struct IDHM, criou-se um pequeno programa para experimentar ler as linhas do arquivo com dados do Idhm. Cada linha foi convertida para um valor do tipo IDHM:

int main(int argc, char** argv) {
    ifstream arq(argv[1]);
    
    if (not arq.is_open()) {
        cout << "Erro: " << argv[1] << " não pode ser aberto" << endl;
        return 0;
    }
    
    string linha;
    while (getline(arq, linha)) {
        // processa linha
        try {
            IDHM dado(linha);

            // faz algo com esse valor IDHM        
        } catch (...) {
            cout << "+++ Erro: " << linha << endl;
        }
    }
    return 0;
}

O próximo passo é experimentar armazenar todos os valores IDHM em uma lista. Asism, as operações do analisador de IDHM podem ser mais facilmente realizadas, pois os dados estarão facilmente acessíveis em memória.

Atividade

• Modifique seu programa para que, ao final da leitura do arquivo, todos os dados IDHM estejam armazenados em uma lista.

Ordenamento de tipos definidos pelo programador

• Sobrecarga de operador

Novos tipos e classes podem ser definidos pelo programador por meio de declarações struct e class. Tais novos tipos não possuem uma relação de precedência predefinida. Se não é possível comparar valores de um tipo de dados, para saber quem vem antes de quem, não é possível também ordenar uma lista que contém esses valores. A solução envolve definir como valores de um novo tipo devem ser comparados para esse propósito, e isso implica definir o operador < para esse novo tipo.

Em C++ é possível definir operadores, o que se chama sobrecarga de operador. No caso de um novo tipo de dados, a definição do operador < pode ser feita assim:

struct Conta {
  string nome;
  int gastos;
 
  // Definição do operador < feita para comparar o valor gasto
  bool operator<(const Conta & outro) {
      return gastos < outro.gastos;
  }

  // construtor vazio ...
  Conta() {
    gastos = 0;
  }

  Conta(const string & umNome) {
    // implementação do construtor do tipo Conta
    nome = umNome;
    gastos = 0;
  }
};

Exemplo de um tipo Conta, que representa o total gasto por uma pessoa em um estabelecimento.

O exemplo a seguir mostra como dois valores Conta poderiam ser comparados com o operador <:

  Conta c1("Manuel Silva");
  Conta c2("Bilica Maria");

  c1.gastos = 100;
  c2.gastos = 200;
  
  if (c1 < c2) {
    cout << c1.nome << " gastou mais que " << c2.nome << endl;
  } else {
    cout << c2.nome << " gastou mais que " << c1.nome << endl;
  }

A comparação dos valores Conta usando o operador <, que no exemplo é feita desta forma:

  if (c1 < c2) {

... é equivalente a esta (feito implicitamente pelo compilador):

  if (c1.operator<(c2)) {

Assim, se o operador < for definido para o tipo Conta, uma lista de Conta pode ser ordenada.

Atividade

• Resolva os exercícios sobre listas que estão no Moodle. Veja os exercícios que envolvem iteração e ordenamento.

Entrega do projeto

• Prazo de entrega: 11/09/2017, 23:59 h
• Entrega feita no Moodle
• Pode ser feito por equipes de no máximo 03 alunos (ideal ser feito em dupla)
• Os critérios de avaliação podem ser visto na descrição da tarefa no Moodle

14/09: Projeto 3: um programa para limpar dados redundantes

Leitura importantes:

• Modularidade, acoplamento e coesão
• Acoplamento, coesão e funcionalidades

Em aplicações que lidam com grandes quantidades de dados, informações redundantes não são aceitáveis. Considere-se o caso dos dados sobre IDHM do projeto 2, no qual o arquivo de dados que alimenta o sistema deve conter somente informações únicas. Se dados repetidos forem aceitos pelo sistema, os resultados de suas operações serão distorcidos ou mesmo incorretos. Sendo assim, a limpeza dos dados de entrada se torna uma função importante desse tipo de sistema.

Com o que foi estudado até o momento é possível limpar um arquivo de dados. Isso pode ser feito usando uma lista, porém há dúvida quanto à eficiência desse tipo de solução. O tempo para realizar uma limpeza pode ser muito alto, se comparado com a complexidade da tarefa.

Atividade

Seja este arquivo de dados:

• Dados sobre IDHM com redundâncias

... escreva um programa que use listas para limpar os dados. Meça o tempo necessário para que seu programa complete a limpeza. O arquivo de projeto do Netbeans a seguir pode ser usado como ponto de partida:

• Projeto 3

Tabela hash

Uma tabela hash é uma estrutura de dados feita para armazenar dados indexados. Ela é particularmente eficiente quando a quantidade de dados é muito menor que o espaço de índices, como mostrado na figura abaixo. Por dado indexado entende-se um dado que é associado a uma chave, a qual funciona como um índice para localizá-lo. Posto de outra forma, pode-se entender a tabela hash como um mapeamento entre chaves e dados. No exemplo do analisador, o dado é um log, e a chave pode ser a URL, o usuário, o IP, ou uma combinação deles. Além disso, a quantidade de dados, por maior que seja, é muito menor que todas as combinações de caracteres de URL, ou que a quantidade de possíveis endereços IP, e assim por diante. A ideia por trás da tabela hash é reduzir o espaço de índices, de forma que sua quantidade seja parecida com a dos dados indexados.

O espaço de chaves e a tabela hash (obtido do livro "Algoritmos, 2a. ed.", de T. Cormen et al)

Alguns exemplos de uso de tabelas hash na vida real:

• Cache de inodes em sistemas de arquivos no Linux
• Alguns usos, de acordo com a Wikipedia
• Matriz esparsa (aplicável em Física, Engenharia, e outras áreas)
• Tabela de rotas em roteadores Linux
• 5 Mitos sobre Tabelas Hash

A prglib possui uma implementação de tabela hash, mostrada a seguir:

template <typename T> class thash : public std::unordered_map<std::string,T> {
 public:
  // cria uma tabela hash com num_linhas linhas
  thash(int num_linhas);
 
  thash(const thash &outra); // construtor de copia
 
  // destrutor
  virtual ~thash();
 
  // adiciona um dado à tabela. Se já existir na tabela um par contendo a chave
  // "chave", o dado desse par deve ser substituído por "algo". Caso contrário,
  // um novo par deve ser adicionado à tabela.
  void adiciona(const std::string& chave, const T& algo);
 
  // remove a chave "chave" e o dado a ela associado.
  T remove(const std::string& chave);
 
  // retorna o dado associado a "chave"
  T& operator[](const std::string& chave);
  T& obtem(const std::string& chave);
 
  // retorna uma lista com as chaves existentes na tabela
  std::shared_ptr<lista<std::string>> chaves() const;
 
  // retorna uma lista com os dados existentes na tabela
  std::shared_ptr<lista<T>> valores() const;
 
  // retorna verdadeiro se "chave" existe na tabela
  bool existe(const std::string& chave) const;
 
  // esvazia a tabela
  void esvazia();
 
  // retorna a quantidade de dados (ou chaves) existentes na tabela
  unsigned int tamanho() const;
 
 private:
  unsigned int linhas; // a quantidade de linhas da tabela
};

A seguir há um exemplo de uso da tabela hash:

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

using namespace std;
using prglib::thash;
using prglib::lista;

/*
 * 
 */
int main(int argc, char** argv) {
    // cria uma tabela com 5 linhas
    thash<long> tab(5);
    
    // adiciona dados à tabela: primeiro parâmetro é a chave, e segundo é 
    // o valor a ela associado
    tab.adiciona("um", 1);
    tab.adiciona("dois", 2);
    tab.adiciona("tres",3);
    
    // mostra os valores armazenados
    cout << tab["um"] << endl;
    cout << tab["dois"] << endl;
    cout << tab["tres"] << endl;
    
    // obtém uma lista com as chaves contidas na tabela.
    // Notar o uso de std::shared_ptr (smart pointer), que é um ponteiro
    // que libera automaticamente a memória apontada quando não mais necessária.    
    auto chaves = tab.chaves();
    cout << "Chaves: ";
    chaves->escrevaSe(cout, ", ");
    
    // Obtém uma lista com os valores contidos na tabela
    cout << endl;
    auto valores = tab.valores();
    cout << "Valores: ";
    valores->escrevaSe(cout, ", ");

    cout << endl;
    
    // Testa se uma determinada chave existe na tabela
    if (tab.existe("dois")) cout << "Tabela contém a chave: dois" << endl;
    else cout << "Tabela NÃO contém a chave: dois" << endl;
    
    // remove uma chave da tabela e, por consequência, o valor a ela associado
    tab.remove("dois");
    cout << "Removeu a chave: dois" << endl;
    
    // Testa se a chave removida ainda existe na tabela
    if (tab.existe("dois")) cout << "Tabela contém a chave: dois" << endl;
    else cout << "Tabela NÃO contém a chave: dois" << endl;

    return 0;
}

Atividade

1. Escreva um programa que conte quantas palavras diferentes existem em um arquivo. Seu programa deve ignorar maiúsculas e minúsculas
2. Escreva um programa que extraia as palavras repetidas de um arquivo. Quer dizer, esse programa deve mostrar como resultado apenas a primeira ocorrência de cada palavra de um arquivo
3. Reescreva o limpador de dados redundantes usando uma tabela hash. Compare o tempo de execução desse novo programa com a versão feita inicialmente com listas.

15/09: Projeto 3: exercícios sobre tabela hash

Na aula de hoje alguns exercícios sobre tabela hash serão realizados.

Exercícios

1. Escreva um programa que conte quantas vezes cada palavra aparece em um arquivo
2. Escreva um programa que calcule o valor a ser pago por um cliente de um mercadinho em um determinado mês
3. Escreva uma classe cujos objetos verificam credenciais de usuários
4. Para cada uma das abordagens a seguir, escreva um programa que armazene os dados sobre IDHM em uma tabela hash:
   • O programa possibilita consultas rápidas a municípios
   • O programa possibilita consultas rápidas por estado (devem ser mostrados todos os municípios do estado)

ATENÇÃO: prova 1 !!!

A prova 1 deve ser realizada por meio do Moodle e INDIVIDUALMENTE. A descrição da prova está ao final da seção Etapa 1: Filas, Pilhas e Listas.

PRAZO: 24/09 23:59h

21/09: Projeto 3: o limpador de dados

• Dicas sobre escritas em arquivos

O projeto 3 trata de implementar um programa para acessar dados de um arquivo contendo informações sobre IDHM. No entanto, as informações sobre IDHM podem conter redundâncias, tais como municípios repetidos. O programa deve primeiro limpar os dados, evitando informações redundantes ou inconsistentes. Feito isso, o programa deve possibilitar consultas aos dados.

No Projeto 2 escreveu-se um programa para acessar dados sobre IDHM. As informações foram lidas de um arquivo, cujas linhas possuem este formato: ANO,UF,Codmun6,Codmun7,Município,IDHM,IDHM_E,IDHM_L,IDHM_R. As colunas ANO, UF, C odmun6, Codmun7 e Município são únicas para cada descrição de IDHM de um município específico. Sendo assim, não podem existir duas ou mais linhas com os mesmos valores para essas colunas, ou com valores inconsistentes.

Uma inconsistência se manifesta pela discrepância entre códigos de município (colunas Codmun6 ou Codmun7) e UF e Município. Por exemplo, estas duas linhas são inconsistentes:

1991,11,110001,1100015,ALTA FLORESTA D'OESTE,0.329,0.112,0.617,0.516
1991,11,110001,1100015,FLORESTOPOLIS,0.329,0.112,0.617,0.516 

... e estas duas também:

1991,11,110001,1100015,ALTA FLORESTA D'OESTE,0.329,0.112,0.617,0.516
1991,12,110001,1100015,ALTA FLORESTA D'OESTE,0.329,0.112,0.617,0.516 

No caso de redundância, as linhas repetidas devem ser retiradas do arquivo de dados. No caso de inconsistência, TODAS as linhas envolvidas devem ser retiradas do arquivo de dados e gravadas num arquivo de log. Se ao menos um problema com inconsistência ocorrer, o programa deve terminar e avisar o usuário sobre o problema. Nesse caso, o programa deve ter processado completamente o arquivo de dados antes de terminar, para poder alertar o usuário sobre todos os dados com problemas. Cabe ao usuário analisar o arquivo de log e selecionar as linhas com os dados corretos, e ao final copiá-las para o arquivo de dados. Quando o arquivo de dados estiver correto, uma nova execução do programa deve possibilitar consultas aos dados carregados.

O arquivo contendo os dados a serem carregados é este:

• Dados de IDHM com redundâncias e inconsistências

As consultas que podem ser feitas são:

• Por Município: devem-se apresentar os dados de IDHM do município para todos os anos em que existem esses dados. Se existir mais de um município com mesmo nome, os dados de todos esses municípios devem ser apresentados.
• Por Codmun6: devem-se apresentar os dados de IDHM do município associado com valor de Codmun6, para todos os anos em que existem esses dados.

OBS: podem-se usar uma ou mais tabelas hash para armazenar os dados.

O programa deve ter uma estrutura semelhante à do Projeto 2, sendo composto por um bloco Interface, um bloco Analisador, e a Prglib:

Atividade

Na aula de hoje pode-se trabalhar no desenvolvimento do projeto 3.

22/09: Projeto 3: conclusão

Leitura importantes:

• Aprenda a programar em 10 anos
• Modularidade, acoplamento e coesão
• Acoplamento, coesão e funcionalidades

A entrega do projeto deve ser feita por meio desta tarefa no Moodle.

• Prazo: 2/10/2017
• Equipes de até 3 pessoas

28/09: Projeto 4: um dicionário para auto-completar palavras

• POG

Diversos programas possuem a função auto-completar para auxiliar usuários na digitação de dados. Essa função tenta adivinhar a palavra ou termo em digitação, oferecendo sugestões para o usuário. Editores de texto, aplicativos de celular (ex: Whatsapp), e até o shell possuem esse tipo de função. Um programa com tal função precisa possuir uma relação de palavras e termos, os quais são comparados com o que o usuário digita para oferecer sugestões. Essa busca deve ser prática e rápida, pois cada novo caractere digitado limita as possíveis palavras oferecidas.

As palavras conhecidas pelo programa precisam estar armazenadas de forma conveniente. Para uma determinada sequência inicial de caracteres digitados, todas as palavras por eles iniciadas devem ser procuradas e apresentadas. Por exemplo, se o usuário tiver digitado ban, possíveis sugestões são banco, banana e bandeira. Além disso, o usuário poderia ter controle sobre quando as sugestões seriam oferecidas. Uma abordagem usual é apresentá-las quando o usuário teclar TAB. No caso de uma interface de texto, isso seria mais prático do que buscar uma lista de palavras e apresentá-las a cada tecla digitada.

As estruturas de dados vistas até o momento não facilitam a realização dessa tarefa: listas possibilitam buscas somente na força bruta, e tabelas hash associam uma única chave a um valor. Porém uma nova estrutura de dados chamada árvore binária pode ser útil para armazenar as palavras e facilitar as buscas.

Árvores binárias

• Árvores binárias

Uma nova estrutura de dados chamada árvore de pesquisa binária proporciona uma grande eficiência no tempo de busca de um dado. Ela também tem outras propriedades interessantes, e que são úteis para resolver diversos problemas. O projeto 4 deve se valer dessa estrutura de dados para armazenar os dados sobre a lista telefônica invertida.

Uma estrutura de dados que possibilita consultas rápidas se chama árvore. Tal estrutura mantém os dados organizados de forma hierárquica, o que reduz bastante a quantidade de comparações necessárias para se encontrar algum valor. Um exemplo é a árvore de diretórios, que organiza os arquivos em disco em diretórios que formam um diagrama hierarquizado. Esse tipo de estrutura é largamente utilizada em bancos de dados, e também possui diversas aplicações em muitas outras áreas de conhecimento (redes de computadores, análise combinatória, mapas digitais, sistemas de decisão, linguística, diagramas em geral).

Uma pequena árvore binária

Um exemplo de árvore é mostrado na figura acima. A hierarquia inicia em um nodo chamado de raiz. Os demais nodos são conectados de forma hierárquica, sem haver caminhos fechados. Cada nodo possui ramos que conectam os nodos um nível abaixo na árvore. Nodos que não possuem ramos são chamados de folhas. Uma árvore cujos nodos possuem no máximo dois ramos cada é chamada de árvore binária, sendo a árvore mais simples que se pode criar.

Árvore de Pesquisa Binária

• Árvore de pesquisa binária na Wikipedia

Uma árvore de pesquisa binária é um tipo especial de árvore binária usada para armazenar valores ordenáveis. Nesse tipo de árvore a seguinte propriedade é verificada em todos os seus nodos:

• valores anteriores àquele contido em um nodo ficam na árvore conectada ao ramo esquerdo.
• valores sucessores àquele contido em um nodo ficam na árvore conectada ao ramo direito.

Dois exemplos de árvores de pesquisa binárias são mostrados abaixo. No exemplo 1 armazenam-se strings na árvore, e no exemplo 2 armazenam-se números. Em ambos os casos a propriedade da árvore de pesquisa binária é verificada. Note que os valores à esquerda de um nodo são sempre antecessores ao valor desse nodo, e do lado direito são sempre sucessores. Com isso, a estrutura da árvore de pesquisa binária implicitamente ordena os valores armazenados, o que é útil para diversas aplicações.

Exemplo 1	Exemplo 2

Mas por que essa estrutura de dados é eficiente para armazenar a lista telefônica invertida ? Basicamente porque, ao hierarquizar os valores, é possível facilmente guardá-los de forma ordenada. Se a árvore estiver bem balanceada (isso é, tem a mesma quantidade de nodos a partir de ambos os ramos de cada nodo), cada comparação da busca divide a quantidade de nodos restante pela metade. Assim, a quantidade de comparações até localizar o valor procurado é limitada superiormente pela altura da árvore (a quantidade de ramos entre o nodo raiz e o nodo folha mais distante da raiz).

Para fins de comparação, seja o projeto 4 implementado com lista encadeada e árvore de pesquisa binária. O custo computacional para localizar um telefone em uma lista é $O(n)$, pois, no pior caso, cada telefone procurado pode ser comparado com todos os telefones existentes na lista. Se for usada uma árvore de pesquisa binária, esse custo pode ser $O(log_{2}n)$, contanto que certas propriedades da árvore sejam verificadas (isso será discutido mais adiante).

A árvore de pesquisa binária da prglib

• Arquivo de projeto do Netbeans

A biblioteca prglib possui uma árvore de pesquisa binária simplificada. Ela foi implementada como uma classe template, para que a árvore possa armazenar qualquer tipo de dado. No entanto, apenas tipos de dados ordenáveis podem ser armazenados (que possuem uma relação de precedência e implementem os operadores == e <). A árvore possui operações para adicionar, procurar e remover dados, para listar os dados em profundidade (in-order, pre-order e post-order) ou largura, para iterar os dados (apenas in-order), e para balanceamento AVL. A declaração dessa árvore está a seguir.

A árvore de pesquisa binária da prglib

template <typename T> class arvore { public: arvore(); arvore(const T & dado); virtual ~arvore(); // adiciona um dado à árvore void adiciona(const T& algo); // busca um dado na árvore T& obtem(const T & algo) const; // lista os dados da árvore na sequêcias in-order, pre-order, post-order // ou em largura void listeInOrder(lista<T> & result); void listePreOrder(lista<T> & result); void listePostOrder(lista<T> & result); void listeEmLargura(lista<T> & result); // retorna a quantidade de dados na árvore unsigned int tamanho() const; // retorna a altura da folha mais profunda unsigned int altura() ; // retorna o fator de balanceamento int fatorB() ; // balanceia a árvore arvore<T> * balanceia(); // balanceia a árvore até não poder mais reduzir sua altura arvore<T> * balanceia(bool otimo); // iterador da árvore (in-order) void inicia(); bool fim(); T& proximo(); // iterador reverso da árvore (in-order) void iniciaPeloFim(); bool inicio(); T& anterior(); // remove um dado T remove(const T & algo); // obtém uma referência ao menor dado T & obtemMenor() const; // obtém uma referência ao maior dado T & obtemMaior() const; // obtém uma lista com os dados menores ou maiores que algo void obtemMenoresQue(lista<T> & result, const T & algo); void obtemMaioresQue(lista<T> & result, const T & algo); // obtém todos valores entre "start" e "end" (inclusive) void obtemIntervalo(lista<T> & result, const T & start, const T & end); }; arvore.h

Um exemplo de uso de uma pequena árvore binária é este:

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

using namespace std;

using prglib::arvore;
using prglib::lista;

/*
 * 
 */
int main(int argc, char** argv) {

    arvore<int> * a = new arvore<int>(10);
    
    a->adiciona(5);
    a->adiciona(7);
    a->adiciona(2);
    a->adiciona(13);
    a->adiciona(11);
    a->adiciona(15);
        
    lista<int> l;
    a->listeInOrder(l);
    
    cout << "In-order: ";
    l.escrevaSe(cout, ", ");
    cout << endl;

    return 0;
}

Atividade

Resolva estes exercícios:

• Criação de uma árvore de pesquisa binária com topologia simples
• Ordenar lista com árvore

Feito esse aquecimento:

1. Crie uma árvore de pesquisa binária contendo as palavras deste arquivo.
2. Procure cada uma das palavras contidas na árvore. Meça quanto tempo levou para encontrá-las (média, menor e maior valor)
   1. Repita a medição, mas ao invés de guardar as palavras em uma árvore, guarde-as em uma lista.
   2. Repita a medição, mas ao invés de guardar as palavras em uma árvore, guarde-as em uma tabela hash.
   3. Compare os tempos gastos em cada caso ...

29/09: Projeto 4: ajustes finos

A eficiência das árvores de pesquisa binária para armazenar dados de forma que possam ser localizados rapidamente depende de como esses dados ficam distribuídos na árvore. Se a árvore estiver desequilibrada (desbalanceada), a eficiência nas buscas será reduzida. Hoje veremos alguns fatores relacionados ao balanceamento de árvores, e como garantir que uma árvore fique bem equilibrada.

Quão eficiente ficou sua árvore ?

Uma árvore fica mais eficiente se estiver balanceada. Isso significa que, para cada nodo da árvore, as alturas dos ramos esquerdo e direito diferem em no máximo uma unidade. Se uma árvore possuir essa propriedade, sua altura será minimizada e assim as buscas serão mais rápidas. Para entender porque, veja que uma árvore com altura h pode conter uma certa quantidade de nodos:

Altura	Nodos (máximo)	Exemplo
0	1
1	3
2	7
3	15

De forma geral, a quantidade máxima de nodos que cabem em uma árvore binária com altura h é dada por esta recorrência:

$N_{h}=1+2\cdot N_{h-1}$

... sendo que $N_{0}=1$. A recorrência acima pode ser escrita mais diretamente como:

$N_{h}=2^{h+1}-1$

Usando esta relação, pode-se descobrir qual a menor altura possível para uma árvore que contenha N nodos:

$h=-1+\lceil log_{2}(1+N)\rceil$

Na prática, as árvores que criamos não estão otimizadas. Porém iremos comparar as alturas dessas árvores com a altura mínima possível para ter uma ideia de quão eficientes elas são.

O cálculo da altura de uma árvore A pode ser feito segundo esta recorrência:

$h(A)={\begin{cases}0,{\text{if }}A_{esq}=NULL\land A_{dir}=NULL\\1+max(h(A_{esq}),h(A_{dir})),{\text{caso contrario}}\\\end{cases}}$

Fator de balanceamento

O fator de balanceamento é a diferença entre as alturas das árvores esquerda e direita, e pode ser calculado assim:

$F_{b}=altura(esquerda)-altura(direita)$

Se para todos os nodos da árvore $\lVert F_{b}<=1\rVert$, então a árvore está balanceada e nada precisa ser feito. Porém se para algum nodo $\lVert F_{b}>1\rVert$, então existe um desequilíbrio (má distribuição de nodos), o qual pode ser corrigido.

Criação de árvores balanceadas

Para criar uma árvore balanceada, pode-se fazer o seguinte:

• se a árvore for criada a partir de um conjunto de dados já disponível, uma boa técnica é embaralhar os dados e depois criar a árvore. Isso cria uma árvore aceitavelmente balanceada, se bem que não de forma otimizada. Um ajuste pode ser feito no balanceamento usando-se um algoritmo apropriado.
• se os dados forem acrescentados gradualmente à árvore,correções em seu balanceamento devem ser feitas periodicamente usando-se um algoritmo apropriado.

Em ambos os casos, um algoritmo de balanceamento é útil para fazer com que a árvore fique bem equilibrada. Um desses algoritmos é apresentado a seguir.

Balanceamento

• AVL Tree

Nos experimentos feitos até agora, as árvores de pesquisa binária apresentaram um bom desempenho tanto para serem criadas quanto para pesquisarem valores. Foi estudado que isso se deve a uma importante propriedade da árvore binária, que limita à altura da árvore a quantidade de operações de comparação em uma pesquisa qualquer. Como a altura é função do logaritmo da quantidade de nodos, ela tende a crescer muito lentamente com o aumento da quantidade de nodos da árvore (ex: uma árvore com pouco mais 2.3 milhões de nodos teria altura de pelo menos 21). Porém isso depende de os nodos estarem igualmente distribuídos dos dois lados da árvore. Em outras palavras, a árvore deve estar balanceada.

A árvore disponibilizada na prglib pode ser balanceada usando o algoritmo clássico AVL. Mas outras abordagens existem, tais como árvores vermelho-preto. A abordagem AVL é mais simples de implementar que RBT, porém a segunda funciona melhor para árvores que são frequentemente modificadas. Uma interessante comparação entre árvores AVL e Vermelho-Preto pode ser lida na Wikipedia:

Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. 
Not only does this make them valuable in time-sensitive applications such as real-time applications, 
but it makes them valuable building blocks in other data structures which provide worst-case 
guarantees; for example, many data structures used in computational geometry can be based on 
red–black trees, and the Completely Fair Scheduler used in current Linux kernels uses red–black 
trees.

The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more 
rigidly balanced than red–black trees, leading to slower insertion and removal but faster retrieval. 
This makes it attractive for data structures that may be built once and loaded without 
reconstruction, such as language dictionaries (or program dictionaries, such as the opcodes of an 
assembler or interpreter).

No caso da árvore da prglib, o balanceamento pode ser realizado por meio do método balanceia:

  // balanceia a arvore usando o algoritmo AVL. 
  // Retorna a raiz da nova arvore ... pois o algoritmo pode modificar a raiz.
  arvore<T> * balanceia();

  // Balanceia o melhor possivel a arvore. Executa o método ''balanceia()'' repetidas
  // vezes, até que a altura da árvore não mais reduza.
  arvore<T> * balanceia(bool otimo);

Um exemplo de como utilizá-lo é mostrado a seguir:

int main() {
  arvore<int> * arv = new arvore<int>(5);

  arv->adiciona(4);
  arv->adiciona(3);
  arv->adiciona(2);
  arv->adiciona(1);
  arv->adiciona(0);

  // a arvore "arv" está totalmente desbalanceada, tendo todos os nodos do lado esquerdo
  // Mostra seu fator de balanceamento e sua altura
  cout << "Altura: " << arv->altura() << endl;
  cout << "Fator de balanceamento: " << arv->fatorB() << endl;

  // balanceia a arvore
  arv = arv->balanceia();

  // Mostra novamente seu fator de balanceamento e sua altura
  cout << "Altura: " << arv->altura() << endl;
  cout << "Fator de balanceamento: " << arv->fatorB() << endl;

  // destroi a arvore
  delete arv;
}

Atividade

1. Crie a árvore que armazena as palavras contidas neste arquivo.
2. Investigue a altura e fator de balanceamento dessa árvore
3. Balanceie sua árvore, e verifique o novo fator de balanceamento e altura. Compare-os com a menor altura possível teoricamente.

05/10: Projeto 4: conclusão

Conclusão da função auto-completar. Hoje deve-se completar a modelagem da árvore de pesquisa binária usada para armazenar as palavras, e especificar o algoritmo de busca da lista de palavras que possuem um prefixo em comum. Finalmente, deve-se modelar o programa que demonstra a função auto-completar ... por exemplo, essa funcionalidade pode ser fornecida por objetos desta classe:

class Oraculo {
 public:
  // construtor: carrega as palavras contidas no arquivo
  Oraculo(const string & arquivo_de_palavras);

  // destrutor
  ~Oraculo();

  // adiciona mais palavras, as quais são lidas de um arquivo
  void adiciona_palavras(const string & arquivo_de_palavras);

  // adiciona mais palavras, as quais estão contidas em uma lista
  void adiciona_palavras(lista<string> & lista_de_palavras);

  // Busca todas as palavras que possuem o prefixo
  lista<string> busca(const string & prefixo);

 private:
  // atributos
 
};

Para ler caracteres do teclado à medida que são digitados (sem esperar pelo ENTER), baseiem-se neste exemplo:

int main(int argc, char** argv) {
    // configura o terminal para retornar imediatamente cada caractere digitado
    system("stty raw -echo icrnl opost");
    cout << "> ";
    while (true) {
        char caractere;
        
        cin.get(caractere);
        if (caractere == '\t') { // TAB
            cout << " !!!TAB!!! ";
        } else {
            if (caractere == 13 or caractere == 10) break;
            else cout << caractere;
        }
        cout.flush();
    }
    cout << endl;
    system("stty cooked echo");
}

A entrega do projeto 4 deve ser feita pelo Moodle:

• Projeto 4 no Moodle

Curiosidade: Árvores de expressão binária

Árvores binárias podem ter outras aplicações além de armazenar dados de forma a possibilitar buscas eficientes. A representação de expressões aritméticas e algébricas é outro uso de árvores. Essas expressões também possuem uma hierarquia, dada pela precedência de operadores, o que as torna passíveis de serem representadas por árvores. Uma vez transformada em uma árvore binária, uma expressão pode ser facilmente avaliada, obtendo-se seu resultado. Esse tipo de árvore é chamado de árvore de expressão binária.

Uma árvore de expressão binária para a expressão (a+b)*c+7

Note-se que ness tipo de árvore as folhas são operandos (constantes ou variáveis), e demais nodos são operadores aritméticos. A topologia da árvore deve respeitar a precedência dos operadores, para que o resultado da expressão possa ser obtido (isso se faz ao percorrê-la segundo in-order).

Árvores de expressão binária são úteis para resolver expressões fornecidas em tempo de execução. Por exemplo, uma calculadora pode permitir que o usuário digite uma expressão a ser calculada, que é lida portanto como uma string. Para resolvê-la, pode-se transformá-la em uma árvore binária, e então calculá-la. Assim, qualquer programa que precise resolver expressões fornecidas pelo usuário pode usar essa técnica para avaliá-las.

Avaliando uma expressão contida em um árvore binária

Uma árvore de expressão binária devidamente construída pode ser facilmente avaliada se for percorrida in-order. O algoritmo basicamente funciona assim:

algoritmo resolveExpressao(arvore):
  Entrada: uma arvore de expressão binária
  Saída: o resultado da expressão após sua avaliação
  Variáveis locais: operador (tipo caractere), resultado (tipo ponto flutuante)

  se arvore for vazia: retorne 0

  se arvore for folha: retorne valor da folha

  operador = raiz da arvore
  Escolha (operador):
    caso '+': 
      resultado = resolveExpressao(arvore esquerda) + resolveExpressao(arvore direita)
    caso '-': 
      resultado = resolveExpressao(arvore esquerda) - resolveExpressao(arvore direita)
    caso '*': 
      resultado = resolveExpressao(arvore esquerda) * resolveExpressao(arvore direita)
    caso '/': 
      resultado = resolveExpressao(arvore esquerda) / resolveExpressao(arvore direita)
    caso '%': 
      resultado = resolveExpressao(arvore esquerda) % resolveExpressao(arvore direita)
    caso '^': 
      resultado = resolveExpressao(arvore esquerda) ^ resolveExpressao(arvore direita)
  fim Escolha
  retorne resultado
fim resolveExpressao

Construção de uma árvore de expressão binária

A construção automática da árvore inicia com um vetor ou lista composta por um nodo (árvore que possui somente a raiz) para cada token da expressão. Em seguida, agrupar sistematicamente os nodos em árvores cujas raízes sejam operadores. Isso deve ser feito respeitando a precedência dos operadores. O funcionamento desse algoritmo pode ser visualizado pela seguinte sequência de diagramas, que mostra o agrupamento dos nodos de acordo com a precedência de operadores, até que no final haja somente uma árvore:

... e então ? Será que é fácil escrever tal algoritmo ?

Curiosidade: Radix tree (trie)

• Trie na Wikipedia

Um trie, ou radix tree, é um tipo de árvore em que as chaves não estão nos nodos e sim nas transições. A chave associada a cada nodo depende da posição do nodo em relação à raiz, tomando-se as transições necessárias para chegar a tal nodo. Valores podem estar associados a folhas e nodos de interesse. Esse tipo de árvore, que NÃO NECESSARIAMENTE É BINÁRIA, é útil para representar conjuntos de dados que podem ser pesquisados por seus prefixos. Exemplos de aplicações são tabelas de roteamento em roteadores e armazenamento de palavras de dicionário (em particular quando se desejam sugerir palavras a partir de suas letras iniciais).

A figura a seguir exemplifica um trie.

Exemplo de trie (obtido na Wikipedia)

Curiosidade: árvores binárias no kernel Linux

• Estruturas de dados disponíveis dentro do kernel Linux (cap. 6 do livro Linux Kernel Development, 3rd ed., de Robert Love, 2010)

Algumas estruturas de dados estão disponíveis para uso dentro do kernel Linux. Há filas, listas, tabelas hash e árvores binárias para ajudar no desenvolvimento tanto do kernel quanto de módulos e device drivers. Elas não se destinam ao desenvolvedor de aplicações, e sim a desenvolvedores do kernel (esperem a disciplina de SOP para entender melhor isso).

Com respeito a árvores binárias, destaca-se este parágrafo ao final do capítulo do livro:

If you need to store a large amount of data and look it up efficiently, consider a red-
black tree. Red-black trees enable the searching in logarithmic time, while still providing
an efficient linear time in-order traversal.Although more complicated to implement than
the other data structures, their in-memory footprint isn’t significantly worse. If you are
not performing many time-critical look-up operations, a red-black tree probably isn’t
your best bet. In that case, favor a linked list.

19/10: Etapa 2: a construção da prglib

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:

• Projeto Netbeans com a nova prglib
• Somente código-fonte da nova prglib

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

• Uma aplicação de filas em roteadores

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

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. Esse tipo de fila é chamado de fila circular, podendo ser imaginada como a figura a seguir:

Fila circular: os números são os índices do vetor que contém a fila

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 de forma a poder identificar o início e 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):

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. Desta forma, as operações de enfileiramento e desenfileiramento podem ser implementadas por algoritmos bastante simples e com baixo custo computacional.

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 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 std::queue<T> {
public:
    fila(unsigned int max_itens);
    fila(const fila<T>& orig);
    virtual ~fila();
    fila<T>& operator=(const fila<T> & outra);
    void enfileira(const T & algo);
    T desenfileira();
    const T & frente() const;
    bool vazia() const;
    bool cheia() const;
    unsigned int comprimento() const;
    unsigned int capacidade() const;
private:
    // qtde de dados na fila, e capacidade da fila
    unsigned int N, cap;

    // a área de memoria onde são armazenados os dados (um vetor)
    T * buffer;

    // posições do ínício e fim da fila
    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 (not 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, 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.

20/10: Avaliação 2

A 2a avaliação individual será realizada presencialmente nesta aula por meio do Moodle. Ela será composta de 5 questões valendo 100 pontos cada. O resultado da avaliação ajusta os conceitos dos projetos 3 e 4 da seguinte forma:

• 3 ou mais questões 100% corretas: os conceitos dos projetos 3 e 4 são aumentados em 2 pontos
• 2 questões 100% corretas: os conceitos dos projetos 3 e 4 são mantidos
• 1 questão 100% correta e outra questão com nota >= 50: os conceitos dos projetos 3 e 4 são reduzidos em 2 pontos
• demais resultados: os conceitos dos projetos 3 e 4 são anulados

26/10: Etapa 2: pilhas

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

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

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

09/11: Etapa 2: Listas encadeadas

Conforme visto no projeto 2, uma lista encadeada é uma estrutura de dados em que os dados são armazenados dinamicamente em memória, de forma a se organizarem em uma sequência. Internamente, cada dado é armazenado em um elemento da lista denominado nodo, que funciona como uma caixa onde se guarda esse dado. Assim, para cada dado armazenado na lista existe um nodo. Cada nodo possui uma referência ao próximo nodo da lista, formando uma sequência parecida com os vagões de um trem. A figura abaixo ilustra uma lista encadeada:

Para se acessar uma lista, basta conhecer a referência para seu primeiro nodo (contida em seus atributos, como mostrado na figura acima). A partir do primeiro nodo pode-se percorrer a lista, seguindo as referências para os nodos subsequentes. Com isso, qualquer nodo da lista pode ser acessado.

Uma lista possui algumas propriedades:

• Os nodos são criados dinamicamente, à medida que for necessário. Assim, a quantidade total de memória usada para a lista depende da quantidade de dados nela armazenados (compare isso com um vetor ou matriz).
• A lista não precisa ocupar uma área de memória contígua: como nodos são alocados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos nodos em memória e sua ordem na lista (novamente compare isso com um vetor ou matriz).
• Não é possível indexar os nodos, por isso para acessar um nodo deve-se obrigatoriamente procurá-lo a partir do início da lista, seguindo cada nodo até chegar àquele procurado.
• Para adicionar um nodo, basta modificar a referência do nodo que o antecede na lista. Assim, não é necessário "empurrar" os nodos seguintes para frente (como seria o caso de um vetor).
• Para remover um nodo é a mesma coisa: basta modificar a referência de seu nodo antecessor. Assim, não é necessário "deslocar pra trás" os nodos seguintes (como seria o caso de um vetor).

Listas simplesmente encadeadas

Um primeiro tipo de lista se chama simplesmente encadeada. Como diz seu nome, os nodos são encadeados de forma unidirecional. Pode-se percorrer a lista do primeiro em direção ao último nodo, mas não em direção contrária. A explicação apresentada na seção anterior focou nesse tipo de lista. Sua implementação no geral é mais simples.

Com base no que foi introduzido, a estrutura de dados lista pode ser definida da seguinte forma:

• atributos: pelo menos referências ao primeiro e ao último nodo
• operações: ao menos operações para adicionar, obter e remover dados da lista; mais especificamente:
  • anexa: adiciona um dado ao final da lista
  • insere: adiciona um dado em uma determinada posição da lista
  • remove: remove um dado de uma determinada posição da lista
  • obtem: obtém um dado de uma determinada posição da lista

A tradução dessa definição para a linguagem C++ pode ser vista a seguir:

Declaração e implementação da lista como uma classe template

template <typename T> class lista { public: //construtor: não precisa de parâmetros para criar uma nova lista lista(); // construtor de cópia lista(const lista &outra); // destrutor ~lista(); // insere "algo" no inicio da lista void insere(const T & algo); // adiciona "algo" no final da lista void anexa(const T & algo); // insere "algo" em uma posição específica da lista void insere(const T & algo, int posicao); void insereOrdenado(const T & algo); // remove o dado que está na "posicao" na lista, e retorna // uma cópia desse dado T remove(int posicao); // remove todos os dados que forem equivalentes a "algo" void retira(const T & algo); // estas duas operações são idênticas: retorna // uma referência ao dado que está na "posicao" na lista T& obtem(int posicao) const; T& operator[](int pos) const; // atribuição: torna esta lista idêntica à outra lista virtual lista& operator=(const lista<T> & outra); // compara duas listas: são iguais se tiverem mesmo comprimento // E todos os dados armazenados forem iguais e na mesma ordem bool operator==(const lista<T> & outra) const; // Retorna uma referência a um dado que seja equivalente a "algo" T& procura(const T &algo) const; // Procura todos os dados equivalentes a "algo", e os // anexa a "lista". Retorna uma referência a "lista". std::shared_ptr<lista<T>> procuraMuitos(const T &algo) const; lista<T> & procuraMuitos(const T &algo, lista<T> & lista) const; // retorna a quantidade de dados armazenados na lista int comprimento() const; // retorna true se lista estiver vazia bool vazia() const; // Esvazia a lista void esvazia(); // apresenta o conteúdo da lista no stream "out" void escrevaSe(std::ostream & out) const; void escrevaSe(std::ostream & out, const std::string & delim) const; // ordena a lista void ordena(); // iteração void inicia(); void iniciaPeloFim(); bool fim() const; bool inicio() const; T & proximo(); T & anterior(); // inverte a ordem dos dados da lista void inverte(); // embaralha os dados de uma lista void embaralha(); // obtém uma sublista lista<T> * sublista(unsigned int pos1, unsigned int pos2) const; lista<T> & sublista(unsigned int pos1, unsigned int pos2, lista<T> & outra) const; private: // declaração do tipo Nodo: privativa, porque // é de uso exclusivo da lista // Este Nodo visa uma lista duplamente encadeada struct Nodo { Nodo * proximo, * anterior; T dado; // construtor do Nodo: prático para uso nos métodos // da lista Nodo(const T & algo) { dado = algo; proximo = nullptr; anterior = nullptr; } }; // ponteiros para primeiro e último nodos Nodo * primeiro, * ultimo; // ponteiro para nodo atual da iteração Nodo * atual; // comprimento da lista long len; }; Arquivo libs/lista.h

OBS: a implementação dos métodos da lista está em libs/lista-impl.h.

Uma vez implementada essa lista básica, ela pode ser testada com este programa:

Programa para testar a lista
#include <iostream> #include <string> #include <prglib.h> using prglib::lista; using namespace std; int main() { lista<string> list; list.anexa("Uma"); list.anexa("coisa"); list.anexa("legal"); cout << "Comprimento: " << list.comprimento() << endl; for (int pos=0; pos < list.comprimento(); pos++) { cout << "Posicao " << pos; cout << ": " << list.obtem(pos) << endl; } }

Outros modelos de listas

Listas encadeadas podem ser implementadas com algumas variações. Duas delas bem conhecidas são:

• Lista duplamente encadeada: cada nodo aponta seu sucessor e antecessor. Esse tipo de lista facilita operações de inserção e remoção de nodos.

• Lista com guardas: guardas são nodos que não contém dados, mas servem para marcar lugares de interesse da lista. O caso mais comum é usar guardas no início e fim da lista, o que facilita a implementação de operações de inserção e remoção de nodos, pois essas operações não precisam tratar os casos último nodo ou primeiro nodo. Esse tipo de lista pode ser simplesmente ou duplamente encadeada.

CURIOSIDADE: como um processo usa a memória

Um processo, que é um programa em execução, usa memória para guardar tanto seus dados (variáveis e constantes) quanto suas instruções (o programa em si). A forma com que cada processo ocupa a memória depende do sistema operacional. No caso do Linux, o diagrama abaixo mostra de forma simplificada como um processo se organiza em memória (maiores detalhes no link abaixo da figura, e nas disciplina de Sistemas Operacionais da 5a fase ... e Microprocessadores da 4a fase também ajuda a entender essa questão).

Anatomia de um processo em memória
(obtido de http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/)

Segundo esse diagrama, um processo aloca regiões de memória para diferentes finalidades. Por exemplo, as instruções de programa ficam no segmento Text, as variáveis dinâmicas alocadas com malloc (linguagem C) ou operador new (C++) ficam no segmento heap, e as variáveis locais e argumentos de função ficam em stack.

Experimento: alocação de memória

Compile e use os dois programas a seguir para comparar as limitações na alocação de memória na pilha e no heap.

• Alocação na pilha
• Alocação no heap

Atividade

Implemente as operações da lista necessárias para que o programa de teste funcione.

10/11: Etapa 2: a lista encadeada

Hoje deve-se continuar a implementação da lista, acrescentando-se três novas operações:

• insere: inserem um dado em uma posição qualquer
• remove: remove um dado de uma posição qualquer
• esvazia: esvazia a lista

Todas as operações devem funcionar como esperado, sendo verificadas com este programa:

Um programa de teste para a lista: anexa, insere, obtem
#include <iostream> #include <string> #include <prglib.h> using prglib::lista; using namespace std; int main() { lista<string> list; list.anexa("Uma"); list.anexa("coisa"); list.anexa("legal"); list.insere("Mais"); cout << "Comprimento: " << list.comprimento() << endl; for (int pos=0; pos < list.comprimento(); pos++) { cout << "Posicao " << pos; cout << ": " << list.obtem(pos) << endl; } }

Outro programa de teste para a lista: anexa, insere, obtem, remove, esvazia

#include <iostream> #include <string> #include <prglib.h> using prglib::lista; using namespace std; void mostraLista(lista<string> & l) { int len = l.comprimento(); cout << "Comprimento: " << len << endl; int pos = 0; while (pos < len) { string algo = l.remove(0); l.anexa(algo); cout << "Posicao " << pos; cout << ": " << algo << endl; pos++; } } int main() { lista<string> l; l.anexa("coisa"); l.anexa("legal"); l.insere("Uma"); mostraLista(l); cout << endl; l.insere("muito", 2); mostraLista(l); cout << endl; string palavra = l.remove(2); cout << "Removeu: " << palavra << endl; mostraLista(l); cout << endl; l.esvazia(); cout << "Após esvaziar: " << endl; mostraLista(l); cout << endl; return 0; }

16/11: Etapa 2: continuação

Apresentação do conteúdo de uma lista

No programa de teste da seção anterior, foi adicionada uma função void mostraLista(lista<string> & l). Essa função simplesmente apresenta cada dado da lista em uma linha. Tal tipo de necessidade deve ser comum a diferentes programas que usam listas, portanto poderia se tornar uma operação da lista. Além disso, faz sentido que uma lista saiba se apresentar na tela ou gravar-se em um arquivo. Essa operação poderia ser definida como os seguintes métodos da classe lista:

// escreve em "out" o conteúdo da lista (um dado por linha)
void escrevaSe(ostream & out);

// escreve em "out" o conteúdo da lista (dados separados por "delimitador")
void escrevaSe(ostream & out, const string & delimitador);

... sendo o parâmetro ostream& out um arquivo aberto em modo escrita (cout serviria, por exemplo).

OBS: pode ser útil saber como funciona a sobrecarga de operadores em C++, uma vez que o operador << para objetos ostream (tais como cout e arquivos abertos para escrita) deve ser definido para tipos de dados e classes criados pelo usuário. Do contrário, escrevaSe não funcionará para esses tipos de dados.

Exercícios

1. Implemente o método escrevaSe
2. Modifique o programa de teste para que use o método escrevaSe

Iterador da lista

A iteração é uma forma de percorrer sucessivamente os dados de uma lista. A iteração inicia com o acesso ao primeiro dado, e próximas iterações retornam os dados seguintes, na ordem em que estão armazenados na lista. Isso é feito por meio de três operações da lista:

• inicia: inicia a iteração.
• proximo: retorna uma referência ao dado contido no nodo atual, e avança para o próximo nodo. Caso não exista nodo atual (i.e. seja o fim da lista), deve-se gerar uma exceção.
• fim: informa se a iteração chegou ao fim e, portanto, não há mais dados para retornar.

Para fazer a iteração, além de possuir essas novas operações a lista deve lembrar em que nodo a iteração está a cada momento. O atributo atual da classe lista serve exatamente para isso. Abaixo pode-se ver a classe lista, destacando-se somente os métodos e atributos usados na interação.

template <class T> class lista {
 public:
  // operações da lista

  // métodos envolvidos na iteração:

  // inicia uma iteração
  void inicia();

  // retorna uma referência ao próximo dado da iteração
  // se não houver mais dados, gera uma exceção
  T& proximo();

  // retorna verdadeiro se a iteração terminou (chegou ao fim da lista)
  bool fim() const;

 private: 
  // o nodo atual da iteração: este novo atributo torna possível
  // que a lista lembre em que nodo a iteração está a cada momento
  Nodo * atual;
  // demais atributos da lista
};

Note que a iteração implica fazer com que o novo atributo atual aponte sucessivamente os nodos da lista. Isso deve funcionar assim:

• após inicia() , o nodo atual é o primeiro nodo.
• se for executado proximo() em seguida, obtém-se uma referência ao dado contido no nodo atual (primeiro nodo), e ao final de sua execução atual aponta o segundo nodo da lista.
• se for executado proximo() novamente, obtém-se uma referência ao dado contido no nodo atual (segundo nodo), e ao final de sua execução, atual aponta o terceiro nodo da lista.
• ... e assim por diante.

Com isso, ao final a operação proximo() deve retornar uma referência ao dado guardado no nodo apontado por atual.

Uma vez existindo o iterador, podem-se percorrer os dados da lista como mostrado neste exemplo:

// encontra a menor string (por ordem alfabética)
string minimo(lista<string> & l) {
  if (l.comprimento() < 1) throw -1; // erro: lista vazia !

  l.inicia();
  string menor = l.proximo();
  
  while (not l.fim()) {
    string & dado = l.proximo();
    if (dado < menor) menor = dado;
  }
  return menor;
}

Outro exemplo usa o iterador para mostrar os dados da lista (com resultado igual ao do método escrevaSe):

void mostraLista(lista<string> & l, ostream & out) {
  l.inicia();
  
  while (not l.fim()) {
    string & dado = l.proximo();
    out << dado << endl;
  }  
}

Exercícios

1. Implemente o iterador da lista
2. Teste o iterador da lista com os programa exemplo mostrados nesta seção
3. Implemente o iterador reverso da lista, que itera os dados do fim para o início da lista. Os métodos envolvidos são: iniciaPeloFim, anterior e inicio (ver lista.h)

17/11: Etapa 2: ordenamento da lista

Listas armazenam conjuntos de dados e, usualmente, existe a necessidade de ordená-los. O ordenamento de uma lista pode ser realizado de diferentes maneiras, sendo apresentados aqui dois algoritmos elementares, porém ineficientes, e um terceiro algoritmo não tão simples, porém bastante eficiente.

Escolhendo a estratégia de ordenamento

• Um sumário de algoritmos de ordenamento na Wikipedia

Uma lista pode ser ordenada de mais de uma forma. Aqui veremos três formas de ordenamento:

• Algoritmo bubble-sort: aplica-se a uma lista já existente, e não requer memória adicional para ordená-la.
• Algoritmo selection-sort: parecido com bubble sort, porém com uma pequena melhoria que reduz um pouco o tempo de ordenamento.
• Algoritmo merge-sort: usa uma estratégia do tipo dividir-e-conquistar para acelerar o tempo de ordenamento. Divide uma lista ao meio sucessivamente, até que se gerem sublistas com apenas um dado. Em seguida, funde essas sublistas de forma ordenada.

Algoritmo de ordenamento bolha (bubble sort)

O algoritmo bubble sort usa a seguinte estratégia para ordenar uma lista (ou vetor):

• Desloca o maior valor em direção ao último nodo da lista
• Desloca o 2o maior valor em direção ao penúltimo nodo da lista
• Desloca o 3o maior valor em direção ao antepenúltimo nodo da lista
• ... e assim por diante

Uma animação do algoritmo, obtida no verbete Bubble Sort na Wikipedia

Esse algoritmo pode ser representado pelo seguinte pseudo-programa:

para j do fim da lista até o segundo nodo da lista
  para k do inicio da lista até o antecessor do nodo j
    se nodo k+1 < nodo k então troca os valores dos nodos k e k+1
  fim para
fim para

Exemplo que demonstra o bubble sort em C++, aplicado a um vetor de strings
#include <iostream> #include <string> using namespace std; int main() { string v[5] = {"zebra", "mamute", "leao", "tatu", "tainha"}; int j, k; for (j=4; j > 0; j--) { for (k=0; k < j; k++) { if (v[k+1] < v[k]) { // troca ! string aux = v[k]; v[k] = v[k+1]; v[k+1] = aux; } } } // mostrar o resultado for (j=0; j < 5; j++) cout << "v[" << j << "] = " << v[j] << endl; return 0; }

Bubble-sort é uma das forma mais simples de ordenar uma lista ou vetor (mas não a mais eficiente).

Algoritmo de ordenamento por seleção (selection sort)

O ordenamento por seleção se apresenta como uma variação do bubble sort. Ele usa esta abordagem:

• Identifica o menor valor a partir da 1a posição da lista e coloca-o na 1a posição
• Identifica o menor valor a partir da 2a posição da lista e coloca-o na 2a posição
• Identifica o menor valor a partir da 3a posição da lista e coloca-o na 3a posição
• Identifica o menor valor a partir da n-ésima posição da lista e coloca-o na n-ésima posição

Esse algoritmo poderia ser implementado de acordo com este pseudo-código:

para j do inicio da lista até o penúltimo nodo da lista
  menor = nodo na posição j
  para k da posicao j+1 até o fim da lista
    se valor do nodo k < valor do nodo menor então menor = nodo k
  fim para
  troca valores dos nodos j e menor
fim para

Exemplo que demonstra o ordenamento por seleção em C++, aplicado a um vetor de strings

#include <iostream> #include <string> using namespace std; int main() { string v[5] = {"zebra", "mamute", "leao", "tatu", "tainha"}; int j, k; for (j=0; j < 4; j++) { int menor = j; for (k=j+1; k < 5; k++) { if (v[menor] > v[k]) menor = k; } if (menor != j) { string aux = v[j]; v[j] = v[menor]; v[menor] = aux; } } // mostrar o resultado for (j=0; j < 5; j++) cout << "v[" << j << "] = " << v[j] << endl; return 0; }

Ele pode ser exemplificado pela figura abaixo, que mostra o ordenamento de uma lista ou vetor contendo 4 valores. As posições verdes correspondem à parte da lista que já está ordenada, e as posições vermelhas são os valores que estão sendo comparados; as setas entre posições vermelhas indicam quando deve ser feita uma operação de troca de valores.

Algoritmo de ordenamento por fusão (merge sort)

O algoritmo de ordenamento por fusão usa uma estratégia de dividir e conquistar da seguinte forma:

1. Subdivide-se uma lista em duas sublistas sucessivamente, até que se obtenha um conjunto de sublistas de comprimento 1.
2. Os pares de sublistas são fundidos sucessivamente, cuidando-se para que, após cada fusão, a sublista resultante esteja ordenada
3. Quando todas as sublistas tiverem sido fundidas, a lista resultante estará ordenada.

Este algoritmo pode ser implementado eficientemente para listas. A versão mostrada como exemplo a seguir se aplica a vetores. A versão adequada para listas pode ser bem melhor, explorando as ligações entre nodos e assim evitando cópias dos dados.

Exemplo de implementação em C++ para ordenar um vetor de string

#include <iostream> #include <string> using namespace std; // m: posicao inicial, n: posicao final void merge(string * v, int m, int n) { int meio; // descomente se quiser ver o inicio e fim de cada sublista //cout << m << "," << n << endl; // se fatia tem um elemento, retorna if (n == m) return; // divide em duas fatias. Observe que isso implica // chamar merge recursivamente meio = (n-m)/2; merge(v, m, m+meio); merge(v, m+meio+1, n); // funde as fatias, que estao ordenadas // a fusao eh feita em um vetor auxiliar // e depois copiada para o vetor principal string aux[n-m+1]; // k: indexa o vetor auxiliar, i: indexa a primeira fatia, // j: indexa a segunda fatia int i, j, k; for (k=0, i=m, j=m+meio+1; i <= m+meio and j <= n; k++) { if (v[i] < v[j]) { aux[k] = v[i]; i++; } else { aux[k] = v[j]; j++; } } // sobras da fusao devem ser anexadas ao vetor auxiliar for (; i <= m+meio; i++, k++) aux[k] = v[i]; for (; j <= n; j++, k++) aux[k] = v[j]; // copia o vetor auxiliar para o vetor principal for (k=0; k < (n-m+1); k++) v[m+k] = aux[k]; } int main() { string v[9] = {"zebra", "mamute", "leao", "tatu", "tainha", "anta", "anchova", "burro","gamba"}; int j, k; merge(v, 0, 8); // mostrar o resultado for (j=0; j < 9; j++) cout << "v[" << j << "] = " << v[j] << endl; return 0; }

Implementação dos ordenamentos na lista encadeada

A lista encadeada criada até o momento não possui todas as funcionalidades necessárias para que possa ser ordenada. Dependendo do algoritmo de ordenamento, algumas operações precisam ser implementadas.

Bubble Sort

O ordenamento bubble sort ordena uma lista já existente. Para implementá-lo, torna-se necessária a operação ordenaBolha, que efetua o ordenamento de uma lista. Essa operação pode ser declarada da seguinte forma:

// Método ordenaBolha: faz o ordenamento de uma lista usando bubble sort
void ordenaBolha();

Selection Sort

O ordenamento selection sort ordena uma lista já existente. Para implementá-lo, torna-se necessária a operação ordenaSelecao, que efetua o ordenamento de uma lista. Essa operação pode ser declarada da seguinte forma:

// Método ordenaSelecao: faz o ordenamento de uma lista usando bubble sort
void ordenaSelecao();

Merge Sort

No caso de Merge Sort, torna-se necessária um método privativo da lista para realizar a subdivisão e subsequente fusão de um trecho da lista. Sendo um método privativo, ele pode explorar os nodos para realizar a fusão.

// n1: nodo inicial do trecho a ser ordenado
// n2: nodo final do trecho a ser ordenado
// n: comprimento do trecho da lista a ser ordenado
void merge(Nodo * n1, Nodo * n2, int n);

O método público ordena_fusao deve ser invocado para ordenar a lista. Esse método nada mais faz que chamar o método merge apropriadamente para de fato realizar o ordenamento.

void ordenaFusao() {
  if (len < 2) return;

  merge(primeiro, ultimo, len);
}

Atividade

1. Implemente os três algoritmos de ordenamento. Teste-os com este programa (modifique-o para cada um dos algoritmos de ordenamento):

   #include <iostream>
   #include <string>
   #include <prglib.h>
   
   using prglib::lista;
   
   using namespace std;
   
   int main() {
     lista<int> l1;
     lista<string> l2;
   
     l1.anexa(67);
     l1.anexa(2343);
     l1.anexa(112);
     l1.anexa(83725);
     l1.anexa(459);
     l1.anexa(23856);
   
     l1.ordena();
     l1.escrevaSe(cout);
   
     cout << endl;
   
     l2.anexa("um");
     l2.anexa("teste");
     l2.anexa("do");
     l2.anexa("ordenamento");
     l2.anexa("seilaqual");
     l2.anexa("da");
     l2.anexa("lista");
   
     l2.ordena();
     l2.escrevaSe(cout);
     cout << endl;
   }
   

2. Compare os três ordenamentos quanto ao tempo que demoram para ordenar uma lista. Você pode criar uma lista de inteiros gerados aleatoriamente, ou uma lista de strings onde se guardam palavras de um arquivo. Crie listas com ao menos 50 mil dados ...

Abaixo segue um exemplo de comparação. O algoritmo merge-sort é utilizado para ordenar listas na linguagem Python:

Comparação entre os ordenamentos para listas contendo entre 5 mil e 120 mil dados aleatórios.

Comparação entre os ordenamentos feitos com uma árvore de pesquisa binária em C++, e com uma lista na linguagem Python (nesse caso, usou-se o ordenamento já existente para essa lista), e list e vector C++ (implementados na STL).

23/11: Etapa 2: conclusão da lista

A lista encadeada está quase pronta, faltando somente estes métodos:

• void ordena(): ordena com o melhor algoritmo que se puder implementar
• void inverte(): inverte a ordem dos dados
• void embaralha(): embaralha os dados. Como dicas, ver o algoritmo Fisher-Yates (também chamado de Knuth) e esta discussão sobre custos desses algoritmos.

Com a lista implementada, pode-se recompilar o projeto 2 ...

24/11: Etapa 2: a árvore de pesquisa binária

No projeto 4 estudaram-se árvores de pesquisa binária como forma de acesso rápido a dados armazenados. Usou-se então uma implementação de árvore fornecida na prglib. Agora deve-se implementar essa estrutura de dados para que ofereça as mesmas operações existentes na prglib original.

Começando uma árvore binária

A árvore de pesquisa binária é formada por nodos que armazenam um dado qualquer (da mesma forma que foi feito com listas), e possui no máximo dois ramos. O ponto de partida pode ser visto na primeira versão do arquivo libs/arvore.h, mostrada abaixo:

Declaração da arvore em libs/arvore.h

#ifndef ARVORE_H #define ARVORE_H namespace prglib { template <typename T> class arvore { public: arvore(); //arvore(const arvore<T> & outra); arvore(const T & dado); ~arvore(); void adiciona(const T& algo); const T& obtem(const T & algo); void listeInOrder(lista<T> & result); void listePreOrder(lista<T> & result); void listePostOrder(lista<T> & result); void listeEmLargura(lista<T> & result); unsigned int tamanho() const; unsigned int altura() ; int fatorB() ; arvore<T> * balanceia(); arvore<T> * balanceia(bool otimo); // iterador in-order void inicia(); bool fim(); const T& proximo(); // iterador in-order reverso void iniciaPeloFim(); bool inicio(); const T& anterior(); // remove um dado equivalente a "algo", retornando uma cópia T remove(const T & algo); // obtém maior ou menor dados contidos na árvore const T & obtemMenor() const; const T & obtemMaior() const; void obtemMenoresQue(lista<T> & result, const T & algo); void obtemMaioresQue(lista<T> & result, const T & algo); // obtém todos valores entre "start" e "end" (inclusive) void obtemIntervalo(lista<T> & result, const T & start, const T & end); protected: T data; arvore<T> * esq, * dir; // operações internas usadas pelo balanceamento arvore<T> * rotacionaL(); arvore<T> * rotacionaR(); }; } // fim do namespace #include <libs/arvore-impl.h> #endif /* ARVORE_H */

Atividade

OBS: O programa abaixo pode ser usado como um testador inicial da implementação da árvore:

Programa de teste da árvore

#include <iostream> #include <string> #include <prglib.h> using namespace std; using prglib::arvore; int main() { string w[7] = {"graviola","caju","sapoti","acai", "banana","morango","laranja"}; // Uma árvore deve ser criada dinamicamente ... isso facilita // sua implementação. arvore<string> * arv = new arvore<string>(w[0]); for (int n=1; n < 6; n++) arv->adiciona(w[n]); for (int n=0; n < 7; n++) { try { cout << "arv[" << w[n] << "] = " << arv->obtem(w[n]) << endl; } catch (...) { cout << "Ops: " << w[n] << " não está na árvore !" << endl; } } delete arv; return 0; } O resultado de sua execução deve ser este: arv[graviola] = graviola arv[caju] = caju arv[sapoti] = sapoti arv[acai] = acai arv[banana] = banana arv[morango] = morango Ops: laranja não está na árvore ! versão alternativa do programa de teste #include <iostream> #include <string> #include <prglib.h> using namespace std; using prglib::arvore; int main() { string w[7] = {"graviola", "caju","sapoti","acai", "banana","morango","laranja"}; // Uma árvore deve ser criada dinamicamente ... isso facilita // sua implementação. arvore<string> * arv = nullptr; for (auto & fruta : w) { if (arv) arv->adiciona(fruta); else arv = new arvore<string>(fruta); } for (auto & fruta : w) { try { cout << "arv[" << fruta << "] = " << arv->obtem(fruta) << endl; } catch (...) { cout << "Ops: " << fruta << " não está na árvore !" << endl; } } delete arv; return 0; }

1. Implemente adiciona e obtem de forma não-recursiva. Nessa versão, esses métodos usam um laço para percorrer os nodos da árvore.

   <syntaxhighlight lang=text>
   algoritmo adiciona(algo):
     Define raiz como nodo atual
     Para sempre faça
       se algo igual ao dado do nodo atual então 
         substitui dado do nodo atual por algo
         termina algoritmo
       fimSe
       se algo menor que dado do nodo atual então 
         se existe ramo esquerdo então nodo atual é o nodo da esquerda
         senão 
           cria novo nodo com algo
           conecta o novo nodo no ramo esquerdo
           termina algoritmo
         fimSe
      senão
         se existe ramo direito então nodo atual é o nodo da direita
         senão 
           cria novo nodo com algo
           conecta o novo nodo no ramo direito
           termina algoritmo
         fimSe
      fimSe    
     fimPara
   fim adiciona
   

2. Como exercício, implemente adiciona e obtem de forma recursiva. Nessa versão, esses métodos NÃO usam um laço para percorrer os nodos da árvore. Dica: note que cada ramo de uma árvore pode ser visto como uma outra árvore. Esses métodos são parecidos, e o seguinte pseudo-código ilustra o método adiciona em uma versão não-recursiva:

   algoritmo adiciona(algo):
     se algo igual ao dado da raiz então 
       substitui dado da raiz por algo
       termina algoritmo
     fimSe
     se algo menor que dado da raiz então 
       se existe ramo esquerdo então adiciona algo na subárvore da esquerda
       senão 
         cria novo nodo com algo
         conecta o novo nodo no ramo esquerdo
         termina algoritmo
       fimSe
     senão
       se existe ramo direito então adiciona algo na subárvore da direita
       senão 
         cria novo nodo com algo
         conecta o novo nodo no ramo direito
         termina algoritmo
       fimSe
     fimSe    
     fimPara
   fim adiciona
   

3. Implemente os métodos obtemMenor e obtemMaior. Eles são bem simples ...
4. Implemente o método altura ... faça-o de forma recursiva, pois a versão não-recursiva não é fácil ! A altura da árvore é uma informação importante relacionada à eficiência na estrutura da árvore (sua topologia), como visto lá numa seção do projeto 4. Como visto, a altura de uma árvore A pode ser calculada com esta recorrência:

$h(A)={\begin{cases}0,{\text{if }}A_{esq}=NULL\land A_{dir}=NULL\\1+max(h(A_{esq}),h(A_{dir})),{\text{caso contrario}}\\\end{cases}}$

30/11: Etapa 2: enumerando os dados de uma árvore

Até o momento nos concentramos em operações básicas de árvores. Elas possibilitam criar e adicionar dados a uma árvore, e pesquisar por um dado em função de um dado específico. Porém outras formas de acessar os dados de uma árvore podem ser úteis, dentre elas o acesso sequencial de acordo com uma determinada ordem. Por exemplo, pode-se desejar acessar os dados de uma árvore de forma ordenada. Assim, devem-se conhecer as quatro ordens de visitação de nodos de uma árvore:

Tipo	Descrição	Exemplo
In order	visitam-se nodos na sequência esquerda, raiz, direita. O resultado é o acesso ordenado em função das chaves	Animação |} Pre order visitam-se nodos na sequência raiz, esquerda, direita. O resultado é uma ordem de acesso que revela a topologia da árvore Animação |} Post order visitam-se nodos na sequência esquerda, direita, raiz. O resultado é uma ordem de acesso das folhas em direção à raiz Animação |} Level order visitam-se nodos cada nível por vez, da esquerda pra direita Animação |} As três primeiras formas de acesso são do tipo busca em profundidade, pois implicam descer até as folhas de um lado antes de visitarem o outro lado da árvore. A última forma de acesso é do tipo busca em largura, pois os nodos são visitados por nível da árvore. Cada uma das formas de acesso tem sua aplicações em algoritmos. Por exemplo, in order serve para ordenar os dados, pre order pode ser usada para copiar uma árvore, e post order pode ser usado para destruir uma árvore. Alguns algoritmos já criados usam algumas dessas formas de acesso (ex: escrevaSe é do tipo in order; o destrutor da árvore e altura são do tipo post order). Hoje será visto como implementar métodos genéricos que enumeram os dados de uma árvore segundo essas sequências de acesso. void listeInOrder(lista<T> & result); void listePreOrder(lista<T> & result); void listePostOrder(lista<T> & result); void listeEmLargura(lista<T> & result); Os métodos de enumeração na classe arvore um algoritmo para listePreOrder em versão não-recursiva A versão não-recursiva de listePreOrder precisa de uma pilha para navegar pelos nodos da árvore. algoritmo PRE_ORDER: empilha raiz enquanto pilha não vazia faça desempilha um nodo faz algo com nodo se nodo tem ramo direito então empilha ramo direito se nodo tem ramo esquerdo então empilha ramo esquerdo fim enquanto fim algoritmo Algoritmo em pseudo-código template <typename T> void arvore<T>::listePreOrder(lista<T> & result) { // OBS: com a lista funcionando como pilha, // push <==> insere(algo), pop <==> remove(0) lista<arvore<T>*> q; // pilha de nodos a visitar q.insere(this); // inicia com a raiz while (not q.vazia()) { // repete até que pilha fique vazia // desempilha um nodo // anexa em result dado do nodo desempilhado // se nodo tem ramo direito, empilha-o // se nodo tem ramo esquerdo, empilha-o } } Esqueleto do método listePreOrder em versão não-recursiva As versões não-recursivas desses algoritmos podem ser facilmente encontradas em forums de programadores, e também na Wikipedia: In-order Pre-order Post-order Em-largura Iteração da árvore A iteraçao da árvore na Prglib original possibilita obter de forma ordenada os dados contidos na árvore. Assim, a iteração segue uma enumeração dos dados no estilo in-order. Para implementá-la deve-se usar um algoritmo não-recursivo, visto que cada chamada do iterador, por meio do método proximo, retorna um único dado. Um algoritmo para enumeração in-order faz uso de uma pilha como estrutura de dados auxiliar. Sendo assim, a classe arvore precisa possuir uma pilha como um novo atributo. Para economizar memória, já que todo nodo da árvore possuirá esse novo atributo, a pilha deve ser criada dinamicamente quando se inicia uma iteração, e destruída ao final da iteração. Para isso a pilha deve ser declarada como o ponteiro p_stack na classe arvore: Declaração da arvore em libs/arvore.h contendo o atributo para a pilha #ifndef ARVORE_H #define ARVORE_H namespace prglib { template <typename T> class arvore { public: arvore(); //arvore(const arvore<T> & outra); arvore(const T & dado); virtual ~arvore(); void adiciona(const T& algo); T& obtem(const T & algo); void listeInOrder(lista<T> & result); void listePreOrder(lista<T> & result); void listePostOrder(lista<T> & result); void listeEmLargura(lista<T> & result); unsigned int tamanho() const; unsigned int altura() ; int fatorB() ; arvore<T> * balanceia(); arvore<T> * balanceia(bool otimo); // iterador in-order void inicia(); bool fim(); T& proximo(); // iterador in-order reverso void iniciaPeloFim(); bool inicio(); T& anterior(); // remove um dado equivalente a "algo", retornando uma cópia T remove(const T & algo); // obtém maior ou menor dados contidos na árvore T & obtemMenor() const; T & obtemMaior() const; void obtemMenoresQue(lista<T> & result, const T & algo); void obtemMaioresQue(lista<T> & result, const T & algo); // obtém todos valores entre "start" e "end" (inclusive) void obtemIntervalo(lista<T> & result, const T & start, const T & end); protected: T data; arvore<T> * esq, * dir; // um ponteiro para pilha a ser usada pelo iterador. // OBS: pode-se usar uma lista como se fosse pilha ! lista<arvore<T>*> * p_stack; arvore<T> * rotacionaL(); arvore<T> * rotacionaR(); }; } // fim do namespace #include <libs/arvore-impl.h> #endif /* ARVORE_H */ O algoritmo para enumeração in-order é mostrado a seguir. Deve-se notar que esse algoritmo enumera todos os dados da árvore. Portanto, ele é uma versão não-recursiva de listeInOrder: algoritmo in-order(lista): cria uma pilha de nodos empilha a raiz e todos os nodos nos ramos mais à esquerda da raiz, até o nodo com menor valor enquanto pilha não vazia faça desempilha um nodo anexa à lista dado do nodo se nodo possui ramo direito então empilha o nodo direito e todos os nodos nos ramos mais à esquerda dele, até o nodo com menor valor fim se fim enquanto destroi pilha fim in-order A iteração da árvore pode aproveitar esse algoritmo com pequenas modificações. Atividade Implemente a iteração in-order de sua árvore (métodos inicia, proximo, fim) Implemente a iteração in-order reversa de sua árvore (métodos iniciaPeloFim, anterior, inicio) 01/12: Etapa 2: balanceamento da árvore AVL Tree Nos experimentos feitos até agora, as árvores de pesquisa binária apresentaram um bom desempenho tanto para serem criadas quanto para pesquisarem valores. Foi estudado que isso se deve a uma importante propriedade da árvore binária, que limita à altura da árvore a quantidade de operações de comparação em uma pesquisa qualquer. Como a altura é função do logaritmo da quantidade de nodos, ela tende a crescer muito lentamente com o aumento da quantidade de nodos da árvore (ex: uma árvore com pouco mais 2.3 milhões de nodos teria altura de pelo menos 21). Porém isso depende de os nodos estarem igualmente distribuídos dos dois lados da árvore. Em outras palavras, a árvore deve estar balanceada. A partir de hoje iremos estudar como balancear uma árvore binária, e para isso usaremos o algoritmo clássico AVL. Mas outras abordagens existem, tais como árvores vermelho-preto. Uma interessante comparação entre árvores AVL e Vermelho-Preto pode ser lida na Wikipedia: Red–black trees offer worst-case guarantees for insertion time, deletion time, and search time. Not only does this make them valuable in time-sensitive applications such as real-time applications, but it makes them valuable building blocks in other data structures which provide worst-case guarantees; for example, many data structures used in computational geometry can be based on red–black trees, and the Completely Fair Scheduler used in current Linux kernels uses red–black trees. The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more rigidly balanced than red–black trees, leading to slower insertion and removal but faster retrieval. This makes it attractive for data structures that may be built once and loaded without reconstruction, such as language dictionaries (or program dictionaries, such as the opcodes of an assembler or interpreter). Fator de balanceamento O fator de balanceamento é a diferença entre as alturas das árvores esquerda e direita, e pode ser calculado assim: $F_{b}=altura(esquerda)-altura(direita)$ Se para todos os nodos da árvore $\lVert F_{b}\rVert <=1$, então a árvore está balanceada e nada precisa ser feito. Porém se para algum nodo $\lVert F_{b}\rVert >1$, então existe um desequilíbrio (má distribuição de nodos), o qual pode ser corrigido. O balanceamento pode ser feito realizando rotações da árvore. Rotações e balanceamento O balanceamento da árvore implica equilibrar as alturas de cada árvore esquerda e direita dentro de uma árvore. Essa operação pode ser feita tendo como base o que se chama de rotações da árvore. Duas rotações básicas são possíveis: rotação à direita e à esquerda. Ambas rotações preservam a propriedade de relação de precedência dos dados contidos na árvore: à esquerda da raiz estão os dados menores que o valor da raiz, e à direita estão os maiores. Na figura a seguir, os círculos representam nodos e os triângulos representam subárvores. Combinando-se essas duas rotações básicas, podem-se realizar quatro tipo de transformações necessárias para o balanceamento de uma árvore AVL: Caso 1: rotação direita Caso 2: rotação esquerda da árvore esquerda Caso 3: rotação esquerda Caso 4: rotação direita da árvore direita O balanceamento é feito combinando-se as rotações elementares (direita e esquerda) para aplicá-las a cada caso, o que aqui se chama de redução. A cada redução reduz-se o módulo do fator de balanceamento em uma unidade. Portanto se esse fator tiver um valor elevado, várias reduções sucessivas serão necessárias até que ele fique dentro do limite aceitável (i.e. $\vert F_{b}\vert <=1$). As reduções podem ser feitas à direita ou esquerda: $F_{b}<-1$: redução à direita: Se caso 4: executa-se rotacionaR na árvore direita executa-se rotacionaL $F_{b}>1$: redução à esquerda: Se caso 2: executa-se rotacionaL na árvore esquerda executa-se rotacionaR O algoritmo de balanceamento pode ser modelado da seguinte forma: algoritmo balanceia(arvore): entrada: arvore (modificada ao final do algoritmo) valor de retorno: raiz da árvore após balanceamento variáveis: Fb (inteiro) se arvore esquerda nao nula entao arvore esquerda <- balanceia(arvore esquerda) se arvore direita nao nula entao arvore direita <- balanceia(arvore direita) Fb <- calcula fator de balanceamento da arvore enquanto Fb < -1 faça reduz à direita e calcula novo Fb fimEnquanto enquanto Fb > 1 faça reduz à esquerda e calcula novo Fb fimEnquanto retorna arvore Tanto as rotações quanto o balanceamento devem ser implementados como métodos da classe arvore. As rotações pode ser declaradas como métodos protegidos ou privativos, pois devem ser usados somente pelo algoritmo de balanceamento: template <class T> class arvore { protected: // os atributos de uma arvore public: // os métodos públicos da Arvore // A operação que calcula o fator de balanceamento int fatorB() const; // A operação que balanceia a árvore // note que ela retorna um ponteiro para a nova raiz ... arvore<T> * balanceia(); arvore<T> * balanceia(bool otimo); // os métodos protegidos da Arvore ... por enquanto são públicos // Quando estiverem prontos, devem ficar protegidos ou privativos // rotação esquerda: retorna a nova raiz da árvore arvore<T> * rotacionaL(); // rotação direita: retorna a nova raiz da árvore arvore<T> * rotacionaR(); }; Assim ... implemente o balanceamento da sua árvore ! Dicas: Implemente o fator de balanceamento Implemente cada uma das rotações, testando-as em árvores pequenas com diferentes topologias. Tendo as rotações corretas, implemente o algoritmo de balanceamento. Teste-o com pequenas árvores cujas topologias sejam conhecidas. Verifique a altura e fator de balanceamento dessas árvores antes e após o balanceamento. Método escrevaSe reescrito para ajudar a visualizar a topologia da árvore Acrescente isto ao arquivo arvore.h, antes da declaração da classe arvore: #include <ostream> using std::ostream; Acrescente este método à declaração dos métodos públicos da classe arvore em arvore.h void escrevaSe(ostream & out) const; Acrescente isto a arvore-impl.h #include <string> using std::string; template <typename T> void arvore<T>::escrevaSe(ostream& out) const { static int nivel = -1; string prefixo; nivel++; prefixo.append(nivel, ' '); if (dir) dir->escrevaSe(out); out << prefixo << data << std::endl; if (esq) esq->escrevaSe(out); nivel--; } Programa de teste das rotações: testa rotacionaL e rotacionaR #include <iostream> #include <string> #include <prglib.h> using namespace std; using prglib::arvore; int main() { arvore<int> * arv; // uma árvore toda pro lado direito arv = new arvore<int>(2); arv->adiciona(3); arv->adiciona(4); arv->adiciona(5); arv->adiciona(6); arv->escrevaSe(cout); cout << endl; arv = arv->rotacionaL(); arv->escrevaSe(cout); cout << endl; arv = arv->rotacionaR(); arv->escrevaSe(cout); cout << endl; delete arv; } TAREFA Implemente o balanceamento AVL de sua árvore, e aplique-o à árvore criada a partir das palavras do arquivo de portugues. A altura inicial da árvore é 42, e a altura após o balanceamento pode chegar a 21 (experimente realizar alguns balanceamentos sucessivos, até que a altura não mais reduza). 07/12: Etapa 2: balanceamento da árvore 08/12: Etapa 2: remoção de um dado da árvore Apesar de não ter sido necessário no Projeto 4, uma outra aplicação da árvore pode necessitar remover dados. Uma forma de fazer isso é listar todos os dados da árvore, remover os dados desejados e, em seguida, reconstruir a árvore, porém isso envolve um grande esforço computacional desnecessário. A solução mais simples é remover somente os dados desejados, fazendo talvez um ajuste pontual na estrutura da árvore. A operação remove definida abaixo deve implementar tal algoritmo . // Este método da classe Arvore remove um nodo que seja igual a "algo" // Retorna o dado removido. // Se o dado não for encontrado, dispara uma exceção T remove(const T & algo); O método para remoção de um nodo da árvore, conforme declarado em arvore.h A remoção de um dado de uma árvore de pesquisa binária tem o seguinte princípio: Localiza-se o nodo que contém o dado a ser removido. Substitui-se o valor desse nodo por uma destas alternativas: O maior valor existente à esquerda do nodo a ser removido. O menor valor existente à direita do nodo a ser removido. A figura abaixo ilustra a remoção de um dado de uma árvore, destacando as duas possibilidades para a operação: No exemplo acima, o menor valor à direita do nodo a ser removido é fácil de ser encontrado: basta seguir os ramos à esquerda da subárvore direita. O maior valor à esquerda também é fácil de ser encontrado: basta seguir os ramos à direita da subárvore esquerda. Mas o caso geral pode ficar mais complicado. Por exemplo, seja a árvore abaixo: Nesse exemplo, o menor valor à direita do nodo a ser removido não é uma folha, nem pode ser encontrado simplesmente seguindo-se os ramos esquerdos da árvore direita. O mesmo vale para o maior valor à esquerda. Para funcionar em todos os casos, o algoritmo de remoção de um dado da árvore pode ser resumido por este pseudo-código: Localize o valor a ser removido Se for uma folha, remove o nodo e retorna Se fator de balanceamento da árvore enraizada no nodo a ser removido for maior que zero, então Procura o maior valor da árvore esquerda Copia esse valor para o nodo que contém o valor a ser removido Remove esse maior valor da árvore esquerda Senão Procura o menor valor da árvore direita Copia esse valor para o nodo que contém o valor a ser removido Remove esse menor valor da árvore direita fimSe Além do método remove, dois outros métodos precisam ser implementados para obter o maior ou o menor valor de uma árvore: // Este método da classe Arvore remove um nodo que seja igual a "algo" // Retorna o dado que foi removido. Se o dado não for encontrado, dispara uma exceção // A raiz da árvore pode ser modificada no processo ... T remove(const T & algo); // Retorna o menor dado da árvore T & obtemMenor() const; // Retorna o mair dado da árvore T & obtemMaior() const; Programa de teste para remoção de valor da árvore #include <iostream> #include <string> #include <prglib.h> using prglib::arvore; using namespace std; int main() { string dados[7] = {"um", "teste", "pequeno", "muito", "da", "simples", "arvore"}; auto arv = new arvore<string>(dados[3]); for (int k=1; k < 4; k++) { arv->adiciona(dados[k+3]); arv->adiciona(dados[3-k]); } arv->escrevaSe(cout); string dado = arv->remove(dados[1]); cout << "Removeu " << dado << endl; arv->escrevaSe(cout); dado = arv->remove(dados[3]); cout << "Removeu raiz: " << dado << endl; arv->escrevaSe(cout); delete arv; return 0; } Atividade Implemente o método remove, e teste-o com o programa de teste. Experimente remover: um valor de uma folha um valor que esteja em um nodo intermediário o valor que está na raiz 14/12: Conclusão da Prglib Entrega da prglib no Moodle 15/12: Prova 3 Prova individual em laboratório