Lista 6 de EDA - Estrutura de dados

Lista de estrutura de dados - 6ª lista

Faça um programa que cadastre 50 produtos.
Cada produto deve ser cadastrado com os seguintes dados: código, nome e preço.

1. Use 3 métodos de ordenação diferentes, liste todos os dados na seguintes formas:

• Ordem crescente de código;
• Ordem decrescente de preço;
• Ordem alfabética de nome;

 2. Verifique no vetor ordenado:

• O produto mais barato, se houver mais de um com o mesmo preço, mostrá-los.
• Calcule e mostre a diferença entre os preços do produto mais barato e do mais caro.

3. Mostre quantas comparações devem ser feitas para encontrar um produto pelo código usando:

• Busca sequencial;
• Busca binária;

Resolução:

#include <stdio_ext.h>
#include <stdlib.h>
#include <string.h>

#define TAMANHO 50

typedef struct
{
    int codigo;
    char nome[80];
    float preco;
} Produto;

/* Protótipos das funções */
void inicializa_vetor (Produto**);
void menu (Produto**, int*);
void cadastrar (Produto**, int*);
void listar (Produto**, int*);
void ordenacao (Produto**, int*, int);
void bubblesort(Produto**, int*);
void selectionsort(Produto**, int*);
void insertionsort(Produto**, int*);
float buscarMaisBarato(Produto**, int*, int);
float buscarMaisCaro(Produto**, int*, int);
int buscaLinear(Produto**, int*, int);
int buscaBinaria(Produto**, int*, int);

int
main (void)
{
    Produto *p[TAMANHO];
    int qtde=0; // quantidade de elementos cadastrados em meu vetor

    inicializa_vetor(p);
    menu(p, &qtde);

    return 0;
}

void
inicializa_vetor(Produto **p)
{
    int i;
    for (i=0; i<TAMANHO; i++) p[i]=NULL;
}

void
menu(Produto **p, int *qtde)
{
    int opcao, ordenado=0;

    while (1)
    {
        printf ("\nInforme a opção desejada\n");
        puts ("1 - Cadastrar");
        puts ("2 - Listar");
        puts ("3 - Ordenar");
        puts ("4 - Produto mais barato");
        puts ("5 - Diferença entre produtos");
        puts ("6 - Busca Linear");
        puts ("7 - Busca Binária");
        puts ("8 - Sair");
        printf (".: ");
        scanf ("%d", &opcao);

        switch (opcao)
        {
            case 1:
                cadastrar(p, qtde);
                ordenado=0;
            break;
            case 2:
                listar(p, qtde);
            break;
            case 3:
                system ("clear");
                puts ("--- Métodos de ordenação ---");
                puts ("1 - Bubble Sort (código)");
                puts ("2 - Selection Sort (preço)");
                puts ("3 - Insertion Sort (alfabética)");
                int ordem;
                scanf ("%d", &ordem);

                if (ordem==1) ordenado=1;

                ordenacao(p, qtde, ordem);
            break;
            case 4:
                system ("clear");
                buscarMaisBarato(p, qtde, 1); // despresando o retorno
            break;
            case 5:
                system ("clear");
                printf ("Mais caro custa = %.2f\nMais barato custa = %.2f\nDiferença = %.2f \n", buscarMaisCaro(p, qtde, 0), buscarMaisBarato(p,qtde,0),
                        buscarMaisCaro(p,qtde,0) -buscarMaisBarato(p,qtde,0));
            break;
            case 6:
                printf ("\nInforme o código.: ");
                int codigo;
                scanf ("%d", &codigo);
                system ("clear");
                printf ("\nForam feitos %d loop(s) para encontrar o número %d.\n", buscaLinear(p, qtde, codigo), codigo);
            break;
            case 7:
                printf ("\nInforme o código.: ");
                scanf ("%d", &opcao);
                if(ordenado)
                {
                    system ("clear");
                    printf ("\nForam feitos %d loop(s) para encontrar o número %d.\n", buscaBinaria(p, qtde, opcao), opcao);
                }
                else puts ("\n -- Primeiro ordene o vetor pelo código antes de realizar a busca binária! -- ");
            break;
            case 8:
                system ("clear");
                puts ("Programa encerrado!");
                exit(0);
            break;
        }
    }
}

