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?
Bibliografia:
Schildt, H. C Completo e Total. 3ª Edição. São Paulo. Pearson Makron Books, 1997.