C Busca Binária struct C: retorna sempre o mesmo valor

Estalha · 21 de novembro de 2021

Bom dia a todos.

Estou tendo problema com esse programa que executa uma busca binária em um arquivo txt organizado da seguinte forma:

AUTOR;OBRA;GENERO;ANO

um em cada linha. Eu preciso implementar uma busca binária recebendo o nome do autor e seu gênero e retornar a sua obra mais recente desse gênero. O problema é que a busca binária estar retornando sempre o mesmo valor, independente dos inputs.

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

#define MAX_AUTOR 80
#define MAX_TIPO 30
#define MAX_GERAL 150

typedef struct DADOS{
    char *nome;
    char *obra;
    char *tipo;
    int ano;
}Dados;


int contaLinhas(FILE *file);
void inicializa(int n, Dados** info);
Dados *buscaBinariaPrincipal(Dados **info, int numObras, char *autor);
int comparaTipo(Dados **info, int inicio);
int menorData(int d1, int d2);

int main(void){
    FILE *arqInfo = fopen("", "r");
    int numLinhas =contaLinhas(arqInfo);
    int posicao = 0;
    
    if(!arqInfo){
        printf("Erro ao abrir o arquivo");
        exit(1);
    }

    Dados *info[MAX_GERAL];
    inicializa(MAX_GERAL, info);
    

    while(posicao <= numLinhas){
        info[posicao]=(Dados*)malloc(sizeof(Dados));

        info[posicao]->nome =(char*)malloc(sizeof(char)*MAX_AUTOR);
        info[posicao]->obra =(char*)malloc(sizeof(char)*MAX_AUTOR);
        info[posicao]->tipo =(char*)malloc(sizeof(char)*MAX_TIPO);

        if((info[posicao] == NULL)||(info[posicao]->nome == NULL)||(info[posicao]->obra == NULL)||(info[posicao]->tipo == NULL)){
            printf("Erro ao alocar memoria");
            exit(1);
        }

        fscanf(arqInfo," %[^\n;]; %[^\n;]; %[^\n;];%d\n",info[posicao]->nome,info[posicao]->obra,info[posicao]->tipo,&info[posicao]->ano);
        posicao++;
    }
    rewind(arqInfo);
    char *autorProcura=(char*)malloc(sizeof(char)*MAX_AUTOR);;
    char *tipoProcura=(char*)malloc(sizeof(char)*MAX_TIPO);;

    if((autorProcura == NULL) || (tipoProcura == NULL)){
        printf("Erro ao alocar memoria");
        exit(1);
    }

    printf("Insira o nome do autor: ");
    scanf(" %[^\n]", autorProcura);
    printf("Insira o tipo de obra: ");
    scanf(" %[^\n]", tipoProcura);
    int numObras = posicao;
    //printf("%s %s %s %d", info[1]->nome,info[1]->obra,info[1]->tipo,info[1]->ano);
    Dados *resultado = buscaBinariaPrincipal(info, numObras, autorProcura);
    printf("%s %s %s %d ",resultado->nome, resultado->obra, resultado->tipo, resultado->ano);

    for(int z=0; z<posicao;z++){
        free(info[z]->nome);
        free(info[z]->obra);
        free(info[z]->tipo);
        free(info[z]);
    }
    free(autorProcura);
    free(tipoProcura);

    fclose(arqInfo);
    return 0;
}


int contaLinhas(FILE *file){

    char c; //le letra por letra, cada letra 1 byte
    char letra ='\n'; //letra parametro para veriicar fim de linha
    int numLinhas = 0;

    while(fread (&c, sizeof(char), 1, file)) {
            if(c == letra) { //se a ultima letra for \n é porque a linha acabou, somando +1
                numLinhas++;    //numero de linhas
            }
    }
    rewind(file);
    return numLinhas;
}

void inicializa (int n, Dados** info){
    int i;
    for (i=0; i<n; i++)
        info[i] = NULL;
}


Dados *buscaBinariaPrincipal(Dados **info, int numObras, char *autor){
    int inicio = 0;
    int final = numObras - 1;

    while(inicio <= final){
        int meio = (inicio + final)/2;
        switch (strcmp(autor, info[meio]->nome)){
            case -1:{
                final = meio -1;
                break;
            }
            case 1:{
                inicio = meio -1;
                break;
            }
            case 0:{
                int resultado = comparaTipo(info, meio);
                return info[meio];
            }
        }
    }
    printf("O autor não foi encontrado");
    return NULL;
}

