Mudanças entre as edições de "PRG2-2015-2b"
Linha 287: | Linha 287: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | 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++..... | ||
+ | |||
+ | |||
+ | |||
+ | Bibliografia: | ||
+ | |||
+ | Schildt, H. C Completo e Total. 3ª Edição. São Paulo. Pearson Makron Books, 1997. |
Edição das 12h00min de 3 de dezembro de 2015
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++.....
Bibliografia:
Schildt, H. C Completo e Total. 3ª Edição. São Paulo. Pearson Makron Books, 1997.