PDA

Visualizza la versione completa : [C] - Ordinamento, algoritmo: Merge Sort


Napoli82
28-02-2004, 14:41
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
28-02-2004, 20:43
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
29-02-2004, 10:49
mi faresti un gran favore visto che non ho avuto altre risp...

Grazie e in bocca al lupo x l'esame. :ciauz:

cicciox80
04-03-2004, 12:29
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 :dhò:

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

bstefano79
04-03-2004, 13:26
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
04-03-2004, 19:10
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 :ciauz:

Loading