Lista con ricerca

Considerate il programma riportato in coda, che contiene alcune funzioni per la manipolazione di liste di interi.

Modificate il programma aggiungendo una funzione find che, avendo come argomenti un intero n e una lista h, cerchi n nella lista e restituisca:

La funzione main non deve essere modificata. In particolare notate che il prototipo della vostra funzione find deve essere compatibile con la sua chiamata all'interno della funzione main.

Esempio

Eseguendo

./soluzione

avendo nel flusso di ingresso le righe:

+ 5
+ 2
+ 9
+ 10
p
? 2
? 3
f

il programma emette sul flusso di uscita:

10 9 2 5
2 appartiene all'insieme
3 non appartiene all'insieme

Esempio

Eseguendo

./soluzione

avendo nel flusso di ingresso le righe:

+ 1
+ 6
p
? 1
f

il programma emette sul flusso di uscita:

6 1
1 appartiene all'insieme

Programma da completare


#include <stdio.h>
#include <stdlib.h>

struct element {
  int info;   
  struct element *next;
};

typedef struct element  element;  


element *insert(int n, element *h);
void printList(element *h);

/* SI MODIFICHI OPPORTUNAMENTE IL SEGUENTE PROTOTIPO DI FUNZIONE */
..... find( .... , ....);




/*  Inserisce un nuovo elemento contenente n in testa alla lista  h   
    Restituisce la lista ottenuta. */
element *insert(int n, element *h){
  element *new = malloc(sizeof(element));
  new->info = n;
  new->next = h;
  return new;
}


/* Stampa gli elementi della lista   h */
void printList(element *h){
  /* h e' usato  per attraversare la  lista */
  for( ; h!= NULL; h=h->next)
    printf("%d ", h->info);
  putchar('\n');
}



/* Cerca l'intero  n nella lista  h.   
   Se n e' nella lista  restituisce  l'indirizzo del primo elemento che lo contiene,
   altrimenti restituisce NULL. */

/***************** SI COMPLETI OPPORTUNAMENTE QUESTA FUNZIONE ********

.... find( ... , ... ){
   ...
}
*****************************************************/



int main(){
  element *head;
  int c, n;   

  head = NULL;
  while((c=getchar())!= 'f'){
    switch(c){

    case '+':  // + n:  aggiungi n (se non e' gia' nell'insieme)
	scanf("%d", &n);
	if(find(n,head) == NULL){// n non e' nella lista
	  head = insert(n, head);
	}
	break;

    case '?':  // ? n:  n e' nell'insieme?
	scanf("%d", &n);
	if(find(n,head)!= NULL)
	  printf("%d appartiene all'insieme\n", n);
	else
	  printf("%d non appartiene all'insieme\n", n);
	break;

    case 'p':   // stampa gli elementi dell'insieme
      printList(head);
      break;

    } // end switch
  } // end while
  return 0;
}