HomeWork7aa0203 < Programmazione1/AA0506/PZ

---+++ Homework 7
Vedi anche DomandeHomework7aa0203, SoluzioneHomework7aa0203, RisultatiHomework7aa0203.
----
%TOC%
----
---+++ 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
Il programma deve gestire un *cursore* sulla lista, ovvero quale e' l'elemento corrente sul quale debbono essere eseguiti i comandi.
   * 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 &lt;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 %RED% _[aggiunta dell'8-12-2002]_ %FINE%
   * *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 %RED% _[aggiunta dell'8-12-2002]_ %FINE%

---+++ Esempi di Input - %RED%Output%FINE%
<center>
<table border='1' size='50%'>
<tr>
<th>Input</th>
<th size="10%">&nbsp;</th>
<th>Input</th>
<th size="10%">&nbsp;</th>
<th>Input</th>
</tr>
<tr valign='top'><td>
<verbatim>
add 1
add 2
add 3
add 4
print
fine
</verbatim>
</td>
<td></td>
<td>
<verbatim>
add 1
add 2
add 3
add 4
prev
prev
print
fine
</verbatim>
</td>
<td></td>
<td>
<verbatim>
add 1
add 2
add 3
add 4
prev
prev
del
print
fine
</verbatim>
</td>
</tr>
<tr valign='top'>
<th>%RED%Output%FINE%</th>
<td></td>
<th>%RED%Output%FINE%</th>
<td></td>
<th>%RED%Output%FINE%</th>
</tr>
<tr valign='top'>
<td>
%RED%
<verbatim>
1
2
3
4 *
</verbatim>
%FINE%
</td>
<td></td>
<td>
%RED%
<verbatim>
1
2 *
3
4
</verbatim>
%FINE%
</td>
<td></td>
<td>
%RED%
<verbatim>
1
3 *
4
</verbatim>
%FINE%
</td></tr>
</table>
</center>

---+++ Parte facoltativa
Implementare il comando aggiuntivo:
   * *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 %RED% _[aggiunta del 9-12-2002]_ %FINE%

---+++ Algoritmo merge-sort
Abbiamo visto in aula come si implementa il passo *merge* dell'algoritmo *merge-sort* (vedi sotto).

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)
      1 ordino separatamente le due sottoliste usando su di esse l'algoritmo *merge-sort* (questa è la chiamata ricorsiva)
      1 fondo le due liste ordinate così ottenute applicando ad esse il passo *merge*
      1 il risultato è la lista ordinata

---++++ Passo merge
Per fondere distruttivamente due liste *X* e *Y* ordinate per ottenere una lista ordinata si può:
   1 se una delle due liste è vuota (NULL) il risultato è l'altra lista
   1 altrimenti confronto i primi elementi *x* ed *y* delle due liste:
      1 se *x&lt;y*:
         1 prendo *x* come primo elemento della lista risultante
         1 fondo il resto di *X* con *Y* ottenendo *Z* (questa è una chiamata ricorsiva a *merge*)
         1 infine attacco *x* davanti a *Z*
      1 altrimenti:
         1 prendo *y* come primo elemento della lista risultante
         1 fondo il resto di *Y* con *X* ottenendo *Z* (questa è una chiamata ricorsiva a *merge*)
         1 infine attacco *y* davanti a *Z*

-- Users.AndreaSterbini - 04 Dec 2002

   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group
This topic: Programmazione1/AA0506/PZ > WebHome > HomeWork7aa0203
Topic revision: r11 - 2003-09-30 - AndreaSterbini