void
cadastrar(Produto **p, int *qtde)
{
    int codigo;
    printf ("\nEntre com o código do produto.: ");
    scanf("%d", &codigo);

    int i;
    for (i=0; i<*qtde; i++)
        if (p[i]->codigo == codigo) break;

    if (i != *qtde)
    {
        system ("clear");
        printf ("\n\n--- Esse Código já está cadastrado! ---\n\n");
    }
    else
    {
        // variável qtde diz o indice que o meu vetor deve inserir o novo registro
        p[*qtde] = (Produto*) malloc (sizeof(Produto));
        p[*qtde]->codigo = codigo;
        __fpurge (stdin);
        printf ("\nEntre com a descrição do produto.: ");
        gets (p[*qtde]->nome);
        printf ("\nEntre com o valor do produto.: ");
        scanf ("%f", &p[*qtde]->preco);
        *qtde = *qtde + 1; // incrementa a quantidade de produtos inseridos em meu vetor
        system ("clear");
        puts ("Produto inserido com sucesso!");
    }
}

void
listar(Produto **p, int *qtde)
{
    system ("clear");
    puts ("--- Lista de produtos ---");
    int i;
    for (i=0; i<*qtde; i++)
        printf ("\nCódigo.: %d \tNome.: %s \tPreço.: %.2f\n", p[i]->codigo, p[i]->nome, p[i]->preco);
}

void
ordenacao(Produto **p, int *qtde, int ordem)
{
    if (ordem == 1) bubblesort(p, qtde);
    else if (ordem == 2) selectionsort(p, qtde);
    else if (ordem == 3) insertionsort(p, qtde);
    else
    {
        system ("clear");
        puts ("--- Opção não cadastrada ---");
    }
}

void
bubblesort(Produto **p, int *qtde)
{
    int i,j;
    Produto *aux;

    for (i=0; i<*qtde; i++)
    {
        for (j=0; j<*qtde; j++)
        {
            if (p[i]->codigo<p[j]->codigo)
            {
                aux = p[i];
                p[i] = p[j];
                p[j] = aux;
            }
        }
    }
    puts ("-- Vetor ordenado com sucesso pelo método BUBBLE SORT! -- \n");
}

void
selectionsort(Produto **p, int *qtde)
{
    int i,j;
    Produto *aux;

    for (i=0; i<*qtde; i++)
    {
        for (j=i; j<*qtde; j++)
        {
            if (p[i]->preco < p[j]->preco)
            {
                aux = p[i];
                p[i] = p[j];
                p[j] = aux;
            }
        }
    }
    puts ("-- Vetor ordenado com sucesso pelo método SELECTION SORT! -- \n");
}

void
insertionsort(Produto **p, int *qtde)
{
    int i,j;
    Produto *eleito;

    for (j=1; j<=*qtde-1; j++)
    {
        eleito = p[j];
        i = j-1;

        while (i>=0 && (strcmp(eleito->nome, p[i]->nome) == -1))
        {
            p[i+1] = p[i];
            i--;
        }
        p[i+1] = eleito;
    }
    puts ("-- Vetor ordenado com sucesso pelo método INSERTION SORT! -- \n");
}

float
buscarMaisBarato(Produto **p, int *qtde, int listar)
{
    int i, index=0;
    float v=p[index]->preco;
    for (i=1; i<*qtde; i++)
    {
        if (p[i]->preco<v)
        {
            v=p[i]->preco;
            index=i;
        }
    }

    if (listar)
    {
        puts ("\n -- Produto(s) mais barato(s) da base de dados --");

        for (i=0; i<*qtde; i++)
        {
            if (v==p[i]->preco)
            {
                printf ("\nCódigo.: %d", p[i]->codigo);
                printf ("\nNome.: %s", p[i]->nome);
                printf ("\nPreço.: %.2f", p[i]->preco);
            }
            puts("");
        }
    }
    return v;
}

float
buscarMaisCaro(Produto **p, int *qtde, int listar)
{
    int i, index=0;
    float v=p[index]->preco;
    for (i=1; i<*qtde; i++)
    {
        if (p[i]->preco>v)
        {
            v=p[i]->preco;
            index=i;
        }
    }

    if (listar)
    {
        puts ("\n -- Produto(s) mais Caro(s) da base de dados --");
        for (i=0; i<*qtde; i++)
        {
            if (v==p[i]->preco)
            {
                printf ("\nCódigo.: %d", p[i]->codigo);
                printf ("\nNome.: %s", p[i]->nome);
                printf ("\nPreço.: %.2f", p[i]->preco);
            }
            puts("");
        }
    }
    return v;
}

