[C] cercare sottosequenza in lista concatenate

[flyshark]

Salve ragazzi, come da oggetto come faccio a cercare una sottosequenza (memorizzata in una lista concatenata) in un'altra lista concatenata? per favore datemi una mano...non so come fare...il linguaggio è ansi c...grazie 1000000

[pallinopinco]

Inizia con il mostrare cosa hai scritto finora (ovviamente senza la parte della ricerca di sottosequenze, visto che non sai come implementarla).

[flyshark]

fino ad'ora ho normalmente acquisito le due liste concatenate leggendo i dati da due file differenti...i puntatori a queste due liste li dovrei poi passare alla funzione che controlla se nella lista2 vi sono delle sottosequenze uguali alla sequenza di dati presenti in lista1...

[pallinopinco]

Ok, un'ultima informazione: devi restituire il numero delle sottosequenze eventualmente presenti o è sufficiente un valore booleano ( 0 = nessuna sottosequenza, 1 = almeno una sottosequenza)?

Dal punto di vista concettuale è semplice, basta scorrere la sottosequenza passando all'elemento successivo se l'elemento precedente è stato individuato nella sequenza. Se l'elemento successivo non è presente si riparte dal principio e si procede fino ad aver concluso la scansione di almeno una delle 2 sequenze. Se giungi alla fine della sottosequenza significa che essa è interamente contenuta nella sequenza, se invece arrivi all'ultimo elemento della sequenza ma non della sottosequenza allora devi restituire FALSE.

[flyshark]

l'ìinformazione che dovrei restituire è praticamente la posizione di inizio di ogni sottosequenza all'interno della lista in cui si effettua la ricerca....
esempio:
lista_sottosequenza: 5-6-7-8
lista in cui cercare la sottosequenza: 1-2-3-4-5-6-7-8-9-0-5-6-7-8-0

si dovrebbe restituire: "5" (posizione di inizio prima sottosequenza) e "11" (inizio seconda sottosequenza)

P.s. grazie sei molto gentile...

[flyshark]

si hai ragione...concettualmente è semplice...ma sono ancora alle prime armi con il c e non riesco a tradurre il tutto in codice... e m'inpallo
prometto che ricambierò il favore come posso... grazie...

[pallinopinco]

e non riesco a tradurre il tutto in codice..

Prova a tradurlo in pseudo-codice, poi ci si lavora insieme per renderlo funzionante.

[flyshark]

temp1=lista_che_contiene_sottosequenza;
temp2=lista_in_cui_cercare_sottosequenza;

indice=1;        //indica la posizione in cui potrebbe iniziare la sequenza
n_volte=0;     //indica il numero di volte che è stata trovata la sequenza
while(temp2!=NULL)      
{
  if(confronta_nodi(temp2,temp1)==0)     //confronta_nodi ritorna 0 se i nodi nn sono uguali,                          
                                                        //ritorna 1 se i nodi sono uguali    
  {
    temp2=temp2->next;
    indice++;
    continue;
  }
  if(confronta_nodi(temp2,temp1)==1)
  {
    check=1;
    temp3=temp2->next;
    temp1=temp1->next;
    while(confronta_nodi(temp3,temp1)==1)
    {
      check++;
      if(check==lunghezza_lista_che_contiene_sottosequenza)
         break;
      temp1=temp1->next;
      temp3=temp3->next;
    }
    if(check==lunghezza_lista_che_contiene_sottosequenza)
    {
      n_volte++;
      ritorno l'indice (indice);
      temp2=temp3->next;
      temp1=lista_che_contiene_sottosequenza;         //cosi temp1 punta di nuovo all'inizio
      indice=indice+lunghezza_lista_che_contiene_sottosequenza;
    }
    else
    {
      temp1=lista_che_contiene_sottosequenza;
      temp2=temp2->next;
      indice++;
    }
  }
}

...che ne dici? potrebbe andare?
P.s. scusa se commetto errori banali...ma come ti ho detto sono alle prime armi....

[pallinopinco]

...che ne dici? potrebbe andare?
P.s. scusa se commetto errori banali...ma come ti ho detto sono alle prime armi....

Inseriscilo in un blocco [ CODE ], così è poco leggibile...

[flyshark]

...scusami...ho modificato...adesso dovrebbe essere piu leggibile...