[C] Ricerca binaria

[sizeof]

Ciao a tutti,
vorrei sapere se la ricerca binaria si può effettuare solo su file ad accesso casuale (binari) oppure se anche su quelli ad acesso sequenziale.
Ho pensato che è possibile farlo per entrambi i tipi di file riportando i dati in memoria (una struct per esempio) ordinandoli e di conseguenza effettuare la ricerca binaria..cosa mi dite?
Grazie

[oregon]

Il termine "binaria" non ha nulla a che fare con il tipo di file da cui provengono i dati.

Indica soltanto che l'algoritmo procede nella ricerca selezionando, di volta in volta, metà dell'insieme esaminato (quindi fa una selezione tra due insiemi).

Se i dati sono in memoria e sono ordinati, non ha importanza da dove provengono.

P.S. Ma perché non ti avvali della documentazione che puoi trovare su internet? Ad esempio wikipedia?

[sizeof]

si si faccio ricerche in rete però mi fido con certezza più di questo forum perchè ricevo risposte specifiche e sicure.

[sizeof]

Ho fatto in questo modo, passando la struct e la chiave di ricerca per riferimento :

#include <stdio.h>
#include <string.h>
#define n 100

struct tracce {
        char titolo[20];
        int copie;
}tra[n];

void ricerca (struct tracce *track, char *key, int low, int high, int v);


int main()
{
    int i, j, k, V;
    char buffer[20];
    char tit[20];
    int num, app;
    char chiave[20];

    FILE *cfPtr;


    if ((cfPtr = fopen("brani.dat", "w")) == NULL ) {
        printf("IL file non può essere aperto.\n");
    } else {
        i = 0;
        printf("Inserisci titolo e copie vendute\n");
        printf("Inserisci EOF per terminare\n");
        scanf("%s%d\n", tra[i].titolo, &tra[i].copie);
        fprintf(cfPtr, "%30s", "BRANI\n");
        fprintf(cfPtr, "%20s %20s", "TITOLO", "COPIE VENDUTE\n");
        fprintf(cfPtr, "%20s %20d\n", tra[i].titolo, tra[i].copie);
        while( !feof(stdin) ) {
            i++;
            scanf("%s%d\n", tra[i].titolo, &tra[i].copie);
            fprintf(cfPtr, "%20s %20d\n", tra[i].titolo, tra[i].copie);
            }
            fclose(cfPtr);
    }
    printf("%d", i);
    printf("\n\n");

    for ( j = 0; j < i; i++ ) {
        for ( k = j + 1; k <= i; k++ ) {
            if (strcmp(tra[j].titolo, tra[k].titolo) > 0 ) {
                strcpy(buffer, tra[j].titolo);
                strcpy(tra[j].titolo, tra[k].titolo);
                strcpy(tra[k].titolo, buffer);
                app = tra[j].copie;
                tra[j].copie = tra[k].copie;
                tra[k].copie = app;
            }
        }
    }

    printf("Inserisci il titolo da cercare : \n");
    scanf("%s", chiave);

    ricerca(tra, chiave, 0, i, V);

    if ( V = 1 ) {
        printf("Il brano cercato è stato trovato\n");
    } else if ( V == 0 )
    {
        printf("Il brano cercato NON è stato trovato\n");
    }








    return 0;
}

void ricerca (struct tracce *track, char *key, int low, int high, int v)
    {
        int middle;

        v = 0;
        while (low <= high) {
            middle = (low + high) / 2;
            if (strcmp (key, track.titolo[middle]) == 0) {
                v = 1;
            } else if (strcmp(key, track.titolo[middle]) < 0) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }

    }

il problema è nel confronto all'interno della procedura tra le 2 stringhe, cioè qui

