Verificare se h2 è sottolista di h1

[Starise]

Devo risolvere il problema di verificare se una lista data h2 è sottolista di un altra lista data, di nome h1.

Le liste con due campi - h1.info : integer e h1.next : link

Intuitivamente ho scritto la seguente soluzione ricorsiva:

....

function sottolista(h1, h2) : boolean

if ( h1 != NULL ) && ( h2 != NULL )
{
     if ( h1.info !=  h2.info ) {
         sottolista (h1, h2.next);
     }else{
         sottolista (h1.next, h2.next);
     }
} else if (h2 == NULL) {
     sottolista = TRUE;
} else {
     sottolista = FALSE;
}

Però com'è facile notare, se:

h1 = 2 -> 0 -> 10 -> 1
h2 = 2 -> 10 -> 1

la funzione restituisce TRUE, mentre il risultato atteso, sarebbe FALSE. L'idea sarebbe di mettere una variabile nell'implementazione che appena h1.info = h2.info, diventa 1, e se successivamente resta cosi; ma se viene trovato che h1.info != h2.info prima che h2 sia NULL, allora diventa 0 e fa fallire il controllo successivo restutuendo FALSE.

Però oltre a essere una pessima soluzione, a quanto ho capito la function deve avere in input solo le due liste e maneggiare quelle, senza l'utilizzo di altre variabili...

Consigli?

[andbin]

Originariamente inviato da Starise

Devo risolvere il problema di verificare se una lista data h2 è sottolista di un altra lista data, di nome h1.

Le liste con due campi - h1.info : integer e h1.next : link

Innanzitutto per "sottolista" intendi che la sequenza di informazioni contenuta nella lista h2 si trova, a partire da un certo punto, nella lista h1?? Io ho capito questo comunque.

Le funzioni ricorsive vanno bene solo per risolvere certi tipi di problemi. Io personalmente parlando, eviterei di usare una funzione ricorsiva per fare un controllo di questo tipo.

Visto che non hai specificato il linguaggio (e il pezzo di codice che hai scritto in che linguaggio è??? ) ti posto una possibile soluzione in linguaggio "C":

int sottolista (LISTA *h1, LISTA *h2)
{
    LISTA *h1_save, *h2_orig = h2;

    while (h1 != NULL)
    {
        h1_save = h1;
        h2 = h2_orig;

        while (h1 != NULL && h2 != NULL)
        {
            if (h1->info != h2->info)
                break;
            if (h2->next == NULL)
                return TRUE;

            h1 = h1->next;
            h2 = h2->next;
        }

        h1 = h1_save->next;
    }

    return FALSE;
}

Non l'ho provato ... quindi non mi assumo responsabilità.

EDIT: ulteriore correzione al sorgente.

[Black imp]

il programma sopra ha un errore: non contempla che gli ultimi elementi della lista 1 siano uguali ai primi della lista 2 e che quindi h1 vada a leggere fuori dalla lista.

#include <stddef.h>

typedef struct LISTA
{
	int info;
	struct LISTA* next;
} LISTA;


int sottoLista( LISTA* l1, LISTA* l2)
{
  LISTA* p1,*p1copy,*p2,*p2copy;
  p1=l1;          
  p2=l2;
  // p2 e p1 sono pleonastici ma così l1 e l2 continuano a puntare alla testa delle rispettive liste

  while(p1!=NULL)
  {
     if (p1->info==p2->info)
     {
        p1copy=p1;
        p2copy=p2;
        while ((p1copy!=NULL)&&(p2copy!=NULL)&&(p1copy->info==p2copy->info))
        {
           p1copy=p1copy->next;
           p2copy=p2copy->next;
        }
        if (p2copy==NULL)
            return 1;
     }
        p1=p1->next;
  }
  return 0;
}

compilato 0 errori

[Starise]

Originariamente inviato da andbin

Visto che non hai specificato il linguaggio (e il pezzo di codice che hai scritto in che linguaggio è??? )

