[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home] [volume] [parte]


Capitolo 587.   Scansione di array

In questo capitolo vengono mostrati alcuni algoritmi, legati alla scansione degli array, portati in C. Per la spiegazione degli algoritmi, se non sono già conosciuti, occorre leggere quanto riportato nel capitolo 543.

587.1   Ricerca sequenziale

Il problema della ricerca sequenziale all'interno di un array, è descritto nella sezione 543.3.1.

Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/ricercaseq.c>.

#include <stdio.h>

int
ricercaseq (int lista[], int x, int a, int z)
{
    int i;

    // Scandisce l'array alla ricerca dell'elemento.

    for (i = a; i <= z; i++)
      {
        if (x == lista[i])
          {
            return i;
          }
      }

    // La corrispondenza non è stata trovata.

    return -1;
}

int
main (int argc, char *argv[])
{
    int lista[argc - 2];
    int x;
    int i;

    // Acquisisce il primo argomento come valore da cercare.

    sscanf (argv[1], "%d", &x);

    // Considera gli argomenti successivi come gli elementi
    // dell'array da scandire.

    for (i = 2; i < argc; i++)
      {
        sscanf (argv[i], "%d", &lista[i-2]);
      }

    // Esegue la ricerca.

    i = ricercaseq (lista, x, 0, argc - 2);

    // Emette il risultato.

    printf ("%d si trova nella posizione %d\n", x, i);

    return 0;
}

Al posto di dichiarare l'array lista con una quantità di elementi definita in fase di funzionamento, si può usare la funzione malloc(), avendo cura di incorporare il file stdlib.h:

#include <stdio.h>
#include <stdlib.h>
...
int
main (int argc, char *argv[])
{
    int *lista = (int *) malloc ((argc - 2) * sizeof (int));
...

Esiste anche una soluzione ricorsiva che viene mostrata nella subroutine seguente:

int
ricercaseq (int lista[], int x, int a, int z)
{
    if (a > z)
      {
        // La corrispondenza non è stata trovata.

        return -1;
      }
    else if (x == lista[a])
      {
        return a;
      }
    else
      {
        return ricercaseq (lista, x, a+1, z);
      }
}

587.2   Ricerca binaria

Il problema della ricerca binaria all'interno di un array, è descritto nella sezione 543.3.2.

Una copia di questo file dovrebbe essere disponibile presso <allegati/a2/ricercabin.c>.

#include <stdio.h>

int
ricercabin (int lista[], int x, int a, int z)
{
    int m;

    // Determina l'elemento centrale.

    m = (a + z) / 2;

    if (m < a)
      {
        // Non restano elementi da controllare: l'elemento cercato
        // non c'è.

        return -1;
      }
    else if (x < lista[m])
      {
        // Si ripete la ricerca nella parte inferiore.

        return ricercabin (lista, x, a, m-1);
      }
    else if (x > lista[m])
      {
        // Si ripete la ricerca nella parte superiore.

        return ricercabin (lista, x, m+1, z);
      }
    else
      {
        // La variabile m rappresenta l'indice dell'elemento cercato.

        return m;
      }
}

int main (int argc, char *argv[])
{
    int lista[argc - 2];
    int x;
    int i;

    // Acquisisce il primo argomento come valore da cercare.

    sscanf (argv[1], "%d", &x);

    // Considera gli argomenti successivi come gli elementi
    // dell'array da scandire.

    for (i = 2; i < argc; i++)
      {
        sscanf (argv[i], "%d", &lista[i-2]);
      }

    // Esegue la ricerca.

    i = ricercabin (lista, x, 0, argc-2);

    // Emette il risultato.

    printf ("%d si trova nella posizione %d\n", x, i);

    return 0;
}

Per questo esempio vale la stessa considerazione fatta nella sezione precedente, a proposito dell'uso di malloc() al posto di un array con una quantità di elementi definita dinamicamente durante il funzionamento del programma.


Appunti di informatica libera 2008 --- Copyright © 2000-2008 Daniele Giacomini -- <appunti2 (ad) gmail·com>


Dovrebbe essere possibile fare riferimento a questa pagina anche con il nome scansione_di_array.htm

[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home]

Valid ISO-HTML!

CSS validator!

Gjlg Metamotore e Web Directory