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

Plano de Ensino

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

• Arquivos para Prova 1 2015-2

Prova 2015-1

• Uma lista de exercícios
• Prova de 2015-1 (ignorem as questões sobre listas)

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