Nessuno! Pseudolinguaggio... siccome il mio prof. dell'uni ci fa fare esercizi in plike, però io mi trovo a scrivere in Clike... ehehehe viene fuori un "merge" dei due terrificante.

Originariamente inviato da andbin

Le funzioni ricorsive vanno bene solo per risolvere certi tipi di problemi. Io personalmente parlando, eviterei di usare una funzione ricorsiva per fare un controllo di questo tipo.

Si, onestamente lo penso anch'io. Iterativamente anch'io avevo sviluppato una mezza soluzione, il problema è che l'esercizio impone l'utilizzo della ricorsione...

[Black imp]

ho aggiunto il return 0 al mio codice.

[Starise]

Originariamente inviato da Black imp

ho aggiunto il return 0 al mio codice.

Adesso è tardi.. ma domani cerco di ricavarne una f ricorsiva.
grazie per la disponibilità

[andbin]

Originariamente inviato da Black imp

il programma sopra ha un errore: non contempla che gli ultimi elementi della lista 1 siano uguali ai primi della lista 2 e che quindi h1 vada a leggere fuori dalla lista.

Sì ... è vero mi era sfuggito quel caso (l'ho detto che non l'ho provato ). Ho quindi semplicemente aggiunto il test di h1 nel secondo while. Così dovrebbe andare. Grazie della segnalazione.


@Starise:
Ok, ora ho capito perché hai usato la ricorsione ... però non ho alcuna voglia di provare a scrivere la funzione con la ricorsione. Non ce l'ho con te .... ma con chi inventa e propone questi esercizi del kaiser che non servono proprio a una mazza.

[Starise]

Originariamente inviato da andbin

@Starise:
Ok, ora ho capito perché hai usato la ricorsione ... però non ho alcuna voglia di provare a scrivere la funzione con la ricorsione. Non ce l'ho con te .... ma con chi inventa e propone questi esercizi del kaiser che non servono proprio a una mazza.

A chi lo dici!
Adesso sto provando una soluzione ricorsiva, ma, sarà che non c'ho la testa... però non riesco a farne una corretta.. o meglio, farne una corretta usando come parametri in ingresso solo le teste della liste...! Cavolo, ma ci vuole per forza un appoggio, una variabile di stato, qualcosa.... uff...

Cioè, ricorsivamente, quando vado a fare un controllo su h1.info e h2.info, quando risultano uguali, io DEVO conoscere se già precedentemente è stato trovato qualche elemento uguale... ma come faccio a dirlo alla successiva chiamata? Non lo so... forse mi sto solo complicando la vita... adesso smetto, fra poco vado a mensa, poi torno a lavorarci su.... lo so che è un es. del KAISER, ma devo trovare una soluzione!

[Black imp]

ah scusa ho capito adesso che eri obbligato a usare una funzione ricorsiva. guarda che è uno scherzetto: non puoi risolverlo facendo il confronto tramite ricorsione perchè tu devi sempre avere la testa di h2. allora non fai altro che
[EDIT]... cerchi ricorsivamente scandendo h1 il primo elemento uguale al primo di h2 e quando lo trovi fai il confronto iterativo. guarda che NON E' POSSIBILE fare altrimenti a meno che il primo elemento uguale di h1 debba per forza essere il primo della lista. allora è una cazzata. ma se la sottolista può trovarsi in mezzo alla prima lista non puoi non usare una iterazione su h2 perchè se no perdi la testa della lista.

funzione(const LISTA * h1, const LISTA * h2)
{ 
   LISTA * l1,l2;
   l1=h1;
   l2=h2;
   if (h1==NULL)
     return false;
   if (h1->info==h2->info)
   {
      for(;(h1=!NULL)&&(h2!=NULL)&&(h1->info==h2->info);)
      {
         h1=h1->next;
         h2=h2->next;
      }
      if (h2==NULL)
        return true;
 
   }
           // non abbiamo trovato ancora il primo elemento uguale o la sottostringa
    return funzione(l1->next,l2);    // ricorsione su h1
}

