PRG2-2015-2b
Programação 2: Diário de aula 2015-2 da turma B
Página da turma do Prof. Marcelo Sobral
Professor: Francisco de Assis
Encontros: 4a feira/13:30, 5a feira/13:30
Atendimento paralelo: 4a de 10:00 às 11:00
19/11: Projeto 3
25/11: Prova 1
A avaliação 1 será uma prova prática individual em laboratório, envolvendo questões sobre filas e pilhas, além de possíveis referências aos projetos 1 e 2.. Cada estudante deve trazer sua implementação de fila e pilha. Durante a prova podem-se consultar a wiki e o manual online do Linux. A prova consistirá de pelo menos quatro questões, valendo 10 pontos cada uma. Sua avaliação será feita da seguinte forma:
< 10 pontos: os projetos 1 e 2 serão avaliados com D. entre 10 e 19 pontos: os conceitos dos projetos 1 e 2 serão reduzidos em um nível. entre 20 e 25 pontos: os conceitos dos projetos 1 e 2 serão mantidos. acima de 25 pontos: os conceitos dos projetos 1 e 2 serão elevados em um nível.
OBS: uma questão será considerada correta somente se compilar, for implementada exatamente como solicitado e fornecer um resultado correto.
Prova 1 2015-2
Prova 2015-1
02/12: Projeto 3: Quebra Definitiva de Linhas de Logs
Uso do sscanf no C++:
/* sscanf exemplo */
#include <stdio.h>
int main ()
{
char sentence []="Ana tem 23 anos";
char str [20];
int i;
sscanf (sentence,"%s %*s %d",str,&i);
printf ("%s -> %d\n",str,i);
return 0;
}
Saída: Ana -> 23
Resolução da Quebra de Logs:
#include <iostream>
#include <fstream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "Lista.h"
using namespace std;
struct DataHorario {
int dia;
string mes;
int ano;
int hora;
int minuto;
int segundo;
};
struct Registro {
string ip;
string usuario;
DataHorario data;
string metodo;
string path;
string http;
int status;
long bytes;
string agente;
};
int dia, ano, hora, minuto, segundo, status;
int long bytes;
char ip[20], data[35], metodo[9], paths[250], usuario [45], agente[40], http[200];
int datadia, dataano;
int main(int argc, char *argv[]) {
// testa se o nome do arquivo foi passado pela linha de comando
if (argc < 2) {
cout << "Uso: " << argv[0] << " nome_arquivo" << endl;
return 0;
}
Registro Regist;
Lista<Registro> Encadeada;
// Cria o objeto ifstream, o que implica abrir o arquivo
ifstream arq(argv[1]);
// Verifica se o arquivo foi aberto, ou se houve algum erro
if (not arq.is_open()) {
cout << "Erro: não conseguiu abrir o arquivo (ele existe ?)" << endl;
return 0;
}
// Lê todas as linhas do arquivo
while (not arq.eof()) {
string linha;
getline(arq, linha);
sscanf(linha.c_str(), "%s %*c %s [%s %*d] \"%s %s %[^\"]\" %d %ld %*s \"%[^\"]\"", ip, usuario, data, metodo, paths, http, &status, &bytes, agente);
string datacompleta= data;
string dia = datacompleta.substr(0,datacompleta.find('/'));
datadia= atoi(dia.c_str());
datacompleta.erase(0,3);
string datames = datacompleta.substr(0,3);
datacompleta.erase(0,4);
string anos = datacompleta.substr(0,4);
datacompleta.erase(0,5);
dataano= atoi(anos.c_str());
Regist.ip = ip;
Regist.usuario= usuario;
Regist.metodo = metodo;
Regist.status = status;
Regist.bytes = bytes;
Regist.path= paths;
Regist.http= http;
Regist.agente=agente;
Regist.data.dia=datadia;
Regist.data.mes=datames;
Regist.data.ano=dataano;
Encadeada.adiciona(Regist);
}
arq.close();
cout<< "Comprimento: "<< Encadeada.comprimento()<<endl;
for (int pos=0;pos<Encadeada.comprimento();pos++)
{
cout<< "IP: "<< Encadeada.obtem(pos).ip<<endl;
cout<< "Usuario: "<< Encadeada.obtem(pos).usuario<<endl;
cout<< "Metodo: "<< Encadeada.obtem(pos).metodo<<endl;
cout<< "Status: "<< Encadeada.obtem(pos).status<<endl;
cout<< "Bytes: "<< Encadeada.obtem(pos).bytes<<endl;
cout<< "Path: "<< Encadeada.obtem(pos).path<<endl;
cout<< "Http: "<< Encadeada.obtem(pos).http<<endl;
cout<< "Agente: "<< Encadeada.obtem(pos).agente<<endl;
cout<< "Dia: "<< Encadeada.obtem(pos).data.dia<<endl;
cout<< "Mes: "<< Encadeada.obtem(pos).data.mes<<endl;
cout<< "Ano: "<< Encadeada.obtem(pos).data.ano<<endl;
cout<< " "<<endl;
}
}
02/12: Ordenação e Pesquisa em Estruturas de Dados
Na computação a ordenação e pesquisa são fundamentais e extensivamente analisadas. Essas rotinas são utilizadas em muitas estruturas de dados, bem como em compiladores, interpretadores e sistemas operacionais.
Ordenação: É um processo de arranjar um conjunto de informações semelhantes em uma ordem crescente ou decrescente. Em particular, seja uma lista ordenada L de n elementos, então:
L1 <= L2 <= ... <= Ln
De modo geral, quando a informação é ordenada apenas uma parte/campo dessa informação é utilizada como chave de ordenação. Essa chave é utilizada nas comparações, porém, quando uma troca é necessária toda a estrutura deve ser transferida. Por exemplo, em uma lista postal, o campo CEP pode ser utilizado como chave para as comparações, porém, em caso de trocas os demais campos como nome e endereço também devem ser transferidos.
Tipo de Algoritmos de Ordenação:
Existem três métodos gerais para ordenar estruturas de dados:
• Por troca; • Por seleção; • Por inserção.
Para entendermos esses três métodos, imaginamos cartas de um baralho. Para ordenar as cartas, utilizando troca, espalham-se as cartas voltadas para cima, em uma mesa, então é realizada a troca das cartas fora de ordem até que o baralho esteja ordenado. Utilizando seleção, espalham-se as cartas na mesa, seleciona-se a de menor valor, retire-a do baralho e segure-a em sua mão. Esse processo deve continuar até que todas as cartas estejam em sua mão e, portanto, o baralho estará ordenado. Para ordenar por inserção, segure todas as cartas em sua mão. Coloque uma carta por vez na mesa, sempre inserindo na ordem correta. O baralho estará ordenado quando não existirem mais cartas em sua mão.
A ordenação Bolha: É a mais conhecida e também uma das piores ordenações já desenvolvidas. Trata-se de uma ordenação por trocas, envolvendo repetidas comparações e, se necessário, a troca de dois elementos adjacentes. Os elementos são como bolhas em um tanque (cada bolha procura seu próprio nível). Exemplo para a matriz de caracteres:
D C A B
Inicial: D C A B
Passo 1: A D C B
Passo 2: A B D C
Passo 3: A B C D
A segui é apresentada uma rotina em C++ que implementa e utiliza o método bolha para a ordenação de uma matriz de caracteres.
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
string bolha (string item, int tamanho)
{ int a, b;
char t;
for(a=1; a<tamanho; a++)
for (b=tamanho-1; b>=a; b--) {
if (item[b-1]> item[b]) {
t= item[b-1];
item[b-1] = item[b];
item[b] =t; }
} return item;
}
int main(int argc, char** argv) {
string linha;
char t;
cout<< "Digite uma Palavra: "<<endl;
getline(cin, linha);
string palavraordenada = bolha(linha,linha.length());
cout<<"A palavra ordenada eh: "<<palavraordenada<<endl;
}
Ordenação por Seleção:
A ordenação por seleção seleciona o elemento de menor valor e troca-o pelo primeiro elemento. Então, para os n-1 elementos restantes, é encontrado o elemento de menor chave, trocando pelo segundo elemento e assim por diante. As trocas continuam até os dois últimos elementos. Por exemplo, se o método de seleção fosse utilizado na matriz BDCA cada passo se apresentaria como:
Inicial: B D A C
Passo 1: A D B C
Passo 2: A B D C
Passo 3: A B C D
E como seria a implementação desse algoritmo? Desenvolva uma rotina capaz de ordenar uma matriz de caracteres por meio do método de seleção....
Resolução:
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
string selecao (string item, int tamanho)
{
int i, j, posicaotroca;
char t;
bool troca;
for(i=0; i<tamanho-1; i++)
{
t=item[i];
troca=false;
for (j=i+1; j<tamanho; j++)
{
if (item[j]<t)
{
troca=true;
posicaotroca=j;
t=item[j];
}
}
if (troca)
{
item[posicaotroca]=item[i];
item[i]=t;
}
}
return item;
}
int main(int argc, char** argv) {
string linha;
char t;
cout<< "Digite uma Palavra: "<<endl;
getline(cin, linha);
string palavraordenada = selecao(linha,linha.length());
cout<<"A palavra ordenada eh: "<<palavraordenada<<endl;
}
Ordenação Quicksort:
É baseada na ideia de partições. O procedimento geral é selecionar um valor, chamado de comparador, e então, fazer partição da matriz em duas seções. Uma seção com os elementos menores que o valor comparando e outras seção com os valores maiores ou igual ao comparando. Esse processo deve repetir até que a estrutura esteja totalmente ordenada.
Veja o Exemplo:
Início: f e d a c d Escolhendo o elemento "d" como comparador: Passo 1: b c a | d e f Escolhendo o elemento "c" como comparador da primeira partição e o elemento "e" como comparador da segunda partição: Passo 2: a b c | d e f (estrutura ordenada)
Observe que o processo é recursivo, dessa maneira a implementação desse algoritmos de ordenação deve aplicar recursividade.
Agora, devemos implementar essa rotina de ordenação em C++.....
09/12: Implementação da Ordenação e Pesquisa na Lista.h
Devemos lembrar que outra solução mais simples que todas as apresentadas também é válida (apesar de maior custo computacional),trata-se de uma ordenação nxn com comparações e trocas entre os elementos adjacentes de um vetor:
string ordenasimples( string item, int tamanho)
{
int a, b;
char t;
for (a=0; a<tamanho; a++)
for (b=1; b<=tamanho; b++)
{
if (item[b-1] > item[b])
{
t= item[b-1];
item[b-1] = item[b];
item[b] = t;
}
}
return item;
}
As estruturas vistas até aqui permitem realizar a ordenação e pesquisa em vetores, e para uma lista encadeada, como fazer? Primeiro temos de disponibilizar um Template para permitir comparar atributos, conforme segue:
template <class T> class Comparador {
public:
virtual int operator()(const T & x1, const T & x2) {
if (x1 == x2) return 0;
if (x1 > x2) return 1;
return -1;
}
};
No Template Lista.h deve-se declarar um método, conforme a seguir:
void ordena(Comparador<T> & comparar)
Após a implementação da ordenação é possível testar na main() com as instruções:
int main (int argc, char *argv[])
{
Lista<string> novalista;
string a="Francisco", b="José", c="Maria";
Comparador<string> comparador;
// Primeiro mostra-se como o comparador funciona ...
cout << "a e b: " << comparador(a, b) << endl;
cout << "a e c: " << comparador(a, c) << endl;
cout << "b e c: " << comparador(b, c) << endl << endl;
// Agora anexam-se as strings na lista
novalista.adiciona(b);
novalista.adiciona(c);
novalista.adiciona(a);
// Ordena-se a lista usando o comparador
novalista.ordena(comparador);
//Mostra a lista ordenada na tela
for (int i=0; i< novalista.comprimento(); i++)
{
cout<< " : " <<novalista.obtem(i)<<endl;
}
}
E para pesquisar um nome nessa lista, como fazer?
10/12: Projeto para a Segunda Nota da Disciplina de Programação II
- Desenvolver um Aplicativo em C++ que receba um Arquivo de Logs Apache.
- Este aplicativo deve apresentar um menu de opções para os usuários com as opções:
1) Anexar ou Adicionar na Lista Encadeada os Registros de Logs
2) Ordenar por pelo campo Bytes a Lista Encadeada contendo os Registro de Logs
3) Imprimir o conteúdo da Lista Encadeada, apresentando todos os campos do Registro de Logs
4) Pesquisar um Registro na Lista Encadeada pelo campo IP ou Usuário ou Método ou Status
5) Excluir um Registro da Lista Encadeada
6) Carregar arquivos Logs Apache para serem analisados (opcional)
7) Realizar o comparativo entre os tempos de execução da ordenação (pelo campo Bytes) da Lista, entre os métodos de ordenação de Seleção pela Ordenação Simples (nxn)
8) Sair do aplicativo
- As opções devem ser implementadas utilizando os métodos da Lista.h
17/12: Dicas para Conclusão do Projeto de Programação II
Devem implementar em C++ uma rotina similar a seguinte (observem os comentários em cada case):
int main(int argc, char** argv) {
int operacao;
cout <<"Qual operacao deseja realizar na Lista encadeada? \n \n";
cout << " 1 - Anexar na Lista Encadeada os Registros de Logs \n";
cout << " 2 - Adicionar na Lista Encadeada os Registros de Logs \n";
cout << " 3 - Ordenar a Lista Encadeada contendo os Registro de Logs pelo campo Bytes \n";
cout << " 4 - Imprimir o conteúdo da Lista Encadeada, apresentando todos os campos do Registro de Logs \n";
cout << " 5 - Pesquisar um Registro na Lista Encadeada pelo campo Metodo \n";
cout << " 6 - Excluir um Registro da Lista Encadeada \n";
cout << " 7 - Comparativo entre os tempos de execucao da ordenacao (por Bytes) da Lista, entre os metodos de ordenacao Simples(nxn) e Selecao \n";
cout << " 8 - Sair \n";
cin >> operacao;
cin.ignore ();
switch (operacao){
case 1:
// Invocar um método que anexa na lista os registros de logs já com os campos quebrados adequadamente
//Para isso construa um método que quebra os arquivos de logs e em seguida anexa na lista encadeada
break;
case 2:
// Idem o anterior porém deve-se utilizar o método adicionar da "Lista.h" ao invés do método anexa
break;
case 3:
//Invocar um método previamente criado, o qual inicialmente verifica se a lista está vazia, e caso não esteja vazia ordenar
// a lista pelo campo bytes utilizando o método seleção
break;
case 4:
//Invocar um método que imprime cada registro de log contido na lista, ou seja, começar em inicio, p-->proximo até fim da lista
break;
case 5:
//Invocar um método previamente criado que solicite ao usuário informar qual o nome do método deseja
// buscar na lista, após a leitura do teclado da chave de busca deve-se aplicar o método de busca
//propriamente dito, caso encontrou mostrar os demais campos, caso não, informar que elemento não foi encontrado
break;
case 6:
//Criar um método similar ao método de pesquisa (conforme mencionado acima) e caso encontre o registro com o campo desejado, deve-se
// excluir o registro associado ao campo encontrado com a chave de busca
// Caso não encontrado nenhum registro com o campo procurado, deve-se informar ao usuário que não há registro na lista com o campo buscado
break;
case 7:
//Requisitar um método previamente implementado que realize o comparativo em termos de tempo de execução de ordenação dos registros por log
//para os métodos de ordenação por selecao e ordenação simples (nxn)
//Para isso pode-se utilizar da diferença entre um timer antes e após completada a ordenação, para os dois métodos
// ou ainda: o "tempo" pode ser convertido em número de passos executados por cada um dos métodos de ordenação
break;
case 8:
exit(0);
break;
}
}
Bibliografia:
Schildt, H. C Completo e Total. 3ª Edição. São Paulo. Pearson Makron Books, 1997.
03/02: Tabelas Hash
Tabelas Hash são tabelas de dispersão úteis para organizar um conjunto de dados com endereçamento direto. Possuem em média um bom desempenho, porém, no pior caso seu desempenho é lamentável!
As Tabelas Hash possuem um universo de chaves que correspondem a um código que identifica o conjunto de dados como único, por exemplo, CPF de uma pessoa ou matricula de um funcionário em uma empresa.
Geralmente o tamanho de uma Tabela Hash é denotado por M. A tabela terá a forma tab[0...M-1] considerando um vetor de posições que irá armazenar um conjunto de dados.
O "pulo do gato" das Tabelas Hash é possuir uma função de espalhamento que a partir de uma chave leve ao índice da tabela onde será armazenado o conjunto de dados.
Por exemplo: Suponhamos que as chaves (v) de uma Tabela Hash vão de 100001 a 9999999 e que o tamanho da tabela seja M=100. Podemos adotar os dois últimos dígitos da chave como o código de espalhamento. Em outros termos, a função de espalhamento será v % M (resto da divisão de v por M).
chave código
123456 56
7531 31
1478 78
É possível obter códigos iguais (colisões) com chaves diferentes? Se sim, como diminuir as chances disso ocorrer?
Existem algumas técnicas que facilitam criar funções de espalhamento. Sedgewick recomenda escolher M levando em conta alguns princípios:
- Deve-se escolher uma potência de 2 que esteja próxima do valor desejado de M. - Posteriormente, assumir para M o número primo que esteja imediatamente abaixo da potência escolhida. Exemplos:
k 2^k M
7 128 127
8 256 251
9 512 509
10 1024 1021
11 2048 2039
12 4096 4093
Exercícios:
1) Crie uma função Hash que gere códigos menores que 500 com chaves no intervalo 1111 a 999999.
2) Implemente em C++ uma função de espalhamento hash (v % M) para um vetor de até 8191. Armazene no vetor Nome, RG e endereço de funcionários de uma companhia. Posteriormente, faça uma função de busca direta utilizando a função de espalhamento tendo como chave o RG. Ou seja, digitando o RG deve-se obter a posição direta onde está gravado os dados do funcionário.
3) Identifique a estratégia utilizada para obter o M=8191. Explique as razões de escolher um número primo para M.
11/02: Implementação da tabela hash
Pelas verificações percebemos que sempre haverá colisões usando Tabela Hash. Dessa forma temos de tratar adequadamente estas colisões. Uma maneira simples e segura de realizar isso é criarmos um vetor com listas encadeadas.
Vamos pensar no seguinte:
- Que atributos deve ter a tabela hash ? Em outras palavras, como iremos declarar um tipo de dados que a represente ?
- Que operações essa tabela deve implementar ?
- Que interface de programação ela deve apresentar ?
Para simplificar nossa tabela, vamos assumir que ela guarde valores de qualquer tipo, e os valores armazenados são indexados por uma chave do tipo string. Assim nossa tabela pode ser declarada da seguinte forma (isto pode ficar num arquivo hash.h):
#ifndef HASH_H
#define HASH_H
#include <cstdlib>
#include <string>
#include "lista.h"
using namespace std;
// esta struct Par serve para associar uma chave e um dado
// note que a tabela hash armazena pares (chave, dado)
template <typename T> struct Par {
string chave;
T valor;
Par(const string& k, const T& dado) {
chave = k;
valor = dado;
}
Par() {}
};
template <typename T> class TabelaHash {
protected:
Lista<Par<T> > * tab;
int capacidade;
public:
TabelaHash(int cap);
TabelaHash(const TabelaHash &outra); // construtor de copia
~TabelaHash();
void adiciona(const string& chave, const T& dado);
T remove(const string& chave);
T operator[](const string& chave) const;
T obtem(const string& chave) const;
Lista<string> chaves() const;
Lista<T> valores() const;
bool existe(const string& chave) const;
void esvazia();
int tamanho() const;
protected:
unsigned int hash(const string & chave) const;
};
#endif
Início da implementação
A implementação inicial deve conter o suficiente para compilar e executar o programa de teste. As seguintes funções-membros (métodos) são necessárias na TabelaHash:
- construtor e destrutor
- adiciona
- operador [] (ou obtem)
| O primeiro programa de teste |
|---|
#include <iostream>
#include <string>
#include "hash.h"
using namespace std;
int main() {
TabelaHash<int> tab1(5);
string chaves[8] = {"chave1", "chave2", "chave3", "chave4", "chave5", "chave6", "chave7", "chave8"};
int dados[8] = {11, 12, 13 , 14, 15, 16, 17, 18};
for (int n=0; n < 8; n++) {
tab1.adiciona(chaves[n], dados[n]);
}
for (int n=0; n < 8; n++) {
cout << "tab1[" << chaves[n] << "] = " << tab1[chaves[n]] << endl;
}
}
Um primeiro teste para a tabela |
O construtor deve criar o vetor de listas, o qual representa a tabela dentro de TabelaHash. Esse construtor tem como parâmetro a quantidade de linhas da tabela, e pode ser escrito assim:
template <typename T> TabelaHash<T>::TabelaHash(int linhas) {
capacidade = linhas;
tab = new Lista<Par<T> >[capacidade];
}
O método adiciona deve adicionar à tabela um dado associado a uma determinada chave. Como chaves devem ser únicas, se já existir algum dado com a mesma chave que se deseja adicionar, esse dado deve ser sobrescrito. Abaixo está uma possível implementação de adiciona, na qual falta tratar o caso de chave já existente.
template <typename T> void TabelaHash<T>::adiciona(const string &chave, const T& dado) {
unsigned int linha = hash(chave);
Par<T> par(chave, dado);
// OBS: e se já existir um par com a mesma chave ?
// NÃO PODE HAVER DOIS PARES COM MESMA CHAVE NA TABELA !!! Chaves são únicas !
tab[linha].adiciona(par);
}
Por fim, o operador [], equivalente à função-membro obtem, deve retornar o dado associado a uma determinada chave. Se a chave não existir na tabela, uma exceção deve ser gerada. Uma implementação funcional porém ineficiente dessa função-membro segue abaixo:
template <typename T> T& TabelaHash<T>::operator[](const string &chave) {
// Calcula o hash da chave, identificando assim a linha onde deve estar a chave
// Para cada Par desta linha:
// se a chave do Par for igual à chave procurada, retorna o dado do Par
//
// SE chave não encontrada, dispara uma exceção
}
25/02: Projeto 5: um dicionário de português
O projeto 5 trata de implementar um dicionário de português, usando os verbetes disponibilizados pelo projeto Dicionário Aberto. Cada entrada do dicionário é composta por um termo e sua descrição. A utilização de um dicionário nesta forma se resume basicamente a procurar por significados de palavras (termos). Sua implementação como um programa torna possível integrá-lo com outros aplicativos, tais como leitores de e-books e editores de texto.
- Arquivos de verbetes
- Uma descrição sobre o formato dos arquivos de verbetes
- Abreviaturas usadas no dicionário
Um programa que implemente um dicionário deve possibilitar uma busca rápida por palavras. Por isso no projeto 5 tem-se como um dos objetivos que haja eficiência no tempo de consulta. Uma nova estrutura de dados chamada árvore de pesquisa binária proporciona uma grande eficiência no tempo de busca de um dado. E também tem outras propriedades interessantes, e que são úteis para resolver diversos problemas. O dicionário deve se valer dessa estrutura de dados para armazenar os verbetes.
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
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 que o 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 os verbetes do dicionário ? 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 dicionário implementado com lista encadeada, tabela hash e árvore de pesquisa binária. O custo computacional para pesquisar todas as palavras em uma lista é , pois para cada palavras procurada pode ser necessário compará-la com todos as palavras existentes na lista. No caso da tabela hash, esse custo é , sendo M a capacidade da tabela (quantidade de linhas) e supondo uma tabela muito bem espalhada. Se for usada uma árvore de pesquisa binária, esse custo pode ser , contanto que certas propriedades da árvore sejam verificadas (isso será discutido mais adiante).
Começando uma árvore binária
Para implementar o dicionário será usada uma árvore binária. Essa árvore é formada por nodos que armazenam um dado qualquer (da mesma forma que foi feito com listas e tabelas hash), e possui dois ramos. O ponto de partida pode ser visto na primeira versão do arquivo arvore.h, mostrada abaixo:
#ifndef ARVORE_H
#define ARVORE_H
#include <string>
#include <fstream>
#include "lista.h"
using namespace std;
// Uma árvore de pesquisa binária: na verdade, um objeto da classe Arvore
// representa um nodo de uma árvore ...
template <class T> class Arvore {
protected:
string chave; // chave e valor guardados neste nodo da árvore
T valor;
Arvore<T> * esq, * dir, * pai; // ramos esquerdo e direito, e uma referência ao nodo pai
public:
Arvore(const string & key, const T& data);
Arvore();
~Arvore();
void adiciona(const string & chave, const T & dado);
// "obtem" e "operator[]" são idênticos
T & obtem(const string & chave);
T & operator[](const string & chave);
// remove um valor da árvore ... deixemos isto por último ;-)
T remove(const string & chave);
// algo mais simples: remove os ramos esquerdo e direito
void esvazia();
// altura da folha mais profunda
unsigned int altura() const;
void escrevaSe(ostream & out) const;
// retorna a subárvore esquerda ou direita
Arvore<T> * esquerda() const;
Arvore<T> * direita() const;
// cria uma lista para onde copia valores/chaves, retornando-a
// como resultado
Lista<T> * valores() const;
Lista<string> * chaves() const;
// grava uma cópia dos valores/chaves na lista fornecida
void valores(Lista<T> & lista) const;
void chaves(Lista<string> & lista) const;
// retorna uma referência a chave ou valor da raiz
string & obtemChave() const {return chave;}
T & obtemValor() const {return valor;}
// verifica se uma chave existe na árvore
bool existe(const string & chave) const;
};
#endif
Atividade
- O programa abaixo pode ser usado como um testador inicial da implementação da árvore:
#include <iostream> #include <string> #include "arvore.h" using namespace std; int main() { string k1 = "palavra1"; string k2 = "palavra2"; string k3 = "palavra3"; string k4 = "palavra4"; string w1 = "banana"; string w2 = "morango"; string w3 = "laranja"; // Uma árvore deve ser criada dinamicamente ... isso facilita // sua implementação. Arvore<string> * arv = new Arvore<string>(k2, w2); arv->adiciona(k1, w1); arv->adiciona(k3, w3); cout << "arv[" << k1 << "] = " << arv->obtem(k1) << endl; cout << "arv[" << k2 << "] = " << arv->obtem(k2) << endl; cout << "arv[" << k3 << "] = " << arv->obtem(k3) << endl; cout << "arv[" << k4 << "] = " << arv->obtem(k4) << endl; delete arv; return 0; }
- Como exercício, implemente adiciona e obtem de forma recursiva. Nessa versão, essas funções 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.
Notas PII
| Aluno | Projeto 1 | Projeto 2 | Prova 1 | Projeto 3 | Prova 2 | Projeto 4 | REC | Final |
|---|---|---|---|---|---|---|---|---|
| Alline Domingos | 8,0 | 8,0 | 5,0 | 7,5 | 3,0 | 8,5 | 8,6 | 8,1 |
| Bruno Marcos Espindola | 10,0 | 9,5 | 7,5 | 10,0 | 7,15 | 9,5 | - | 9,0 |
| Caroline Liz Scoz | 5,0 | 7,5 | 6,0 | 8,0 | 4,4 | |||
| Gustavo Wagner | 8,0 | 8,0 | 7,5 | 7,5 | 6,2 | 8,5 | - | 7,6 |
| Jefersson Ricardo | 5,0 | 7,5 | 5,0 | 8,0 | 1,0 | |||
| Joseane Bortoli | 5,0 | 7,5 | 5,0 | 8,0 | 4,6 | |||
| Murilo Bauer | 10,0 | 9,5 | 7,5 | 10,0 | 9,8 | 9,5 | - | 9,4 |
| Paula Cristina Grando | 10,0 | 9,0 | 6,5 | 9,0 | 6,2 | 8,5 | - | 8,2 |
| Ricardo Amorin | 10,0 | 9,0 | 7,5 | 9,0 | 7,0 | 8,5 | - | 8,5 |
| Sérgio Luiz Heinzen | 10,0 | 9,5 | 7,5 | 10,0 | 8,2 | 9,5 | - | 9,2 |
| Thiago Grisolf | 5,0 | 8,0 | 7,0 | 7,5 | 0,0 | 8,5 | 0,0 | REPROVADO |
Apoio para árvores Binárias: <https://pt.wikibooks.org/wiki/Programar_em_C/%C3%81rvores_bin%C3%A1rias: