Oppure

Loading
07/06/11 20:02
Ghost_M91W
Per favore ho bisogno di una mano, in pratica ho questo algoritmo che funziona per le liste doppiamente concatenate, ma devo modificarlo per le liste lineari. Sembrerebbe una scemenza, infatti non riesco a spiegarmi il motivo ma pare che se la lista non è concatenata va in crash per overflow ricorsivo... vi posto il codice, non ho cancellato gli aspetti che ne fanno una lista concatenata ma li ho solo oscurati... non riesco a capire HELP!
#include <stdio.h>
#include <stdlib.h>
#include <time.h>//Per la random

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

//Gestione di una lista doppiamente concatenata:
  void add(Nodo ** lista, Nodo ** corrente, int valore);//aggiunge un nodo subito dopo il nodo corrente
  void print(Nodo * lista);//stampa la lista

 //Per ordinare la lista
  void sort(Nodo ** lista);//ordina la lista con merge-sort
  Nodo * merge(Nodo * L1, Nodo * L2);
  void split(Nodo * lista, Nodo ** pari, Nodo ** dispari);
  void push(Nodo * lista, Nodo ** elemento);

void main()
{
 Nodo * lista	= NULL;//Definisce la lista
 Nodo * corrente = NULL; //Nodo corrente acquisito
 int i, a[10], n=10;

 //Genera un vettore casuale numeri da 1 a 50 random
 srand((unsigned int)time(0));//Genero un seed per la creazione dell'array
 for (i=0;i<=n-1;i++) a[i]=rand()%51; //Creo l'array
 //Genero una lista a partire dall'array
 for (i=0;i<=n-1;i++) add(&lista, &corrente, a[i]);
 printf("--------------------------------------------------\n");
 printf(" Applicazione dell'algoritmo MERGE-SORT a una li-\n");
 printf(" sta doppiamente concatenata\n");
 printf("--------------------------------------------------\n");
 printf(" Verra' generata una lista casuale da ordinare:\n\n");
 printf("           LISTA GENERATA DISORDINATA\n\n    ");
 if (lista != NULL)print(lista);
 else printf("vuota\n");
 printf("\n--------------------------------------------------\n");
 printf(" Chiamata alla function MERGESORT:\n\n");
 printf("           LISTA ORDINATA CON MERGESORT:\n\n    ");
 //ORDINA LA LISTA
 if (lista != NULL)	sort(&lista);
 else printf("vuota\n");
 //STAMPA LA LISTA ORDINATA
 if (lista != NULL)print(lista);
 else printf("vuota\n");
 printf("\n--------------------------------------------------\n");
 system("PAUSE");
}


//	Aggiunge un nuovo nodo alla lista di dato VALORE
// subito dopo il nodo CORRENTE
void add(Nodo ** lista, Nodo ** corrente, int valore)
{
 //alloco memoria per il nodo da inserire
 Nodo *nuovo = calloc(1,sizeof(Nodo));
 //copio le informazioni nel nuovo nodo
 nuovo->valore = valore;
	//nel caso in cui il valore sia il primo nodo, lo faccio puntare da *lista
 if (*lista == NULL) {*lista = nuovo;
                      *corrente = nuovo;
                      return;
                     }

 //collego il nuovo nodo a quello successivo e a quello precedente
 if (*corrente != NULL) {nuovo->next = (*corrente)->next; //nuovo a successivo
                        // nuovo->prev = *corrente; //nuovo a precedente
                         (*corrente)->next = nuovo; //faccio puntare nodo dal precedente
                     //    if (nuovo->next != NULL) //se il successivo esiste
//                         nuovo->next->prev = nuovo; //faccio puntare nodo dal successivo
                        }
 //visto che devo aggiungere in coda, collego il puntatore corrente all'ultimo nodo aggiunto
 //in modo da averlo già in posizione
 *corrente = nuovo;
}

//Stampa della lista RICORSIVA
void print(Nodo * lista)
{if (lista == NULL) return;//ISTANZA BANALE [Lista vuota]

 printf("%3d ",lista->valore);//Stampa elemento
 print(lista->next);//Chiamata ricorsiva passandogli il successivo
}

//funzione principale [MERGESORT] che chiamerà le funzioni [SPLIT] e [MERGE]
//le function sono tutte e tre RICORSIVE
void sort(Nodo ** lista)
{//queste sono le teste delle sottoliste da ricavare dalla lista in input
 Nodo * pari = NULL;
 Nodo * dispari = NULL;
 //una lista di 1 solo elemento è già ordinata
 // ISTANZA BANALE, 0 o 1 elementi
 if (*lista == NULL) return;
 if ((*lista)->next == NULL) return;
 //una lista di 2 o più elementi si ordina eseguendo:

 //divido la lista in due liste minori di pari dimensioni
 split(*lista,&pari,&dispari);
 //AUTOATTIVAZIONI
 //viene chiamata di nuovo la function sort per entrambe le liste appena generate
 sort(&pari);//CHIAMATA RICORSIVA 1
 sort(&dispari);//CHIAMATA RICORSIVA 2

 //fondo le liste a due a due a partire dall'istanza banale
 *lista = merge(pari,dispari);
 printf("Ok\n");
}


//	merge di due liste doppiamente linkate e ordinate
Nodo * merge(Nodo * L1, Nodo * L2)
{Nodo * minore = NULL;
 //SE una delle due liste è vuota (NULL)
 //il risultato è l'altra lista
 //ISTANZA BANALE
 if (L1 == NULL) return L2;
 if (L2 == NULL) return L1;
 //ALTRIMENTI confronto i primi elementi L1 e L2 delle due liste
 if (L1->valore < L2->valore) {minore = L1;//L1 è primo elemento della lista risultante
                               //AUTOATTIVAZIONE
                               minore->next = merge(minore->next,L2);//collego il successivo del nodo minore
                               //a chiamata ricorsiva con l'altra lista
                              }
 else { minore = L2;//L2 è primo elemento della lista risultante
        minore->next = merge(L1,minore->next);//idem come sopra
      }
 //terminate le autoattivazioni, genero il legame inverso
 // if (minore->next != NULL) minore->next->prev = minore;

 //restituisco la lista fusa [che ovviamente parte da minore]
 printf("OK\n");
 return minore;
}


//	divide una lista in due (elementi in posizione pari/dispari)
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari)
{
 //CASO BANALE: la lista è vuota
 if (lista == NULL) {*pari = NULL;
                     *dispari = NULL;
                     return;
                    }
 //se ci sono almeno 2 elementi: CHIAMATA RICORSIVA saltando i primi due
 //AUTOATTIVAZIONE
 if (lista->next != NULL) split(lista->next->next,pari,dispari);

 //Aggiungo in testa prima il secondo (se c'e') alla semilista dispari
 if (lista->next != NULL)push(lista->next,dispari);
 //poi aggiungo il primo in testa alla lista pari (deve esservi per forza un nodo)
 if(lista!=NULL) push(lista,pari);
 printf("OOOK\n");
}


void push(Nodo * lista, Nodo ** elemento)
{//Se l'elemento non è vuoto
 if (*elemento != NULL)
 //Il precendete di elemento è la lista
// (*elemento)->prev = lista;
 //il prossimo di lista è l'elemento
 lista->next = *elemento;
 *elemento = lista; //elemento è la nuova testa
}


Vi ringrazio in anticipo ma la questione è seria...
aaa