int comparaTipo(Dados **info, int inicio){
    int i =0;
    while(strcmp(info[inicio]->nome, info[inicio+i]->nome) == 0){
        i++;
    }
    int final = i;
    while(inicio <= final){
        int meio = (inicio + final)/2;
        int inicioConstante = meio;
        if(menorData(info[inicioConstante]->ano,info[meio]->ano) == -1)
            final = meio -1;
        else 
            if(menorData(info[inicioConstante]->ano,info[meio]->ano) == 1)
                inicio = meio + 1;
            else{
                while((meio>0) && menorData(info[inicioConstante]->ano,info[meio-1]->ano) == 0){
                meio--;}
                int retorno = meio;
                return retorno;
            }
    }
    printf("Genero não encontrado ");
    return -1;
}

int menorData(int d1, int d2){
    if(d1 < d2) return -1;
    if(d1 > d2) return 1;
    return 0;
}

arfneto · 21 de novembro de 2021

2 horas atrás, Estalha disse:

Estou tendo problema com esse programa que executa uma busca binária em um arquivo txt organizado da seguinte forma:

AUTOR;OBRA;GENERO;ANO

um em cada linha. Eu preciso implementar uma busca binária recebendo o nome do autor e seu gênero e retornar a sua obra mais recente desse gênero. O problema é que a busca binária estar retornando sempre o mesmo valor, independente dos inputs.

A busca binária não é no arquivo txt mas sim num vetor info[], certo?

E se a busca vai ser por autor imagino, e não pelo par autor/genero. Talvez o mais simples seja indexar apenas autores e manter o vetor ordenado por autor e genero, depois ano e obra, e assim a busca bina'ria retorna o índice da primeira obra do autor e a partir daí busca as obras.

Estalha · 21 de novembro de 2021

@arfneto Eu tentei fazer assim também, criei mais 1 função auxiliar para fazer a parte do gênero porém o resultado permanece o mesmo

arfneto · 21 de novembro de 2021

@Estalha poste o arquivo de teste e o código

Mas entenda que mesmo que a busca leve ao autor/genero não vai saber se é a primeira obra do ano.... pode ser a última ou qualquer outra.

Para funcionar precisa classificar por autor/genero sem duplicidade, retornando o índice da primeira obra do autor/genero na busca. Assim é só seguir em frente na sequencia e ver as obras por ano e dentro do ano por titulo/////

arfneto · 22 de novembro de 2021

Escreva em torno dos dados.

Pense no modelo antes de escrever o código. Vai perder muito menos tempo testando.

Tem só isso no seu programa

typedef struct DADOS
{
    char* nome;
    char* obra;
    char* tipo;
    int   ano;
} Dados;

Você até colocou o nome no plural, mas não adianta: é uma obra só. E não precisa de dois nomes. A estrutura pode muito bem ser anônima. Prefira:

typedef struct
{
    char* nome;
    char* obra;
    char* tipo;
    int   ano;

} Dado;

Mas entenda que esses exercícios de programação quase sempre envolvem um container, uma lista de coisas. São os livros, as músicas da playlist, o estoque. Tudo igual. Mas parece que não ensinam ou não escrevem sobre como compor isso.

COMPARE


typedef struct
{
    char* nome;
    char* obra;
    char* tipo;
    int   ano;

} Dado;

typedef struct
{
    size_t limite;
    size_t N;   // quantas
    Dado*  lv;  // os livros

} Dados;

Ler o arquivo todo para saber quantas obras são é algo ingênuo. Crie o arquivo em blocos.

E a função de comparação deve comparar o que? Duas obras, claro. Assim pode usar o sort normal, já que nada acrescenta programar isso porque não parece estar no enunciado.

E claro que a busca binária deve ser flexível porque assim pode usar para encontrar o autor e depois a obra.

Considere

#define LIMITE_OBRAS 100

typedef struct
{
    char* nome;
    char* obra;
    char* tipo;
    int   ano;

} Dado;

typedef struct
{
    size_t limite;
    size_t N;   // quantas
    Dado*  lv;  // os livros

} Dados;

int    compara(Dado* l1, Dado* l2);
Dados* apaga(Dados*);
Dados* cria(const size_t limite);
size_t busca(int* vet, size_t ini, size_t fim);