Homework 7

Obiettivi

• gestire liste doppiamente linkate
• implementare algoritmi ricorsivi su liste (facoltativo)

Svolgimento

Si scriva un programma C per gestire una lista di interi doppiamente linkata.

Una lista doppiamente linkata e' una lista in cui ogni elemento contiene (oltre al dato) due puntatori:

• next che punta al prossimo elemento della lista
  • l'ultimo elemento della lista ha next==NULL
• prev che punta all'elemento precedente della lista
  • il primo elemento della lista ha prev==NULL

Comandi da riconoscere

• all'inizio la lista e' vuota (NULL) e il cursore e' vuoto (NULL)

Il programma accetta i seguenti comandi letti da stdin (su righe diverse).

• fine termina l'esecuzione del programma
• add <intero> crea un nuovo nodo che contiene l'intero e lo aggiunge dopo il cursore
  • il cursore viene spostato sul nuovo nodo
• next muove il cursore al nodo successivo (fermandosi all'ultimo nodo se necessario)
• prev muove il cursore al nodo precedente (fermandosi al primo nodo se necessario)
• del elimina il nodo indicato dal cursore e lo disalloca
  • il cursore viene posizionato sul nodo successivo se esiste, altrimenti su quello precedente se esiste
  • se la lista è vuota stampa la stringa vuota seguita da \n [aggiunta dell'8-12-2002]
• print stampa tutta la lista, un intero per riga e indica la posizione del cursore facendo seguire il valore dalla stringa " *" (spazio asterisco)
  • se la lista è vuota stampa la stringa vuota seguita da \n [aggiunta dell'8-12-2002]

Esempi di Input - Output

add 1
add 2
add 3
add 4
print
fine

add 1
add 2
add 3
add 4
prev
prev
print
fine

add 1
add 2
add 3
add 4
prev
prev
del
print
fine

1
2
3
4 *

1
2 *
3
4

1
3 *
4

Parte facoltativa

• sort che ordina la lista usando l'algoritmo merge-sort
  • il cursore rimane sul nodo che indicava prima
  • se la lista è vuota stampa vuota e va accapo [aggiunta del 9-12-2002]

Algoritmo merge-sort

Per ordinare una lista disordinata usando l'algoritmo merge-sort si usa la seguente definizione ricorsiva:

• una lista di 1 solo elemento è già ordinata
• una lista di 2 o più elementi si ordina eseguendo:
  1. spezzo la lista in due sottoliste di dimensioni simili
     • ad esempio scorro la lista e sposto un elemento sì ed uno no su due liste separate (elementi pari ed elementi dispari)
  2. ordino separatamente le due sottoliste usando su di esse l'algoritmo merge-sort (questa è la chiamata ricorsiva)
  3. fondo le due liste ordinate così ottenute applicando ad esse il passo merge
  4. il risultato è la lista ordinata

Passo merge

1. se una delle due liste è vuota (NULL) il risultato è l'altra lista
2. altrimenti confronto i primi elementi x ed y delle due liste:
   1. se x<y:
      1. prendo x come primo elemento della lista risultante
      2. fondo il resto di X con Y ottenendo Z (questa è una chiamata ricorsiva a merge)
      3. infine attacco x davanti a Z
   2. altrimenti:
      1. prendo y come primo elemento della lista risultante
      2. fondo il resto di Y con X ottenendo Z (questa è una chiamata ricorsiva a merge)
      3. infine attacco y davanti a Z

-- AndreaSterbini - 04 Dec 2002

• Set ALLOWTOPICCHANGE = DocentiProg1Group