Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Fusione Liste
Forum - C/C++ - Fusione Liste

Avatar
spaghetto (Normal User)
Newbie


Messaggi: 4
Iscritto: 18/12/2007

Segnala al moderatore
Postato alle 11:31
Sabato, 05/01/2008
Salve ragazzi, sto cercando di fare un esercizio con le liste, soltanto non capisco dove possa essere l' errore...
L' es. consiste nell' unire due liste passate ad una funzione che mi restituisce un puntatore a struttura.

Inoltre NON devo verificare se le liste siano già ordinate.

Ecco qui come ho cercato di svolgere l' esercizio..

allora la struttura è così:

Codice sorgente - presumibilmente C++

  1. struct node {
  2.  
  3.   int inf;
  4.  
  5.   struct node * pun;
  6.  
  7. };
  8.  
  9. typedef struct node node;



e invece la mia funzione è questa...dove sbaglio?

Codice sorgente - presumibilmente C/C++

  1. node * funz(node * l1, node * l2) {
  2.  
  3. node * ptr, * succ, * prec;
  4.  
  5. while(l1!=NULL) {
  6.  
  7. succ=l1->pun;
  8.  
  9. prec=NULL;
  10.  
  11. ptr=l2;
  12.  
  13. while(ptr!=NULL) {
  14.  
  15.   if(ptr->inf >= l1->inf) {
  16.  
  17.     if(prec==NULL) {
  18.  
  19.        l1->pun=ptr;
  20.  
  21.        l2=l1;
  22.  
  23.     }
  24.  
  25.     else {
  26.  
  27.         prec->pun=l1;
  28.  
  29.         l1->pun=ptr;
  30.  
  31.     }
  32.  
  33.   }
  34.  
  35.   prec=ptr;
  36.  
  37.   ptr=ptr->pun;
  38.  
  39.   }
  40.  
  41.   if(succ!=NULL) l1=succ;
  42.  
  43.   else return l2;
  44.  
  45.   }
  46.  
  47. }




Allora quello che cerco di fare è questo:

io ho due liste, l1 ed l2, e l' idea mia è quella di spostare ogni elemento della prima lista nella seconda, in questo modo, mi rimarrebbe diciamo la seconda lista.

Così facendo quando arrivo alla fine ritorno il puntatore alla testa della seconda lista.

Vi ringrazio in anticipo per le risposte!

Ultima modifica effettuata da spaghetto il 05/01/2008 alle 11:37
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 10:54
Lunedì, 14/01/2008
Ma non basterebbe prendere l'ultimo elemento della lista l1, farlo puntare al primo elemento della lista l2 e poi ritornare un puntatore al primo elemento della lista l1?


Il mio blog: https://piero.dev
PM Quote
Avatar
bangirasu (Normal User)
Rookie


Messaggi: 39
Iscritto: 15/08/2007

Segnala al moderatore
Postato alle 14:38
Giovedì, 17/01/2008
Come ha detto piero è la migliore soluzione visto che hai detto che sono già ordinate, inoltre se la lista unita deve essere indipendente dalle altre due ti consiglio di fare una copia della uno e della due e poi fare puntare l'ultimo elemento della 2 al primo elemento della 1.

Ultima modifica effettuata da bangirasu il 17/01/2008 alle 14:38
PM Quote
Avatar
spaghetto (Normal User)
Newbie


Messaggi: 4
Iscritto: 18/12/2007

Segnala al moderatore
Postato alle 18:39
Sabato, 19/01/2008
No ragazzi mi sono spiegato male, l' esercizio consisteva sì nella fusione di due liste, ma ordinate! Devo unirle creando questa liste con gli elementi ordinati...
lo avevo risolto in questo modo...
Specifico che le liste dovevano essere inserite in input con gli elementi ordinati...

Codice sorgente - presumibilmente C/C++

  1. node * funz(node * l1, node * l2) {
  2.   node * ptr, * succ, * prec;
  3.   while(l1!=NULL) {
  4.      succ=l1->pun;
  5.      prec=NULL;
  6.      ptr=l2;
  7.   while(ptr!=NULL) {
  8.     if(ptr->inf >= l1->inf) {
  9.        if(prec==NULL) {
  10.           l1->pun=ptr;
  11.           l2=l1;
  12.           break;
  13.           }
  14.     else {
  15.         l1->pun=ptr;
  16.         prec->pun=l1;
  17.         break;
  18.     }
  19.   }
  20.   else if(ptr->pun== NULL && ptr->inf < l1->inf) {
  21.           ptr->pun=l1;
  22.           l1->pun=NULL;
  23.           break;
  24.          }
  25.   else {  prec=ptr;
  26.          ptr=ptr->pun;
  27.      }
  28. }
  29.   if(succ!=NULL) l1=succ;
  30.   else return l2;
  31.    }
  32. }



:k:

PM Quote
Avatar
bangirasu (Normal User)
Rookie


Messaggi: 39
Iscritto: 15/08/2007

Segnala al moderatore
Postato alle 0:45
Lunedì, 21/01/2008
Ah! adesso ho capito! Ogni lista è ordinata ma gli elementi della prima lista non sono tutti minori di ogni elemento della seconda, cioè bisogna fare una cosa del genere:

