[C] Esercizio su liste

[nixonik]

salve, visto che domani ho un esame, qualcuno sarebbe così gentile da dirmi come si fa in C questo esercizio?
E' un esercizio vecchio, vorrei solo capire come vanno modificati i puntatori perchè non capisco.

Scrivere una funzione C:
lista alternaListaPlace (lista L, lista M)
che restituisce una lista in cui i nodi di L sono alternati con quelli di M. Eseguire l'operazione
senza allocare nuova memoria, ma semplicemente spostando i puntatori. Se una delle due liste è più
corta dell'altra, la coda della più lunga viene semplicemente attaccata in fondo. Restituire come
risultato un puntatore alla testa della lista alternata.

[stdecden]

Cosa intendi per lista alternata

lista1 = [1 3 5 7 9]
lista2 = [2 4 6 8]
listaAlt = [1 2 3 4 5 6 7 8 9]

[nixonik]

esatto....come dice senza allocare nuova memoria, ma soltanto modificando i puntatori..

[AnonimoVeneziano]

Tra le regole del forum ce n'è una che dice : "Non si risolvono esercizi completi di scuola o università" .

Posta una tua soluzione (probabilmente sbagliata) e poi noi la correggiamo

Ciao

[AnonimoVeneziano]

Ah, cambia il titolo del thread in "[C] Esercizio su liste" il prima possibile , altrimenti appena arriva cionci te lo chiude :/

[nixonik]

lo so, ma io non ho idea di come si faccia...avevo fatto qualcosa del genere

slistptr alternalista (slistptr L, slistptr M)
{
         slistptr alternata;
         int c=1;
         
         while ((L!=NULL)||(M!=NULL))
          {
            if (c%2==0){
              alternata->str=M->str;
              M=M->next;}
            else{
              alternata->str=L->str;
              L=L->next;}
            c++;
            alternata=alternata->next;
          }
         while (alternata!=NULL)
     {
      printf("%d -> ",alternata->str);
      alternata=alternata->next;
     }}

ma è completamente sbagliata...uno perchè credo che facendo così c'è bisogno di allocare memoria...e io devo modificare solo i puntatori...
ILLUMINATEMI
non devo consegnare l'esercizio, è solo che domani ho l'esame e vorrei capirci meglio

[AnonimoVeneziano]

Prova questa versione.

Non ti assicuro che funzioni perchè non ho potuto provarla (su sto PC non ho un compilatore C purtroppo) . E' una versione ricorsiva. Distrugge entrambe le liste (E' l'unico modo di fare se non ne vuoi allocare un altra) e ne crea un altra che è la concatenazione delle due nel modo richiesto (in teoria )

slistptr alternaListe(slistptr L, slistptr M) {
  if (L == NULL)
    return M;
  if (M == NULL)
    return L;
  L->next = alternaListe(M, L->next);

  return L;
}

Fammi sapere se funziona

Ciao

[nixonik]

Funziona
non passerò mai questo esame
Grazie cmq

Mi spiegheresti com'è che fa a funzionare però? O.o

diciamo che se la L è vuota ritorna M e se M è vuota ritorna L..fin qui ok....
poi non capisco l'assegnazione..nel secondo elemento di L mette...?? come funziona? :S

[AnonimoVeneziano]

Eh, le funzioni ricorsive possono essere un po' criptiche

La funzione spezzetta il problema in parti sempre più semplici (ad ogni chiamata di funzione) fino a raggiungere il momento in cui il problema è talmente semplice da essere risolvibile con una (o poco più) istruzione.

Il metodo di "spezzettamento" è richiamare la funzione "alternaListe()" invertendo i suoi parametri (cioè facendo diventare nella successiva chiamata quella che correntemente è M la L e quella che adesso è L->next la M della nuova chiamata).

Questo procedimento di inversione inquadra perfettamente il problema originale che è "alternare" gli elementi all'interno delle liste, infatti, se noti , la lista che nella prima chiamata è L nella seconda diventa M per poi tornare L nella terza chiamata. In pratica si alternano, esattamente come deve succedere per gli elementi della lista finale. Inoltre con il L->next piano piano si avanza nella lista elemento per elemento arrivando infine a NULL (quando una delle due liste sarà stata completamente iterata).


A questo punto il lavoro della funzione è terminate e ritorna l'altra lista che non è NULL come ultimo elemento della nuova lista (o se le liste hanno la stessa lunghezza ritorna comunque NULL).


Putroppo spiegare il funzionamento di una funzione ricorsiva senza un appoggio grafico è tosta. Ti consiglio di farti uno schizzetto su carta segnandoti i valori delle variabili tra le varie chiamate di funzioni per due liste relativamente corte (2 o 3 elementi)

Ciao

[nixonik]

ci proverò...
grazie mille per il tuo tempo