Algoritmi notevoli per gli array

In questo articolo, parliamo di alcuni algoritmi per la risoluzione di alcune operazioni sui vettori. E’ importante specificare, che gli algoritmi sono scritti in pseudo-codice ovvero una rappresentazione in linguaggio naturale della soluzione algoritmica. Questo svincola la soluzione dal particolare ambiente di sviluppo, ovvero dal linguaggio di programmazione utilizzato.
Una prima evidente differenze, risiede nella rappresentazione che conferiamo al vettore e/o array. La rappresentazione di un array, in pseudo-codice è indicato con una lettura maiuscola e con una coppia di parentesi “[“,”]”. che può indicare genericamente il vettore se non inserito nelle parentesi. Diversamente in partentesi è inserita la posizione dell’elemento da considerare ad esempio X[1] indica il primo elemento dell’array.
Nei linguaggi di programmazione quali il C/C++/Java, ecc il primo elemento dell’array è indicato con il valore dell’indice pari a zero.
Una semplice rappresentazione può essere quella di una tabellina monodimensionale una riga.

213-5788991321112
12345678910

Link sponsorizzato

E’ rappresentato un vettore di 10 elementi interi. la seconda riga indica la posizione dell’elemento che utilizzeremo nello pseudo-codice. L’indice in questo caso ha un intervallo di variazione da 1 a 10.
Le operazioni notevole sui vettori sono:

  • caricamento e/o primo inserimento dati nel vettore
  • modifica di un elemento
  • cancellazione di un elemento

Il caricamento e/o primo inserimento di elementi nell’array, avviene sempre mediante un ciclo iterativo con l’indice del ciclo che è anche indice del vettore. L’intervallo di variazione è da 1 a N dove N è la dimensione del vettore. Questo non vuol dire che non è possibile realizzare algoritmi di inserimento dati nei vettori con altri cicli. E’ importante invece utilizzare una struttura ciclica condizionata quando il numero degli elementi deve essere determinato dall’utente mediante uina scelta. La dichiarazione delle dimensioni del vettore in molti linguaggio di programmazione deve essere definita prima del programma come Pascal, Cobol; mentre per altri come Visual Basic, C++ può essere dinamica ovvero variare nell’algoritmo aumentando però la difficoltà nella gestione e lo spazio di memoria a disposizione.
Vediamo il caricamento con strutrura iterativa:

Inizio
Scrivi “Dammi il numero degli elementi”
Leggi N
Ciclo su K=1 .. N
Scrivi “Inserisci gli elementi”
Leggi Vet(k)
Fine Ciclo su K

Nel caso di struttura condizionata si ha un ciclo di questo tipo

Inizio
Risposta= “S”
N=1
I=1
Mentre (Risposta=”S”) esegui
Scrivi “Dammi elementi”
Leggi Vet(i)
Scrivi “Altri elementi”
Leggi Risposta
I=I+1
Fine Ciclo
N=I
Fine

N come si nota sarà la dimensione finale del vettore. In questo caso si è utilizzzata una variabile stringa di appoggia per prendere l’input dell’utente per continuare o meno l’inserimento.

Modifica di elementi 

Vediamo ora come operare per modificare un elemento all’interno di un vettore. Essendo il vettore una struttura ad accesso diretto basterà chiedere la posizione dell’elemento da modificare. Nel caso invece si volesse modificare un elemento con un valore specifico è necessario effettuare una ricerca e poi la modifica. Questo sarà oggetto della ricerca.

L’algoritmo pertanto prevede di prendere in Input la posizione dell’elemento da modificare che chiameremo pos.

Inizio
Scrivi “Dammi la posizione dell’elemento da modificare”
Leggi Pos
Scrivi “Dammi il nuovo valore da sostituire”
Leggi X
Vet(Pos)=X
Fine

Come si nota non è stato effettuato nessun ciclo.

Cancellazione

La cancellazione di elementi all’interno del vettore può avvenire in modo logico (temporaneo) o fisico (permanente). La cancellazione logica prevede di cancellare logicamente un elemento inserendo un valore nullo nel caso di stringhe, un numero negativo nel caso di un vettore con soli numeri positivi. Si ottiene inserendo valori non inerenti al contesto della struttura dati per la quale è stata definita. In generale come per la modifica si deve conoscere la posizione altrimenti si è obbligati ad una ricerca dell’elemento da cancellare. Vediamo la cancellazione di un elemento di posizione Pos all’interno di un vettore.

Cancellazione logica

Inizio
Scrivi “Dammi la posizione dell’elemento da cancellare “
Leggi Pos
Vet(Pos)=0
Fine

Se trattasi di un vettore di stringhe si ha:

Inizio
Scrivi “Dammi la posizione dell’elemento da cancellare “
Leggi Pos
Vet(Pos)=””
Fine

La cancellazione fisica deve per forza passare attraverso il ricompattamento del vettore ovvero la riduzione del numero di elementi. Ad esempio se il vettore è di N elementi il nuovo vettore sarà di dimensione N-1.
All’uopo vediamo un semplice algoritmo per lo svolgimento di tale procedura.

Inizio
Flag=0
Scrivi “Dammi la posizione dell’elemento da cancellare”
Leggi Pos
Ciclo su I=1 .. N
Se I=Pos allora
Vet(I)= Vet(I+1)
Flag=1
Fine SE
Se Flag=1 allora
Vet(I)= Vet(I+1)
Fine Se
Fine Ciclo su I
Fine