Skip to content Skip to navigation

Connexions

You are here: Home » Content » Liste, pile e code

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

Liste, pile e code

Module by: Davide Rocchesso. E-mail the author

User rating (How does the rating system work?)
Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

:
(0 ratings)

Summary: Si presentano le principali strutture dati atte alla manipolazione lineare di dati in quantità non prevedibile a priori.

Liste

Una istanza di classe può contenere, tra le sue variabili, anche un puntatore ad un oggetto della classe stessa. Questo consente di concatenare oggetti di una stessa classe, a formare strutture complesse quali liste o alberi. In particolare, una lista è ottenuta dalla concatenazione di nodi, ciascuno dei quali contiene un puntatore al nodo successivo, nonché un campo dati talvolta chiamato cargo.

Esempio 1: Attraversamento di una lista

Nel codice Processing che segue viene creata una lista di tre nodi concatenati. Quindi tale lista viene visitata per attraversamento e il cargo di ogni nodo viene stampato. Si notino le seguenti cose:

  • La classe Node ha due tipi di costruttore, uno senza parametri ed uno con parametri. Quest'ultimo consente la creazione con inizializzazione del cargo e del puntatore al nodo successivo.
  • C'è un metodo toString che converte il cargo in una stringa stampabile ogni volta che viene invocata la funzione print sul nodo.

       
void setup() {
  Node node3 = new Node (3, null);
  Node node2 = new Node (2, node3);
  Node node1 = new Node (1, node2); 
  printList(node1);
}

void printList (Node list) {
    Node node = list;
    
    while (node != null) {
        print(node);
        node = node.next;
    }
    println();
}

class Node {
  int cargo;
  Node next;
  
  Node() {
    cargo = 0;
    next = null;
  }
  
  Node (int cargo, Node next) {
    this.cargo = cargo;
    this.next = next;
  }
  
  String toString() { //rende l'oggetto di classe Node stampabile
    return cargo + " ";
  }
}

Così come gli array sono il supporto naturale dei cicli for e delle iterazioni sequenziali, così le liste sono il supporto naturale della algoritmica ricorsiva. Gli algoritmi ricorsivi sono definiti induttivamente stabilendo l'operazione per un elemento base (la base della ricorsione) e stabilendo come utilizzare il risultato dell'elaborazione sulla lista privata di tale elemento. Inoltre, bisogna assicurarsi che l'elaborazione così arrangiata in maniera "telescopica" raggiunga ad un certo punto una condizione di terminazione della ricorsione. Ciò non è sempre banale perché le catene di puntatori degli elementi di una lista potrebbero presentare dei loop, la cui visita procederebbe senza fine. Nell'esempio Esempio 1 si può introdurre una funzione di stampa dall'ultimo elemento al primo: 


       
void printBackward (Node list) {
 if (list == null) return; // terminazione della ricorsione
 
 Node head = list;
 Node tail = list.next;
 
 printBackward(tail);
 print(head);   // base della ricorsione
}

Si può costruire una classe che incorpori l'intera lista e le operazioni che su di essa si intendono eseguire. Ad esempio, si può estendere Esempio 1 con l'introduzione di una classe IntList che supporta stampe per attraversamento diretto e inverso (ricorsivo). Si noti l'uso di un doppio metodo printBackward, uno con e uno senza argomenti, per consentire l'invocazione del metodo sull'oggetto lista senza necessità di passare un puntatore alla testa della lista stessa. 



       
IntList lista;

void setup() {
  lista = new IntList();
  lista.addFirst(3);
  lista.addFirst(2);
  lista.addFirst(1);
  lista.printList();
  lista.printBackward();
}

class IntList {
 int length;
 Node head;

   IntList() {
     length = 0;
     head = null;
   }

   void addFirst (int i) {
     Node node = new Node(i, head);
     head = node;
     length++;
   }
   
   void printList () {
     Node node = head;
    
      while (node != null) {
        print(node);
        node = node.next;
      }
      println();
   }