Lista 1: 1 5 10 15 20 25
Lista 2: 1 7 8 17 31 33 40
Lista risultato: 1 1 5 7 8 10 15 17 20 25 31 33 40

Modo iterativo:
Codice sorgente - presumibilmente Delphi

  1. List merge (List LL1, List LL2)
  2. {
  3.  
  4. /* per comodita` costruisco LL3 che è il "manico" della lista,
  5.  * poi la restituisco senza manico
  6.  */
  7.  
  8.  List LL3, last, aux;
  9.  
  10.  LL3 = calloc(1, sizeof(struct cella));
  11.  LL3->next= NULL;
  12.  
  13.  last= LL3; /* last punta "sempre" all'ultimo record di LL3 */
  14.  
  15.  while ((LL1 != NULL) && (LL2 !=NULL))
  16.  {
  17.    if ( LL1->cont <= LL2->cont )
  18.    {
  19.     /* copio da LL1 in LL3 */
  20.      aux = calloc(1, sizeof(struct cella));
  21.      aux->cont = LL1->cont;
  22.      aux->next = NULL;
  23.  
  24.      last->next = aux;
  25.      last = aux;
  26.  
  27.      LL1 = LL1->next;
  28.    }
  29.    else
  30.    {
  31.     /* copio da LL2 in LL3; simmetrico al precedente */
  32.      aux = calloc(1, sizeof(struct cella));
  33.      aux->cont = LL2->cont;
  34.      aux->next = NULL;
  35.  
  36.      last->next = aux;
  37.      last = aux;
  38.  
  39.      LL2 = LL2->next;
  40.    }
  41.  
  42.  } /* fine del while */
  43.  
  44. /* a questo punto una delle due liste e` esaurita,
  45.  * ma l'altra no .......
  46. */
  47.  
  48. if (LL1 == NULL)
  49.   while (LL2 != NULL)
  50.   {
  51.     aux = calloc(1, sizeof(struct cella));
  52.     aux->cont = LL2->cont;
  53.     aux->next = NULL;
  54.  
  55.     last->next = aux;
  56.     last = aux;
  57.  
  58.     LL2 = LL2->next;
  59.   }
  60. else
  61.  /* analogo al precedente */
  62.   while (LL1 != NULL)
  63.   {
  64.     aux = calloc(1, sizeof(struct cella));
  65.     aux->cont = LL1->cont;
  66.     aux->next = NULL;
  67.  
  68.     last->next = aux;
  69.     last = aux;
  70.  
  71.     LL1 = LL1->next;
  72.   }
  73.  
  74. return (LL3->next);
  75. /* cosi' restituisco una lista senza "manico" */
  76. }



Non sarebbe male farla ricorsivamente. Nella Rete ho trovato questa soluzione ricorsiva e funzionante:
Codice sorgente - presumibilmente C#

  1. void aux_rec_merge (List LL1, List LL2, List *LL)
  2. {
  3.    int *tcont;
  4.    List TL1 = NULL, TL2 = NULL;
  5.    
  6.    char choice = (LL1 == NULL);
  7.    choice *= 2;
  8.    choice |= (LL2 == NULL);
  9.  
  10.    switch (choice) {
  11.      case 0:
  12.        if (LL1->cont <= LL2->cont) {
  13.          tcont = &(LL1->cont);
  14.          TL1 = LL1->next;
  15.          TL2 = LL2; }
  16.        else {
  17.          tcont = &(LL2->cont);
  18.          TL1 = LL1;
  19.          TL2 = LL2->next; }
  20.        break;
  21.      case 1:
  22.        tcont = &(LL1->cont);
  23.        TL1 = LL1->next;
  24.        TL2 = LL2;
  25.        break;
  26.      case 2:
  27.        tcont = &(LL2->cont);
  28.        TL1 = LL1;
  29.        TL2 = LL2->next;
  30.        break;
  31.      default:
  32.        return; }
  33.    
  34.    (*LL) = calloc(1, sizeof(struct cella));
  35.    (*LL)->cont = *tcont;
  36.    (*LL)->next = NULL;
  37.  
  38.    aux_rec_merge(TL1, TL2, &((*LL)->next));  
  39. }
  40.  
  41. List rec_merge (List LL1, List LL2)
  42. {
  43.   List LL = NULL;
  44.   aux_rec_merge(LL1, LL2, &LL);
  45.  
  46.   return LL;
  47. }



"rec_merge" si appoggia ad una funzione ausiliaria ricorsiva "aux_rec_merge".

La struct Cella è così definita
Codice sorgente - presumibilmente C++

  1. typedef struct { int  cont;
  2.                  List next; } Cella;
  3. typedef  Cella * List;


Ultima modifica effettuata da bangirasu il 21/01/2008 alle 0:47
PM Quote
Avatar
spaghetto (Normal User)
Newbie


Messaggi: 4
Iscritto: 18/12/2007

Segnala al moderatore
Postato alle 14:45
Lunedì, 21/01/2008
Si in effetti la soluzione ricorsiva andrebbe bene!
Solo che non mi so muovere più di tanto!!!
Cmq l' importante è aver risolto il quesito!

PM Quote