Vettore dinamico

RICERCA LINEARE

La ricerca, grazie a quest'algoritmo, viene effettuata elemento per elemento, fino a che l'elemento ricercato non viene trovato o finché l'indice non raggiunga la fine. Domanda - Cosa deve fare questo codice? 1. Deve prendere in entrata il vettore con i valori; 2. Effettuare i confronti con i vari elementi del vettore, se il valore è presente, segnalarne la presenza e passare il valore della posizione, se il valore non è presente segnalarne l'assenza; 3. 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 int. Poiché int deve essere di sola lettura, è necessario utilizzare il qualificatore const. Ogni vettore deve avere una dimensione massima e dunque ecco la presenza del parametro dim, dovrà anch'esso essere di sola entrata.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 intpos 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, il tutto sta però 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.

3. Possiamo restituire la posizione o costruendo una funzione di tipo int e facendone ritornare il valore tramite return oppure costruendo una funzione ed effettuando il passaggio per riferimento.

Ecco il codice, che andrà nel file ricerca.cpp:


void ricercaLineare (const int* vettore, const int dim, const int elem, int &pos, bool &flag) {
    int i;
    // all'inizio la variabile flag è falsa.
    flag=false;
    // per i=0, se i è minore della dimensione massima del vettore e contemporaneamente la
    // variabile flag è falsa, allora incrementa il valore di i.
    for (i=0; ((i<dim)&&(flag==false)); i++) {
        // se l'elemento i-esimo del vettore è uguale a quello che stiamo cercando...
        if (vettore[i]==elem) {
            // ... assegna il valore vero alla variabile flag...
            flag=true;
            // ... ed assegna a pos il valore di i.
            pos=i;
        }
    }
}


Mentre nel file ricerca.h:


void ricercaLineare (const int* vettore, const int dim, const int elem, int &pos, bool &flag);

