Enrere Mòdul 8
Fonaments de Programació. Llenguatge C/C++---
Pràctica    Resum teòric Exercicis
Pràctica d'ampliació

 
Cerca dicotòmica o binària

En aquesta pràctica aprendrem a realitzar una cerca d'un registre a partir d'un camp donat en una llista de registres ordenats per aquest camp.

 

Desenvolupament de la pràctica

Si les dades d'un conjunt de registres estan desordenades, per poder accedir a un registre determinat només és possible una cerca seqüencial tal i com s'ha fet en la pràctica 1 del mòdul 7. En el cas de que els registres estiguin ordenats es pot fer servir un mètode notablement  superior que és la cerca binària o dicotòmica. Aquest mètode, com el mètode d'ordenació ràpida, està basat en el mètode "divideix i venceràs". 

El mètode consisteix en consultar l'element central de la llista de registres. Si aquest element és més gran que el registre cercat, es torna a fer el mateix amb la primera meitat dels registres, en cas contrari s'agafa la segona meitat. Aquest procés recursiu es repeteix fins que la part que queda de la llista ja no té registres, o fins que es troba el registre cercat. 

Per visualitzar com funciona aquest mètode imaginem que volem buscar la dada 11 d'un conjunt de 10 dades enteres ordenades: 1,3,5,6,8,9,11,15,16,20. 

Anomenarem primer=1 (primera dada), ultim=10 (última dada), tall=5 (dada central). Aquesta dada central, o dada de tall, divideix al conjunt de dades en dues parts. Una comparació (8<11) ens diu que la nostra dada està a la segona part.

Fem primer=tall+1 i tornem a calcular el punt de tall, en aquest cas tall=8. Tornem a fer la comparació de la dada 8, que és 15 amb la dada a cercar (11), i com 15>11, ens quedem amb la primera part, és a dir, fem ultim =tall-1. Aquest procediment es fa fins que tall coincideix amb la dada cercada o bé fins que primer i ultim coincideixen entre ells i no amb la dada cercada.

El següent esquema il·lustra el procediment anterior: 

1 2 3 4 5 6 7 8 9 10 primer tall últim
1 3 5 6 8 9 11 15 16 20 1 5 10
9 11 15 16 20 6 8 10
9 11 6 6 7
11 7 7 7
 

En el programa, el codi del qual es troba a continuació, hi ha implementat aquest algorisme en el cas de cercar un camp d'una estructura en una llista de registres ordenats en un arxiu de disc.

Definiu un projecte nou anomenat m8pa1 i afegiu-li un arxiu de font C/C++ anomenat m8pa1.cpp. Escriviu el següent codi:

//m8pa1.cpp. Cerca dicotómica

#include <sys/types.h>
#include <sys/stat.h>
#include <stdio.h>



struct fitxa{
    int codi;
    char nom[20];
    char cognoms[20];
    float nota;
};

fitxa cerca(FILE *fp, int n_reg, int codi);

void main(){
    FILE *fp;
    fitxa alumne;
    int codi;
    char arxiu[12];
    struct _stat buf;

    printf("Introduïu el nom de l'arxiu de dades\n");
    scanf("%s",arxiu);

    if((fp=fopen(arxiu, "r"))==NULL){
        printf("Error al intentar obrir l'arxiu\n");
        return;
    }

    if(_stat( arxiu, &buf )!=0 ){
        printf( "Error de la funció _stat\n" );
        return;
    }

    n_reg=buf.st_size/sizeof(alumne);
   
    printf("Introduïu el codi d'alumne a buscar..");
    scanf("%d", &codi);

   

    alumne=cerca(fp,n_reg,codi);

    if(alumne.codi!=-1)
         printf("%d %s %s %f", alumne.codi, alumne.nom,
                alumne.cognoms, alumne.nota);
    else
         printf("no es troba el registre sol·licitat\n");
    fclose(fp);

}

 

fitxa cerca(FILE *fp, int n_reg, int codi){


     int primer, ultim, tall,final=0;
    fitxa alumne;    

    primer=1;
    ultim=n_reg;

    while(1){
        tall=(primer+ultim)/2;
        fseek(fp,(tall-1)*sizeof(alumne),SEEK_SET);
        fread(&alumne, sizeof(alumne),1,fp);

        if(codi<alumne.codi)
           ultim=tall-1;
        else{

            if(codi>alumne.codi) primer=tall+1;
            else return alumne;
        }

        if(primer>ultim){
            alumne.codi=-1;
            return alumne;
        }
    }

}

 

 Explicació del programa

En la primera part del codi s'han posat les declaracions globals. Aquest programa defineix una estructura global amb quatre camps. Posteriorment, a la funció principal i a la funció cerca(), es declararan dues variables locals amb aquesta estructura i amb el nom alumne. 

Els dos arxius de capçalera: sys/types.h i sys/stat.h serveixen, com ja s'ha vist a la pràctica 5 d'aquest mòdul, per usar l'estructura _stat i la funció del mateix nom que permet obtenir la mida en octets d'un arxiu.

A la primera part de la funció main(), després de les declaracions de variables, es demana el nom de l'arxiu que conté les dades i s'obre:
    printf("Introduïu el nom de l'arxiu de dades\n");
    scanf("%s",arxiu);

    if((fp=fopen(arxiu, "r"))==NULL){
        printf("Error al intentar obrir l'arxiu\n");
        return;
    }

La següent part esbrina el nombre de registres que té l'arxiu. Això es fa dividint la mida total de l'arxiu (buf.st_size) entre la mida d'un registre (sizeof(alumne)):
  if(_stat( arxiu, &buf )!=0 ){
        printf( "Error de la funció _stat\n" );
        return;
    }

    n_reg=buf.st_size/sizeof(alumne);

A continuació demana el codi que ha de buscar en l'arxiu i crida a la funció crida(). Aquesta funció té tres arguments: El punter a l'arxiu (fp), el nombre total de registres d'aquest arxiu (n_reg) i el codi a cercar (codi).

Aquesta funció declara tres variables: primer, ultim, i tall. La variable primer s'inicialitza a 1, la variable ultim s'inicialitza a n_reg i la variable tall serà el resultat de sumar els continguts de primer i ultim i dividir per dos.

En aquesta funció hi ha un bucle continu en el qual es troben aquestes dues línies:

 
        fseek(fp,(tall-1)*sizeof(alumne),SEEK_SET);
        fread(&alumne, sizeof(alumne),1,fp);

La primera d'aquestes línies situa el punter o marcador de l'arxiu al començament del registre tall i la segona llegeix el registre tall (llegeix l'estructura sencera).

Una vegada llegit el registre tall es compara el camp codi amb la variable codi. Si la variable és més petita fa: ultim=tall-1, si la variable és més gran fa: primer=tall+1, i si la variable és igual, retorna el valor de l'estructura.