  void printBackward() {
    printBackward(head);
    println();
  }
  
  void printBackward (Node head) {
   if (head == null) return; // terminazione della ricorsione

   Node tail = head.next;
 
   printBackward(tail);
   print(head);   // base della ricorsione
  }
 }
 


class Node {
  int cargo;
  Node next;
  
  Node() {
    cargo = 0;
    next = null;
  }
  
  Node (int cargo, Node next) {
    this.cargo = cargo;
    this.next = next;
  }
  
  String toString() { //rende l'oggetto di classe Node stampabile
    return cargo + " ";
  }
}
Questo è un esempio di classe wrapper, cioè di confezionamento object-oriented di una struttura dati. Le classi wrapper esistono per tutti i tipi primitivi di Java (double, int, ecc.) e consentono di creare e manipolare oggetti che contengono valori primitivi. Ad esempio, la classe wrapper Integer può essere interrogata in relazione al più piccolo e più grande valore rappresentabile mediante Integer.MIN_VALUE e Integer.MAX_VALUE, rispettivamente. Il valore numerico di un oggetto della classe Integer si ottiene con il metodo intValue(). Anche gli array in Java sono accessibili mediante una classe wrapper. La classe Arrays, accessibile importando java.util.*, consente di fare operazioni di test di uguaglianza, di ricerca, e di ordinamento. Ad esempio, il semplice codice 

       
import java.util.*;

void setup() {
  int[] a = new int[10];
  int[] b = new int[10];
  
  for (int i=0; i<10; i++) {
    a[i] = i;
    b[i] = i;
  }
  println(Arrays.equals(a,b));
}
esegue un test di uguaglianza tra due array di interi.

Lettura

Si legga il capitolo 14 di How to Think Like a Computer Scientist

Pile

Lo stack, o pila, è una struttura dati di grande importanza. Ad esempio, essa è implicitamente coinvolta nell'esecuzione di codice ricorsivo, quale quello del metodo printBackward. In effetti, a runtime le chiamate a procedura sono sistemate, insieme ai loro parametri, una sopra all'altra nell'ordine in cui sono invocate. Nell'esempio, alla terza chiamata ricorsiva di printBackward ci si trova in cima allo stack una chiamata su una lista di un solo elemento. Ad uno stack si accede mediante due sole operazioni, la push (immissione) di un elemento in cima allo stack, e la pop (rimozione) di un elemento dalla cima dello stack. Una classe Stack è già disponibile in Java (e in Processing) dopo aver importato java.util.*. Essa funziona su oggetti della classe Object, che è la più generica delle classi Java, nonché superclasse di tutte.

Esempio 2: Attraversamento inverso di una lista

La visita in ordine inverso, dalla coda alla testa, degli elementi di una lista si può ottenere per via ricorsiva, come già visto in Paragraph 3. Alternativamente, si può usare uno stack come struttura dati di appoggio. 



import java.util.*;

IntList lista;
Stack pila;

void setup() {
  pila = new Stack();
  lista = new IntList();
  lista.addFirst(3);
  lista.addFirst(2);
  lista.addFirst(1);
  lista.printList();
  for (Node node = lista.head; node != null; node = node.next) {
   pila.push(node); 
  }
  while (!pila.isEmpty()) {
    Node node = (Node) pila.pop();
    print(node);
  }
}

