Precisazione sulla visibilit`a delle variabili durante l...

Precisazione sulla visibilita delle variabili durante

l’esecuzione delle funzioni

var a = new Array (4);

var y= 7;

function foo(vet,x) {var i=0;

...

} //fine foo

foo(a,y);

print(y);

✲

Stato

a e vet sono 2 nomi diversi per lo stessoarray, mentre y e x sono due variabili diverseche per un accidente hanno lo stesso valore

{(a, ),(y,7) (foo, function (vet,x) {...}), (vet, ), (x,7) (i,0)}❄ ✛

0 61 undefined2 undefined3 undefined

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 1

Precisazione sulla visibilita delle variabili durante

l’esecuzione delle funzioni


var y= 7

function foo(vet,x) {var i=0;

x=34;

...

} //fine foo

foo(a,y);print(y);

✲

Stato

se modifico x, y rimane invariato. y e visibilee modificabile nella funzione ma e globale: davietato usarle in questo corso

{(a, ),(y,7) (foo, function (vet,x) {...}), (vet, ), (x,34) (i,0)}❄ ✛



Non e necessario usare nomi diversi


var y= 7

function foo(a,y) {var i=0;

y=34;

} //fine foo

foo(a,y);

print(y);

✲

Stato

le variabili locali alla funzione hanno gli stessinomi delle variabili globali ma sono variabilidiverse

{(a, ),(y,7) (foo, function (a,y) {...}), (a, ), (y,7) (i,0)}❄ ✛





var y= 7


y=34;

} //fine foo

foo(a,y);

print(y);

✲

Stato

le variabili globali non sono in questo casoaccessibili perche sono coperte dalle variabililocali.






var y= 7


y=34;

} //fine foo

foo(a,y);

print(y);✲

Stato

Quando l’esecuzione della funzione termina,il controllo torna al programma chiamante ele variabili ritornano accessibili. print(y)

stampa 7.




Funzioni che restituiscono array

In JavaScript le funzioni possono anche restituire array come risultatodella computazione:

Esempio: La funzione leggiVet puo essere scritta anche cosi‘:

var k = asknum(), a;

function leggiVet(n) {var vet=new Array(n), i;

for (i = 0; i < vet.length; i++)

vet[i]=asknum();

return vet; //fine leggiVet }a=leggiVet(k);

...

� Il chiamante passa alla funzione solo la dimensione (k) dell’array dacreare e inizializzare e dichiara la variabile a senza inizializzarla.


Evoluzione dello stato

var k=asknum(), a;

function leggiVet(n) {var i, vet=new Array(n), i;;

for (i=0; i<vet.length; i++)

vet[i]=asknum();

return vet;//fine leggiVet }a=leggiVet(k);✲

Stato

Stato in cui viene invocata leggiVet nel casoin cui il valore in input sia 4. L’esecuzione delprogramma principale viene sospesa e passa adeseguire la funzione.

{(k,4), (a,undefined ), (leggiVet, function (n) {...})}



var k=asknum(), a;



vet[i]=asknum();

return vet;//fine leggiVet }a=leggiVet(k);

✲

Stato

Stato durante l’invocazione di leggiVet, dopola dichiarazione delle variabili

{(k,4), (a,undefined ), (leggiVet, function (n) {...}),(n,4),(vet, ), (i,undefined),}

❄0 undefined1 undefined2 undefined3 undefined



var k=asknum(), a;



vet[i]=asknum();

return vet;//fine leggiVet }a=leggiVet(k);

✲

Stato

Stato durante l’invocazione di leggiVet, dopol’esecuzione del for nel caso in input siano statiimmessi i valori 8,-2,0,1

{(k,4), (a,undefined ), (leggiVet, function (n) {...}),(n,4),(vet, ), (i,4),}

❄0 81 -22 03 1



var k=asknum(), a;



vet[i]=asknum();

return vet;//fine leggiVet }a=leggiVet(k);✲

Stato

Stato dopo la terminazione dell’asecuzione dileggiVet e dell’assegnamento del reference,risultato della invocazione alla variabile a delchiamante.

{(k,4), (a, ), (leggiVet, function (n) {...})}�

��✠

0 81 -22 03 1


Ordinamento

Data una sequenza di elementi in ordine qualsiasi, ordinarla.

� Questo e un problema fondamentale, che si presenta in moltissimicontesti, ed in diverse forme.

� Nel nostro caso formuliamo il problema in termini di ordinamento divettori:

Dato un array A di n elementi, ordinarlo in modo crescente

� Per semplicita faremo sempre riferimento a vettori di interi.

5 2 4 6 1 3=⇒

1 2 3 4 5 6


Ordinamento per selezione del minimo (selection sort)

� Esempio: Ordinamento di un mazzo di carte� Ho 2 gruppi di carte: N carte non ordinate, O carte ordinate� si seleziona la carta piu piccola di N e la si inserisce in prima posizione

in O� delle rimanenti di N si seleziona la piu piccola e la si inserisce in

seconda posizione in O ecc.� rimane una sola carta in N e la si inserisce in ultima posizione in O� si termina quando non ci sono piu carte

� Ordinamento di un array, abbiamo 2 cicli :� per inserire l’elemento corretto in ogni posizione dell’array (scansione

di tutto l’array)� per ogni posizione e neccessario selezionare l’elemento piu piccolo tra i

rimanenti.

Per non perdere elementi e per lavorare sui rimanenti dobbiamoscambiare l’elemento piu piccolo selezionato con l’elemento che sitrova nella posizione corrente. In questo modo abbiamo una porzionedi array non ordinata (N) e una porzione di array ordinata (O).


� in nero la parte che rimane da analizzare (N)in blu l’elemento minimo selezionatoin verde lo scambio effettuatoin rosso la parte ordinata (O)in marrone gli indici

0 1 2 3 4 50 5 2 4 6 1 3

5 2 4 6 1 31 2 4 6 5 3

1 1 2 4 6 5 31 2 4 6 5 31 2 4 6 5 3

2 1 2 4 6 5 31 2 4 6 5 31 2 3 6 5 4

3 1 2 3 6 5 41 2 3 6 5 41 2 3 4 5 6

4 1 2 3 4 5 61 2 3 4 5 61 2 3 4 5 6

5 1 2 3 4 5 61 2 3 4 5 6


Implementazione dell’ordinamento per ricerca dei minimi in

JavaScript

Definiamo la funzione principale selSort

function selSort(vet){var i, temp,k;

for (i=0; i<vet.length-1; i++)

{k=minPos(vet,i,vet.length);temp=vet[i];

vet[i]=vet[k];

vet[k]=temp;

}Resta da definire minPos


Implementazione della ricerca della posizione dell’elemento

minimo in una porzione di array

Definizione della funzione minPos che calcola la posizionedell’elemento dell’array che contiene il valore minimo relativamente allporzione di array contenuta tra i valori dei 2 indici passati comeparametri (i, vet.length-1)

function minPos(vet,from, to){var min=from;

for (from++; from<=to; from++)

if (vet[from]<vet[min]) min=from;

return min;

}Sono tutti necessari i 3 parametri di minPos?


Programma principale per testare la procedura di

ordinamento definita

Usiamo la procedura leggiVet definita precedentemente e la print

predefinita.

var a=new Array(8);

leggiVet(a); //inizializzazione di a

print(a); //stampa di a

selSort(a); //ordinamento di a

print(a); //nuova stampa di a


Ordinamento a bolle (bubble sort)

E simile al precedente, cambia il modo di portare l’elemento minimodella porzione di array ancora non ordinata nella posizione corretta.

� l”idea e che si fanno galleggiare gli elementi piu piccoli (“piu leggeri”)verso l’inizio dell’array (“verso l’alto”), scambiandoli con quelliadiacenti.

� L’ordinamento e suddiviso in n-1 fasi:� fase 0: 0o elemento (il piu piccolo) in posizione 0� fase 1: 1o elemento in posizione 1� · · ·� fase n-2: (n-2)o elemento in posizione n-2, e quindi

(n-1)o elemento in posizione n-1

� Nella fase i: cominciamo a confrontare dal basso e portiamol’elemento piu piccolo (piu leggero) in posizione i


5 2 4 6 1 35 2 4 6 1 35 2 4 1 6 35 2 1 4 6 35 1 2 4 6 31 5 2 4 6 3

1 5 2 4 6 31 5 2 4 3 61 5 2 3 4 61 5 2 3 4 61 2 5 3 4 6

1 2 5 3 4 6

1 2 3 5 4 6

1 2 3 4 5 6

1 2 3 4 5 6


� Si usano due for annidati:� il piu esterno itera sulle i posizioni dell’array.� il piu interno per portare l’elemento piu piccolo (della porzione non

ordinata) in posizione i-esima

function bubbleSort(vet) {var temp,i,j;

for (i = 0; i < vet.length-1; i++)

for (j = vet.length-1; j > i; j--)

if (vet[j] < vet[j-1]){temp=vet[j];

vet[j]= vet[j-1];

vet[j-1]=temp;} }


Operazioni che sfruttano la dinamicita degli array

� L’operazione primitiva che permette di modificare il numero deglielementi di un array e l’aggiunta di uno o piu elementi in fondoall’array:

� Esempio: vet[vet.length]=asknum();

Aggiunge un elemento all’array vet di indice vet.length e valoreletto dall’input.

� Esempio: vet[vet.length+2]=asknum();

Aggiunge 3 elementi all’array vet due di indice vet.length evet.length+1 e valore undefined e uno di indice vet.length+2 evalore letto dall’input.

� esistono alcune operazioni (metodi) predefinite che permettono anchedi eliminare elementi da un array. Li vedremo piu avanti.

� tutti gli esempi visti considerano array il cui numero di elementi restacostante durante tutta l’esecuzione. Vediamo ora degli esempi diprogrammi che aggiungono elementi ad un array.


Inserzione di un elemento in un array ordinato

� Se una struttura dati (array) e statica ovvero il numero dei suoielementi non cambia, ha senso avviare una procedura di ordinamentoal momento dell’inizializzazione.

� Se viceversa una struttura dati (array) e dinamica la cosa piu sensatae di mantenerla ordinata, inserendo i nuovi elementi in modo cherispettino l’ordinamento.

� notare che un array vuoto, dimensione 0 e ordinato per definizione e

� lo stesso vale per un array di un unico elemento.� per inserire un nuovo elemento al posto giusto dobbiamo

� scorrere gli elementi che lo precedono per decidere la posizione che glicompete

� spostare di un posto verso destra gli elementi maggiori per fargli spazio.


Un esempio

� In nero l’elemento da inserire,� in rosso gli elementi gia inseriti nell array []� in blu gli elementi gia inseriti che e stato necessario spostare al passo

precedente� se l’elemento da inserire andra ad occupare una posizione gia

occupata, l’elemento corrispondente e sottolineato.

5 [ ][5]

2 [5][2, 5]

4 [2, 5][2, 4, 5]

1 [2, 4, 5][1, 2, 4, 5]

3 [1, 2, 4, 5][1, 2, 3, 4, 5]


� Una volta individuata la posizione i in cui inserire il nuovo elementodobbiamo farle spazio, ovvero spostare verso destra di una posizionetutti gli elementi da i in poi.

Inserzione di 3, da inserire in posizione 2

0 1 2 3 43 1 2 4 53 1 2 4 5

1 2 3 4 5

E necessario spostare 5 in posizione 4 e 4 in posizione 3

� A questo punto la posizione 2 e libera e possiamo inserire l’elementoin modo ordinato

1 2 3 4 5

� Se l’elemento da inserire e maggiore di tutti gli elementi dell’arraynon dobbiamo spostare nulla, ma inserire in fondo.


Shift a destra per array dinamici

� Dobbiamo percio definire una procedura che sposta tutti gli elementidi un array (vet verso destra di una posizione a partire da una dataposizione from<vet.length).

� dobbiamo aggiungere un nuovo elemento all’array che ha come valoreil valore dell’elemento che si trova in ultima posizione, che quindi nonviene perso

� Bisogna procedere da destra verso sinistra per non perdere glielementi

function shiftRD(vet, from)

{var j;

for (j=vet.length; j>from; j--)

vet[j]=vet[j-1];

}


Possiamo ora definire la procedura di ordinamento per inserzione comesegue

function insOrd(vet, x){var i=0, trovato=false;

while (i<vet.length && !trovato) {if (a[i]<x) i++;

else trovato=true;}if (!trovato) a[vet.length]=x;

else { shiftRD(vet, i);

vet[i]=x; } }� i e la posizione in cui dobbiamo inserire il nuovo elemento, e cioe in

caso di ordinamento crescente la posizione del primo elemento cherisulta > del valore che stiamo inserendo.

� se sono ammessi elementi ripetuti cambia qualcosa?


Un’altra soluzione piu compatta

� Questa soluzione utilizza una funzione insertInPos con 3 parametri:

� l’array vet,� la posizione p in cui inserire l’elemento� l’elemento da inserire x

� La funzione si preoccupa di spostare a destra tutti gli elementi,aumentando la dimensione dell’array per poter memorizzare unelemento in piu.

function insertInPos(vet,p,x) {var j;

for (j=vet.length; j>p; j--)

vet[j]=vet[j-1];

vet[i]=x; }


La nuova definizione della funzione insOrd

� Notare la guardia del while (i<vet.length && a[i]<x).

� Questa condizione e corretta per la regola di valutazione strettadell’&&.

� Se la prima condizione i<vet.length e falsa, la seconda condizionea[i]<x non viene valutata.

function insOrd(vet, x){var i=0,

while (i<vet.length && a[i]<x) i++;

insertInPos(vet, i, x); }


Ancora un’altra soluzione per insOrd

� Questa soluzione usa un metodo predefinito su oggetti array, invecedella funzione insertInPos definita sopra:

il metodo splice viene invocato con nomeArray.splice(p,0,x),quindi abbiamo:

function insOrd(vet, x){var i=0,

while (i<vet.length && a[i]<x) i++;

vet.splice(i,0, x); }


Eliminazione di elementi da un array

� La rimozione di un elemento da un array non e un’operazioneprimitiva e puo essere effettuata solo attraverso i metodi: uno diquesti e ancora il metodo splice,

� indicando la posizione del primo elemento da rimuovere e il numero dielementi da rimuovere,

� ad esempio con nomeArray.splice(p,1), viene rimosso l’elementoin posizione p :

function EliminaElem(vet, x){var i=0,

while (i<vet.length && a[i]<=x) i++;

if (i!=vet.length) vet.splice(i,1); }


Merge di due array ordinati

a2 4 6 8

0 1 2 3

b1 4 6 9 17

0 1 2 3 4

c

0

Si scandiscono a e b insieme finche entrambi contengono elementi e siseleziona l’elemento piu piccolo tra i due esaminati, che viene aggiunto a cdinamicamente. Abbiamo 3 indici uno per ogni array.



a2 4 6 8

0 1 2 3

b1 4 6 9 17

0 1 2 3 4

c1 2 4 4 6 8 9 10 17

0 1 2 3 4 5 6 7 8

Situazione finale


Precisazione sulla visibilit`a delle variabili durante l...

Documents

Transcript of Precisazione sulla visibilit`a delle variabili durante l...