PROBLEMA Strutture e Liste [C]

[computer7]

Premessa:
Salve a tutti, sono uno studente che programma da 2 anni, inizialmente Pascal e quest'anno il C.
L'ultimo periodo di scuola,nel corso di informatica, ci sono state spiegate le strutture e le liste, il problema è che proprio in questo periodo ho dovuto effettuare un operazione al cuore e quindi ho saltato gli ultimi 2 mesi di scuola.
Mi sono stati dati gli appunti e ho studiato da solo liste e strutture.

Vengo al problema:
Mi sono stati dati degli esercizi proprio sulle liste e, a parte l' "impostazione" base" del codice, non so come continuare.

Vi posto solo 1 esercizio dei 9 a me dati per chiedervi un aiuto, di cui ve ne sarei grato.



Sia L una lista definita da

struct lista{
int val;
struct lista*next;
}L;



Scrivere in C una funzione ricorsiva che preso in input L e un intero el, verifichi se esiste una occorrenza di el nella lista.

Suggerimento: Scorrere in avanti la lista in chiamate ricorsive e:
- Se L=NULL, ritornare 0.
-Se L_val=L, ritornare 1.
Altrimenti ritornare il risulatato della chiamata ricorsiva su L-->next


Ecco, non riesco proprio a capire la consegna del problema.
Spero qualcuno riesca a spiegarmelo piu chiaramente, Grazie :)

 

[matteoc91]

Prima di andare avanti con la spiegazione vorrei chiederti una cosa; avete già visto la struttura della memoria in termini di stack e heap (presumo di si, ma è sempre meglio chiedere)? Perchè se no la spiegazione diventa un po' complessa da comprendere :)

Cmq andando avanti provo a fare un'infarinata generale per cercare di spiegarti come funziona il concetto di lista.
In sostanza la struttura che definisci non è altro che un elemento che ha in sè alcuni campi che potremmo definire "valore" dall'elemento stesso (nel nostro caso il campo val) ed un puntatore ad un altro elemento dello stesso tipo. In questo senso il modo in cui viene definita la struttura lista potrebbe essere un po' fuorviante, in quanto la lista non è l'elemento definito dalla struttura, ma un insieme composto da più elementi di quel tipo.
Un altro modo in cui potresti definirla è questo:

typedef struct _nodo* list;
struct _nodo{
  int val;
  list next;
};

In sostanza quindi una lista non è altro che un insieme di nodi, dove ogni nodo punta ad un successivo ed è puntato da un precedente (fatta eccezione per il primo elemento che non è puntato da nessuno e l'ultimo dove il puntatore è nullo).

Per comprendere bene il concetto di lista basta che pensi a stack e heap; nello stack hai la dichiarazione della lista che punterà ad un elemento della stessa (il primo, a meno che non ci siano errori logici nel codice, altrimenti sarebbe impossibile riuscire a ritrovare gli altri elementi), gli elementi della lista si troveranno nella memoria heap.

Ora, posta la dichiarazione della lista e l'allocazione dello spazio in memoria per poterla inizializzare (utilizzando la malloc), non ti resta che percorrerla per cercare un ipotetico elemento che ti viene richiesto (ed è qua se ho ben capito che hai dei problemi) :)
Per prima cosa devi sapere dove si trovano gli elementi che vuoi visualizzare e come raggiungerli; per farla breve, abbiamo detto sopra che la variabile che crei nel main (suppongo), la quale contiene la lista, punta al primo elemento della stessa, mentre gli altri elementi sono via via puntati dall'elemento precedente finchè non si arriva al caso in cui il puntatore sia nullo.
Per visualizzare la lista ti basta quindi posizionarti su di un elemento e chiederti se lo stesso è nullo o meno:

if(L==NULL) return 0;
else
   ....

Ora, se l'elemento non è nullo basta che controlli il valore del suo campo:

if(L==NULL) return 0;
else{
  if(L->val==el) return 1;
  else ...
}

Se hai trovato l'elemento hai terminato e restituisci 1, altrimenti devi spostarti sull'elemento successivo, ovvero devi consultare il campo next dell'elemento che stai considierando in quel momento. Supponiamo che queste operazioni le facciamo in un metodo che richiamiamo in un certo istante dal main.
A questo punto hai 2 alternative: la prima è ciclare con un while (in questo caso però dobbiamo modificare un po' il codice di sopra) oppure possiamo (come suggerito dall'esercizio) usare un metodo ricorsivo.
Nel caso del metodo ricorsivo avremo:

int metodo(L lista, int el){
   if(lista==NULL) return 0;
   else{
      if(lista->val==el) return 1;
      else return metodo(lista->next,el);
   }
}

In alternativo con il ciclo while in un metodo esterno avremo:

int metodo(L lista, int el){
   while(lista!=NULL){
      if(lista->val==el) return 1;
      lista=lista->next;
   }
   return 0;
}

Il vantaggio nell'utilizzare il ciclo while risiede nella minore allocazione di stack, ovvero (supponendo di avere un compilatore non ottimizzato) il metodo ricorsivo tenderà ad allocare porzioni di stack per ogni invocazione ricorsiva del metodo stesso (essendo questo un esercizio puoi anche sorvolare su questo fatto).

Per "riempire" la lista puoi comportarti nello stesso modo del metodo col ciclo while (obv non farai più controlli sugli elementi, ma gli assegnerai un determinato valore), ma attenzione a non scorrere la vera lista ma di creare una variabile temporanea che punti agli stessi elementi; il motivo è che se si fa scorrere la variabile passata per riferimento al metodo, la stessa non punterà più al primo elemento della lista, quindi non potrai più andare a ricercare gli elementi precedenti l'ultimo.

Spero di essermi spiegato in maniera chiara :)
CIao,
Matteo.

 