int
buscaLinear(Produto **p, int *qtde, int codigo)
{
    int i, x=0;
    for (i=0; i<*qtde; i++)
    {
        if (p[i]->codigo == codigo)
        {
            x=1;
            break;
        }
    }
    if (x==0)
        puts ("-- Nenhum registro foi encontrado! --");
    return i;
}

int
buscaBinaria(Produto **p, int *qtde, int codigo)
{
    int esquerda=0, meio, direita=*qtde-1;
    int status=0, x=0;

    while (esquerda <= direita)
    {
        x++;
        meio = (esquerda+direita)/2;
        if (p[meio]->codigo == codigo) status = 1;
        if (p[meio]->codigo < codigo) esquerda = meio + 1;
        else direita = meio - 1;
    }

    if (status == 1)
    {
        printf ("\n \t\t -- Registro número %d", p[meio]->codigo);
        printf ("\n Nome.: %s", p[meio]->nome);
        printf ("\n Preço.: %.2f", p[meio]->preco);
        puts("");
    }
    else
        printf ("\n\t\t -- Nenhum registro foi encontrado!--\n");
    return x;
}
Dúvidas ou sugestões deixe um comentário. Até a próxima!

Programando em Java - parte 12

Herança

Na programação orientada a objetos temos o recurso de herança, que nada mais é que abstrair uma classe o mais genericamente possível e escrever outras classes mais especificas aproveitando os comportamentos e atributos da classe genérica. A ideia da herença é aumentar a produtividade na escrita do código e também deixar o código mais limpo, evitando a redundancia de código entre as classes (código repetido).

Como todo conceito da POO não é explicitamente obrigatório o uso de herança em seu código também não, porém, não usá-lo significa quebra conceitual.

Uma classe que faz tudo!

Muitos programadores acham que é beneficio criar uma classe que faça completamente tudo em seu sistema. Não há problema algum em declarar todas as funcionalidades de um sistema dentro de uma classe. No entanto, seu código fica muito mais complexo e a dificuldade de manutenção aumenta muito. Vejamos como poderiamos resolver o mesmo problema primeiramente sem utilizar a herança, depois utilizando a herança de forma errada e por fim aplicando a herança corretamente.

Classe animal.java

Olá meu nome é Juca! 
Preciso de um sistema que cadastre meus bichos de estimação. Sabe senhor programador eu sou um cara muito versátil quando se fala de animais, eu gosto de: cachorros, gatos, lagartos, passáros, tartarugas .. Preciso de um sistema bom, barato e que me entregue o mais rápido possível OK?!

Bom, muitas vezes você vai se deparar com os Jucas da vida, e a pergunta é como os maus programadores fariam esse sistema? Será que eles usariam Herança? Vamos para o exemplo:

public class BichoEstimacao {
// geral
private Animal animal;
private String nome;
private Date aniversario;
// mamiferos
private String corPelo;
private int nroGlandulasMamaria;
// repteis
private float temperaturaCorporal;
private String corEscama;
// métodos
}

Bom apesar de resolver todos os nossos problemas quanto a modelagem do sistema, programar todas as funcionalidades em apenas uma classe pode dificultar o desenvolvimento. Supondo que dois ou mais desenvolvedores são responsáveis pela implementação dos bichos de estimação, provavelmente eles modificariam a mesma classe em paralelo. Além disso, os desenvolvedores ficariam  confusos ao abrirem o código dessa classe.

Uma classe para cada animal

Para modelar melhor os animais, evitando uma quantidade grande de atributos e métodos desnecessários, criaremos uma classe para cada Animal.

public class Gato {
    // geral
    private Animal animal;
    private String nome;
    private Date aniversario;
    // gato
    private String corPelo;
    private int nroGlandulasMamarias;
    private String raca;
}


public class Tiu {
    // geral
    private Animal animal;
    private String nome;
    private Date aniversario;
    // tiu
    private String corEscama;
    private float temperaturaCorpo;
    private boolean chocando;
}
Criar uma classe para cada animal torna o sistema mais flexível, pois qualquer alteração em um determinado serviço não causará efeitos colaterais nos outros. Porém, essas classes apresentam redundância de código e sabemos que a herança veio para abolir isso! E pior, qualquer alteração que seja comum a todos os animais deverá ser implementada classe por classe. Isso quer dizer que ainda estamos errando em alguma coisa.

