Как использовать бинарный поиск по массиву строк - PullRequest
Новая
       9

Как использовать бинарный поиск по массиву строк

0 голосов
/ 15 мая 2018

Мне нужно написать программу, используя только те вещи, которые я изучил в классе, где я регистрирую информацию из автомобиля, сортирую ее и использую бинарный поиск для поиска автомобильного номера.Если номерной знак найден, распечатайте всю информацию об этом конкретном автомобиле. Если не указано "Не найдено", и вернет -1 .Все работает нормально до двоичного поиска, проблема в том, что он не находит номерной знак, он всегда возвращает -1. 

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

#define MAX_CARRO 5  // DEFINE TAMANHO DA STRUCT

typedef struct   // STRUCT
{
    char placa[50];
    char marca[50];
    char modelo[50];
    char ano[50];
    char valordiaria[50];
} carro;
carro car[MAX_CARRO];

int compare (const void * a, const void * b)
{    
    carro *carroA = (carro *)a;
    carro *carroB = (carro *)b;   

    return strcmp(carroA, carroB);
}

int main()
{
    int x=0; //COUNTER

    for(x=0; x<MAX_CARRO; x++) // CAR REGISTER
    {    
        printf("\nCarro: %d", (x+1));

        printf("\nPlaca: ");
        scanf("%s",car[x].placa);    

        printf("Marca: ");
        scanf("%s",car[x].marca);    

        printf("Modelo: ");
        scanf("%s",car[x].modelo);    

        printf("Ano: ");
        scanf("%s",car[x].ano);    

        printf("Valor da diaria: ");
        scanf("%s",car[x].valordiaria);    
    }    

    qsort (car, MAX_CARRO, sizeof(carro), compare);  // USO DO QSORT

    printf("\n\nSTRUCT ORDENADA: \n");
    for(x=0; x<MAX_CARRO; x++) // MOSTRA NA TELA A STRUCT ORDENADA
    {
        printf("\n\n\nCarro: %d", (x+1));
        printf("\nPlaca: %s", car[x].placa);
        printf("\nMarca: %s", car[x].marca);
        printf("\nModelo: %s", car[x].modelo);
        printf("\nAno: %s", car[x].ano);
        printf("\nValor da diaria: %s", car[x].valordiaria);
    }

    char k[10];

    //           *****BINARY SEARCH******    
    printf("\n\n\n*****BUSCA DE PLACAS*****\n\n\n\n");
    printf("Digite a placa que deseja procurar: \n");
    scanf("%s", &k);

//              ***PROBLEM***     

    int low, high, mid;

    low=0;
    high = MAX_CARRO-1;
    while(low<=high)
    {
        mid = (low+high)/2;

        if (strcmp(k, car[mid].placa)<0)
            high=mid-1;    

        else if (strcmp(k, car[mid].placa)>0)
            low=mid+1;    

        else
        {
            printf("\nPlaca: %s", car[mid].placa);
            printf("\nMarca: %s", car[mid].marca);
            printf("\nModelo: %s", car[mid].modelo);
            printf("\nAno: %s", car[mid].ano);
            printf("\nValor da diaria: %s", car[mid].valordiaria);
        }    

        printf("\n\n****Not found****\n\n\n");
        return -1; //     
    }    
}

1 Ответ

0 голосов
/ 15 мая 2018

У вас есть несколько ошибок.

Первая ошибка в вашей функции сравнения ().Вы не можете написать эту строку 

return strcmp(carroA, carroB);

Поскольку strcmp работает только с типами char *, а carroA и carroB относятся к типу carro *.Вы должны поместить 

 return strcmp(carroA->placo, carroB->placo);

Теперь вы будете сортировать ваши структуры по значению placo.

Теперь давайте взглянем на вашу основную функцию.

Первая ошибка в main() в вашей строке кода 

  scanf("%s", &k);

Вам не нужно &, вы должны сделать это следующим образом 

  scanf("%s",k);

Вторая ошибка в вашем цикле while () впоследняя строка 

  return -1;

Это огромная вещь, потому что main () вернет -1.Если вы хотите, чтобы main () завершала работу, как при появлении ошибки, вы должны написать return 1;

Возможно, вам следует использовать одну переменную, чтобы определить погоду, которую вы нашли в бинарном поиске 

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

#define MAX_CARRO 5  // DEFINE TAMANHO DA STRUCT

typedef struct   // STRUCT
{
    char placa[50];
    char marca[50];
    char modelo[50];
    char ano[50];
    char valordiaria[50];
} carro;
carro car[MAX_CARRO];

int compare (const void * a, const void * b)
{    
    carro *carroA = (carro *)a;
    carro *carroB = (carro *)b;   

    return strcmp(carroA->placa, carroB->placa);
}

int main()
{
    int x=0; //COUNTER

    for(x=0; x<MAX_CARRO; x++) // CAR REGISTER
    {    
        printf("\nCarro: %d", (x+1));

        printf("\nPlaca: ");
        scanf("%s",car[x].placa);    

        printf("Marca: ");
        scanf("%s",car[x].marca);    

        printf("Modelo: ");
        scanf("%s",car[x].modelo);    

        printf("Ano: ");
        scanf("%s",car[x].ano);    

        printf("Valor da diaria: ");
        scanf("%s",car[x].valordiaria);    
    }    

    qsort (car, MAX_CARRO, sizeof(carro), compare);  // USO DO QSORT

    printf("\n\nSTRUCT ORDENADA: \n");
    for(x=0; x<MAX_CARRO; x++) // MOSTRA NA TELA A STRUCT ORDENADA
    {
        printf("\n\n\nCarro: %d", (x+1));
        printf("\nPlaca: %s", car[x].placa);
        printf("\nMarca: %s", car[x].marca);
        printf("\nModelo: %s", car[x].modelo);
        printf("\nAno: %s", car[x].ano);
        printf("\nValor da diaria: %s", car[x].valordiaria);
    }

    char k[10];

    //           *****BINARY SEARCH******    
    printf("\n\n\n*****BUSCA DE PLACAS*****\n\n\n\n");
    printf("Digite a placa que deseja procurar: \n");
    scanf("%s", k);

//              ***PROBLEM***     

    int low, high, mid;

    low=0;
    high = MAX_CARRO-1;
    int found=0;
    while(low<=high && !found)
    {
        mid = (low+high)/2;

        if (strcmp(k, car[mid].placa)<0)
            high=mid-1;    

        else if (strcmp(k, car[mid].placa)>0)
            low=mid+1;    

        else
        {
            found = 1;
            printf("\nPlaca: %s", car[mid].placa);
            printf("\nMarca: %s", car[mid].marca);
            printf("\nModelo: %s", car[mid].modelo);
            printf("\nAno: %s", car[mid].ano);
            printf("\nValor da diaria: %s", car[mid].valordiaria);
        }    


    } 
    if(!found)
        printf("\n\n****Not found****\n\n\n");
 return 0; //
}
...