[C] liste,cerca ed elimina sequenze numeri

[pucchi91]

Salve,ho un problema con un esercizio sulle liste in C. Premetto che sono alle prime armi e anche se capisco come in teoria dovrebbero funzionare non riesco a scrivere il programma.
L'esercizio è il seguente:

"Sia data una struttura

typedef struct elemento
{
    int val;
    struct elemento *next
} item;

che rappresenta un elemento di una lista di interi.
Si scriva una procedura

lista *SeekAndDestroy(lista *l, int k)

che data una lista lis di interi positivi e un intero positivo k, cerca all'interno di list la prima sequenza di elementi consecutivi la cui somma sia esattamente k, e elimina tali elementi dalla lista. La funzione deve restituire un puntatore al primo elemento della lista così modificata.

La mia idea era quella di scansionare la lista facendo sommare i valori.Tipo come se fosse un array,avere due puntatori che puntano rispettivamente uno al primo e l'altro al secondo elemento e sommarli.Poi confrontare la somma con il valore k. se la somma<k fare una specie di chiamata ricorsiva in cui alla somma aggiungo il prossimo elemento finché non si raggiunge il valore k. Il problema è che non so come far capire al programma di salvare i precedenti valori e e poi come eliminarli una volta trovata la sequenza.
Avevo anche pensato a salvare questi interi in una nuova lista(esempio list current) e poi magari attraverso la funzione ricerca cercare nella vecchia lista gli elementi della list current ed eliminarli,ma come ho detto mi blocco nel scrivere in concreto il programma.
Grazie

[M.A.W. 1968]

Non sei lontano dalla soluzione, ma devi riflettere meglio. L'idea dei due puntatori è fondamentalmente valida.

Non hai alcun bisogno della ricorsione nella implementazione, anche se conviene pensare al programma in termini ricorsivi. Ad ogni step, infatti, possono configurarsi solamente tre stati, secondo una banale relazione d'ordine. Siano current il puntatore al nodo corrente ed S la somma dei valori fin qui accumulati, inizialmente nulla:

1) S + current->val < k: in questo caso si fa solo avanzare il puntatore al nodo corrente;

2) S + current->val = k: abbiamo trovato la sequenza. Se first è il puntatore al primo elemento di potenziale sequenza dal cui valore parte la sommatoria, "eliminare" i valori significa null'altro che collegare al nodo precedente a first il nodo successivo a quello corrente. Qui le cose sono solo leggermente complicate, a livello concettuale, dal fatto che trattasi di lista semplicemente linkata, e quindi il riferimento al "nodo precedente" non è immediatamente disponibile. Nella prassi, può essere sempre utile il ricorso ad un nodo iniziale fittizio con valore nullo, molto più elegante ed efficiente rispetto all'uso di un duplice puntatore a due elementi consecutivi.

3) S + current->val > k: qui si procede sottraendo alla sommatoria il valore del "primo" nodo della potenziale sequenza, e quindi modificando il valore di first (che punterà al nodo successivo).

Ora rifletti meglio su questi semplici step e prova ad implementarli concretamente.