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 <valore, next> 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) è

      # 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

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à:

         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