SoluzioneHomework7aa0203 < Programmazione1/AA0506/PZ

Tags: view all tags

---+++ Soluzione dell'Homework 7
Vedi anche HomeWork7aa0203, DomandeHomework7aa0203, RisultatiHomework7aa0203.

Ecco la mia implementazione dell'esercizio 7

----
<verbatim>
/*
   Gestione di una lista doppiamente linkata:
   add <intero>   aggiunge un nodo subito dopo il nodo corrente
   del      elimina il nodo corrente e setta il nodo corrente al nodo precedente (successivo se non esiste)
   print      stampa la lista con un asterisco a fianco del nodo corrente
   next      seleziona il prossimo nodo
   prev      seleziona il nodo precedente
   sort      ordina la lista con merge-sort
*/

#include <stdio.h>

/* definizione della struttura del nodo */
typedef
   struct nodo {
      int valore;
      struct nodo * next;
      struct nodo * prev;
   } Nodo ;

#define MAXLINE 1000
#define TRUE 1
#define FALSE 0

void add(Nodo ** lista, Nodo ** corrente, int valore);
void del(Nodo ** lista, Nodo ** corrente);
void prev(Nodo ** corrente);
void next(Nodo ** corrente);
void print(Nodo * lista, Nodo * corrente);
void sort(Nodo ** lista);
Nodo * merge(Nodo * L1, Nodo * L2); 
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari);
void push(Nodo * elemento, Nodo ** lista);

int main(int argc, char * argv[]) {
   char   riga[MAXLINE] = { 0 };
   int    val    = 0;
   Nodo * lista    = NULL;
   Nodo * corrente = NULL;

   scanf("%[^\n]",riga);
   while (0 != strcmp(riga,"fine")) {
      if (1 == sscanf(riga,"add%*[ ]%d",&val))
         add(&lista, &corrente, val);
      else 
      if (0 == strcmp(riga,"del")) {
         if (lista != NULL)
            del(&lista, &corrente);
         else 
            printf("vuota\n");
      } else 
      if (0 == strcmp(riga,"next"))
         next(&corrente);
      else 
      if (0 == strcmp(riga,"prev"))
         prev(&corrente);
      else 
      if (0 == strcmp(riga,"sort")) {
         if (lista != NULL)
            sort(&lista);
         else 
            printf("vuota\n");
      } else 
      if (0 == strcmp(riga,"print")) {
         if (lista != NULL)
            print(lista, corrente);
         else 
            printf("vuota\n");
      };
      scanf("\n%[^\n]",riga);
   }
}

/*
   Aggiungo un nuovo nodo alla lista
*/
void add(Nodo ** lista, Nodo ** corrente, int valore)
{
   /* alloco un nuovo nodo */
   Nodo * nuovo = (Nodo*)malloc(sizeof(Nodo));
   nuovo->valore = valore;
   nuovo->next = NULL;
   nuovo->prev = NULL;

   /* caso speciale del primo nodo */
   if (*lista == NULL) {
      *lista = nuovo;
      *corrente = nuovo;
      return;
   }

   /* taglia e cuci della lista */
   if (*corrente != NULL) {
      nuovo->next = (*corrente)->next;
      nuovo->prev = *corrente;
      (*corrente)->next = nuovo;
      if (nuovo->next != NULL)
         nuovo->next->prev = nuovo;
   }

   /* aggiorno il cursore  */
   *corrente = nuovo;
}

/*
   Elimino il nodo corrente
*/
void del(Nodo ** lista, Nodo ** corrente)
{   
   Nodo * dacancellare = *corrente;
   if (*corrente == NULL) 
      return;

   /* il prossimo nodo (se c'e') diventa il nodo corrente */
   if ((*corrente)->next != NULL)
      *corrente = (*corrente)->next;
   else
      *corrente = (*corrente)->prev;

   /* taglia e cuci della lista */
   if (dacancellare->prev != NULL)
      dacancellare->prev->next = dacancellare->next;
   if (dacancellare->next != NULL)
      dacancellare->next->prev = dacancellare->prev;
   if (*lista == dacancellare)
      *lista = dacancellare->next;

   /* libero la memoria */
   free(dacancellare);
}

/*
   Mi sposto sul nodo precedente
*/
void prev(Nodo ** corrente)
{
   if (*corrente == NULL || (*corrente)->prev == NULL)
      return;
   else
      *corrente = (*corrente)->prev;
}

/*
   Mi sposto sul nodo successivo
*/
void next(Nodo ** corrente)
{
   if (*corrente == NULL || (*corrente)->next == NULL)
      return;
   else
      *corrente = (*corrente)->next;
}

/*
   Stampa della lista
*/
void print(Nodo * lista, Nodo * corrente)
{
   if (lista == NULL) return;
   if (lista == corrente)
      printf("%d *\n",lista->valore);
   else   
      printf("%d\n",lista->valore);
   print(lista->next,corrente);
}

/*
   Mergesort della lista
*/
void sort(Nodo ** lista)
{
   Nodo * pari = NULL;
   Nodo * dispari = NULL;

   /* caso base, 0 o 1 elementi */
   if (*lista == NULL) return;
   if ((*lista)->next == NULL) return;
   
   /* divido la lista in due gruppi di pari dimensioni */
   split(*lista,&pari,&dispari);

   /* ordino le due parti */
   sort(&pari);
   sort(&dispari);

   /* ora che sono ordinate le posso fondere */
   *lista = merge(pari,dispari);
}

/*
   merge distruttivo di due liste doppiamente linkate e ordinate
*/
Nodo * merge(Nodo * L1, Nodo * L2) 
{   
   Nodo * minore = NULL;
   /* casi base */
   if (L1 == NULL) return L2;
   if (L2 == NULL) return L1;
   /* trovo il minore */
   if (L1->valore < L2->valore) {
      minore = L1;
      minore->next = merge(minore->next,L2);
   } else {
      minore = L2;
      minore->next = merge(L1,minore->next);
   }
   /* aggiusto il legame inverso */
   if (minore->next != NULL)
      minore->next->prev = minore;
   /* torno il primo nodo */
   return minore;
}

/*
   divido una lista in due (elementi in posizione pari/dispari)
*/
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari)
{
   /* caso base: nessun elemento */
   if (lista == NULL) {
      *pari = NULL;
      *dispari = NULL;
      return;
   }
   /* se ci sono almeno 2 elementi ricorro saltando i primi due 
      ed ottengo il resto della lista separato in pari e dispari */
   if (lista->next != NULL)
      split(lista->next->next,pari,dispari);

   /* aggiungo i due elementi iniziali a pari e dispari */
   /* prima il secondo (se c'e') */
   if (lista->next != NULL) 
      push(lista->next,dispari);
   /* poi il primo */
   push(lista,pari);
}

void push(Nodo * elemento, Nodo ** lista) 
{
   if (*lista != NULL)
      (*lista)->prev = elemento;
   elemento->next = *lista;
   *lista = elemento;
}

</verbatim>
----

-- Users.AndreaSterbini - 04 Dec 2002

   Set ALLOWTOPICCHANGE = Users.DocentiProg1Group