LISTE
Competenze richieste:
Si consiglia la visione dell’attività del gruppo Bebras “Cambio di direzione” reperibile qui: Bebras dell’informatica — Quesiti d’esempio
Materiale
Età
Numero di Giocatori
Competenze acquisite
Attività di introduzione all’argomento delle liste
PREPARAZIONE:
Leggi le istruzioni del gioco alla classe.
Riassumendo: i giocatori giocano contemporaneamente e cercano di scoprire dietro a quale animale si trovi il regalo nascosto. Per trovarlo, si segue il percorso delle tessere del domino. Tra le tessere del domino sul tavolo si cerca l’animale di partenza indicato sulla carta sfida. Sulla tessera è rappresentato un secondo animale da cercare e così via fino ad arrivare ad un animale che ha lo sfondo del colore indicato dalla carta sfida, e girando la tessera deve essere rappresentato il regalo indicato dalla carta sfida.
QUESTO É INFORMATICA!
Il principio per cui a partire da una carta, si arriva ad una seconda, dalla seconda si arriva alla terza carta e così via, ricorda una struttura dati molto usata in informatica, la lista.
La lista, come i vettori e le matrici serve per memorizzare un gruppo di dati, a differenza della variabile che ne memorizza solo uno.
Nella lista si memorizzano gli elementi associando ad ognuno di essi il riferimento che permette di individuare l’elemento successivo, quindi ogni elemento è composto dal dato e dal riferimento, cioè il puntatore al prossimo elemento. La lista ha una testa che consiste nel primo elemento ed ha anche una coda, ovvero l’ultimo elemento il cui puntatore è nullo perché non punta a nessun prossimo elemento.
Nel gioco gli elementi della lista corrispondono alle tessere, la testa corrisponde alla carta di partenza, invece la coda alla carta finale; il puntatore al prossimo elemento è determinato a partire dalla seconda figura rappresentata nella tessera, questa seconda figura infatti è un indizio che ci fornisce l’informazione necessaria per trovare la tessera successiva, proprio come il puntatore nella lista ci indica l’elemento successivo. Nella carta finale, ovvero la coda della lista, è presente la seconda figura (il puntatore) che dovrebbe determinare la tessera successiva, ma non viene utilizzata in quanto si è arrivati alla carta richiesta dalla carta sfida, possiamo quindi dire che in questo caso il puntatore è nullo.
Possiamo immaginare il puntatore come una freccia che indica il prossimo elemento.
Una caratteristica importante della lista è che nel corso del tempo la sua dimensione può cambiare, basta aggiungere un elemento al fondo, questo non è possibile con i vettori e matrici in quanto bisogna decidere fin dall’inizio la loro dimensione, ovvero il numero di elementi.
Se la maestra decidesse di sottoporre i suoi alunni a 10 verifiche durante l’anno potrebbe utilizzare un vettore di dimensione pari a 10 per ogni bambino, anzi, meglio una matrice di 10 colonne e tante righe quanti sono gli alunni. Ma se all’ultimo minuto decidesse di preparare un’ultima interrogazione? Non riuscirebbe ad aggiungere l’undicesimo voto in mancanza del posto libero, quindi dovrebbe cancellare tutto il lavoro fatto e rifarlo da capo con la nuova dimensione.
Utilizzando la lista è invece possibile aggiungere un elemento senza dover rifare il lavoro perché non ha una dimensione fissa scelta dall’inizio, la nuova coda sarà l’ultimo voto aggiunto e il puntatore della vecchia coda non è più nullo ma indica l’ultimo voto aggiunto, cioè la nuova coda:
Se la maestra decidesse di modificare dei voti, con il vettore e la matrice basterebbe utilizzare gli indici per indicare la posizione del dato da modificare, ad esempio: se VOTO[1][4]=5 e la maestra decide di correggerlo con 6, è necessario solamente scrivere VOTO[1][4]=6.
Utilizzando la lista dovrebbe invece scorrere tutti gli elementi fino a trovare l’elemento da modificare e scrivendo LISTA.DATO=6.
Se la maestra decidesse di cancellare un elemento da un vettore o da una matrice dovrebbe scrivere VOTO[1][3]=NULL, significa che la cella del vettore o matrice c’è ancora ma rimane vuota, nella lista invece è possibile, con delle operazioni leggermente complesse da spiegare in questo contesto, rimuovere definitivamente l’elemento.
Vediamo un altro esempio, chiedi ai bambini facendoli discutere sulle differenze tra un treno e un pullman, ci sono mai saliti? Sanno come sono fatti? Questo li aiuterà nel capire bene la differenza.
Il treno è formato da tanti vagoni collegati tra loro che contengono persone/merci, proprio come una lista è formata da tanti elementi uniti tramite puntatori che contengono informazioni (numeri). Immaginiamo che un treno sia formato da 4 vagoni di prima classe, dei veri e propri alloggi per una sola persona. Il treno viene riempito dal primo vagone fino all’ultimo per un totale massimo di 4 persone. E se arrivasse una quinta persona? Basta semplicemente aggiungere un altro vagone alla fine del treno, attaccato al quarto vagone.
Come è utile collegare i vagoni, è spesso utile collegare locazioni di memoria di un computer e ciò viene tipicamente visualizzato usando riquadri e frecce. Così come i vagoni collegati fanno parte di uno stesso treno, gli elementi di una lista sono collegati a indicare l’appartenenza a una stessa struttura dati, appunto una lista.
La manipolazione di contenuti della memoria memorizzati in questo modo è una parte importante della rappresentazione delle strutture dati.
Il pullman invece è formato da un unico “vagone”, immaginiamo che contenga solamente 4 sedie su cui possono sedere solo 4 persone e non ne possano salire altre. Proprio come il vettore, un’unica struttura che contiene delle “celle”. In questo caso se si volesse aumentare la capacità del mezzo non si potrebbe aggiungere una sedia perché il pullman è stato costruito in modo da ospitare massimo quattro persone, non si può “allungare”, bisognerebbe avere un pullman più grande.
Quindi, se abbiamo bisogno di un pullman che possa ospitare 5 persone dobbiamo utilizzarne uno nuovo più grande.
Ricapitolando, il computer deve essere istruito dalle persone per poter risolvere i problemi degli utenti. Come prima cosa deve poter memorizzare i dati. Ci sono vari modi per salvare i dati,
utilizzando una variabile che ci permette di memorizzare un valore, utilizzando un vettore oppure una matrice, la cui differenza sostanzialmente consiste nell’avere tante righe al posto di una sola, che permettono, a differenza della variabile, di memorizzare un gruppo di informazioni, infine utilizzando una lista, una struttura graficamente simile al vettore che permette anch’essa di memorizzare un insieme di dati ma le differenze consistono nel modo in cui vengono effettuate certe operazioni, ad esempio l’aggiunta o la cancellazione di un elemento. Un bravo programmatore deve essere in grado di scegliere la giusta struttura dati per gestire e memorizzare le informazioni.