[Starise]

La tua soluzione è buona, ma non considera il caso in cui:

h1 = 1 -> 2 -> 3 -> 1 -> 2 -> 4

h2 = 1 -> 2 -> 4

La tua funzione una volta trovato un elemento uguale scorre fin quando un elemento non è diverso, o una delle liste è NULL, poi ritorna un valore. Tuttavia, come vedi nell'esempio che ho fatto sopra, più avanti, in h1 potrebbe esserci una esatta corrispondenza di elementi di h2, e quindi il risultato atteso è TRUE, mentre la tua funzione restituisce immediatamente FALSE.

E' un casino sta cosa... perchè c'è bisogno, una volta completato il while, di restituire TRUE, oppure continuare a valutare la situazione finchè h1 = NULL.

Nel frattempo ho scritto questa: (scusate se uso una notazione pLike ma purtroppo gli esercizi devo farli in questa maniera; questo significa che oltre a non poterla provre, se non a mente, non posso usare break; oppure return che sono istruzioni del C. Sarebbe stato più facile.. )

function sottolista (h1,h2) : boolean
...
if ( h1 != NULL ) then
    if ( h1.info != h2.info ) then
       sottolista ( h1.next, h2 )
    else /* h1.info e h2.info sono uguali */
        h1_temp = h1
        h2_temp = h2
        while ( h1_temp != NULL ) AND ( h2_temp != NULL ) AND ( h1_temp.info = h2_temp.info ) do
             h1_temp = h1_temp.next
             h2_temp = h2_temp.next
             if( h2_temp = NULL ) then
                 sottolista = TRUE;
             else
                 sottolista ( h1.next, h2 )
             endif
        endwhile
    endif
else /* h1 è diventato NULL */
       sottolista = FALSE
endif
...
end function

[Black imp]

sì ho sbagliato. il primo return false va tolto. il secondo va lasciato ma va tolto l'else. adesso è giusto.

correggo il codice...

ho anche aggiunto una variabile che memorizza h1.

[Black imp]

sto leggendo il tuo. la chiusura del while è sbagliata. deve finire dopo i due assegnamenti prima dell'if. e poi non hai salvato il valore di h1 quindi ricorri dopo il while, se la sottolista non è stata trovata, passando un elemento della lista che non è il successivo di quello che stavi esaminando all'inizio.

una cosa, fai attenzione anche nello pseudocodice ad abituarti a differenziare quando stai assegnando un valore e quando lo stai confrontando. nel primo caso usi '=' o ':=' nel secondo usa '=='. altrimenti se in C scrivi if(a=2) anzichè if(a==2) ti darà sempre true!

[Starise]

Beh, cosa dire, adesso la tua soluzione sembra perfetta e funzionante in ogni caso!! Sai, mi spiace di averti fatto perdere tanto tempo, ma ancora trovo ostico l'approccio corretto a utilizzare dei metodi ricorsivi, soprattutto in questo tipo di esercizi.

Mi fa rabbia che poi non era tanto difficile... mi sono "inceppato" per delle stupidate e questo mi fa rabbia! Spero di trovare in rete (perchè sul mio libro sono praticamente inesistenti) delle risorse e degli esercizi su questa tipologia di problemi... mi sa che passerò il resto di luglio a studiare!!!

Comunque mi sei stato davvero di grandissimo aiuto! Grazie e ancora grazie!

[Starise]

Originariamente inviato da Black imp

una cosa, fai attenzione anche nello pseudocodice ad abituarti a differenziare quando stai assegnando un valore e quando lo stai confrontando. nel primo caso usi '=' o ':=' nel secondo usa '=='. altrimenti se in C scrivi if(a=2) anzichè if(a==2) ti darà sempre true!

Lo so! E' un mio difetto che devo togliere!
Grazie per il consiglio, ne farò tesoro!

[Black imp]

Originariamente inviato da Starise

