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 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;
}
}
Data da entrega: 23/12/2015.
Enviar para: francisco.assis@ifsc.edu.br
Bibliografia:
Schildt, H. C Completo e Total. 3ª Edição. São Paulo. Pearson Makron Books, 1997.