Esercizi – parte 1



Scaricare 17.22 Kb.
10.12.2017
Dimensione del file17.22 Kb.

Esercizi – parte 2

IMPLEMENTAZIONE DI STRUTTURE DATI ELEMENTARI

1. Si implementi in Java il tipo di dato astratto Lista, dotato delle consuete operazioni cons(el), cdr() e car(). Si usi la classe Java LinkedList.



Sol. Si ricordi che cons(el) inserisce el in testa alla lista, cdr() elimina e restituisce l’elemento in testa alla lista, car() restituisce l’elemento in tesa alla lista senza eliminarlo. La classe LinkedList permette l’implementazione di tutte queste operazioni in modo diretto. Sarebbe tuttavia un esempio di cattiva programmazione implementare l’ADT Lista usando direttamente un oggetto di classe LinkedList, poiche’ tale classe mette a disposizione numerosi metodi che non corrispondono ad operazioni previste dall’ADT Lista. Un modo di procedere e’ quello di definire una variabile privata di classe LinkedList e definire metodi pubblici di accesso che corrispondono alle operazioni previste per l’ADT. Ad esempio:
public class Lista {

private LinkedList myList;


public Lista() {

myList = new LinkedList();

}

public void cons(Object el) {



myList.addFirst(el);

}

public Object cdr() {



myList.removeFirst();

}

public Object car() {



myList.getFirst();

}

}


Per comprendere pienamente la soluzione proposta si consulti la documentazione Java relativa alla classe LinkedList.
2. Si implementi in Java l’ADT Pila, con le operazioni push(el), pop(), top() e isEmpty(). Si usi la classe LinkedList.

Sol. Procedendo come nel caso precedente abbiamo:
public class Pila {

private LinkedList myStack;


public Pila() {

myStack = new LinkedList();

}

public void push(Object el) {



myList.addFirst(el);

}

public Object pop() {



myList.removeFirst();

}

public Object top() {



myList.getFirst();

}

boolean isEmpty() {



return (myStack.size() == 0);

}

}


Si osservi che i) Il tipo Lista corrisponde sostanzialmente al tipo Pila e che ii) isEmpty() e’ stata implementata usando il metodo size() di LinkedList, che restituisce il numero di elementi presenti nell’oggetto di classe LinkedList.
3. Il tipo astratto DoppioStack e’ consente le seguenti operazioni:

  • headPush(): inserimento in testa.

  • tailPush(): inserimento in coda.

  • headPop(): rimozione e restituzione dell’elemento in testa.

  • tailPop(): rimozione e restituzione dell’ elemento in testa.

  • headTop(): restituzione (senza rimozione) dell’elemento in testa.

  • tailTop():restituzione (senza rimozione) dell’elemento in coda.

Si implementi in Java tale tipo usando LinkedList

Sol. Procedendo analogamente ai due casi precedenti abbiamo:
public class DoppioStack {

private LinkedList myStack;


public DoppioStack() {

myStack = new LinkedList();

}

public void headPush(Object el) {



myList.addFirst(el);

}

public void tailPush(Object el) {



myList.addLast(el);

}

public Object headPop() {



myList.removeFirst();

}

public Object tailPop() {



myList.removeLast();

}

public Object headTop() {



myList.getFirst();

}

public Object tailTop() {



myList.getLast();

}

}


4. Nella stesura di un programma per la gestione di finestre grafiche, Giovanni ha bisogno di implementare uno stack di oggetti. A tale scopo, Giovanni usa una variabile myStack di classe LinkedList, adottando la convenzione che l’elemento in posizione 0 sia quello in cima allo stack. Tra le altre, Giovanni scrive le seguenti linee di codice:
…………

nextWindow = myStack.removeLast(); // finestra in cima allo stack

…………
i) Che errore ha commesso Giovanni? ii) L’errore sara’ segnalato in fase di compilazione? iii) In caso negativo, come bisognerebbe procedere per evitare tale tipo di errori?

Sol. i) Data la convenzione adottata da Giovanni, la cima dello stack e’ restituita da myStack.removeFirst(). ii) L’errore non sara’ segnalato in caso di compilazione, perche’ la riga di codice sopra descritta non presenta errori sintattici o semantici. iii) Il modo corretto di procedere sarebbe quello di implementare uno stack procedendo come nell’esercizio 2.

COMPLESSITA’ DI ALGORITMI CHE USANO ADT ELEMENTARI


5. Si supponga di avere a disposizione l’ ADT Pila. Si supponga che Pila metta a disposizione le operazioni

  • push(el): inserisce l'elemento specificato da el in cima alla pila

  • pop(): elimina l'elemento in cima alla pila

  • top(): restituisce l'elemento in cima alla pila senza cancellarlo dalla lista

  • isEmpty(): verifica se la pila è vuota

Si proponga un algoritmo con complessita’ lineare che, data una pila A, crea una seconda pila B che e’ la copia di A. L’algoritmo puo’ fare uso di 1 pila di appoggio. A deve rimanere inalterata.



Sol. Un semplice algoritmo si ottiene dalla successione di due cicli while come segue:
while(!A.isEmpty())

C.push(A.pop()); // C e’ una pila di appoggio

while(!C.isEmpty()) {

A.push(C.top()); // ripristina A

B.push(C.pop()); // copia in B

}

E’ immediato verificare che il costo dell’algoritmo e’ lineare.


6. Si supponga di avere a disposizione l’ ADT Coda. Si supponga che Coda metta a disposizione le operazioni

  • enqueue(el): inserisce l'elemento specificato da el in coda

  • dequeue(): elimina l'elemento in testa

  • firstEl(): restituisce l'elemento in testa senza rimuoverlo isEmpty(): verifica se la coda è vuota

Si proponga un algoritmo con complessita’ lineare che, data una coda A, crea una seconda coda B che e’ la copia di A. L’algoritmo non puo’ fare uso di code di appoggio. A deve rimanere inalterata.



Sol. Un algoritmo che risolve il problema e’ il seguente:
count = 0; // conta il numero di elementi nella coda iniziale

while(!A.isEmpty()) {

B.enqueue(A.dequeue()); // crea B

count++;


} /* Qui B e’ una copia di A, ma A e’ vuota */

for (i=0; i < count; i++) {

A.enqueue(B.firstEl()); // ripristina A

B.enqueue(B.dequeue()); // scorri B



} /* Qui A e’ ripristinata e B e’ una sua copia */




©astratto.info 2017
invia messaggio

    Pagina principale