Vettore dinamico

Algoritmi di ricerca e ordinamento su vettore allocato dinamicamente

Lo scopo di questo esercizio è quello di creare un algoritmo in C++ che, ricevuta in ingresso una matrice allocata dinamicamente, restituisca la posizione di un qualsiasi elemento ricercato dall'utente in una qualsiasi posizione dell'array. Utilizzeremo per trovare il nostro elemento due tipi di ricerca: la ricerca lineare e la ricerca binaria.

Cominciamo con la creazione dei primi due file del nostro programma: ricerca.cpp e ricerca.h, che ovviamente conterranno i blocchi di codice utili alla ricerca dell'elemento.

Ricerca lineare

La ricerca, grazie a quest'algoritmo, viene effettuata elemento per elemento, fino a che l'elemento ricercato non venga trovato o finché l'indice non raggiunga la fine.

Domanda – Cosa deve fare questo codice?

• Deve prendere in entrata il vettore con i valori;
• Effettuare i confronti con i vari elementi del vettore, se il valore c'è, segnalarne la presenza e passare il valore della posizione, se il valore non c'è segnalarne l'assenza;
• Restituire la posizione.

1. Se la funzione deve prendere in entrata un vettore dinamico, dobbiamo dichiararlo a mezzo dell'asterisco, supponendo che il nostro algoritmo ordinerà, ad esempio, interi, possiamo tipizzarlo tramite const e poiché int deve essere di sola lettura è necessario utilizzare il qualificatore. Ogni vettore deve avere una dimensione massima e dunque ecco la presenza del parametro dim, dovrà anch'esso essere di sola entrata e pertanto non suscettibile di modifica e per ovvi motivi deve essere di tipo intero. L'elemento da ricercare, dal momento che stiamo trattando un array di interi, sarà a sua volta di tipo int e anch'esso solo di input. Invece pos e flag saranno rispettivamente di tipo intero (perché la posizione deve essere necessariamente rappresentata tramite un numero naturale) e di tipo booleano. Flag sarà la variabile che ci dirà se all'interno del nostro vettore c'è l'elemento cercato.

2. Dovendo essere un'azione ripetuta per tutti gli elementi del vettore è logico utilizzare un ciclo for, nell'impostare correttamente le condizioni di uscita. Fin quando il ciclo deve continuare? Il ciclo deve continuare se la dimensione massima dell'array non è stata ancora raggiunta e se l'elemento non è stato ancora trovato. Se l'elemento viene trovato settare la variabile flag come vera, altrimenti lasciarla come falsa.

3. Possiamo restituire la posizione o costruendo una funzione di tipo int e facendone ritornare il valore tramite return oppure costruttivamente usando altre modalità. Ognuna di queste opzioni consente di gestire diversamente il flusso del programma in base alle necessità specifiche del progetto.