Uma classe genérica e várias específicas

Na modelagem dos animais do sistema do Juca, podemos aplicar o conceito de Herança. A ideia consiste em reutilizar o código de uma classe em N classes.

Aplicando herança a esse sistema, vamos ter uma classe BichoEstimacao com todos os atributos e métodos comuns à um animal de estimação, e vamos ter uma classe mais específica detalhando as caracteristicas e comportamentos que cada animal possui.

As classes Gato e Tiu seriam "relacionadas" a classe BichoEstimacao para poder reaproveitar o seu código já definido. Veja a representação UML abaixo:

Os objetos das classes específicas Gato e Tiu possuirão tanto os atributos e métodos definidos em suas respectivas classes quanto os definidos na classe BichoEstimacao. Dizemos que BichoEstimacao é a classe pai, e a Gato e Tiu são suas classes filhas. 

Para "associar/ligar" uma classe especifica a uma classe genérica em Java, utilizamos o comando extends. Não é necessário redefinir o conteúdo já declarado na classe genérica.

public class BichoEstimacao {
    // geral 
    private Animal animal;
    private String nome;
    private Date aniversario;
}
public class Gato extends BichoEstimacao {
    // gato
    private corPelo;
    private nroGlandulasMamarias;
    private raca;
}
public class Tiu extends BichoEstimacao {
    // tiu
    private String corEscama;
    private float temperaturaCorpo;
    private boolean chocando;
}
As classes filhas podem acessar todos os métodos e atributos de seu pai. Java não dá suporte a herança multipla, ou seja, para a Java um Pai pode ter vários filhos já os filhos são de um único pai. Esse pensamento traduzido para vida real é muito lógico já que um filho tem um único pai biológico e esse pai pode ter vários filhos.

Gato mimo = new Gato();
//chamada a um método da classe BichoEstimacao
mimo.setNome = "Mimo";
//chamada a um método da classe Gato
mimo.setRaca = "Angora";

Calcular idade

Todos os animais possuim uma idade certo? Vamos considerar inicialmente que para todos animais o calculo de idade é o mesmo. Sendo assim poderiamos implementar um método na classe BichoEstimacao para calcular a idade dos animais. Este método será reaproveitado por todas as classes que herdam da classe BichoEstimacao.

public class BichoEstimacao {
// atributos public int calculaIdade(int anoNascimento, int anoAtual) { return anoAtual - anoNascimento; }  }
BichoEstimacao bicho = new BichoEstimacao();
Gato megui = new Gato();
System.out.println("Idade: ", + bicho.calculaIdade(2010,2012));
System.out.println("Idade: ", + megui.calculaIdade(2012,2012));

Reescrita de método

Como sabemos cada animal representa uma idade diferente ao calculo da idade humana, alguns animais possuem um envelhicimento mais tardio e outros mais recentes. Como essa lógica é específica de cada animal devemos implementar esse calculo na classe BichoEstimacao.

class Gato extends BichoEstimacao {
// atributos
public int calcIdadeGato(int anoNascimento, int anoAtual) {
return (anoAtual - anoNascimento) * 7 ;
}

Para os objetos da classe Gato devemos chamar o método calcIdadeGato. Para todos os outros animais devemos chamar o método calculaIdade.

Mesmo assim isso não impederia que o método calculaIdade fosse chamado de um objeto da classe Gato, pois este método é herdado da sua classe Pai BichoEstimacao. Deste modo existe o risco de acidentamente invocarmos o método errado.

O correto é substituir a implementação do método calculaIdade(int anoNascimento, int anoAtual) herdado da classe BichoEstimacao na classe Gato. Para isso, basta escrever o método calculaIdade(int anoNascimento, int anoAtual) também na classe Gato do mesmo jeito que ela foi definida na classe Pai (BichoEstimacao), ou seja, com a mesma assinatura.

class Gato extends BichoEstimacao {
// atributos
public int calculaIdade(int anoNascimento, int anoAtual) {
return (anoAtual - anoNascimento) * 7 ;
}

Os métodos das classes filhas tem prioridade sobre os métodos da classe pai. Se o método chamado existe na classe filha ele será chamado, caso contrário se ele não exister será procurado sua existencia na classe Pai.