...
if (strcmp (key, track.titolo[middle]) == 0) {
                v = 1;
            } else if (strcmp(key, track.titolo[middle]) < 0) {
...

mi dice che titolo non è una struttura...cosa sbaglio ?

[oregon]

Semmai

track[middle].titolo

[sizeof]

Semmai

track[middle].titolo

si infatti avevo già trovato questo errore e ora mi da errore di segmantation fault

#include <stdio.h>
#include <string.h>
#define n 100

struct tracce {
        char titolo[20];
        int copie;
}tra[n];

void ricerca (struct tracce *track, char *key, int low, int high, int v);


int main()
{
    int i, j, k, V;
    char buffer[20];
    char tit[20];
    int num, app;
    char chiave[20];

    FILE *cfPtr;


    if ((cfPtr = fopen("brani.dat", "w")) == NULL ) {
        printf("IL file non può essere aperto.\n");
    } else {
        i = 0;
        printf("Inserisci titolo e copie vendute\n");
        printf("Inserisci EOF per terminare\n");
        scanf("%s%d\n", tra[i].titolo, &tra[i].copie);
        fprintf(cfPtr, "%30s", "BRANI\n");
        fprintf(cfPtr, "%20s %20s", "TITOLO", "COPIE VENDUTE\n");
        fprintf(cfPtr, "%20s %20d\n", tra[i].titolo, tra[i].copie);
        while( !feof(stdin) ) {
            i++;
            scanf("%s%d\n", tra[i].titolo, &tra[i].copie);
            fprintf(cfPtr, "%20s %20d\n", tra[i].titolo, tra[i].copie);
            }
            fclose(cfPtr);
    }
    printf("%d", i);
    printf("\n\n");

    for ( j = 0; j < i; i++ ) {
        for ( k = j + 1; k <= i; k++ ) {
            if (strcmp(tra[j].titolo, tra[k].titolo) > 0 ) {
                strcpy(buffer, tra[j].titolo);
                strcpy(tra[j].titolo, tra[k].titolo);
                strcpy(tra[k].titolo, buffer);
                app = tra[j].copie;
                tra[j].copie = tra[k].copie;
                tra[k].copie = app;
            }
        }
    }

    printf("Inserisci il titolo da cercare : \n");
    scanf("%s", chiave);

    ricerca(tra, chiave, 0, i, V);

    if ( V = 1 ) {
        printf("Il brano cercato è stato trovato\n");
    } else if ( V == 0 )
    {
        printf("Il brano cercato NON è stato trovato\n");
    }








    return 0;
}

void ricerca (struct tracce *track, char *key, int low, int high, int v)
    {
        int middle;

        v = 0;
        while (low <= high) {
            middle = (low + high) / 2;
            if (strcmp (key, track[middle].titolo) == 0) {
                v = 1;
            } else if (strcmp(key, track[middle].titolo) < 0) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }

    }

credo nellla fase di ordinamento..

[sizeof]

Qualcuno sa dirmi cosa sbaglio in questo programma..perchè non mi accetta la chiave di ricerca ???

#include <stdio.h>
#include <string.h>
#define n 100

struct tracce {
        char titolo[20];
        int copie;
}tra[n];

void ricerca (struct tracce track[], char key[], int low, int high, int v);


int main()
{
    int i, j, k, V;
    char buffer[20];
    char tit[20];
    int num, app;
    char chiave[20];

    FILE *cfPtr;


    if ((cfPtr = fopen("brani.dat", "w")) == NULL ) {
        printf("IL file non può essere aperto.\n");
    } else {
        i = 0;
        printf("Inserisci titolo e copie vendute\n");
        printf("Inserisci EOF per terminare\n");
        scanf("%s%d\n", tra[i].titolo, &tra[i].copie);
        fprintf(cfPtr, "%30s", "BRANI\n");
        fprintf(cfPtr, "%20s %20s", "TITOLO", "COPIE VENDUTE\n");
        fprintf(cfPtr, "%20s %20d\n", tra[i].titolo, tra[i].copie);
        while( !feof(stdin) ) {
            i++;
            scanf("%s%d\n", tra[i].titolo, &tra[i].copie);
            fprintf(cfPtr, "%20s %20d\n", tra[i].titolo, tra[i].copie);
            }
            fclose(cfPtr);
    }

    printf("\n\n");

    for ( j = 0; j < i; j++ ) {
        for ( k = j + 1; k <= i; k++ ) {
            if (strcmp(tra[j].titolo, tra[k].titolo) > 0 ) {
                strcpy(buffer, tra[j].titolo);
                strcpy(tra[j].titolo, tra[k].titolo);
                strcpy(tra[k].titolo, buffer);
                app = tra[j].copie;
                tra[j].copie = tra[k].copie;
                tra[k].copie = app;
            }
        }
    }

    printf("%30s", "BRANI\n");
    printf("%20s %20s", "TITOLO", "COPIE VENDUTE\n");
    for ( j = 0; j <= i; j++ ) {
        printf("%20s %19d\n", tra[j].titolo, tra[j].copie);
    }




    printf("Inserisci il titolo da cercare : \n");
    scanf("%s", chiave);



    ricerca(tra, chiave, 0, i, V);

    printf("%d\n", V);

    if ( V = 1 ) {
        printf("Il brano cercato è stato trovato\n");
    } else if ( V == 0 )
    {
        printf("Il brano cercato NON è stato trovato\n");
    }


    return 0;
}

void ricerca (struct tracce track[], char key[], int low, int high, int v)
{
        int middle;

        v = 0;
        while (low <= high) {
            middle = (low + high) / 2;
            if (strcmp (key, track[middle].titolo) == 0) {
                v = 1;
            } else if (strcmp(key, track[middle].titolo) < 0) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
}

[sizeof]

A quanto pare la procedura non mi restituisce il valore intero di V ma il suo indirizzo...è questo che sbaglio?

[sizeof]

Alla fine ho rimediato in questo modo..però quello di prima non l'ho ancora capito

#include <stdio.h>
#include <string.h>
#define n 100

struct tracce {
        char titolo[20];
        int copie;
}tra[n];

void ricerca (struct tracce track[], char key[], int low, int high);


int main()
{
    int i, j, k, V;
    char buffer[20];
    char tit[20];
    int num, app;
    char chiave[20];

    FILE *cfPtr;


    if ((cfPtr = fopen("brani.dat", "w")) == NULL ) {
        printf("IL file non può essere aperto.\n");
    } else {
        i = 0;
        printf("Inserisci titolo e copie vendute\n");
        printf("Inserisci EOF per terminare\n");
        scanf("%s%d\n", tra[i].titolo, &tra[i].copie);
        fprintf(cfPtr, "%30s", "BRANI\n");
        fprintf(cfPtr, "%20s %20s", "TITOLO", "COPIE VENDUTE\n");
        fprintf(cfPtr, "%20s %20d\n", tra[i].titolo, tra[i].copie);
        while( !feof(stdin) ) {
            i++;
            scanf("%s%d\n", tra[i].titolo, &tra[i].copie);
            fprintf(cfPtr, "%20s %20d\n", tra[i].titolo, tra[i].copie);
            }
            fclose(cfPtr);
    }

    printf("\n\n");

    for ( j = 0; j < i; j++ ) {
        for ( k = j + 1; k <= i; k++ ) {
            if (strcmp(tra[j].titolo, tra[k].titolo) > 0 ) {
                strcpy(buffer, tra[j].titolo);
                strcpy(tra[j].titolo, tra[k].titolo);
                strcpy(tra[k].titolo, buffer);
                app = tra[j].copie;
                tra[j].copie = tra[k].copie;
                tra[k].copie = app;
            }
        }
    }

    printf("%30s", "BRANI\n");
    printf("%20s %20s", "TITOLO", "COPIE VENDUTE\n");
    for ( j = 0; j <= i; j++ ) {
        printf("%20s %19d\n", tra[j].titolo, tra[j].copie);
    }




    printf("Inserisci il titolo da cercare : \n");
    scanf("%s", chiave);

    ricerca(tra, chiave, 0, i);








    return 0;
}

void ricerca (struct tracce track[], char key[], int low, int high)
{
        int middle;
        int v;


        while (low <= high) {
            middle = (low + high) / 2;
            v = strcmp (key, track[middle].titolo);
            if ( v == 0) {
                printf("Il brano cercato è stato trovato\n");
                break;
            } else if ( v < 0) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        if ( v != 0 ) {
            printf("Il brano cercato NON è stato trovato\n");
        }
}