[C] - Ordinamento, algoritmo: Merge Sort

[Napoli82]

Ciao a tutti,
il mio problema è che non riesco a scrivere in C una versione dell'algoritmo Merge Sort che lavori su una lista concatenata bidirezionale (doubly linked list).

Le strutture dati che uso sono:

 struct nodo {
 char *parola;
 struct nodo *prec;
 struct nodo *next;
};

struct lista {
 struct nodo *testa;
 struct nodo *coda;
};

Mentre il codice che ho scritto per il Merge Sort è:

struct nodo *Split(struct nodo *n1, struct nodo *padre)
{
 struct nodo *n2 = NULL;
 if((n1 && n1->next) && (n1!=n1->next))
 {
  n2 = n1->next;
  n2->prec = n1->prec;
  n1->prec = padre;
  n1->next = n2->next;
  n2->next = Split(n1->next,n1);
 }
 return n2;
}

struct nodo *Merge(struct nodo *n1,struct nodo *n2)
{
 if(n1 == NULL)
  return n2;
 else
  if (n2 == NULL)
   return n1;
  else
   if(strcmp(n1->parola,n2->parola) < 0)
   {
    n2->prec = n1;
    n1->next = Merge(n1->next,n2);
    return n1;
   }
   else
   {
    n1->prec = n2;
    n2->next = Merge(n1,n2->next);
    return n2;
   }
}

struct lista *MergeSort(struct lista *lis)
{
 struct lista *lis2 = lis;
 if(lis->testa && lis->testa->next)
 {
  lis2->testa = Split(lis->testa,NULL);
  lis = MergeSort(lis);
  lis2 = MergeSort(lis2);
  lis->testa = Merge(lis->testa,lis2->testa);
 }
 return lis;
}

Credo che l'errore sia nel Merge, comunque sapreste indicarmi cosa sbaglio?

Grazie.

[cicciox80]

PORC#@! Il merge (vers. array) lo devo portare lunedì all'esame di algoritmi avanzati (con tutte le analisi di complessità asintotica, di spazio etc.)

Se hai un po' di pazienza (e se nessuno ha ancora risposto) quando torno lunedì ti invio la risposta (ci devo pensare)

[Napoli82]

mi faresti un gran favore visto che non ho avuto altre risp...

Grazie e in bocca al lupo x l'esame.

[cicciox80]

L'esame l'ho fatto stamattina, c'erano un bel po' di persone così il prof. ci ha divisi, cmq ho preso 27, il professore è stato un po' tirchio

Sto ora leggendo l'algoritmo del mergesort su lista: non capisco in quale maniera dovrebbe funzionare l'algoritmo di splitting... se faccio delle prove su carta mi ritrovo un qualcosa che non è più una lista, forse è qui che non va qualcosa; dammi una descrizione informale di cosa dovrebbe fare la function split

[bstefano79]

struct lista *MergeSort(struct lista *lis)
{
struct lista *lis2 = lis;
if(lis->testa && lis->testa->next)
.............


cosa succede se chiami MargeSort(NULL)?
lis->testa non esiste

[Napoli82]

Split divede la lista in due liste, una con gli elementi di posto dispari della lista di partenza ed una con gli elementi di posto pari.

Cmq ho risolto così

struct lista *Split(struct lista *n1)
{
 struct lista *n2;
 struct nodo *testa1 = n1->testa, *testa2, *appoggio = NULL;
 n2 = (struct lista *)malloc(sizeof(struct lista));
 if(n1->testa && n1->testa->next)
  testa2 =  n1->testa->next;
 do
 {
  n2->testa = n1->testa->next;
  n2->testa->prec = n1->testa->prec;
  n1->testa->next =n2->testa->next;
  n1->testa->prec = appoggio;
  appoggio = n1->testa;
  n1->testa = n1->testa->next;
  if(n1->testa)
  {
   n2->testa->next = n1->testa->next;
   if(!n2->testa->next)
    n1->testa->prec = appoggio;
  }
 }while(n2->testa->next);
 n1->testa = testa1;
 n2->testa = testa2;
 return n2;
}

struct nodo *Merge(struct nodo *n1,struct nodo *n2)
{
 struct nodo *uscita;
 if(n1 == NULL)
  uscita = n2;
 else
  if(n2 == NULL)
   uscita = n1;
  else
   if(strcmp(n1->parola,n2->parola) < 0)
   {
    n2->prec = n1;
    n1->next = Merge(n1->next,n2);
    uscita = n1;
   }
   else
   {
    n1->prec = n2;
    n2->next = Merge(n1,n2->next);
    uscita = n2;
   }
 return uscita;
}

struct lista *MergeSort(struct lista *lis)
{
 struct lista *lis2;
 if(lis->testa && lis->testa->next)
 {
  lis2 = Split(lis);
  lis = MergeSort(lis);
  lis2 = MergeSort(lis2);
  lis->testa = Merge(lis->testa,lis2->testa);
 }
 return lis;
}

Grazie lo stesso x l'interessamento, ciao