Ricerca di un elemento in un array

da Cristina | Feb 21, 2019 | Algoritmi in C

In questa lezione vedremo come effettuare la ricerca di un elemento in un array.

Nella programmazione, spesso è necessario cercare un elemento all’interno di un array. In questo articolo, esploreremo due metodi per affrontare questo problema utilizzando il linguaggio C. Il primo metodo sarà implementato senza l’uso di funzioni, mentre il secondo sfrutterà funzioni per rendere il codice più modulare e leggibile.

Ricerca di un elemento in un array – Metodo Senza Funzioni

In questa prima soluzione, affronteremo il problema senza l’ausilio di funzioni.

Il programma consente all’utente di inserire una serie di numeri in un array e dopo di cercare un numero specifico all’interno di quell’array. Alla fine, viene visualizzato il numero di volte che il numero cercato compare nell’array.

Ecco in dettaglio i passaggi che effettueremo:

1. Viene dichiarato un array a di interi con dimensione MAX.
2. Vengono dichiarate le variabili n (per memorizzare il numero di elementi dell’array), i (per contare gli elementi durante il loop), x (il numero da cercare nell’array) e count (per contare quante volte il numero compare nell’array).
3. Dapprima l’utente inserisce il numero di elementi dell’array tramite scanf() e lo memorizza nella variabile n.
4. Dopo l’utente inserisce gli elementi dell’array utilizzando un loop for, dove i varia da 0 a n-1. Ogni elemento viene memorizzato nell’array a.
5. L’utente inserisce il numero da cercare nell’array che sarà memorizzato in una variabile x.
6. Poi viene eseguito un loop for per attraversare tutti gli elementi dell’array. Ogni elemento viene confrontato con il numero cercato x. Se l’elemento è uguale a x, incrementa count.
7. Alla fine del loop, il programma determina se count è uguale a zero. Se è così, il numero cercato non è stato trovato nell’array e viene stampato un messaggio appropriato. Altrimenti, viene stampato il numero di volte che il numero cercato appare nell’array.
8. Il programma restituisce 0 per indicare il completamento senza errori.

Algoritmo per la ricerca

Ecco dunque l’implementazione dell’algoritmo:

#include <stdio.h>
#define MAX 100

int main() {
    int a[MAX];
    int n, i, x, count = 0;

    printf("Inserisci il numero di elementi nell'array: ");
    scanf("%d", &n);

    printf("Inserisci gli elementi dell'array:\n");
    for (i = 0; i < n; i++) {
        printf("Elemento %d: ", i + 1);
        scanf("%d", &a[i]);
    }

    printf("Inserisci il numero da cercare nell'array: ");
    scanf("%d", &x);

    for (i = 0; i < n; i++) {
        if (a[i] == x) {
            count++;
        }
    }

    if (count == 0) {
        printf("Il numero %d non è stato trovato nell'array.\n", x);
    } else {
        printf("Il numero %d è stato trovato %d volte nell'array.\n", x, count);
    }

    return 0;
}

Questo metodo è semplice e diretto ma può diventare inefficiente per array molto grandi, poiché richiede un confronto con ogni elemento dell’array.

Potremmo infatti tener conto di varie ottimizzazioni, ad esempio potremmo utilizzare una tabella di frequenza, invece di attraversare l’array ogni volta per contare quante volte appare un numero. Inizializziamo un array di frequenza con dimensione pari al valore massimo possibile (ad esempio, se il massimo è 100, l’array di frequenza sarà di dimensione 101) e quindi attraversiamo l’array una volta sola, incrementando il contatore corrispondente all’indice dell’array di frequenza per ogni numero incontrato. Questo riduce la complessità temporale da O(n^2) a O(n).

#include <stdio.h>
#define MAX 100

int main() {
    int a[MAX] = {0}; // Inizializza l'array con zeri
    int freq[MAX] = {0}; // Tabella di frequenza
    int n, i, x;

    printf("Inserisci il numero di elementi nell'array: ");
    scanf("%d", &n);

    printf("Inserisci gli elementi dell'array:\n");
    for (i = 0; i < n; i++) {
        printf("Elemento %d: ", i + 1);
        scanf("%d", &a[i]);
        freq[a[i]]++; // Incrementa la frequenza del numero inserito
    }

    printf("Inserisci il numero da cercare nell'array: ");
    scanf("%d", &x);

    if (freq[x] == 0) {
        printf("Il numero %d non è stato trovato nell'array.\n", x);
    } else {
        printf("Il numero %d è stato trovato %d volte nell'array.\n", x, freq[x]);
    }

    return 0;
}

Ricerca di un elemento in un array – Metodo con le Funzioni

Sviluppiamo adesso una soluzione, utilizzando le funzioni per suddividere il codice in blocchi più gestibili e leggibili.

Svilupperemo alcune funzioni:

1. Funzione inserisciArray: Questa funzione consente all’utente di inserire elementi nell’array. Chiede all’utente quanti elementi vuole inserire, quindi utilizza un ciclo for per leggere ciascun elemento dall’input e memorizzarlo nell’array a[]. Restituisce il numero totale di elementi inseriti.
2. stampaArray: Questa funzione stampa tutti gli elementi dell’array. Utilizza un ciclo for per scorrere l’array e stampare ciascun elemento su una riga separata.
3. Funzione ricercaElemento: Questa funzione cerca quante volte un certo numero appare nell’array. Chiede all’utente di inserire il numero da cercare e quindi utilizza un ciclo for per scorrere l’array e contare quante volte il numero cercato appare. Alla fine, stampa il numero di occorrenze del numero cercato nell’array.
4. main: La funzione principale del programma si occupa di dichiarare un array a[] di dimensione MAX e una variabile n per memorizzare il numero di elementi inseriti. Dopo chiama la funzione inserisciArray per inserire gli elementi nell’array, quindi chiama la funzione stampaArray per stampare gli elementi dell’array. Infine, chiama la funzione ricercaElemento per cercare il numero specificato nell’array e stampare il risultato.

Ecco dunque il codice completo:

#include <stdio.h>
#define MAX 100

int inserisciArray(int a[]) {
    int n, i;
    printf("Quanti elementi vuoi inserire nell'array?: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        printf("Inserisci elemento %d: ", i + 1);
        scanf("%d", &a[i]);
    }
    return n;
}

void stampaArray(int a[], int n) {
    int i;
    printf("Elementi dell'array:\n");
    for (i = 0; i < n; i++) {
        printf("%d\t", a[i]);
    }
    printf("\n");
}

void ricercaElemento(int a[], int n) {
    int x, i, count = 0;
    printf("Inserisci il numero da cercare nell'array: ");
    scanf("%d", &x);
    for (i = 0; i < n; i++) {
        if (a[i] == x) {
            count++;
        }
    }
    if (count == 0) {
        printf("Il numero %d non è stato trovato nell'array.\n", x);
    } else {
        printf("Il numero %d è stato trovato %d volte nell'array.\n", x, count);
    }
}

int main() {
    int a[MAX], n;
    n = inserisciArray(a);
    stampaArray(a, n);
    ricercaElemento(a, n);
    return 0;
}

Quindi, questo programma fornisce un’interfaccia semplice per manipolare gli array, permettendo all’utente di inserire elementi, visualizzare gli elementi dell’array e cercare quanti volte un certo numero appare nell’array.

Ricerca di un elemento in un array – Tabella di frequenza

Possiamo usare una soluzione che utilizza una tabella di frequenza per tenere traccia delle occorrenze di ciascun elemento presente nell’array.

Introduciamo quindi un array di frequenza freq, inizializzato con tutti gli elementi a 0. Ogni volta che incontriamo un elemento nell’array, incrementiamo il contatore corrispondente nell’array di frequenza. Alla fine, controlliamo il valore di frequenza per l’elemento cercato e stampiamo il risultato. Questo approccio riduce la complessità della ricerca a O(1), poiché stiamo semplicemente accedendo direttamente alla frequenza dell’elemento anziché scorrere l’intero array per contare le occorrenze.

Ecco dunque il codice completo:

#include <stdio.h>
#define MAX 100
#define MAX_ELEMENT 1000

int inserisciArray(int a[]) {
    int n, i;
    printf("Quanti elementi vuoi inserire nell'array?: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        printf("Inserisci elemento %d: ", i + 1);
        scanf("%d", &a[i]);
    }
    return n;
}

void stampaArray(int a[], int n) {
    int i;
    printf("Elementi dell'array:\n");
    for (i = 0; i < n; i++) {
        printf("%d\t", a[i]);
    }
    printf("\n");
}

void ricercaElemento(int a[], int n) {
    int freq[MAX_ELEMENT] = {0}; // Array di frequenza
    int x, i;
    printf("Inserisci il numero da cercare nell'array: ");
    scanf("%d", &x);

    // Calcola la frequenza di ciascun elemento nell'array
    for (i = 0; i < n; i++) {
        freq[a[i]]++;
    }

    // Controlla se l'elemento è presente e stampa la sua frequenza
    if (freq[x] == 0) {
        printf("Il numero %d non è stato trovato nell'array.\n", x);
    } else {
        printf("Il numero %d è stato trovato %d volte nell'array.\n", x, freq[x]);
    }
}

int main() {
    int a[MAX], n;
    n = inserisciArray(a);
    stampaArray(a, n);
    ricercaElemento(a, n);
    return 0;
}

Conclusioni

In questa lezione abbiamo esplorato un semplice programma in linguaggio C che consente agli utenti di ricerca elementi in un array. Nelle prossime lezioni continueremo a lavorare con gli array in C.

Link utili:

Corso linguaggio C

Array o vettori

Selection sort

Merge sort

Insertion Sort