[computer7]

Ciao Matteo, intanto grazie:)

Ho capito quasi tutta la spiegazione e fortunatamente buttando giù lo pseudo-codice ieri l'esercizio mi è abbastanza chiaro.

Mi rimane un dubbio che riguarda la malloc: quanto spazio devo lasciare libero per la lista? è a mia scelta? voglio dire, ipoteticamente, la lista può essere "infinita"?

 

[matteoc91]

Ciao Matteo, intanto grazie:)

Ho capito quasi tutta la spiegazione e fortunatamente buttando giù lo pseudo-codice ieri l'esercizio mi è abbastanza chiaro.

Mi rimane un dubbio che riguarda la malloc: quanto spazio devo lasciare libero per la lista? è a mia scelta? voglio dire, ipoteticamente, la lista può essere "infinita"?

La lista di base non ha una dimensione, anche perchè altrimenti sarebbe molto più comodo usare un array :)
Di fatti se noi usiamo un array (allocato dinamicamente o staticamente, poco importa) l'accesso diretto agli elementi sarebbe molto più semplice e performante rispetto a quello di una lista e lo spazio occupato in memoria sarebbe pressoché lo stesso.
Il vantaggio di usare una lista sta nel fatto che questa non ha (come detto sopra) una dimensione preimpostata.
Se ricordi quello che ho scritto sopra, ho definito la lista come una sequenza di nodi; in generale quando usi una malloc non stai esattamente definendo lo spazio che la lista occuperà in memoria, ma stai riservando lo spazio di un singolo nodo.

L *lista = (L *) malloc( sizeof(L) );

Questa, secondo la definizione data dall'esercizio, dovrebbe essere la malloc che vai a definire nel codice; probabilmente ti confonde un po' utilizzare il termine lista, in quanto qua non stai riservando spazio per l'intera lista, ma solo per il primo elemento :)
Di fatti per ogni elemento successivo che vai a creare dovrai usare un'altra malloc.

Se invece dovessimo definire la dimensione della lista a priori, a questo punto sarebbe più comodo utilizzare un array dinamico:

[B]tipo[/B] *array = ([B]tipo[/B] *) malloc( DIM * sizeof([B]tipo[/B]) );

Dove con tipo potremmo definire un array di interi, un array di liste, o altra roba; ma se noti facendo così non sfrutti più il campo next dei nodi della lista, il quale sarà sempre nullo.
A questo punto quindi sarebbe molto più comodo ridefinire la struttura creata ed eliminare il campo next, in questo modo avremo semplicemente un array di nodi, ma non avremo più una lista :)

 

[computer7]

Ah certo, che scemo! :)

Grazie, ora ho capito. Spieghi molto bene,come un professore, ti ringrazio ;)

Ora cerco di svolgerlo e svolgere anche gli altri e t chiedo scusa se disturbo ad agosto! :)

 

[matteoc91]

Figurati ;)
Ciao,
Matteo