Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - AIUTO!!! MERGESORT SU LISTE!
Forum - C/C++ - AIUTO!!! MERGESORT SU LISTE!

Avatar
Ghost_M91W (Ex-Member)
Newbie


Messaggi: 5
Iscritto: 10/05/2011

Segnala al moderatore
Postato alle 22:02
Martedì, 07/06/2011
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!
Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>//Per la random
  4.  
  5. /* definizione della struttura del nodo */
  6. typedef struct nodo {int valore;
  7.                      struct nodo * next;
  8.                      //struct nodo * prev;
  9.                     } Nodo ;
  10.  
  11. //Gestione di una lista doppiamente concatenata:
  12.   void add(Nodo ** lista, Nodo ** corrente, int valore);//aggiunge un nodo subito dopo il nodo corrente
  13.   void print(Nodo * lista);//stampa la lista
  14.  
  15.  //Per ordinare la lista
  16.   void sort(Nodo ** lista);//ordina la lista con merge-sort
  17.   Nodo * merge(Nodo * L1, Nodo * L2);
  18.   void split(Nodo * lista, Nodo ** pari, Nodo ** dispari);
  19.   void push(Nodo * lista, Nodo ** elemento);
  20.  
  21. void main()
  22. {
  23.  Nodo * lista   = NULL;//Definisce la lista
  24.  Nodo * corrente = NULL; //Nodo corrente acquisito
  25.  int i, a[10], n=10;
  26.  
  27.  //Genera un vettore casuale numeri da 1 a 50 random
  28.  srand((unsigned int)time(0));//Genero un seed per la creazione dell'array
  29.  for (i=0;i<=n-1;i++) a[i]=rand()%51; //Creo l'array
  30.  //Genero una lista a partire dall'array
  31.  for (i=0;i<=n-1;i++) add(&lista, &corrente, a[i]);
  32.  printf("--------------------------------------------------\n");
  33.  printf(" Applicazione dell'algoritmo MERGE-SORT a una li-\n");
  34.  printf(" sta doppiamente concatenata\n");
  35.  printf("--------------------------------------------------\n");
  36.  printf(" Verra' generata una lista casuale da ordinare:\n\n");
  37.  printf("           LISTA GENERATA DISORDINATA\n\n    ");
  38.  if (lista != NULL)print(lista);
  39.  else printf("vuota\n");
  40.  printf("\n--------------------------------------------------\n");
  41.  printf(" Chiamata alla function MERGESORT:\n\n");
  42.  printf("           LISTA ORDINATA CON MERGESORT:\n\n    ");
  43.  //ORDINA LA LISTA
  44.  if (lista != NULL)     sort(&lista);
  45.  else printf("vuota\n");
  46.  //STAMPA LA LISTA ORDINATA
  47.  if (lista != NULL)print(lista);
  48.  else printf("vuota\n");
  49.  printf("\n--------------------------------------------------\n");
  50.  system("PAUSE");
  51. }
  52.  
  53.  
  54. //      Aggiunge un nuovo nodo alla lista di dato VALORE
  55. // subito dopo il nodo CORRENTE
  56. void add(Nodo ** lista, Nodo ** corrente, int valore)
  57. {
  58.  //alloco memoria per il nodo da inserire
  59.  Nodo *nuovo = calloc(1,sizeof(Nodo));
  60.  //copio le informazioni nel nuovo nodo
  61.  nuovo->valore = valore;
  62.         //nel caso in cui il valore sia il primo nodo, lo faccio puntare da *lista
  63.  if (*lista == NULL) {*lista = nuovo;
  64.                       *corrente = nuovo;
  65.                       return;
  66.                      }
  67.  
  68.  //collego il nuovo nodo a quello successivo e a quello precedente
  69.  if (*corrente != NULL) {nuovo->next = (*corrente)->next; //nuovo a successivo
  70.                         // nuovo->prev = *corrente; //nuovo a precedente
  71.                          (*corrente)->next = nuovo; //faccio puntare nodo dal precedente
  72.                      //    if (nuovo->next != NULL) //se il successivo esiste
  73. //                         nuovo->next->prev = nuovo; //faccio puntare nodo dal successivo
  74.                         }
  75.  //visto che devo aggiungere in coda, collego il puntatore corrente all'ultimo nodo aggiunto
  76.  //in modo da averlo già in posizione
  77.  *corrente = nuovo;
  78. }
  79.  
  80. //Stampa della lista RICORSIVA
  81. void print(Nodo * lista)
  82. {if (lista == NULL) return;//ISTANZA BANALE [Lista vuota]
  83.  
  84.  printf("%3d ",lista->valore);//Stampa elemento
  85.  print(lista->next);//Chiamata ricorsiva passandogli il successivo
  86. }
  87.  
  88. //funzione principale [MERGESORT] che chiamerà le funzioni [SPLIT] e [MERGE]
  89. //le function sono tutte e tre RICORSIVE
  90. void sort(Nodo ** lista)
  91. {//queste sono le teste delle sottoliste da ricavare dalla lista in input
  92.  Nodo * pari = NULL;
  93.  Nodo * dispari = NULL;
  94.  //una lista di 1 solo elemento è già ordinata
  95.  // ISTANZA BANALE, 0 o 1 elementi
  96.  if (*lista == NULL) return;
  97.  if ((*lista)->next == NULL) return;
  98.  //una lista di 2 o più elementi si ordina eseguendo:
  99.  
  100.  //divido la lista in due liste minori di pari dimensioni
  101.  split(*lista,&pari,&dispari);
  102.  //AUTOATTIVAZIONI
  103.  //viene chiamata di nuovo la function sort per entrambe le liste appena generate
  104.  sort(&pari);//CHIAMATA RICORSIVA 1
  105.  sort(&dispari);//CHIAMATA RICORSIVA 2
  106.  
  107.  //fondo le liste a due a due a partire dall'istanza banale
  108.  *lista = merge(pari,dispari);
  109.  printf("Ok\n");
  110. }
  111.  
  112.  
  113. //      merge di due liste doppiamente linkate e ordinate
  114. Nodo * merge(Nodo * L1, Nodo * L2)
  115. {Nodo * minore = NULL;
  116.  //SE una delle due liste è vuota (NULL)
  117.  //il risultato è l'altra lista
  118.  //ISTANZA BANALE
  119.  if (L1 == NULL) return L2;
  120.  if (L2 == NULL) return L1;
  121.  //ALTRIMENTI confronto i primi elementi L1 e L2 delle due liste
  122.  if (L1->valore < L2->valore) {minore = L1;//L1 è primo elemento della lista risultante
  123.                                //AUTOATTIVAZIONE
  124.                                minore->next = merge(minore->next,L2);//collego il successivo del nodo minore
  125.                                //a chiamata ricorsiva con l'altra lista
  126.                               }
  127.  else { minore = L2;//L2 è primo elemento della lista risultante
  128.         minore->next = merge(L1,minore->next);//idem come sopra
  129.       }
  130.  //terminate le autoattivazioni, genero il legame inverso
  131.  // if (minore->next != NULL) minore->next->prev = minore;
  132.  
  133.  //restituisco la lista fusa [che ovviamente parte da minore]
  134.  printf("OK\n");
  135.  return minore;
  136. }
  137.  
  138.  
  139. //      divide una lista in due (elementi in posizione pari/dispari)
  140. void split(Nodo * lista, Nodo ** pari, Nodo ** dispari)
  141. {
  142.  //CASO BANALE: la lista è vuota
  143.  if (lista == NULL) {*pari = NULL;
  144.                      *dispari = NULL;
  145.                      return;
  146.                     }
  147.  //se ci sono almeno 2 elementi: CHIAMATA RICORSIVA saltando i primi due
  148.  //AUTOATTIVAZIONE
  149.  if (lista->next != NULL) split(lista->next->next,pari,dispari);
  150.  
  151.  //Aggiungo in testa prima il secondo (se c'e') alla semilista dispari
  152.  if (lista->next != NULL)push(lista->next,dispari);
  153.  //poi aggiungo il primo in testa alla lista pari (deve esservi per forza un nodo)
  154.  if(lista!=NULL) push(lista,pari);
  155.  printf("OOOK\n");
  156. }
  157.  
  158.  
  159. void push(Nodo * lista, Nodo ** elemento)
  160. {//Se l'elemento non è vuoto
  161.  if (*elemento != NULL)
  162.  //Il precendete di elemento è la lista
  163. // (*elemento)->prev = lista;
  164.  //il prossimo di lista è l'elemento
  165.  lista->next = *elemento;
  166.  *elemento = lista; //elemento è la nuova testa
  167. }



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

PM Quote