class IntList {
 ... omissis ...
 
class Node {
 ... omissis ...
Si può notare che
  • gli elementi della lista sono inseriti nella pila nel loro ordine naturale, essendo così estraibili da questa in ordine inverso,
  • esiste un metodo isEmpty() della classe Stack che consente di verificare la condizione di pila vuota,
  • è necessario fare un type casting sull'oggetto restituito dalla pop(). Questo è un generico Object in quanto la classe Stack non è in grado di conoscere il tipo dei suoi elementi.
  • in generale è sempre possibile convertire un algoritmo ricorsivo in uno non ricorsivo facendo uso di uno stack. In questo esempio la pila viene usata in luogo del run-time stack.

Valutazione di espressioni

Lo stack è anche la struttura dati che con maggior naturalezza supporta la valutazione di espressioni. Per essere più precisi, data una stringa contenente operandi e operatori in notazione postfissa, una scansione lineare della stringa accompagnata dall'utilizzazione di uno stack di appoggio può consentire una facile valutazione della espressione. E' necessario inoltre individuare i token della stringa (operandi o operatori), separati da delimitatori che tipicamente sono caratteri di spaziatura. C'è una classe di java.util, chiamata StringTokenizer, che fa proprio questo. Ad esempio, la "tokenizzazione" di una espressione in notazione postfissa si può eseguire con: 


	    
import java.util.*;

StringTokenizer st = new StringTokenizer("11 22+33*", " +-*/", true);

while (st.hasMoreTokens())
  println(st.nextToken());
dove gli argomenti di StringTokenizer(), oltre a comprendere la stringa da analizzare, comprendono la lista dei delimitatori e un parametro boolean che indica che i separatori devono essere considerati anch'essi come token. La valutazione di espressioni su stringhe è un esempio semplice di parsing.

Exercise 1

Si costruisca un valutatore di espressioni in notazione postfissa con operatori di somma e moltiplicazione su numeri interi.

Solution

Nella soluzione che segue la stringa da analizzare è scritta in testa al codice. Si fa uso del metodo equals() della classe String e del metodo parseInt() della classe Integer. Si noti inoltre il matching di espressione regolare supportato dalla classe String. In questo caso l'espressione regolare rappresenta una qualsiasi sequenza di cifre. 


		
import java.util.*;

StringTokenizer st = new StringTokenizer("3 12 21 ++ 10*", " +*", true);
Stack pila = new Stack();
String tocco;
int op1=0, op2=0;

while (st.hasMoreTokens()) {
    tocco=st.nextToken();
    if (tocco.equals("+")) {  
       if (!pila.isEmpty()) op2 = Integer.parseInt((String)pila.pop());
       if (!pila.isEmpty()) {
         op1 = Integer.parseInt((String)pila.pop());
         pila.push(Integer.toString(op1+op2)); 
       }
    }
    else if (tocco.equals("*")) {  
       if (!pila.isEmpty()) op2 = Integer.parseInt((String)pila.pop());
       if (!pila.isEmpty()) {
         op1 = Integer.parseInt((String)pila.pop());
         pila.push(Integer.toString(op1*op2)); 
       } 
    }
    else if (tocco.matches("\\d+")) { // token as a sequence of digits
      pila.push(tocco);
      println(tocco);
    }
    
    }
println(pila);

Lo stack delle trasformazioni geometriche

Un ambito di impiego molto importante della struttura dati a stack è la grafica interattiva. In particolare, le trasformazioni geometriche che si effettuano in OpenGL avvengono per moltiplicazione matrice-vettore, e le matrici sono memorizzate sullo stack delle trasformazioni. Ciò consente di costruire modelli gerarchici di oggetti nello spazio. Nel momento in cui si fa pushMatrix() la cima della pila contiene la matrice di trasformazione geometrica che si sta applicando ad un particolare oggetto, o in altri termini lo stato corrente del sistema. Le trasformazioni applicate successivamente alla pushMatrix() vengono "dimenticate" nel momento in cui si fa una popMatrix(), in questo modo ripristinando lo stato precedente a queste ultime trasformazioni.

Esempio 3: Geometria grafica costruttiva

Un semplice esempio di modello gerarchico è un braccio meccanico costituito da tre parallelepipedi: una base, un omero, e un avanbraccio. La collocazione dell'omero è fissa rispetto alla base, e di questa deve seguirne gli spostamenti. Allo stesso modo, l'avanbraccio è vincolato geometricamente all'omero. Il codice seguente disegna il braccio meccanico che è spostabile nel suo complesso mediante il mouse. Grazie all'uso dello stack, l'omero può ruotare indipendentemente dalla base restando ad essa vincolato. L'avanbraccio può ruotare indipendentemente dall'omero restando a questo vincolato. 


	           
int LAVANB = 70;
int LOMERO = 80;
int LBASE = 30;
float OMEROT = PI/3;
float AVANROT = PI/5;

void setup(){
          size(200, 200, P3D); 
	}

void avanbraccio(){
  pushMatrix();
  translate(0, LAVANB/2, 0);
  box(20, LAVANB, 20);
  popMatrix();
}

void omero(){
  pushMatrix();
  translate(0, LOMERO/2, 0);
  box(20, LOMERO, 20);
  popMatrix();
}