int &pos, bool &flag); oppure più semplicemente: void ricercaLineare (const int*, const int, const int, int& , bool&); RICERCA BINARIA La ricerca binaria, diversamente dalla lineare, presuppone che il nostro vettore sia già ordinato. Si prendono due variabili (i e j), al primo viene assegnato l'indice della prima cella del vettore (nell'esempio sotto riportato i=0), al secondo l'indice dell'ultima (nell'esempio sotto riportato j=10, in generale j=dimensioneArray-1, per i linguaggi che si basano sullo zero indexing). 3.2 5.9 7.4 ... 0 1 2 3 4 5 6 7 8 9 10 Lo scopo sta nell'individuare sottoliste sempre più piccole in cui il valore da ricercare può essere contenuto, perché non è detto che ci sia. Domanda – Cosa deve fare questo codice? Si effettua una somma tra i e j e si divide per due il risultato, quindi un confronto tra vettore[(i+j)/2] e l'elemento da cercare. Se l'elemento è

maggiore di vettore[(i+j)/2], allora i=(((i+j)/2)+1) altrimenti se l'elemento è minore di vettore[(i+j)/2] allora j=(((i+j)/2)+1).

Esempio: elemento da trovare: 1210 12 13 17 20 22 250 1 2 3 4 5 610 12 13 17 20 22 250 1 2 3 4 5 6

Prendiamo ad esempio un vettore di interi, dobbiamo trovare il numero 12. Il nostro algoritmo dice:

1. Somma i e j e dividi per 2 i=0, j=6 (0+6)/2=3
2. Prendi l'elemento vettore[(i+j)/2] e confrontalo con l'elemento da trovare vettore[4] contiene 20>12
3. Poiché 12 è minore di vettore[(i+j)/2] allora j=(((i+j)/2)+1).

Ma quando l'algoritmo termina? Possono presentarsi due condizioni: che l'elemento sia stato trovato o che l'elemento non vi sia e che dunque j si trovi ad essere minore di i (supposto j>i).

Facendo dei ragionamenti del tutto analoghi a prima, commentiamo unicamente quello che ci è nuovo. Ecco un'altra funzione del file ricerca.cpp:

void ricercaBinaria(int* vettore,

const int dim, int &elem, int &pos, bool &flag) {
    // dobbiamo scrivere anche una funzione che ordini l'array
    ordineCrescente(vettore, dim);
    flag=false;
    int i, j, k;
    i=0; 
    j=dim-1;
    // questa volta è più semplice utilizzare un do, al posto del for
    do {
        // determinato k tramite la somma di i+j e la sua successiva divisione per 2
        k=((i+j)/2);
        // se l'elemento di posto k è proprio l'elemento che stiamo cercando
        if (vettore[k]==elem) {
            // flag è vera
            flag=true;
            // assegna a pos il valore di k
            pos=k;
        }
        // altrimenti se l'elemento di posto k è minore dell'elemento da cercare
        else if (vettore[k]<elem) {
            // assegna ad i il valore di k incrementato di 1
            i=k+1;
        }
        // altrimenti
        else if (vettore[k]>elem) {
            // assegna a j il valore di k incrementato di 1
            j=k+1;
        }
    // fin quando flag è falsa e j è maggiore di i
    } while ((flag==false)&&(j>i));
}

Nell'header file ricerca.h bisogna ricordarsi di immettere l'intestazione.

della funzione:

void ricercaBinaria(int* vettore, const int dim, int &elem, int &pos, bool &flag);

o più semplicemente:

void ricercaBinaria(int*, const int, int&, int&, bool&);

ORDINAMENTO CRESCENTE

Viene effettuato in buona sostanza grazie all'ausilio di una terza variabile temporanea. Se volessimo scambiare il contenuto di due variabili sarebbe scorrettissimo scrivere:

a=b;
b=a;

pertanto quella che ci viene in aiuto è una terza variabile, che mantiene temporaneamente il contenuto di una delle due per effettuare lo scambio, altrimenti impossibile.

22 1222
12 1222
12 2222

Domanda – Cosa deve fare questo codice?

Deve rilevare se all'interno del vettore ci sono degli elementi tali che vettore[i]>vettore[i+1] e in quel caso effettuare lo scambio fino a che tutto non risulti ordinato.

Possiamo implementare il tutto in un ciclo contenuto in un for do-while.

Il primo ciclo servirà per controllare che tutto sia stato oramai ordinato, il secondo

effettuerà gli eventuali necessari scambi.
Ecco la funzione tradotta, da aggiungere al file ricerca.cpp:


//la funzione prende come ingresso unicamente la dimensione dell’array, che non deve
//essere cambiata per non creare errori. Il vettore invece non deve essere const
//in quanto devono essere effettuati degli scambi su di esso.
void ordineCrescente(int* vettore, const int dim) {
    bool flag;
    int t, i;

    //eseguito {
    //assegna a flag valore falso, poiché non sono stati effettuati scambi
    flag=false;

    //se avessimo scritto dim, il programma sarebbe entrato in un area di memoria non
    //allocata, generando errore al tempo di esecuzione.
    for (i=0; i<(dim-1); i++) {
        //se l’elemento vettore[i] è maggiore del successivo
        if (vettore[i]>vettore[i+1]) {
            //assegna alla variabile temporale il valore della casella corrispondente
            //all’indice che si sta considerando
            t=vettore[i];

            //scambia i valori tra la cella e la sua successiva
            vettore[i]=vettore[i+1];

            //scambia i valori
        }
    }
}

Tra la variabile temporale e la successiva, il vettore[i+1] viene settato come t. Questo imposta la variabile flag come vera, poiché è stato effettuato uno scambio. ```html

tra la variabile temporale e la successiva, il vettore[i+1]=t;//setta la variabile flag come vera poiché è stato effettuato uno scambioflag=true;

``` Finché flag è vera, cioè fino a che sono effettuati scambi. In realtà, quando non vengono effettuati più scambi, è perché l'array è ormai ordinato e quindi flag assume valore falso. ```html

//finché flag è vera, cioè fino a che sono effettuati scambi. In realtà quando non vengono//effettuati più scambi è perché l’array è oramai ordinato e quindi flag assume valore falso.

``` N.B.: l'istruzione vuole dire 'finché flag permane vera'. ```html

//N.B.: l’istruzione vuole dire ‘finché flag permane vera’.

``` ```html

}while (flag);

``` Aggiungere all'header file l'intestazione: ```html

void ordineCrescente(int* vettore, const int dim);

``` Oppure più semplicemente: ```html

void ordineCrescente(int*, const int);

``` ```html

hunter85 – http://www.quellidiinformatica.org la community studenti di Ingegneria Informatica di Napoli

```