Beh, cosa dire, adesso la tua soluzione sembra perfetta e funzionante in ogni caso!! Sai, mi spiace di averti fatto perdere tanto tempo, ma ancora trovo ostico l'approccio corretto a utilizzare dei metodi ricorsivi, soprattutto in questo tipo di esercizi.

Mi fa rabbia che poi non era tanto difficile... mi sono "inceppato" per delle stupidate e questo mi fa rabbia! Spero di trovare in rete (perchè sul mio libro sono praticamente inesistenti) delle risorse e degli esercizi su questa tipologia di problemi... mi sa che passerò il resto di luglio a studiare!!!

Comunque mi sei stato davvero di grandissimo aiuto! Grazie e ancora grazie!

figurati è stato un piacere almeno mi sono distratto dalla pallosissima documentazione che sto facendo per l'ultimo elaborato della mia vita - poi c'è la tesi... -. non affliggerti per due ragioni: 1 la ricorsione non è inizialmente intuitiva, è un modello di pensiero frattale cui non siamo abituati. 2 questa ricorsione è ingannevole pretestuosa perchè in realtà il confronto non puoi farlo per ricorsione ma per iterazione e utilizzi la ricorsione al posto di un ciclo esterno che scorra h1 quindi è del tutto pleonastica. ci sono problemi di ricorsione vera che non hanno bisogno di tenere traccia di alcunchè tra una chiamata e l'altra come l'esplorazione di un albero.

ecco se cerchi esempi di ricorsione cerca codice sugli alberi, vedrai che si fa quasi tutto per ricorsione. in bocca al lupo!

[Starise]

Originariamente inviato da Black imp

....non affliggerti per due ragioni: 1 la ricorsione non è inizialmente intuitiva, è un modello di pensiero frattale cui non siamo abituati. 2 questa ricorsione è ingannevole pretestuosa [cut]....
ci sono problemi di ricorsione vera che non hanno bisogno di tenere traccia di alcunchè tra una chiamata e l'altra come l'esplorazione di un albero.

Darò un'occhiata, comunque sto iniziando a entrare un pochino nell'ottica della ricorsione. L'importante è individuare un caso banale in cui fermare il programma, un caso in cui fare la ricorsione.... poi tutto il resto viene ""da se""!

[Starise]

@Black imp - hai la casella pvt piena!

[Black imp]

Originariamente inviato da Starise

@Black imp - hai la casella pvt piena!

liberata

[marco.r]

Originariamente inviato da Starise

Darò un'occhiata, comunque sto iniziando a entrare un pochino nell'ottica della ricorsione. L'importante è individuare un caso banale in cui fermare il programma, un caso in cui fare la ricorsione.... poi tutto il resto viene ""da se""!

Il codice ricorsivo non è poi cosi' difficile in questo caso, anzi, secondo me piu' comprensibile. In questo caso possiamo scriverlo con una doppia ricorsione:

/* WARNING: è un po' di tempo che non scrivo codice C++... :D */
struct Lista
{
    int value;
    Lista* next;
};


bool iniziaCon( Lista* h2, Lista* h1 )
{
    if (h1 == 0)
        return true;
    if (h2 == 0)
        return false;
    return h1->value == h2->value && iniziaCon(h2->next,h1->next);
}

bool sottolista( Lista* h1, Lista* h2 )
{
    if (h1 == 0)
        return true;
    if (h2 == 0)
        return false;
    return iniziaCon( h2, h1 ) || sottolista(h1,h2->next);
}

Se guardi bene si legge praticamente come si scrive:
- una lista vuota è sottolista di qualsiasi lista
- nessuna lista non vuota è sottolista di una lista vuota
- h1 è sottolista di h2 se h2 inizia con h1, oppure se h1 è sottolista della coda di h2

Seconda ricorsione, iniziaCon. Per prima abbiamo i due casi base:
- la lista vuota è l'inizio di qualsiasi lista
- nessuna lista (non vuota) è l'inizio di una lista vuota.
- Se h1 e h2 non sono vuote, h2 inizia con h1 se i due valori in testa coincidono e la coda di h2 inizia con la coda di h1