	void draw(){
          background(0);
          translate(mouseX,mouseY);
          rotateY(PI/6);
          box(LBASE);
          translate(0, LBASE, 0);
          rotateX(OMEROT);
          omero();
          translate(0, LOMERO, 0);
          rotateX(AVANROT);
          avanbraccio();
	}

Lettura

Si legga il capitolo 15 di How to Think Like a Computer Scientist

Code

La struttura dati chiamata coda (queue) organizza una politica di accesso alle informazioni analoga a quella applicata idealmente quando si fa la fila presso uno sportello. Il primo cliente ad essere servito è il primo che si è presentato alla coda dello sportello. Una coda (e in realtà anche una pila) può essere realizzata mediante una lista concatenata, consentendo in questo modo di non porre limiti alla lunghezza della coda stessa. L'accesso alla lista che supporta la coda avviene mediante un puntatore di testa e uno di coda.

Esempio 4: Inserimento in coda ed estrazione dalla coda

Si può realizzare una coda mediante concatenazione di nodi e preparazione di due punti di accesso. Questo garantisce che l'accesso in inserimento ed in estrazione sia efficiente e a tempo costante. Nella realizzazione qui riportata la classe Node è atta a realizzare nodi con cargo di tipo Object generico. La presenza del metodo toString() garantirà che il nodo è stampabile. 



Queue q;
Integer uno = new Integer(1);
Integer due = new Integer(2);
Integer tre = new Integer(3);

void setup() {
  q = new Queue();
  q.add(uno);
  q.add(due);
  q.add(tre);
  println(q.remove());
  println(q.remove());
  println(q.remove());
}

class Queue {
 int length;
 Node first, last;

   Queue() {
     length = 0;
     first = null;
     last = null;
   }
   
   boolean isEmpty() {
     return first == null;
   }

   void add (Object obj) {
     Node node = new Node(obj, null);
     if (last != null) {
       last.next = node;
     }
     last = node;
     if (first == null) {
       first = last;
     }
     length +=1;
   }
   
   Object remove () {
     Node result = first;
     if (first != null) {
       first = first.next;
     }
     else {
       last = null;
     }
     length -= 1;
     return result;
   }
 }
 


class Node {
  Object cargo;
  Node next;
  
  Node() {
    cargo = null;
    next = null;
  }
  
  Node (Object cargo, Node next) {
    this.cargo = cargo;
    this.next = next;
  }
  
  String toString() { //rende l'oggetto di classe Node stampabile
    return cargo + " ";
  }
}
Spesso si preferisce, per ragioni di semplicità realizzativa ed efficienza, realizzare la coda usando un array come struttura di supporto. In questo caso la crescita della coda è limitata dalla lunghezza dell'array. Questa realizzazione si chiama buffer circolare ed è impiegato, ad esempio, per la realizzazione di ritardi variabili nell'elaborazione dei segnali.

Lettura

Si legga il capitolo 16 di How to Think Like a Computer Scientist

Content actions

Give Feedback:

E-mail the module author | Rate module ( How does the rating system work?)

Rating system

Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

(0 ratings)

Download:

Module PDF

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.

| A lens (?)

Definition of a lens

Lenses

A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual Connexions member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks