HomeWork4 < Architetture2/MZ/AA16

Tags: view all tags

---+ Homework 4 - ordinamento di una lista di numeri

Il cuore dell'esercizio è l'ordinamento di una lista di numeri.
La lista è implementata come un vettore di 100 nodi, ovvero coppie *&lt;valore, next&gt;* di 100 elementi in cui
   * il primo elemento della coppia contiene il *valore* del nodo (numero intero)
   * il secondo elemento della coppia può contenere:
      * il valore *-1* che indica che non c'è un nodo seguente nella lista (questo è l'ultimo)
      * oppure l'indice del prossimo elemento nel vettore di coppie

Per gestire l'inserimento e la cancellazione di nodi dalla lista dovete prevedere di manipolare 2 liste:
   * la lista dei nodi vuoti, realizzata all'inizio come segue:
      * all'inizio tutti i nodi contenuti nel vettore hanno valore 0 (zero) e ciascun nodo punta alla posizione successiva, il nodo a indice 99 ha *next=-1*
   * la lista dei valori inseriti, presi mano a mano dalla lista dei nodi vuoti (add) oppure rimessi sulla lista dei nodi vuoti (del)

---++ Inserimento dell'input

Il vostro programma riceve una successione di comandi indicati da una lettera, seguita sulle righe successive da eventuali parametri:
   * *A* (Add) aggiunge un elemento *in testa alla lista*, con 1 argomento:
      * *Valore*, un intero a 32 bit da memorizzare nella lista
      * ovvero prende il primo elemento della lista dei nodi liberi e lo aggiunge in testa alla lista di valori, modificandone valore e campo next 
   * *D* (Del) toglie il primo elemento dalla lista di valori e lo "rilascia", ovvero lo inserisce come primo elemento nella lista di nodi liberi, senza azzerarne il valore
   * *V* (stampa Vettore)
      * stampa su una riga tutti gli elementi del vettore separati da spazio, ed in fondo un accapo
      * Esempio: valore0 next0 valore1 next1 valore 2 next2 .... valore99 next99
   * *P* (Print) stampa su una riga la lista di valori nell'ordine di visita dei nodi (seguendo il campo next) separati da spazio, e con un accapo in fondo
   * *Q* (Quit) termina il programma
   * *S* (Sort) ordina la lista di valori con l'algoritmo che preferite

---++ Ordinamento

Per ordinare la lista potete usare un qualsiasi algoritmo di ordinamento a piacere, *ma ATTENZIONE:*
   * i nodi della lista NON si devono muovere, l'unica cosa che potete cambiare sono i puntatori al prossimo elemento

Tra gli algoritmi di ordinamento, i più adatti ad una implementazione tramite una lista sono:
   * *insertionSort* o *selectionSort* (più semplici)
   * *mergesort* (più complicato) con l'accortezza di:
      * realizzare la routine *merge* aggiungendo alla lista risultante il minimo tra i due primi nodi delle due liste da fondere solo DOPO aver già fuso il resto delle due liste (quindi dopo la chiamata ricorsiva)
      * realizzare la routine *mergesort* spezzando la lista da ordinare in due liste di metà lunghezza:
         * o visitando la lista e spezzandola dopo N/2 nodi
         * oppure visitando la lista e costruendo con i suoi elementi due liste contenenti i nodi in posizione pari ed in posizione dispari nella lista originale (anche qui può convenire farlo in uscita dalla ricorsione)
      * NOTA: nella versione con liste non è necessario un vettore di appoggio

---++Esempio
Se l'input (commentato con l'indice al primo elemento della lista, l'indice al primo elemento della lista di nodi liberi, e col contenuto del vettore) è
<verbatim>
      # List | Free | Vettore
V     #   -1 |   0  |         0 1 0 2 0 3 0 4 0 5 ... 0 99 0 -1
A     # Add 10
10    #    0 |   1  | 10 -1       0 2 0 3 0 4 0 5 ... 0 99 0 -1 
A     # Add 20
20    #    1 |   2  | 10 -1 20 0      0 3 0 4 0 5 ... 0 99 0 -1
A     # Add 12
12    #    2 |   3  | 10 -1 20 0 12 1      0 4 0 5 ... 0 99 0 -1
D     #    1 |   2  | 10 -1 20 0      12 3 0 4 0 5 ... 0 99 0 -1
V     # stampa del vettore
A     # Add 14
14    #    2 |   3  | 10 -1 20 0 14 1      0 4 0 5 ... 0 99 0 -1
A     # Add 94
94    #    3 |   4  | 10 -1 20 0 14 1 94 2     0 5 ... 0 99 0 -1
P     # stampa della lista
V     # stampa del vettore
S     # ordinamento
      #    0 |   4  | 10  2 20 3 14 1 94 -1    0 5 ... 0 99 0 -1
P     # stampa della lista
V     # stampa del vettore
D     # cancello il primo nodo, che ora è nella lista Free
      #    2 |   0  | 10  4     20 3 14 1 94 -1    0 5 ... 0 99 0 -1
P     # stampa della lista
V     # stampa del vettore
Q     # uscita dal programma
</verbatim>
La lista che abbiamo costruito contiene nell'ordine gli elementi: *94 -> 14 -> 20 -> 10*

E quindi l'output (commentato e con qualche spazio aggiunto) sarà:
<verbatim>
         0 1 0 2 0 3 0 4 0 5 ... 0 99 0 -1     # nessun nodo inserito, il vettore contiene solo la lista dei nodi vuoti
10 -1 20 0      12 3 0 4 0 5 ... 0 99 0 -1     # dopo la cancellazione del valore 12 il vettore appare così
94 14 20 10                                    # sono stati inseriti 4 valori, appaiono in ordine inverso perchè ogni inserimento è un "push" sulla lista
10 -1 20 0 14 1 94 2     0 5 ... 0 99 0 -1     # dopo che sono stati inseriti anche gli altri valori il vettore appare così
10 14 20 94                                    # dopo il sort la lista è ordinata in ordine crescente
10  2 20 3 14 1 94 -1    0 5 ... 0 99 0 -1     # ed il vettore appare così (i valori non si sono mossi, sono cambiati solo i campi "next" dei nodi)
14 20 94                                       # i nodi rimasti dopo aver cancellato il primo
10  4     20 3 14 1 94 -1    0 5 ... 0 99 0 -1 # ora il nodo a indice 0 è nella lista Free, mentre i valori partono dal nodo a indice 2
</verbatim>

---++ Consegna entro il 31 maggio

Per consegnare usate la solita [[http://twiki.di.uniroma1.it/~andrea/consegna-HW-2017.html][pagina]]

La [[%ATTACHURL%][pagina dei test]] per ora contiene alcuni esempi costruiti a mano, appena posso li verifico con la mia implementazione