Le operazioni che possiamo compiere sugli array sono numerose alcune sono fondamentali, in quanto con le dovute modifiche sono utilizzate per altre strutture dati. E’ stato già definito il vettore o il concetto di array con una struttura dati volatile collettiva identificata da un nome collettivo e costituita da elementi dello stesso tipo.
Tale struttura dati che chiameremo semplicemente array permette di trattare una sequenza di elementi con un’unica variabile strutturata risultando più comoda la gestione.
La struttura dati può essere ordinata o non ordinata. In questo ultimo caso oggetto di questo articolo e del video allegato, consideriamo la necessità della ricerca di elementi all’interno dell’array. La ricerca è funzionale ad una serie di ulteriori operazioni come il conteggio di valori presenti nella struttura in base ad un criterio, la modifica di elementi che rispondono a determinati criteri e tante altre operazioni.
Le operazioni illustrate qui sono la ricerca sequenziale e quella sequenziale con flag. La ricerca sequenziale prevede la scansione dell’intero array per individuare un elemento fornito in input come criterio di ricerca. Questa ricerca restituisce la posizione dell’ultimo <elemento che corrisponda al criterio di ricerca. In caso di mancata individuazione dell’elemento è stampato un messaggio di errore. Tale ricerca quando il numero degli elementi è molto grande è molto dispendiosa in termini di elaborazione, possiamo dire che il tempo medio di elaborazione è funzione lineare di N che fissiamo come dimensione del vettore. Esistono degli algoritmi ottimizzati ma riguardano in prevalenza strutture ordinate e quindi per vedere queste procedure ottimizzate occorre introdurre prima qualche algoritmo di ordinamento.
Nella ricerca con flag, l’obiettivo è di velocizzare l’algoritmo e di fare in modo che alla prima occorrenza individuata sia interrotta la ricerca. Questo riduce il tempo e solo nei casi in cui l’elemento è verso la fine dell’array il tempo è sempre molto lungo.
Gli algoritmi sono quindi essenzialmente due e sono svilupati mediante la metodologia top-down.
Il primo algoritmo è:
Nel diagramma di flusso presentato sono presenti due algoritmi il primo è il programma principale che dopo aver definito la dimensione del vettore e caricato gli elementi con una procedura già peraltro vista nella lezione precedente (Articolo Linguaggio C – Lezione n.8), richiede l’inserimento di un valore da cercare nell’array. Viene richiamata la funzione che effettua una ricerca mediante il ciclo for (il secondo flow chart nella figura) e restituisce in caso di esito positivo della ricerca la posizione dell’elemento. Per semplicità la variabile pos=-1 indica che l’elemento non è stato individuato.
Il controllo dopo l’invocazione della funzione passa al programma principale che valuta il valore della variabile pos, la quale se è diversa da -1 come valore indica la presenza dell’elemento cercato almeno una volta nell’array. Al contrario se la variabile pos ritorna come valore -1 indica che l’elemento all’interno dell’array non esiste.
Una variante della ricerca sequenziale è quella con flag ovvero sfruttare una variabile sentinella che interrompa il ciclo quando la prima occorrenza sia individuata.
Il Diagramma di Flusso è:
In questo caso la variabile flag indica se l’elemento è stato trovato o meno nell’array e attraverso un ciclo pre condizionale while viene ripetuto fin quando l’indice dell’array non ha raggiunto la dimensione dell’array che in questo flow chart è il parametro l e contemporaneamente fin quando la variabile flag non vale 1.
Nel momento in cui l’elemento è individuato vien interrotto il ciclo e viene restituito al programma principale la posizione del primo elemento individuato.
Il codice C del programma con la ricerca sequenziale con flag è presentato insieme alla spiegazione nel video.