dal sito http://utenti.lycos.it/dsilist/

Compito C - Esercizio 0 (di sbarramento) (parole presenti in un array di char).c 
/*
  Dato un array s di caratteri di dimensione nota n, si scriva una funzione C 
  che conti il numero di parole presenti in s, dove per PAROLA si intende una 
  sequenza di caratteri consecutivi che non contiene spazi.
*/

#include <stdio.h>
#include <ctype.h>

void GetString(char *s);
int IsWord(char *s);

main()
{
  char str[1000];
  int r=0;
  
  printf("Immettere una stringa: ");
  GetString(str);
  printf("%s\n",str);
  
  if(!str)
  {
    printf("La stringa e' vuota. \n");
    return 0;
  }
  
  r=IsWord(str);
  printf("Numero di parole trovate: %d \n",r);
  
  fflush(stdin);
  getch();
  return 1;
}

void GetString(char *s)
{
  char c;
  
  c=getchar();
  while(c!='\n')
  {
    *s++=c;
    c=getchar();
  }
  *s='\0';
}

int IsWord(char *s)
{
  int c=0,i=0,l=strlen(s);
  
  if(!c)
  {
    if(isalnum(s[i]))
      c++;
    i++;
  }
  
  while(i>0)
  {
    if(isalnum(s[i]) && isalnum(s[i-1]))
    {
      i++;
    }
    
    else
    if(isalnum(s[i]) && isspace(s[i-1]))
    {
      c++;
      i++;
    }
    
    else
    if(isspace(s[i]) && isalnum(s[i-1]))
    {
      i++;
    }
    
    else
    if((s[i]=='\0') && isalnum(s[i-1]))
    {
      c++;
      return c;
    }
    
    else
    if((s[i]=='\0') && isspace(s[i-1]))
    {
      return c;
    }
  }
}


Compito B - Esercizio 0 (di sbarramento) (albero binario con un cammino 'radice-foglia' strettamente crescente).c 
/*
  Dato un albero binario contenente numeri interi, 
  scrivere una funzione ricorsiva per verificare se esiste un 
  cammino 'radice->foglia' che sia strettamente crescente.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode
{
	int val;
	struct TreeNode *sx;
	struct TreeNode *dx;
}Node;

Node* CreateTree();
void PrintTree(Node *t);
void DeleteTree(Node *t);
int Sesquipedale(Node *t);

main()
{
	Node *root=NULL;
	int i=0;

	root=CreateTree();
	PrintTree(root);
	if(Sesquipedale(root))
    printf("Esiste un cammino 'radice->foglia' strettamente crescente \n");
  else
    printf("Non esiste un cammino 'radice->foglia' strettamente crescente \n");
  DeleteTree(root);
	getch();
  return 1;
}

Node* CreateTree()
{
	Node *t=NULL;
	int i,n;

	t=(Node*)malloc(sizeof(Node));
  if(t)
	{
    t->sx=t->dx=NULL;
    
    printf("Valore del nodo: ");
  	scanf("%d",&t->val);
    
    printf("# di figli del nodo: ");
    scanf("%d",&n);
    
    while(n<0 && n>2)
    {
      printf("Errore!\nImmettere un valore compreso tra '0' e '2' \n");
      printf("# di figli del nodo: ");
    	scanf("%d",&n);
  	}
  
  	if(n)
  	{
      t->sx=CreateTree();
      if(n==2)
        t->dx=CreateTree();
    }  		
  }
	return t;
}

void PrintTree(Node *t)
{
  if(t)
  {
    int n=0;
    
    if(t->sx)
      n++;
    if(t->dx)
      n++;
    if(n==0)
      printf("%d \n",t->val);
    if(n==1)
      printf("%d <%d> \n",t->val,t->sx->val);
    if(n==2)
      printf("%d <%d> <%d> \n",t->val,t->sx->val,t->dx->val);
    PrintTree(t->sx);
    PrintTree(t->dx);
  }
}

void DeleteTree(Node *t)
{
  if(t)
  {
    DeleteTree(t->sx);
    DeleteTree(t->dx);
    free(t);
  }
}

int Sesquipedale(Node *t)
{
	int result=1;
  
  if(!t)
    return 1;
	else 
  if(t->sx && t->dx)
	{
		if(t->val < t->sx->val)
      result=Sesquipedale(t->sx);
		else
      result=0;
		if(!result)
    {
      if(t->val < t->dx->val)
        result=Sesquipedale(t->dx);
  		else
        result=0;
		}
	}
	else
  if(t->sx)
	{
		if(t->val < t->sx->val)
      result=Sesquipedale(t->sx);
		else
      result=0;
	}
	else
  if(t->dx)
	{
		if(t->val < t->dx->val)
      result=Sesquipedale(t->dx);
		else
      result=0;
	}
	return result;
}

Compito B - Esercizio 1 (albero binario con nodi 'spropositati').c 
/*
  Sia dato un albero binario i cui nodi possono essere colorati (ogni nodo ha un campo denominato 'colore'). 
  Un nodo si dice 'spropositato' se nel suo sottoalbero se il numero di nodi di colore verde è maggiore del numero di nodi di colore rosso. 
  Si assuma che il sottoalbero di un nodo 'x' non contiene x. 
  Dopo aver definito le appropriate strutture dati, si scriva una funzione C che restituisce il numero di nodi di colore giallo che sono spropositati. 
  Si dia una stima della complessità computazionale della vostra procedura.
*/

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct node
{
	char color[20];
	struct node *sx;
	struct node *dx;
} Node;

Node* CreateTree();
void PrintTree(Node *node);
void DeleteTree(Node *node);
int Function(Node *t);
int CheckColor(Node *t,char *s);

int main()
{
  Node *root=NULL;
  
  root=CreateTree();
	PrintTree(root);
	printf("Numero di nodi 'spropositati': %d \n",Function(root));
  DeleteTree(root);
  getch();
	return 1;
}

Node* CreateTree()
{
	Node *t=NULL;
	int i,n;
  
  t=(Node*)malloc(sizeof(Node));
	if(t)
  {
    t->sx=NULL;
  	t->dx=NULL;
  
  	printf("colore del nodo: ");
  	scanf("%s",t->color);
  	printf("# di figli del nodo: ");
    scanf("%d",&n);
    
    while(n<0 && n>2)
    {
      printf("Errore!\nImmettere un valore compreso tra '0' e '2' \n");
      printf("# di figli del nodo: ");
    	scanf("%d",&n);
  	}
  
  	if(n)
  	{
      t->sx=CreateTree();
      if(n==2)
        t->dx=CreateTree();
    }
  }
	return t;
}

void PrintTree(Node *t)
{
	if(!t)
    return;
    
	printf("%s \n",t->color);
	PrintTree(t->sx);
	PrintTree(t->dx);
}

void DeleteTree(Node *t)
{
	if(!t)
    return;

	DeleteTree(t->sx);
	DeleteTree(t->dx);
	free(t);
}

int Function(Node *t)
{
  int result=0;
  
  if(!t)
    return 0;
  else
  if(strcmp(t->color,"giallo")==0)
  {
    if(CheckColor(t,"verde")>CheckColor(t,"rosso"))
      result++;
  }
  result+=Function(t->sx)+Function(t->dx);
  return result;
}

int CheckColor(Node *t,char *s)
{
  int i,r=0;
  
  if(!t)
    return 0;
  if(strcmp((t->color),s)==0)
    r++;
  r+=CheckColor(t->sx,s)+CheckColor(t->dx,s);
  return r;
}


Compito C - Esercizio 1 (albero binario con nodi 'corrotti').c 
/*
  Sia dato un albero binario i cui nodi possono essere colorati (ogni nodo ha un campo denominato 'colore'). 
  Un nodo si dice 'corrotto' se nel suo sottoalbero ci sono dei nodi di colore verde.
  Dopo aver definito le appropriate strutture dati, si scriva una funzione C che restituisce il nu8mero di nodi di colore rosso che non sono corrotti. 
  Si dia una stima della complessità computazionale della vostra procedura.
*/

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct node
{
	char color[20];
	struct node *sx;
	struct node *dx;
} Node;

Node* CreateTree();
void PrintTree(Node *node);
void DeleteTree(Node *node);
int Function(Node *t);
int CheckColor(Node *t,char *s);

int main()
{
  Node *root=NULL;
  
  root=CreateTree();
	PrintTree(root);
	printf("Numero di nodi rossi non 'corrotti': %d \n",Function(root));
  DeleteTree(root);
  getch();
	return 1;
}

Node* CreateTree()
{
	Node *t=NULL;
	int i,n;
  
  t=(Node*)malloc(sizeof(Node));
	if(t)
  {
    t->sx=NULL;
  	t->dx=NULL;
  
  	printf("colore del nodo: ");
  	scanf("%s",t->color);
  	printf("# di figli del nodo: ");
    scanf("%d",&n);
    
    while(n<0 && n>2)
    {
      printf("Errore!\nImmettere un valore compreso tra '0' e '2' \n");
      printf("# di figli del nodo: ");
    	scanf("%d",&n);
  	}
  
  	if(n)
  	{
      t->sx=CreateTree();
      if(n==2)
        t->dx=CreateTree();
    }
  }
	return t;
}

void PrintTree(Node *t)
{
	if(!t)
    return;
    
	printf("%s \n",t->color);
	PrintTree(t->sx);
	PrintTree(t->dx);
}

void DeleteTree(Node *t)
{
	if(!t)
    return;

	DeleteTree(t->sx);
	DeleteTree(t->dx);
	free(t);
}

int Function(Node *t)
{
  int result=0;
  
  if(!t)
    return 0;
  else
  if(strcmp(t->color,"rosso")==0)
  {
    if(!CheckColor(t,"verde"))
      result++;
  }
  result+=Function(t->sx)+Function(t->dx);
  return result;
}

int CheckColor(Node *t,char *s)
{
  int i,r=0;
  
  if(!t)
    return 0;
  if(strcmp((t->color),s)==0)
    r++;
  r+=CheckColor(t->sx,s)+CheckColor(t->dx,s);
  return r;
}

Compito A - Esercizio 0 (albero binario con un cammino 'radice-foglia' di lunghezza k strettamente crescente).c 
/*
  Dato un albero binario contenente numeri interi, 
  scrivere una funzione ricorsiva per verificare se esiste un 
  cammino 'radice->foglia' che sia strettamente crescente.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode
{
 int val;
 struct TreeNode *sx;
 struct TreeNode *dx;
}Node;

Node* CreateTree();
void PrintTree(Node *t);
void DeleteTree(Node *t);
int Function(Node *t, int k);
int IsLeaf(Node *t);

main()
{
 Node *root=NULL;
 int i=0,k=0;

 root=CreateTree();
 PrintTree(root);
 printf("Valore di k?: ");
 scanf("%d",&k);
 if(Function(root,k))
     printf("Esiste un cammino 'radice->foglia' di lunghezza %d strettamente crescente \n",k);
 else
   printf("Non esiste un cammino 'radice->foglia' di lunghezza %d strettamente crescente \n",k);
 DeleteTree(root);
 getch();
 return 1;
}

Node* CreateTree()
{
 Node *t=NULL;
 int i,n;

 t=(Node*)malloc(sizeof(Node));
  if(t)
 {
    t->sx=t->dx=NULL;
    
    printf("Valore del nodo: ");
   scanf("%d",&t->val);
    
    printf("# di figli del nodo: ");
    scanf("%d",&n);
    
    while(n<0 && n>2)
    {
      printf("Errore!\nImmettere un valore compreso tra '0' e '2' \n");
      printf("# di figli del nodo: ");
     scanf("%d",&n);
   }
  
   if(n)
   {
      t->sx=CreateTree();
      if(n==2)
        t->dx=CreateTree();
    }    
  }
 return t;
}

void PrintTree(Node *t)
{
  if(t)
  {
    int n=0;
    
    if(t->sx)
      n++;
    if(t->dx)
      n++;
    if(n==0)
      printf("%d \n",t->val);
    if(n==1)
      printf("%d <%d> \n",t->val,t->sx->val);
    if(n==2)
      printf("%d <%d> <%d> \n",t->val,t->sx->val,t->dx->val);
    PrintTree(t->sx);
    PrintTree(t->dx);
  }
}

void DeleteTree(Node *t)
{
  if(t)
  {
    DeleteTree(t->sx);
    DeleteTree(t->dx);
    free(t);
  }
}

int Function(Node *t,int k)          // la funzione riceve inizialmente il nodo radice e il valore k della lunghezza del cammino
{
 int result=0;
  
  if(!t)                             // se l'albero non esiste esco
    return 1;                        // e secondo la regola Panconesiana ciò che non contraddice soddisfa, quindi torno 1 :D
  
  if(k==0)                           // se siamo alla fine del cammino radice->foglia..
    if(IsLeaf(t))                    // ..t è una foglia?
      return 1;                      // se si torno 1
    else
      return 0;                      // altrimenti torno 0
  
  if(t->sx)                          // se esiste un nodo figlio sinistro..
 {
  if(t->val < t->sx->val)            // ..e il suo valore è maggiore del nodo padre
      result=Function(t->sx,k-1);    // il risultato dipenderà da ciò che avviene nel sottoalbero del nodo figlio
  }
 if(!result)                         // se non ho ancora trovato un cammino valido (altrimenti result varrebbe 1) cerco un cammino nel sottoalbero destro
 {
   if(t->dx)                         // se esiste un nodo figlio destro..
   {
      if(t->val < t->dx->val)        // ..e il suo valore è maggiore del nodo padre
        result=Function(t->dx,k-1);  // il risultato dipenderà da ciò che avviene nel sottoalbero del nodo figlio
  }
 }
 return result;                      // ritorna 0 se non è stato trovato un cammino valido, 1 altrimenti
}

int IsLeaf(Node *t)                  // funzione che determina se il nodo passatole è una foglia
{
  if(!t->sx && !t->dx)
    return 1;                        // se il nodo è una foglia torna 1
  else
    return 0;                        // altrimenti torna 0
}


***********************************************************

Compito A - Esercizio 1 (albero binario con nodi 'spropositati') 1.c 
/*
  Sia dato un albero binario i cui nodi possono essere colorati (ogni nodo ha un campo denominato 'colore'). 
  Un nodo si dice 'spropositato' se nel suo sottoalbero il numero di nodi di colore verde è maggiore del numero di nodi di colore rosso. 
  Si assuma che il sottoalbero di un nodo 'x' non contiene x. 
  Dopo aver definito le appropriate strutture dati, si scriva una funzione C che restituisce il numero di nodi di colore giallo che sono spropositati. 
  Si dia una stima della complessità computazionale della vostra procedura.
*/

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct node
{
	char color[20];
	struct node *sx;
	struct node *dx;
} Node;

Node* CreateTree();
void PrintTree(Node *t);
void DeleteTree(Node *t);
void Function(Node *t);
void Rosso(Node *t);
void Verde(Node *t);
int Verify(Node *t);

int contG=0, contV=0,contR=0;

int main()
{
  Node *root=NULL;
  
  root=CreateTree();
	PrintTree(root);
	printf("Numero di nodi gialli 'spropositati': %d \n",contG);
  DeleteTree(root);
  getch();
	return 1;
}

Node* CreateTree()
{
	Node *t=NULL;
	int i,n;
  
  t=(Node*)malloc(sizeof(Node));
	if(t)
  {
    t->sx=NULL;
  	t->dx=NULL;
  
  	printf("colore del nodo: ");
  	scanf("%s",t->color);
  	printf("# di figli del nodo: ");
    scanf("%d",&n);
    
    while(n<0 && n>2)
    {
      printf("Errore!\nImmettere un valore compreso tra '0' e '2' \n");
      printf("# di figli del nodo: ");
    	scanf("%d",&n);
  	}
  
  	if(n)
  	{
      t->sx=CreateTree();
      if(n==2)
        t->dx=CreateTree();
    }
  }
	return t;
}

void PrintTree(Node *t)
{
	if(!t)
    return;
    
	printf("%s \n",t->color);
	PrintTree(t->sx);
	PrintTree(t->dx);
}

void DeleteTree(Node *t)
{
	if(!t)
    return;

	DeleteTree(t->sx);
	DeleteTree(t->dx);
	free(t);
}

void Function(Node *t)
{
  if(!t)
    return;
  else
  if(strcmp(t->color,"giallo")==0)
    contG+=Verify(t);
  
  Function(t->sx);
  Function(t->dx);
  
  return;
}

int Verify(Node *t)
{
  contR=contV=0;
  Verde(t);
  Rosso(t);
  
  if(contR<contV)
    return 1;
  else
    return 0;
}

void Verde(Node *t)
{
  if(!t)
    return;
  if(!strcmp(t->color,"verde"))
    contV++;
  Verde(t->sx);
  Verde(t->dx);
  return;
}

void Rosso(Node *t)
{
  if(!t)
    return;
  if(!strcmp(t->color,"rosso"))
    contR++;
  Rosso(t->sx);
  Rosso(t->dx);
  return;
}


Compito A - Esercizio 1 (albero binario con nodi 'spropositati') 2.c 
/*
  Sia dato un albero binario i cui nodi possono essere colorati (ogni nodo ha un campo denominato 'colore'). 
  Un nodo si dice 'spropositato' se nel suo sottoalbero il numero di nodi di colore verde è maggiore del numero di nodi di colore rosso. 
  Si assuma che il sottoalbero di un nodo 'x' non contiene x. 
  Dopo aver definito le appropriate strutture dati, si scriva una funzione C che restituisce il numero di nodi di colore giallo che sono spropositati. 
  Si dia una stima della complessità computazionale della vostra procedura.
*/

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct node
{
	char color[20];
	struct node *sx;
	struct node *dx;
} Node;

Node* CreateTree();
void PrintTree(Node *node);
void DeleteTree(Node *node);
int Function(Node *t);
int CheckColor(Node *t,char *s);

int main()
{
  Node *root=NULL;
  
  root=CreateTree();
	PrintTree(root);
	printf("Numero di nodi gialli 'spropositati': %d \n",Function(root));
  DeleteTree(root);
  getch();
	return 1;
}

Node* CreateTree()
{
	Node *t=NULL;
	int i,n;
  
  t=(Node*)malloc(sizeof(Node));
	if(t)
  {
    t->sx=NULL;
  	t->dx=NULL;
  
  	printf("colore del nodo: ");
  	scanf("%s",t->color);
  	printf("# di figli del nodo: ");
    scanf("%d",&n);
    
    while(n<0 && n>2)
    {
      printf("Errore!\nImmettere un valore compreso tra '0' e '2' \n");
      printf("# di figli del nodo: ");
    	scanf("%d",&n);
  	}
  
  	if(n)
  	{
      t->sx=CreateTree();
      if(n==2)
        t->dx=CreateTree();
    }
  }
	return t;
}

void PrintTree(Node *t)
{
	if(!t)
    return;
    
	printf("%s \n",t->color);
	PrintTree(t->sx);
	PrintTree(t->dx);
}

void DeleteTree(Node *t)
{
	if(!t)
    return;

	DeleteTree(t->sx);
	DeleteTree(t->dx);
	free(t);
}

int Function(Node *t)
{
  int result=0;
  
  if(!t)
    return 0;
  else
  if(strcmp(t->color,"giallo")==0)
  {
    if(CheckColor(t,"verde")>CheckColor(t,"rosso"))
      result++;
  }
  result+=Function(t->sx)+Function(t->dx);
  return result;
}

int CheckColor(Node *t,char *s)
{
  int i,r=0;
  
  if(!t)
    return 0;
  if(strcmp((t->color),s)==0)
    r++;
  r+=CheckColor(t->sx,s)+CheckColor(t->dx,s);
  return r;
}


Compito A - Esercizio 2 (elemento maggioritario in una lista).c 
/*
  Data una lista di interi a puntatori semplici, un elemento che compare il 
  numero massimo di volte si dice MAGGIORITARIO.
  Si scriva una funzione C per verificare che l'elemento maggioritario è unico.
  Si dia una stima della complessità computazionale della vostra procedura.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct ListNode
{
  int val,occorrenza;
  struct ListNode *next;
} Node;

void InsertNode(Node **p,int item);
void PrintList(Node *p);
void DeleteList(Node *p);
Node* Maggioritario(Node *p);
int IsAlone(Node* p,Node*f);

main()
{
	Node *list=NULL,*start=NULL,*result=NULL;
	int i=0,n=0,x=0,item=0;
	
  inizio:
  printf("Numero degli elementi da inserire: ");
  fflush(stdin);
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    printf("Valore dell'elemento %d: ",i+1);
    fflush(stdin);
    scanf("%d",&item);
    InsertNode(&list,item);
    if(!i)
      start=list;
  }
  list=start;
  
  result=Maggioritario(start);

  PrintList(start);
  
  printf("Primo elemento maggioritario della lista: %d \n",result->val);
  x=IsAlone(start,result);
  if(x)
    printf("L'elemento maggioritario e' unico \n");
  else
    printf("L'elemento maggioritario non e' unico \n");
	DeleteList(start);
	printf("Premere un tasto per terminare... \n\n");
	getch();
	goto inizio;
  return 1;
}

void InsertNode(Node **p,int item)
{
	Node *new=(Node*)malloc(sizeof(Node));

	if(new)
	{
		new->val=item;
		new->occorrenza=0;
		new->next=NULL;
		
		if(!(*p))
      *p=new;
    else
      *p=(*p)->next=new;
	}
	else
    printf("Memory allocation failed! \n");
}

void PrintList(Node *p)
{
  while(p)
  {
    printf("%d(%d) ",p->val,p->occorrenza);
    p=p->next;
  }
  printf("NULL \n");
}

void DeleteList(Node *p)
{
	Node *temp=NULL;
	
  while(p)
	{
		temp=p;
		p=p->next;
		free(temp);
	}
	free(p);
}

Node* Maggioritario(Node *p)          // p punta al primo elemento della lista
{
 int k=0,r=0;
 Node *f=p,*s=p,*t=NULL;                    // faccio puntare 'f' e 's' al primo elemento della lista
 
    while(f)                        // se non esiste 'f' esco (la lista è vuota oppure sonno arrivato alla fine)
    {
        while(s)                    // se non esiste 's' esco (sono arrivato alla fine degli elementi da confrontare con f->val)
        {
            if(f->val==s->val)      // se gli elementi sono uguali
                (f->occorrenza)++;  // incremento il contatore
            s=s->next;              // faccio puntare 's' all'elemento successivo
        }
        if((f->occorrenza)>r)                     // se il numero di occorrenze è maggiore di quello precedente (0 per il primo ciclo)
        {
            r=(f->occorrenza);                    // assegno ad 'r' il nuovo risultato
            t=f;
        }
        f=f->next;                  // faccio puntare 'f' all'elemento successivo
        s=f;                        // faccio puntare 's' all'elemento puntato da 'f' (quelli confrontati prima non li controllo +)
    }
    return t;                       // ritorno r (0 se la lista non esiste, un valore > 0 altrimenti)
}

int IsAlone(Node* p,Node* f)
{
  int k=0;
  
  while(p)
  {
    if(f->occorrenza==p->occorrenza)
    {
      if(!k)
        k=1;
      else
        return 0;
    }
    p=p->next;
  }
  return 1;
}


Esame 03-09-24.txt 
PROGRAMMAZIONE II - SCRITTO 24/9/03

COMPITO A

Esercizio di sbarramento.
Dato un albero binario contenente numeri interi ed un numero intero k > 0, scrivere una funzione ricorsiva per verificare se esiste un cammino radice-foglia di lunghezza k che sia strettamente crescente.

Esercizio 1. 
Sia dato un albero binario i cui nodi possono essere colorati, i.e. ogni nodo ha un campo denominato colore. Un nodo si dice spropositato se nel suo sottoalbero il numero di nodi di colore VERDE è maggiore del numero di nodi di colore ROSSO. Dopo aver definito le appropriate strutture dati, si scriva una funzione C che restituisce il numero di nodi di colore GIALLO che sono spropositati.
Si dia una stima della complessità computazionale della vostra procedura.

Esercizio 2. 
Data una lista di interi a puntatori semplici, un elemento che compare il numero massimo di volte si dice maggioritario. Si scriva una funzione C per verificare che l'elemento maggioritario è unico.
Si dia una stima della complessità computazionale della vostra procedura.


Compito A - Esercizio 0 (albero, lista, cammino radice-foglia).c 
/*
  Scrivere una funzione ricorsiva che, dati in ingresso un albero binario ed 
  una lista, entrambi di numeri interi, verifichi che esiste un cammino 
  radice->foglia identico alla lista.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct treenode
{
	int val;
	struct treenode *sx;
	struct treenode *dx;
} TreeNode;

typedef struct listnode
{
  int val;
  struct listnode *next;
} ListNode;

TreeNode* CreateTree();
void DeleteTree(TreeNode *t);
void InsertNode(ListNode **p,int item);
void DeleteList(ListNode *p);

int main()
{
  TreeNode *tnode=NULL,*result=NULL;
  ListNode *list=NULL,*start=NULL,*lnode=NULL;
  int sum=0,n=0,i=0,item=0;
  
	printf("Numero di elementi da inserire: ");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Valore dell'elemento %d: ",i+1);
		scanf("%d",&item);
		InsertNode(&list,item);
		if(!i)
			start=list;
	}
	tnode=CreateTree();
	printf("%d \n",Check(tnode,start));
  DeleteTree(tnode);
  getch();
	return 1;
}

void InsertNode(ListNode **p,int item)
{
	ListNode *newItem=(ListNode*)malloc(sizeof(ListNode));

	if(newItem)
	{
		newItem->val=item;
		newItem->next=NULL;
		
		if(!(*p))
      *p=newItem;
    else
      *p=(*p)->next=newItem;
	}
	else
    printf("Allocazione della memoria falita! \n");
}

void DeleteList(ListNode *p)
{
	ListNode *temp=NULL;
	
	while(p->next)
	{
		temp=p;
		p=p->next;
		free(temp);
	}
	free(p);
}

TreeNode* CreateTree()
{
	TreeNode *t=NULL;
	int i,n;
  
  t=(TreeNode*)malloc(sizeof(TreeNode));
	if(t)
  {
    t->val=0;
  	t->sx=NULL;
  	t->dx=NULL;
  
  	printf("valore del nodo: ");
  	scanf("%d",&(t->val));
  	printf("# di figli del nodo: ");
    scanf("%d",&n);
    
    while(n<0 && n>2)
    {
      printf("Errore!\nImmettere un valore compreso tra '0' e '2' \n");
      printf("# di figli del nodo: ");
    	scanf("%d",&n);
  	}
  
  	if(n)
  	{
      t->sx=CreateTree();
      if(n==2)
        t->dx=CreateTree();
    }
  }
	return t;
}

void PrintTree(TreeNode* t)
{
	if(!t)
    return;
    
	printf("%d\n",t->val);
	PrintTree(t->sx);
	PrintTree(t->dx);
}

void DeleteTree(TreeNode *t)
{
	if(!t)
    return;

	DeleteTree(t->sx);
	DeleteTree(t->dx);
	free(t);
}

int Check(TreeNode *t,ListNode *l)
{
  int r=0;
  
  if(!t && !l)
    return 1;
  if((t && !l) || (!t && l))
    return 0;
  if(t->val==l->val)
  {
    r=Check(t->sx,l->next);
    if(!r)
      r=Check(t->dx,l->next);
  }
  return r;
}


Compito A - Esercizio 1 (lista con nodi 'schiacciati' e 'corrotti').c 
/*
  Sia data una lista a puntatori semplici contenente numeri interi. 
  Se i<j si dice che a(j) è un "successore" di a(i) [a(j) viene dopo di a(i)].
  Un elemento si dice "schiacciato" se esiste un successore + grande di lui, 
  mentre si dice "corrotto" se esiste un suo successore che è schiacciato.
  
  Si scriva una funzione che restituisce il numero di elementi corrotti della lista.
  Si dia una stima del tempo di calcolo della vostra proceduta.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct listnode
{
  int val,corrotto,schiacciato;
  struct listnode *next;
} ListNode;

void InsertNode(ListNode **p,int item);
void PrintList(ListNode *p);
void DeleteList(ListNode *p);
int Schiacciato(ListNode *p);
int Corrotto(ListNode *p);
int ContaCorrotti(ListNode *p);

main()
{
	ListNode *curNode=NULL,*startNode=NULL;
	int n=0,i=0,item=0;
	
	printf("Numero di elementi da inserire: ");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Valore dell'elemento %d: ",i+1);
		scanf("%d",&item);
		InsertNode(&curNode,item);
		if(!i)
			startNode=curNode;
	}
	PrintList(startNode);
	
  curNode=startNode;  
	while(curNode)
	{
    curNode->schiacciato=Schiacciato(curNode);
    curNode=curNode->next;
  }

  curNode=startNode;
	while(curNode)
	{
    curNode->corrotto=Corrotto(curNode);
    curNode=curNode->next;
  }
  
  printf("Nodi corrotti: %d \n",ContaCorrotti(startNode));

	DeleteList(startNode);
	getch();
	return 1;
}

void InsertNode(ListNode **p,int item)
{
	ListNode *new=(ListNode*)malloc(sizeof(ListNode));

	if(new)
	{
		new->val=item;
		new->schiacciato=0;
		new->corrotto=0;
		new->next=NULL;
		
		if(!(*p))
      *p=new;
    else
      *p=(*p)->next=new;
	}
	else
    printf("Allocazione della memoria falita! \n");
}

void PrintList(ListNode *p)
{
  while(p)
  {
    printf("%d -> ",p->val);
    p=p->next;
  }
  printf("NULL\n");
}

void DeleteList(ListNode *p)
{
	ListNode *temp=NULL;
	
	while(p->next)
	{
		temp=p;
		p=p->next;
		free(temp);
	}
	free(p);
}

int Schiacciato(ListNode *p)
{
  ListNode *c=p->next;
  
  while(c)
  {
    if(p->val < c->val)
      return 1;
    c=c->next;
  }
  return 0;
}

int Corrotto(ListNode *p)
{
  ListNode *c=p->next;
  
  while(c)
  {
    if(c->schiacciato)
      return 1;
    c=c->next;
  }
  return 0;
}

int ContaCorrotti(ListNode *p)
{
  if(!p)
    return 0;
  else
    return (p->corrotto+ContaCorrotti(p->next));
}

Compito A - Esercizio 2 (2 liste con 'totalizzatore').c 
/*
  Siano date due liste di interi a puntatori semplici DELLA STESSA LUNGHEZZA 
  p = p1p2..pn e q = q1q2..qn. La lista p è TOTALIZZATORE di q se, per 1<=i<=n, 
  si ha p[i] = q[i] + q[i+1] + ... + q[n].
  Si scriva una funzione C per verificare se p e il totalizzatore di q. Si può 
  assumere che le liste abbiano la stessa lunghezza.
  Si dia una stima della complessità computazionale della vostra procedura.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct listnode
{
  int val,corrotto,schiacciato;
  struct listnode *next;
} ListNode;

void InsertNode(ListNode **p,int item);
void PrintList(ListNode *p);
void DeleteList(ListNode *p);
int Totalizzatore(ListNode *p,ListNode *q);
int CalcolaSomma(ListNode *p);

main()
{
	ListNode *startNode1=NULL,*curNode1=NULL,*startNode2=NULL,*curNode2=NULL;
	int n=0,i=0,item=0;
	
	printf("Numero di elementi da inserire: ");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Valore dell'elemento %d: ",i+1);
		scanf("%d",&item);
		InsertNode(&curNode1,item);
		if(!i)
			startNode1=curNode1;
	}
	for(i=0;i<n;i++)
	{
		printf("Valore dell'elemento %d: ",i+1);
		scanf("%d",&item);
		InsertNode(&curNode2,item);
		if(!i)
			startNode2=curNode2;
	}
	
  PrintList(startNode1);
  PrintList(startNode2);
  
  printf("%d \n",Totalizzatore(startNode1,startNode2));
	
	DeleteList(startNode1);
	DeleteList(startNode2);
	
	getch();
	return 1;
}

void InsertNode(ListNode **p,int item)
{
	ListNode *new=(ListNode*)malloc(sizeof(ListNode));

	if(new)
	{
		new->val=item;
		new->schiacciato=0;
		new->corrotto=0;
		new->next=NULL;
		
		if(!(*p))
      *p=new;
    else
      *p=(*p)->next=new;
	}
	else
    printf("Allocazione della memoria falita! \n");
}

void PrintList(ListNode *p)
{
  while(p)
  {
    printf("%d -> ",p->val);
    p=p->next;
  }
  printf("NULL\n");
}

void DeleteList(ListNode *p)
{
	ListNode *temp=NULL;
	
	while(p->next)
	{
		temp=p;
		p=p->next;
		free(temp);
	}
	free(p);
}

int Totalizzatore(ListNode *p,ListNode *q)
{
  if(!p)
    return 1;
  else
  {
    if(p->val==CalcolaSomma(q))
      return Totalizzatore(p->next,q->next);
    else
      return 0;
  }
}

int CalcolaSomma(ListNode *p)
{
  if(!p)
    return 0;
  else
    return (p->val+CalcolaSomma(p->next));
}


Compito A - Esercizio 0 di sbarramento.c 
/*
Scrivere una funzione che, dati in input una lista di interi ed un numero 
intero 'x', restituisca il puntatore al primo elemento più grandedi x, se 
esiste, e NULL altrimenti.
*/

#include <stdio.h>
#include <malloc.h>

int Speculare(int *p1,int *p2,int d);
int* InsVect(int d);

main()
{
	int *v1=NULL,*v2=NULL,dim;
	
	printf("Dimensione del vettore: ");
	scanf("%d",&dim);
	printf("Vettore #1\n");
  v1=InsVect(dim);
	printf("Vettore #2\n");
	v2=InsVect(dim);
	if(Speculare(v1,v2,dim))
		printf("Si\n");
  system ("PAUSE");
	return 1;
}

int* InsVect(int d)
{
	int *v=NULL,i;
	
	v=(int*)malloc(d*sizeof(int));
	for(i=0;i<d;i++)
	{
		printf("Valore dell'elemento %d: ",i+1);
		scanf("%d",&v[i]);
	}
	return v;
}

int Speculare(int *p1,int *p2,int d)
{
	int i;
	
	for(i=0;i<d;i++)
	{
		if(p1[i]!=p2[d-1-i])
			return 0;
	}
	return 1;
}


Compito A - Esercizio 1.c 
/*
Una "rotazione" di un vettore x[] + il vettore che si ottiene spostando ogni 
elemento di un certo numero di posti "verso sinistra", assumendo che l'elemento 
alla sinistra di x[0] sia x[n-1].
Si scriva una funzione tale che, dati due vettori x[] ed y[], restituisce '1'
se uno è la rotazione dell'altro, '0' altrimenti.
Dare una stima del tempo di calcolo della vostra funzione.
*/

#include <stdio.h>
#include <malloc.h>

// nei commenti indico con A sempre il 1° vettore e con B sempre il 2°

int* InsVect(int d);
void DeleteArray(int *v);
int Traslazione(int *a,int *b,int size,int tr);

main()
{
  int *v1=NULL,*v2=NULL,dim=0,t=0,i=0,result;
  
  printf("Dimensione del vettore: ");
  scanf("%d",&dim);
  v1=InsVect(dim);
  v2=InsVect(dim);
  
  for(i=0;i<dim;i++)
  {
    // nel ciclo confronto il 1° elemento di A con gli elementi di B;
    // se trovo un elemento di B che corrisponde ad A[0] allora la differenza 
    // tra gli indici sarà una possibile traslazione.
    
    if(v1[0]==v2[i])
    {
      t=i;
      result=Traslazione(v1,v2,dim,t); // 't' è il valore della possibile traslazione
    }
    if(result)
      break;
  }
  if(result)
    printf("Si!\n");
  else
    printf("No!\n");
  
  system("PAUSE");
}

int* InsVect(int size)
{
	int *v=NULL,i;
	
	v=(int*)malloc(size*sizeof(int));
	for(i=0;i<size;i++)
	{
		printf("Valore dell'elemento %d: ",i+1);
		scanf("%d",&v[i]);
	}
	printf("\n");
  return v;
}

int Traslazione(int *a,int *b,int size, int t)
{
  int i=0,j=0,result=1;
  
  for(i=1;i<size-t;i++) // confronto gli elementi di A con quelli di B fino alla fine del vettore B
    if(a[i]!=b[i+t])
    {
      result=0;
      break;
    }
  if(result) // se finora il confronto tra gli elementi ha dato esito positivo...
  {
    for(j=0;j<t;i++,j++) // confronto gli ulteriori elementi (gli ultimi del vettore A e i primi del vettore B se t>0)
      if(a[i]!=b[i-size+t])
      {
        result=0;
        break;
      }
  }
  return result;
}

Compito A - Esercizio 2.c 
/*
Una "coda" è una struttura dati nella quale gli elementi vengono inseriti da 
un lato (coda) ed estratti dall'altro (testa).
Implementare le funzioni di creazione della coda e di inserimento ed estrazione 
di un elemento. Gli elementi sono dei numeri interi.
Dare una stima della complessità computazionale delle vostre funzioni.
*/

#include <stdio.h>
#include <malloc.h>

struct queuenode
{
	int val;
	struct queuenode *next;
};

typedef struct queuenode Node;

void InsertNodo(Node **H,Node **T,int V);
void ExtractNodo(Node **H,Node **T);
void PrintQueue(Node **H,Node **T);
void PrintAndDestroyQueue(Node **H,Node **T);

main()
{
	Node *head=NULL,*tail=NULL;
	int i,n,value;
	printf("# di elementi da inserire: ");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("inserisci l'elemento %d: ",i+1);
		scanf("%d",&value);
		InsertNodo(&head,&tail,value);
	}
	PrintQueue(&head,&tail);
	ExtractNodo(&head,&tail);
	PrintQueue(&head,&tail);
	InsertNodo(&head,&tail,10);
	PrintAndDestroyQueue(&head,&tail);
	getch();
  return 1;
}

void InsertNodo(Node **H,Node **T,int V)
{
	Node *item=NULL;

	if(item=(Node*)malloc(sizeof(Node)))
	{
		item->val=V;
		item->next=NULL;
		if(*H)
		{
			(*T)->next=item;
			*T=item;
		}
		else
		{
			*H=item;
			*T=item;
		}
	}
}

void ExtractNodo(Node **H,Node **T)
{
	Node *temp=NULL;
	if (!(*H)) 
		return;
	temp=(*H)->next;
	free(*H);
	*H=temp;
	if(!(*H))
		*T=NULL;	
}

void PrintQueue(Node **H,Node **T)
{
	Node *temp=*H;
  
  while(temp)
	{
		printf("%2d -> ",temp->val);
		temp=temp->next;
	}
	printf("NULL\n");
}

void PrintAndDestroyQueue(Node **H,Node **T)
{
  while(*H)
  {
    PrintQueue(H,T);
    ExtractNodo(H,T);
  }
  printf("NULL\n");
}



Compito B - Esercizio 0 di sbarramento.c 
/*
Si scriva una funzione che, val una lista di interi ed un intero 'item', 
restituisce il puntatore dell'elemento che contiene item, se esso è presente, 
e NULL altrimenti.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct listNode
{
  int val;
  struct listNode *next;
} Node;

void InsertNode(Node **p,int item);
void PrintList(Node *p);
void DeleteList(Node *p);
Node* FindNode(Node *s,int item);

main()
{
	Node *list=NULL,*start=NULL,*node=NULL;
	int n=0,i=0,item=0;
	
	printf("Numero di elementi da inserire: ");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Valore dell'elemento %d: ",i+1);
		scanf("%d",&item);
		InsertNode(&list,item);
		if(!i)
			start=list;
	}
	PrintList(start);
  printf("Valore da cercare?: ");
  scanf("%d",&item);
  if(node=FindNode(start,item))
    printf("Nodo trovato! \n");
  else
    printf("Nodo assente! \n");    
	DeleteList(start);
	getch();
	return 1;
}

void InsertNode(Node **p,int item)
{
	Node *new=(Node*)malloc(sizeof(Node));

	if(new)
	{
		new->val=item;
		new->next=NULL;
		
		if(!(*p))
      *p=new;
    else
      *p=(*p)->next=new;
	}
	else
    printf("Allocazione della memoria falita! \n");
}

void PrintList(Node *p)
{
  while(p)
  {
    printf("%d -> ",p->val);
    p=p->next;
  }
  printf("NULL\n");
}

void DeleteList(Node *p)
{
	Node *temp=NULL;
	
	while(p->next)
	{
		temp=p;
		p=p->next;
		free(temp);
	}
	free(p);
}

Node* FindNode(Node* p,int item)
{
  while(p)
  {
    if(p->val==item)
      return p;
    else
      p=p->next;
  }
  return p;
}



Compito B - Esercizio 1.c 
/*
Siano date 2 liste di interi 'p' e 'q' e si denoti rispettivamente con 'P' e 'Q' 
l'insieme degli elementi in esse contenute.
Si scriva una funzione che determini se P è un sottoinsieme di Q.
Si dia una stima del tempo di calcolo della vostra funzione.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct listNode
{
  int val;
  struct listNode *next;
} Node;

void InsertNode(Node **s,int item);
void PrintList(Node *s);
void DeleteList(Node *s);
void CheckLenght(int *l,int *num);
int CheckPresence(Node *P,Node *Q);

main()
{
  Node *p=NULL,*sp=NULL,*q=NULL,*sq=NULL;
  int i=0,item=0,number=0,result=0,lp=0,lq=0;
  
  CheckLenght(&lp,&number);
  for(i=0;i<lp;i++)
  {
    printf("Valore dell'elemento %d: ",i+1);
    scanf("%d",&item);
    InsertNode(&p,item);
    if(!i)
      sp=p;
  }

  CheckLenght(&lq,&number);
  for(i=0;i<lq;i++)
  {
    printf("Valore dell'elemento %d: ",i+1);
    scanf("%d",&item);
    InsertNode(&q,item);
    if(!i)
      sq=q;
  }

  printf("P: ");
  PrintList(sp);
  printf("Q: ");
  PrintList(sq);
  
  if(lp>=lq)
    result=CheckPresence(sp,sq);
  else
    result=CheckPresence(sq,sp);
    
  if(result)
    printf("P e' un sottoinsieme di Q \n");
  else
    printf("P non e' un sottoinsieme di Q \n");
  
  DeleteList(sp);
  DeleteList(sq);
  getch();
  return 1;  
}

void CheckLenght(int *l,int *num)
{
  *num+=1;
  if(*num==1)
    printf("Lunghezza della lista P: ");
  if(*num==2)
    printf("Lunghezza della lista Q: ");                  
  scanf("%d",&*l);
}

void InsertNode(Node **p,int item)
{
	Node *new=(Node*)malloc(sizeof(Node));

	if(new)
	{
		new->val=item;
		new->next=NULL;
		
		if(!(*p))
      *p=new;
    else
      *p=(*p)->next=new;
	}
	else
    printf("Allocazione della memoria falita! \n");
}

void PrintList(Node *cur)
{
  while(cur)
  {
    printf("%2d, ",cur->val);
    cur=cur->next;
  }
  printf("NULL \n");
}

void DeleteList(Node *s)
{
  Node *t=NULL;
  
  if(!s)
    return;
  while(s->next)
  {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           
    t=s;
    s=s->next;
    free(t);
  }
  free(s);
}

int CheckPresence(Node *list1,Node *list2)
{
  int r=0;
  
  while(list2)
  {
    if(list1->val==list2->val)
    {
      r=1;
      break;
    }
    else
    {
      list2=list2->next;
    }
  }
  if(!r)
    return 0;
  else
    list1=list1->next;
}



Compito B - Esercizio 2.1.c 
/*
Dato un vettore 'x[]' di interi, scrivere una funzione che calcoli il numero 
massimo di volte che un numero compare.
Dare una stima della complessità computazionale della vostra funzione.
*/

#include <stdio.h>
#include <malloc.h>

int* CreateArray(int d);
void PrintArray(int *v,int d);
void DeleteArray(int **v);
int CheckPresence(int *v,int d);

main()
{
	int *array=NULL,dim,result=0;

	printf("Dimensione del vettore: ");
	scanf("%d",&dim);
	array=CreateArray(dim);
	PrintArray(array,dim);
	printf("Risultato: %d \n",CheckPresence(array,dim));
	DeleteArray(&array);
	getch();
}

int* CreateArray(int d)
{
	int i;
	int *v=(int*)malloc(d*sizeof(int));

	if(v)
		for(i=0;i<d;i++)
		{
			printf("Valore dell'elemento %d: ",i+1);
			scanf("%d",&v[i]);
		}
	return v;
}

int CheckPresence(int *v,int d)
{
	int i,j,k,r=0;

	for(i=0;i<d;i++)
	{
		for(j=0,k=0;j<d;j++)
		{
			if(v[i]==v[j])
				k++;
		}
		if(k>r)
			r=k;
	}
	return r;
}

void PrintArray(int *v,int d)
{
	int i;

	for(i=0;i<d;i++)
		printf("%2d ",v[i]);
	printf("\n");
}

void DeleteArray(int **v)
{
	free(*v);
	printf("Vettore deallocato \n");
}


Compito B - Esercizio 2.2.c 
/*
Dato un vettore 'x[]' di interi, scrivere una funzione che calcoli il numero 
massimo di volte che un numero compare.
Dare una stima della complessità computazionale della vostra funzione.
*/

#include <stdio.h>
#include <malloc.h>

void GetLenght(int *l);
int* CreateVector(int d);
int MakeCounter(int v,int c,int d);
int Sort(int v,int dim);
int MaxPresence(int *v);
void DeleteVector(int **v);

main()
{
  int *vector=NULL,counter[19]={0},dim=0,i=0,result=0;
  
  GetLenght(&dim);
  vector=CreateVector(dim);
  //min=Sort(vector,dim);
  
  for(i=0;i<dim;i++)
    printf("%d ",vector[i]);
  
  printf ("\n");
  
  for(i=0;i<dim;i++)
    counter[vector[i]]++;
  
  result=MaxPresence(counter);
  printf("%d \n",result);
  
  DeleteVector(&vector);
  getch();
  return 1;
}
void GetLenght(int *l)
{
  printf("Dimensione del vettore?: ");
  scanf("%d",l);
}

int* CreateVector(int d)
{
  int *v=NULL,i;
  
  if(v=(int*)malloc(d*sizeof(int)))
    for(i=0;i<d;i++)
    {
      printf("Valore dell'elemento %d: ",i+1);
      scanf("%d",&v[i]);
    }
  return v;
}

int MakeCounter(int v,int c,int d)
{
  int i;
  
  for(i=0;i<d;i++)

  return c;
}

int MaxPresence(int *v)
{
  void Swap(int *elem1,int *elem2);
  int i;
/*
  for(i=0;i<19-1;i++)
  {
    if(v[i]>v[i+1])
      Swap(&v[i],&v[i+1]);
  }
*/
  for(i=19-1;i>0;i--)
  {
    if(v[i]<v[i-1])
      Swap(&v[i],&v[i-1]);
  }
  return v[i];
}

void Swap(int *elem1,int *elem2)
{
  int temp;
  
  temp=*elem1;
  *elem1=*elem2;
  *elem2=temp;
}

void DeleteVector(int **v)
{
  free(*v);
}



Compito C - Esercizio 0 di sbarramento.c 
/*
Scrivere una funzione che verifica se un vettore di interi dato in input, di 
dimensione nota pari ad 'n', contiene un segmento iniziale della serie di 
Fibonacci.
*/

#include <stdio.h>
#include <malloc.h>

int* CreateArray(int d);
void DeleteArray(int *v);
int Check(int *v,int index,int size);

main()
{
  int *v1=NULL,dim=0,i=0,result=0;
  
  do
  {
    printf("Dimensione del vettore: ");
    scanf("%d",&dim);
  }while(dim<3);
  
  v1=CreateArray(dim);
  
  for(i=0;i<dim;i++)
  {
    if(v1[i]==1)
      result=Check(v1,i,dim);
    if(result)
      break;
  }
  
  if(result)
    printf("Si \n");
  else
    printf("No \n");
  
  DeleteArray(v1);
  
  getch();
  return 1;
}

int* CreateArray(int size)
{
	int *v=NULL,i;
	
	v=(int*)malloc(size*sizeof(int));
	for(i=0;i<size;i++)
	{
		printf("Valore dell'elemento %d: ",i+1);
		scanf("%d",&v[i]);
	}
	printf("\n");
  return v;
}

void DeleteArray(int *v)
{
  free(v);
}

int Check(int *v,int index,int size)
{
  if((v[index+1]==v[index
  ]) && (v[index+2]==v[index]+v[index+1]))
    return 1;
  else
    return 0;
}



Compito D - Esercizio 0 di sbarramento.c 
/*
Scrivere una funzione che, dati in input una lista di interi ed un numero 
intero 'x', restituisca il puntatore al primo elemento più grandedi x, se 
esiste, e NULL altrimenti.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct ListNode
{
  int val;
  struct ListNode *next;
} Node;

void InsertNode(Node **p,int item);
void PrintList(Node *p);
void DeleteList(Node *p);
Node* FindNode(Node *p,int item);

main()
{
	Node *list=NULL,*node=NULL,*start=NULL;
	int n=0,i=0,item=0,x=0;
	
  printf("Numero degli elementi da inserire?: ");
  scanf ("%d",&n);
  for(i=0;i<n;i++)
  {
    printf("Valore dell'elemento %d: ",i+1);
    scanf("%d",&item);
    InsertNode(&list,item);
    if(!i)
      start=list;
  }
  PrintList(start);
  printf("Elemento chiave: ");
	scanf("%d",&x);
	node=FindNode(start,x);
  if(node)
		printf("Nodo trovato, valore: %d \n",node->val);
	else
		printf("Non esiste alcun nodo con valore maggiore di quello inserito (%d)\n",x);
	DeleteList(start);
	getch();
  return 1;
}

void InsertNode(Node **p,int item)
{
	Node *new=(Node*)malloc(sizeof(Node));

	if(new)
	{
		new->val=item;
		new->next=NULL;
		
		if(!(*p))
      *p=new;
    else
      *p=(*p)->next=new;
	}
	else
    printf("Memory allocation failed! \n");
}

void PrintList(Node *p)
{
  while(p)
  {
    printf("%d -> ",p->val);
    p=p->next;
  }
  printf("NULL\n");
}

Node* FindNode(Node *p,int item)
{
  Node *c=NULL;
  
  while(p)
  {
    if(item<p->val)
    {
      c=p;
      break;
    }
    else
    {
      p=p->next;
    }
  }
  return c;
}

void DeleteList(Node *p)
{
	Node *temp=NULL;
	
	while((p)->next)
	{
		temp=p;
		p=(p)->next;
		free(temp);
	}
	free(p);
}


Compito D - Esercizio 1 (by Luca).c 
#include <stdio.h>
#include <malloc.h>

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

typedef struct list Node;

Node* InsertNode(Node *p,int V);
Node* MyAlloc(Node *p,Node **f,int X); // parametro aggiuntivo!! vedi il corpo della funzione per spiegazioni!
void DeleteList(Node *p);
void Print(Node *p);

main()
{
	Node *list=NULL,*node=NULL,*first=NULL;
	int n=0,i=0,data=0,x=0;
	
	printf("Numero di elementi da inserire?: ");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Valore dell'elemento %d?: ",i+1);
		scanf("%d",&data);
		list=InsertNode(list,data);
		if(!i)
			first=list;
	}
	printf("Elemento da inserire?: ");
	scanf("%d",&x);
	node=MyAlloc(first,&first,x);
	if(node)
		printf("Inserimento riuscito!\n");
	else
		printf("Inserimento fallito!\n");
	Print(first);
	DeleteList(first);
	getch();
  return 1;
}

Node* InsertNode(Node *p,int V)
{
	Node *item=(Node*)malloc(sizeof(Node));

	if(item)
	{
		item->val=V;
		item->next=NULL;
		
		if(!p)
			p=item;
		else
			p->next=item;
	}
	else
    printf("Memory allocation failed! \n");
	return item;
}

Node* MyAlloc(Node *p,Node **f,int X)
{
	Node *item=NULL,*temp=NULL,*prev=NULL;
	
	if(item=(Node*)malloc(sizeof(Node)))	
	{
		item->val=X;
		item->next=NULL;

		if(p->val>item->val)
		{
			item->next=p;
			*f=item;
// la funzione è stata corretta perchè se inserisco un elemento in testa alla lista devo aggiornare first
// serve un parametro in piu!
		
			return item;
		}
		
		while(p->next)
		{
			if(p->next->val>item->val)
			{
				item->next=p->next;
				p->next=item;
				return item;
			}
			p=p->next;
		}

		p->next=item;
		return item;
	}
	return NULL;
}

// questa l'ho riscritta, era lei che dava l'errore, non la funzione di inserimento!
// non so cosa avevi combinato ma cosi funziona!
void DeleteList(Node *p)
{
	Node *temp=NULL;
	
	while(p)
	{
		temp=p;
		p=p->next;
		free(temp);
	}
	
}

// questa l'ho aggiunta per vedere se funzionava
void Print(Node *p)
{
	while (p)
	{
		printf("%d ",p->val);
		p=p->next;
	}
}


Compito D - Esercizio 1.c 
/*
Scrivere una funzione che, dati in input una lista di interi ordinata ed un 
valore 'x', inserisca x al posto giusto.
Si può assumere di avere a disposizione una funzione 'InsertItem' che 
restituisce il puntatore ad un elelemto di tipo lista.
Dare una stima dei tempo di calcolo della votra funzione.
*/

#include <stdio.h>
#include <malloc.h>

typedef struct ListNode
{
  int data;
  struct ListNode *next;
} Node;

void InsertNode(Node **p,int item);
void PrintList(Node *p);
void DeleteList(Node *p);
Node* InsertItem(Node **f,Node *p,int item);

main()
{
	Node *list=NULL,*node=NULL,*start=NULL;
	int n=0,i=0,data=0,item=0,x=0;
	
  printf("Numero degli elementi da inserire?: ");
  scanf ("%d",&n);
  for(i=0;i<n;i++)
  {
    printf("Valore dell'elemento %d: ",i+1);
    scanf("%d",&item);
    InsertNode(&start,item);
		if(!i)
			start=list;
	}
  PrintList(start);
  printf("Elemento da inserire?: ");
	scanf("%d",&x);
	node=InsertItem(&start,start,x);
  PrintList(start);
	if(node)
		printf("Inserimento riuscito!\n");
	else
		printf("Inserimento fallito!\n");
	DeleteList(start);
	getch();
  return 1;
}

void InsertNode(Node **p,int item)
{
  Node *new=NULL,*prev=NULL,*cur=NULL;
  
  if(new=(Node*)malloc(sizeof(Node)))
  {
    new->data=item;
    new->next=NULL;
    
    prev=NULL;
    cur=*p;
    
    while(cur && item>cur->data)
    {
      prev=cur;
      cur=cur->next;
    }
    if(!prev)
    {
      new->next=*p;
      *p=new;
    }
    else
    {
      prev->next=new;
      new->next=cur;
    }
  }
}

void PrintList(Node *p)
{
  while(p)
  {
    printf("%2d -> ",p->data);
    p=p->next;
  }
  printf("NULL \n");
}

Node* InsertItem(Node **f,Node *p,int item)
{
  Node *new=NULL,*prev=NULL,*cur=NULL;
  
  if(new=(Node*)malloc(sizeof(Node)))
  {
    new->data=item;
    new->next=NULL;
    
    prev=NULL;
    cur=p;
    
    while(cur && item>cur->data)
    {
      prev=cur;
      cur=cur->next;
    }
    if(prev==NULL)
    {
      new->next=p;
      p=new;
    }
    else
    {
      prev->next=new;
      new->next=cur;
    }
  }
  *f=p;
  return new;
}

void DeleteList(Node *p)
{
	Node *temp=NULL;
	
	while((p)->next)
	{
		temp=p;
		p=(p)->next;
		free(temp);
	}
	free(p);
}



Compito D - Esercizio 2.c 
/*
  In questo esercizio tratteremo alberi binari i cui nodi contengono numeri interi.
  Come di consueto diremo che un nodo x è minore di un nodo y se la chiave contenuta in x è minore di quella contenuta in y.
  Un albero binario si dice PSEUDO-ORDINATO se, dato un qualunque nodo x, esso è maggiore del suo figlio sinistro e minore del suo figlio destro 
  (se il figlio manca la condizione è soddisfatta).
  Si scriva una funzione C che, dato un albero, verifichi se esso è pseudo-ordinato o meno.
  Si può supporre:
    a. che l'albero di input sia completo, cioè che ogni suo nodo eccetto le foglie abbia entrambi i figli;
    b. di poter disporre di una funzione pre-definita ifLeaf(Tree t) che restituisce vero se t è una foglia e falso altrimenti;
  Si dia una stima del tempo di calcolo della vostra funzione.  
*/

#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode
{
	int val;
	struct TreeNode *sx;
	struct TreeNode *dx;
}Node;

Node* CreateTree();
void PrintTree(Node *t);
void DeleteTree(Node *t);
int PseudoOrdinato(Node *t);

main()
{
	Node *root=NULL;
	int i=0;

	root=CreateTree();
	PrintTree(root);
	if(PseudoOrdinato(root))
    printf("L'albero e' di tipo 'pseudo.ordinato' \n");
  else
    printf("L'albero non e' di tipo 'pseudo.ordinato' \n");
  DeleteTree(root);
	getch();
  return 1;
}

Node* CreateTree()
{
	Node *t=NULL;
	int i,n;

	t=(Node*)malloc(sizeof(Node));
  if(t)
	{
    t->sx=t->dx=NULL;
    
    printf("Valore del nodo: ");
  	scanf("%d",&t->val);
    
    printf("# di figli del nodo: ");
    scanf("%d",&n);
    
    while(n<0 && n>2)
    {
      printf("Errore!\nImmettere un valore compreso tra '0' e '2' \n");
      printf("# di figli del nodo: ");
    	scanf("%d",&n);
  	}
  
  	if(n)
  	{
      t->sx=CreateTree();
      if(n==2)
        t->dx=CreateTree();
    }  		
  }
	return t;
}

void PrintTree(Node *t)
{
  if(t)
  {
    int n=0;
    
    if(t->sx)
      n++;
    if(t->dx)
      n++;
    if(n==0)
      printf("%d \n",t->val);
    if(n==1)
      printf("%d <%d> \n",t->val,t->sx->val);
    if(n==2)
      printf("%d <%d> <%d> \n",t->val,t->sx->val,t->dx->val);
    PrintTree(t->sx);
    PrintTree(t->dx);
  }
}

void DeleteTree(Node *t)
{
  if(t)
  {
    DeleteTree(t->sx);
    DeleteTree(t->dx);
    free(t);
  }
}

int PseudoOrdinato(Node *t)
{
  if(!t)
    return 1;
  if(t->sx && t->dx)
  {
    if(!(t->val>t->sx->val && t->val<t->dx->val))
      return 0;
    if(!PseudoOrdinato(t->sx))
      return 0;
    if(!PseudoOrdinato(t->dx))
      return 0;
  }
  else
  if(t->sx)
  {
    if(!(t->val>t->sx->val))
      return 0;
  }
  else
  if(t->dx)
  {
    if(!(t->val<t->dx->val))
      return 0;
  }
}

Compito A - Esercizio 0 di sbarramento.c 
#include <stdio.h>
#include <malloc.h>

typedef struct ListNode
{
  int val;
  struct ListNode *next;
} Node;

void InsertNode(Node **p,int item);
void PrintList(Node *p);
void PrintInverseList(Node *p);
void DeleteList(Node *p);

main()
{
	Node *list=NULL,*node=NULL,*start=NULL;
	int n=0,i=0,val=0,item=0,x=0;
	
  printf("Numero degli elementi da inserire: ");
  scanf ("%d",&n);
  for(i=0;i<n;i++)
  {
    printf("Valore dell'elemento %d: ",i+1);
    scanf("%d",&item);
    InsertNode(&list,item);
    if(!i)
      start=list;
  }
  list=start;
  PrintList(start);
  getch();
  PrintInverseList(start);
	DeleteList(start);
	getch();
  return 1;
}

void InsertNode(Node **p,int item)
{
	Node *new=(Node*)malloc(sizeof(Node));

	if(new)
	{
		new->val=item;
		new->next=NULL;
		
		if(!(*p))
      *p=new;
    else
      *p=(*p)->next=new;
	}
	else
    printf("Memory allocation failed! \n");
}

void PrintList(Node *p)
{
  while(p)
  {
    printf("%d -> ",p->val);
    p=p->next;
  }
  printf("NULL \n");
}

void DeleteList(Node *p)
{
	Node *temp=NULL;
	
	while((p)->next)
	{
		temp=p;
		p=(p)->next;
		free(temp);
	}
	free(p);
}

void PrintInverseList(Node *p)
{
  if(!p)
  {
    printf("NULL -> ");
    return;
  }
  PrintInverseList(p->next);
  printf("%d -> ",p->val);
}



Compito A - Esercizio 1 (1° parte).c 
#include <stdio.h>

void f(int *p);

main()
{
  int v[3]={50,25,10};
  
  f(v);
  printf ("%d %d %d \n", v[0], v[1], v[2]);
  getch();
}

void f(int *p)  //p punta a v[0]
{
  int *q;
  
  q = p + 2;  //q punta a v[2]
  *p = *q;  //v[0]=v[2]
}



Compito A - Esercizio 1 (2° parte).c 
#include <stdio.h>

void f(int *);

main()
{
  int v[3]={10,20,30};
  
  f(v);
  printf ("%d %d %d \n", v[0], v[1], v[2]);
  getch();
}

void f(int *p)  //p punta a v[0]
{
  int *q, r;
  q = p + 2;    //q punta a v[2]
  r = p[1];     //r=v[1]
  *p = *q - r;  //v[0]=v[2]-v[1]
}



Compito A - Esercizio 2.c 
#include <stdio.h>
#include <malloc.h>

typedef struct ListNode
{
  int val;
  struct ListNode *next;
} Node;

void InsertNode(Node **p,int item);
void PrintList(Node *p);
void DeleteList(Node *p);
int CheckPresence(Node *p);

main()
{
	Node *list=NULL,*node=NULL,*start=NULL;
	int n=0,i=0,val=0,item=0,x=0;
	
  printf("Numero degli elementi da inserire: ");
  scanf ("%d",&n);
  for(i=0;i<n;i++)
  {
    printf("Valore dell'elemento %d: ",i+1);
    scanf("%d",&item);
    InsertNode(&list,item);
    if(!i)
      start=list;
  }
  list=start;
  PrintList(start);
  printf("%d \n",CheckPresence(start));
	DeleteList(start);
	getch();
  return 1;
}

void InsertNode(Node **p,int item)
{
	Node *new=(Node*)malloc(sizeof(Node));

	if(new)
	{
		new->val=item;
		new->next=NULL;
		
		if(!(*p))
      *p=new;
    else
      *p=(*p)->next=new;
	}
	else
    printf("Memory allocation failed! \n");
}

void PrintList(Node *p)
{
  while(p)
  {
    printf("%d ",p->val);
    p=p->next;
  }
  printf("NULL \n");
}

void DeleteList(Node *p)
{
	Node *temp=NULL;
	
  while(p)
	{
		temp=p;
		p=p->next;
		free(temp);
	}
	free(p);
}

int CheckPresence(Node *p)          // p punta al primo elemento della lista
{
 int k,r=0;
 Node *s=p;                         // faccio puntare s al primo elemento della lista
 
    while(p)                        // se non esiste p esco (la lista è vuota oppure sonno arrivato alla fine)
    {
        k=0;                        // k tiene il conto dell'occorrenza dell'elemento puntato da p (va azzerata ad ogni ciclo)
        while(s)                    // se non esiste s esco (sonno arrivato alla fine degli elementi da confrontare con p->val)
        {
            if(p->val==s->val)      // se gli elementi sono uguali
                k++;                // incremento il contatore
            s=s->next;              // faccio puntare s all'elemento successivo
        }
        if(k>r)                     // se il numero di occorrenze è maggiore di quello precedente (0 per il primo ciclo)
            r=k;                    // assegno ad r il nuovo risultato
        p=p->next;                  // faccio puntare p all'elemento successivo
        s=p;                        // faccio puntare s all'elemento puntato da p (quelli confrontati prima non li controllo più)
    }
    return r;                       // tirorno r (0 se la lista non esiste, un valore > 0 altrimenti)
}



Compito B - Esercizio 2 (1° parte).c 
#include <stdio.h>

void f(int *);

main()
{
  int v[3]={10,20,30};
  
  f(v);
  printf ("%d %d %d \n", v[0], v[1], v[2]);
  getch();
}

void f(int *p)  //p punta a v[0]
{
  int *q;
  
  q = p + 1;  //q punta a v[1]
  *p = *q;  //v[0]=v[1]
}



Compito B - Esercizio 2 (2° parte).c 
#include <stdio.h>

void f(int *);

main()
{
  int v[3]={10,20,30};
  
  f(v);
  printf ("%d %d %d \n", v[0], v[1], v[2]);
  getch();
}

void f(int *p)  //p punta a v[0]
{
  int *q, r;
  q = p + 1;    //q punta a v[1]
  r = p[2];     //r=v[2]
  *p = *q + r;  //v[0]=v[1]+v[2]
}


Compito B - Esercizio 0 di sbarramento.c 
// Si definisca una struttura dati atta a rappresentare un albero n-ario;
// Si scriva una funzione che, dato in input un albero n-ario, ne calcoli la profondità;

#include <stdio.h>

typedef struct TreeNode
{
  int val;
  int n;
  struct TreeNode **child;
} Node;

Node* GetTree();
int CheckTree(Node *curNode,int depth,int maxDepth);
void DeallocaTree(Node *curNode);

main()
{
  int depth=-1,maxDepth=-1,result;
  Node *tree=NULL;
  
  tree=GetTree();
  printf("Passo al controllo della profondita'.\n");  
  result=CheckTree(tree,depth,maxDepth);
  if(result==-1) 
  {
    printf("L'albero sembra non esistere\n");
    system("PAUSE");
    return 0;
  }
  else
  {
    printf("%d\n",result);
    getch();
    DeallocaTree(tree);
    system("PAUSE");
    return 1;
  } 
}

Node* GetTree()
{
	int i=0;
  Node *curNode=NULL;
  
  if(curNode=(Node*)malloc(sizeof(Node)))
  {
//  printf("Valore del nodo: ");
//  scanf("%d",&(curNode->val));
    printf("# di figli del nodo: ");
    scanf("%d",&(curNode->n));
    
    if(curNode->n>0)
      if(curNode->child=(Node**)malloc(curNode->n*sizeof(Node*)))
        for(i=0;i<curNode->n;i++)
          curNode->child[i]=GetTree();
  }
  return curNode;
}

int CheckTree(Node *curNode,int depth,int maxDepth)
{
  int i,temp;
  
  if(!curNode)
    maxDepth=depth;
  else
  {
    depth++;  //il nodo esiste, quindi lo esploro e incremento il livello
    if(depth>maxDepth)  //se il livello attuale è > di quello massimo raggiunto finora
      maxDepth=depth;   //assegno al livello massimo il valore di quello attuale
    for(i=0;i<curNode->n;i++)  //finchè esiste un nodo figlio lo esploro
    {
      temp=CheckTree(curNode->child[i],depth,maxDepth);
      if(temp>maxDepth)  //se il livello attuale è > di quello massimo raggiunto finora
        maxDepth=temp;   //assegno al livello massimo il valore di quello attuale
    }      
    depth--;  //non ci sono nodi figli, quindi torno indietro e decremento il livello
  }
  return maxDepth;
}

void DeallocaTree(Node *curNode)
{
  int i=0;
  
  if(curNode)
  {
    for(i=0;i<curNode->n;i++)
      DeallocaTree(curNode->child[i]);
    free(curNode);
  }
  else
  {
    printf("(DeallocaTree) L'albero sembra non esistere. \n");
  }
}

Compito B - Esercizio 1.c 
/*
Un root binario contenente numeri interi si dice "panciuto" se esso contiene
un elemento 'x' il cui valore è pari alla somma degli elementi contenuti nel 
suo sottoalbero.
Si scriva una funzione che verifichi se un root è panciuto o meno.
(Suggerimento: la funzione può restituire un puntatore ad una 'struct')
*/

#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode
{
	int val;
	struct TreeNode *sx;
	struct TreeNode *dx;
} Node;

Node* CreateTree();
void PrintTree(Node *item);
void DeleteTree(Node *item);
int Sum(Node *nodo,Node **Ptr);

int main()
{
  Node *root=NULL,*temp=NULL;
  
	root=CreateTree();
	PrintTree(root);
	Sum(root,&temp);
	if(temp)
		printf("Node panciuto= %d\n",temp->val);
	DeleteTree(root);
	return 1;
}

Node* CreateTree()
{
	int existSx=0;
	int existDx=0;
	Node *item=(Node*)malloc(sizeof(Node));
	item->val=0;
	item->sx=NULL;
	item->dx=NULL;

	printf("valore del nodo: ");
	scanf("%d",&(item->val));
	printf("esiste il figlio sinistro/destro?: ");
	scanf("%d%d",&existSx,&existDx);
	if (existSx)
		item->sx=CreateTree();
	if (existDx)
		item->dx=CreateTree();

	return item;
}

void PrintTree(Node* item)
{
	if (!item)
    return;

	printf("%d\n",item->val);
	PrintTree(item->sx);
	PrintTree(item->dx);
}

void DeleteTree(Node *item)
{
	if(!item)
    return;
  
	if(item->sx)
		DeleteTree(item->sx);
	if(item->dx)
    DeleteTree(item->dx);
  
	free(item);
}

Sum(Node *item,Node **Ptr)
{
	int s;
	
	if(!item)
		return 0;
	s=Sum(item->sx,Ptr)+Sum(item->dx,Ptr);
	if(s==item->val)
		*Ptr=item;
	return s+item->val;
}



Compito B - Esercizio 2.c 
/*
Un albero n-ario contenente numeri interi si dice "patriarcale" se nessun nodo 
ha un figlio di valore maggiore.
Si scriva una funziona che, dato in input un albero n-ario, verifichi se esso è 
patriarcale.
Si dia una stima della complessità computazionale della vostra procedura.
*/

#include <stdio.h>
#include <malloc.h>

struct node
{
	int val;
	int n;
	struct node **child;
};

struct node* CreateTree();
int Depth(struct node *nodo, int n);
void DeleteTree(struct node *nodo);
int Patriarcale(struct node *nodo);

main()
{
	struct node *radice=NULL;
	int p=0;

	radice=CreateTree();
	p=Depth(radice,0);
	printf("%d\n",p);
	if(Patriarcale(radice))
		printf("Yeah!\n");
	else
		printf("No!\n");
	DeleteTree(radice);
	system ("PAUSE");
  return 1;
}

struct node* CreateTree()
{
	struct node *nodo=NULL;
	int i;

	if(!(nodo=(struct node*)malloc(sizeof(struct node))))
		return NULL;

	printf("Valore del nodo: ");
	scanf("%d",&nodo->val);

  printf("# di figli del nodo: ");
  scanf("%d",&nodo->n);
  while (nodo->n<0)
  {
    printf("Errore!\nImmettere un valore maggiore di zero.\n");
    printf("# di figli del nodo: ");
  	scanf("%d",&nodo->n);
	}

	if(nodo->n>0)
	{
		if(nodo->child=(struct node**)malloc(nodo->n*sizeof(struct node*)))
		{
    	for(i=0;i<(nodo->n);i++)
    		nodo->child[i]=CreateTree();
		}
   }
	else
		nodo->child=NULL;
	return nodo;
}

int Depth(struct node *nodo,int level)
{
	int p=0,i=0,depth=0;

	if(nodo->n>0)
  {
  	level++;
  	for(i=0;i<(nodo->n);i++)
  	{
  		if(nodo->child[i])
  			p=Depth(nodo->child[i],level);
  
  		if(p>depth)
  			depth=p;
    }
	level=depth;
	}
	return level;
}

int Patriarcale(struct node *nodo)
{
	int i,result=1;
	
	if(nodo)
  {
  	for(i=0;i<nodo->n;i++)
  		if(nodo->val<nodo->child[i]->val)
  			return 0;
  	for(i=0;i<nodo->n;i++)
  	{
  		result=Patriarcale(nodo->child[i]);
  		if(!result)
  			break;
  	}
	}
	return result;
}


void DeleteTree(struct node *nodo)
{
  int i=0;
  
  if(nodo)
  {
    for(i=0;i<nodo->n;i++)
      DeleteTree(nodo->child[i]);
  }
  free(nodo);
}


Gestione di una lista doppiamente linkata.c 
/*
	Gestione di una lista doppiamente linkata:
	add <intero>	aggiunge un nodo subito dopo il nodo corrente
	del		elimina il nodo corrente e setta il nodo corrente al nodo precedente (successivo se non esiste)
	print		stampa la lista con un asterisco a fianco del nodo corrente
	next		seleziona il prossimo nodo
	prev		seleziona il nodo precedente
	sort		ordina la lista con merge-sort
*/

#include <stdio.h>

/* definizione della struttura del nodo */
typedef
	struct nodo {
		int valore;
		struct nodo * next;
		struct nodo * prev;
	} Nodo ;

#define MAXLINE 1000
#define TRUE 1
#define FALSE 0

void add(Nodo ** lista, Nodo ** corrente, int valore);
void del(Nodo ** lista, Nodo ** corrente);
void prev(Nodo ** corrente);
void next(Nodo ** corrente);
void print(Nodo * lista, Nodo * corrente);
void sort(Nodo ** lista);
Nodo * merge(Nodo * L1, Nodo * L2); 
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari);
void push(Nodo * elemento, Nodo ** lista);

int main(int argc, char * argv[]) {
	char	riga[MAXLINE] = { 0 };
	int	 val	 = 0;
	Nodo * lista	 = NULL;
	Nodo * corrente = NULL;

	scanf("%[^\n]",riga);
	while (0 != strcmp(riga,"fine")) {
		if (1 == sscanf(riga,"add%*[ ]%d",&val))
			add(&lista, &corrente, val);
		else 
		if (0 == strcmp(riga,"del")) {
			if (lista != NULL)
				del(&lista, &corrente);
			else 
				printf("vuota\n");
		} else 
		if (0 == strcmp(riga,"next"))
			next(&corrente);
		else 
		if (0 == strcmp(riga,"prev"))
			prev(&corrente);
		else 
		if (0 == strcmp(riga,"sort")) {
			if (lista != NULL)
				sort(&lista);
			else 
				printf("vuota\n");
		} else 
		if (0 == strcmp(riga,"print")) {
			if (lista != NULL)
				print(lista, corrente);
			else 
				printf("vuota\n");
		};
		scanf("\n%[^\n]",riga);
	}
}

/*
	Aggiungo un nuovo nodo alla lista
*/
void add(Nodo ** lista, Nodo ** corrente, int valore)
{
	/* alloco un nuovo nodo */
	Nodo * nuovo = (Nodo*)malloc(sizeof(Nodo));
	nuovo->valore = valore;
	nuovo->next = NULL;
	nuovo->prev = NULL;

	/* caso speciale del primo nodo */
	if (*lista == NULL) {
		*lista = nuovo;
		*corrente = nuovo;
		return;
	}

	/* taglia e cuci della lista */
	if (*corrente != NULL) {
		nuovo->next = (*corrente)->next;
		nuovo->prev = *corrente;
		(*corrente)->next = nuovo;
		if (nuovo->next != NULL)
			nuovo->next->prev = nuovo;
	}

	/* aggiorno il cursore  */
	*corrente = nuovo;
}

/*
	Elimino il nodo corrente
*/
void del(Nodo ** lista, Nodo ** corrente)
{	
	Nodo * dacancellare = *corrente;
	if (*corrente == NULL) 
		return;

	/* il prossimo nodo (se c'e') diventa il nodo corrente */
	if ((*corrente)->next != NULL)
		*corrente = (*corrente)->next;
	else
		*corrente = (*corrente)->prev;

	/* taglia e cuci della lista */
	if (dacancellare->prev != NULL)
		dacancellare->prev->next = dacancellare->next;
	if (dacancellare->next != NULL)
		dacancellare->next->prev = dacancellare->prev;
	if (*lista == dacancellare)
		*lista = dacancellare->next;

	/* libero la memoria */
	free(dacancellare);
}

/*
	Mi sposto sul nodo precedente
*/
void prev(Nodo ** corrente)
{
	if (*corrente == NULL || (*corrente)->prev == NULL)
		return;
	else
		*corrente = (*corrente)->prev;
}

/*
	Mi sposto sul nodo successivo
*/
void next(Nodo ** corrente)
{
	if (*corrente == NULL || (*corrente)->next == NULL)
		return;
	else
		*corrente = (*corrente)->next;
}

/*
	Stampa della lista
*/
void print(Nodo * lista, Nodo * corrente)
{
	if (lista == NULL) return;
	if (lista == corrente)
		printf("%d *\n",lista->valore);
	else	
		printf("%d\n",lista->valore);
	print(lista->next,corrente);
}

/*
	Mergesort della lista
*/
void sort(Nodo ** lista)
{
	Nodo * pari = NULL;
	Nodo * dispari = NULL;

	/* caso base, 0 o 1 elementi */
	if (*lista == NULL) return;
	if ((*lista)->next == NULL) return;
	
	/* divido la lista in due gruppi di pari dimensioni */
	split(*lista,&pari,&dispari);

	/* ordino le due parti */
	sort(&pari);
	sort(&dispari);

	/* ora che sono ordinate le posso fondere */
	*lista = merge(pari,dispari);
}

/*
	merge distruttivo di due liste doppiamente linkate e ordinate
*/
Nodo * merge(Nodo * L1, Nodo * L2) 
{	
	Nodo * minore = NULL;
	/* casi base */
	if (L1 == NULL) return L2;
	if (L2 == NULL) return L1;
	/* trovo il minore */
	if (L1->valore < L2->valore) {
		minore = L1;
		minore->next = merge(minore->next,L2);
	} else {
		minore = L2;
		minore->next = merge(L1,minore->next);
	}
	/* aggiusto il legame inverso */
	if (minore->next != NULL)
		minore->next->prev = minore;
	/* torno il primo nodo */
	return minore;
}

/*
	divido una lista in due (elementi in posizione pari/dispari)
*/
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari)
{
	/* caso base: nessun elemento */
	if (lista == NULL) {
		*pari = NULL;
		*dispari = NULL;
		return;
	}
	/* se ci sono almeno 2 elementi ricorro saltando i primi due 
		ed ottengo il resto della lista separato in pari e dispari */
	if (lista->next != NULL)
		split(lista->next->next,pari,dispari);

	/* aggiungo i due elementi iniziali a pari e dispari */
	/* prima il secondo (se c'e') */
	if (lista->next != NULL) 
		push(lista->next,dispari);
	/* poi il primo */
	push(lista,pari);
}

void push(Nodo * elemento, Nodo ** lista) 
{
	if (*lista != NULL)
		(*lista)->prev = elemento;
	elemento->next = *lista;
	*lista = elemento;
}


bucket-sort.c 
/*
	 HomeWork3: bucket-sort
	 Usiamo le seguenti strutture dati:
	 - vettore contenente i valori da ordinare
	 - matrice per eseguire le passate
	 - vettore di 10 elementi che tiene il conto di quanti sono inseriti in ciascuna riga della matrice
*/

#include <stdio.h>
#include <limits.h>
 
/* numero di valori in input */
#define SIZE 50
/* i valori vengono considerati come numeri in base 10 */
#define RANGE 10
 
/*
	esegue una passata per la potenza data
	- trasferisce da vettore a matrice
	- rimette nel vettore
	- azzera il vettore che conta quanti numeri sono inseriti in ciascuna riga della matrice
	- torna il valore
		'1' se tutti i valori sono minori della potenza corrente
		'0' se ce n'e' uno maggiore o uguale
*/
int passata(int valori[SIZE], int matrice[RANGE][SIZE], int potenza)
{
	int inseriti[RANGE] = { 0 };	/* numero di elementi inseriti in ciascuna riga della matrice */
	int tuttiminori = 1;		/* indicatore che tutti i valori sono minori della potenza */
	int cifra = 0;			/* cifra corrente */
	int i, j, k;

	/* azzero il numero di numeri inseriti in ciascuna riga*/
	for (i=0 ; i < RANGE ; i++)
		inseriti[i] = 0;

	/* facciamo una passata */
	for (i=0 ; i<SIZE ; i++) {
		/* calcolo la cifra corrente del valore corrente*/
		cifra = (valori[i] / potenza) % 10;
		/* inserisco il valore nella riga giusta ed incremento il conteggio degli elementi presenti */
		matrice[cifra][inseriti[cifra]++] = valori[i];
		/* se il valore corrente è maggiore della prossima potenza devo ripetere la passata */
		/* faccio il confronto dopo un cast a double per essere sicuro di gestire numeri vicino a INT_MAX */
		if (valori[i] >= (double)potenza*10)
			tuttiminori = 0;
	}

	/* ricopiamo i valori indietro nel vettore di appoggio nell'ordine giusto */
	k = 0;
	for (i=0 ; i < RANGE ; i++)
		for (j=0 ; j < inseriti[i] ; j++)
			valori[k++] = matrice[i][j];

	/* faccio sapere se serve un'altra passata */
	return tuttiminori;
}

/* programma principale */
int main(int argc, char * argv[]) {
	 /* dichiarazioni */
	 int matrice[RANGE][SIZE] = { 0 };	/* matrice */
	 int valori[SIZE] = { 0 };		/* vettore di appoggio dei valori */
	 int i;
	 int potenza = 1;			/* potenza di dieci corrente */
	 int passate = 1;			/* conteggio delle passate */
	 int tuttiminori = 0;		/* indicatore=1 se tutti i valori sono minori della prossima potenza */

	 /* lettura degli input */
	 for (i=0 ; i<SIZE ; i++)
		  scanf("%d",&valori[i]);

	 /* ciclo per le varie potenze di 10 crescenti */
	 while (tuttiminori==0) {
		 tuttiminori = passata(valori, matrice, potenza);
		 potenza *= 10;
		 passate ++;
	 }

	 /* output dei valori (che sono tornati nel vettore di appoggio) */
	 for (i=0 ; i<SIZE ; i++)
		  printf("%d\n",valori[i]);

	 /* stampa del numero di passate */
	 printf("%d\n",passate);

	 return 0;
}


funzioni ricorsive.c 
/*
	 HomeWork5: funzioni ricorsive
*/
#include <stdio.h>

/* struct usata da fibonacci_efficiente (versione che torna una coppia) */
typedef struct {
		int last;
		int prev;
} coppia;

/* array che 'ricorda' i valori calcolati (solo fino a 50) */
int memo[50] = { 0 };
int memo1[50] = { 0 };

/* prototipi delle funzioni usate */
void traccia(int x, int p);
void traccia2(int x, int y, int p);
int fattoriale(int x,int p);
int fibonacci(int x, int p);
coppia fibonacci_efficiente(int x, int p);
int fibonacci_memo(int x, int p);
int quarantadue(int x, int p);
int emme(int x, int p);		
int emme_memo(int x, int p);		/* ricorda la sola m 		*/
int emme_memo_memo(int x, int p);	/* ricorda sia m che g 		*/
int GCD(int x, int y, int p);

/************************************************************************/
int main(int argc, char * argv[]) {
	/* dichiarazioni */
	int x = 0,
		 y = 0;
	int prof = 1;	/* profondita` */
	 
	/* controllo l'input */
	if (argc>4 || argc<2) 
		 return 1;
	if (argv[1][0] != '-') 
		 return 1;
	
	/* leggo 2' (e 3') argomento */
	if (argc>2)
		 x = atoi(argv[2]);
	if (argc>3)
		 y = atoi(argv[3]);
	
	/* seleziono la funzione a seconda del secondo carattere dell'opzione */
	switch (argv[1][1]) {
	case 'f':
		 y = fattoriale(x,prof);
		 printf("%d\n",y);
		 break;
	case 'F':
		 y = fibonacci(x,prof);
		 printf("%d\n",y);
		 break;
	case 'E':
		 y = fibonacci_efficiente(x,prof).last;
		 printf("%d\n",y);
		 break;
	case 'A':
		 y = fibonacci_memo(x,prof);
		 printf("%d\n",y);
		 break;
	case 'G':
		 if (x>y)
		y = GCD(y,x,prof);
		 else
		y = GCD(x,y,prof);
		 printf("%d\n",y);
		 break;		 
	case 'h':
		 y = quarantadue(x,prof);
		 printf("%d\n",y);
		 break;
	case 'v':
		 break;
	case 'm':
		 y = emme(x,prof);
		 printf("%d\n",y);
		 break;
	case 'M':
		 y = emme_memo(x,prof);
		 printf("%d\n",y);
		 break;
	case 'D':
		 y = emme_memo_memo(x,prof);
		 printf("%d\n",y);
		 break;
	default:
		 return 1;
	}
	return 0;
}

/*************************************************************************/
void traccia(int x, int p)
{
	 int i;
	 for (i=0;i<p;i++)
	printf("*");
	 printf(" %d\n",x);
}

void traccia2(int x, int y, int p)
{
	 int i;
	 for (i=0;i<p;i++)
	printf("*");
	 printf(" %d %d\n",x,y);
}

/*************************************************************************/
int fattoriale(int x,int p)
{
	 traccia(x,p);
	 if (0==x)
	return 1;
	 else
	return x * fattoriale(x-1,p+1);
}

/*************************************************************************/
/*
 * fibonacci-ricorsiva-di-Sterbini-che-non-si-ricorda-il-caso-base
 */
int fibonacci(int x, int p)
{
	 traccia(x,p);
	 if (0==x || 1==x)
	return 1; 
	 else
	return fibonacci(x-1,p+1) + fibonacci(x-2,p+1);
}

/* questa implementazione torna i due valori F(n) e F(n-1) da cui calcola
 * F(n+1) e F(n)
 * usiamo una struct 'coppia' per tornare i due valori
 */
coppia fibonacci_efficiente(int x, int p)
{
	 int y;
	 coppia c={1,1};
	 traccia(x,p);
	 if (x>1) {
	c = fibonacci_efficiente(x-1,p+1);
	y = c.prev + c.last;
	c.prev = c.last;
	c.last = y;
	 };	
	 return c;
}

/* questa funzione 'ricorda' i valori calcolati in modo da non doverli
 * ricalcolare
 */
int fibonacci_memo(int x, int p)
{
	 int result = 0;
	 traccia(x,p);
	 
	 /* se gia' l'ho calcolato lo prendo dal vettore */
	 if (memo[x] != 0)
	return memo[x];
	 
	 /* altrimenti lo calcolo nel modo standard */
	 if (x == 0 || x == 1) 
	result = 1;
	 else
	result = fibonacci_memo(x-1, p+1) + fibonacci_memo(x-2, p+1);

	 /* e mi ricordo il risultato */
	 memo[x] = result;
	 return result;
}

/*************************************************************************/
int quarantadue(int x, int p)
{
	 traccia(x,p);
	 if (0==x)
	return 42;
	 else
	return 2*x + quarantadue(x-1,p+1);
}

/*************************************************************************/
/*
#  m(0) = 0
# m(x) = m(x-1) + 2*g(x)
# g(0) = 1
# g(x) = g(x-1) - 2*m(x-1) 
*/

int gi(int x, int p); /* prototipo necessario per la chiamata doppiamente ricorsiva*/
int emme(int x, int p)
{
	 traccia(x,p);
	 if (0==x)
	return 0;
	 else
	return emme(x-1,p+1) + 2 * gi(x,p+1);
}

int gi(int x, int p)
{
	 traccia(x,p);
	 if (0==x)
	return 1;
	 else
	return gi(x-1,p+1) - 2 * emme(x-1,p+1);
}


/* versione che memorizza i risultati della sola 'm' */
int gi_memo(int x, int p)
{
	 traccia(x,p);
	 if (0==x)
	return 1;
	 else
	return gi_memo(x-1,p+1) - 2 * emme_memo(x-1,p+1);
}

int emme_memo(int x, int p)
{
	 int result = 0;
	 traccia(x,p);

	 /* se gia' l'ho calcolato lo prendo dal vettore */
	 if (memo[x] != 0)
	return memo[x];
	 
	 if (0==x)
	result = 0;
	 else
	result = emme_memo(x-1,p+1) + 2 * gi_memo(x,p+1);
	
	 memo[x] = result;
	 return result;
}

/* versione che memorizza i risultati sia di 'm' che di 'g' */
int gi_memo_memo(int x, int p)
{
	 int result = 0;
	 traccia(x,p);

	 /* se gia' l'ho calcolato lo prendo dal vettore */
	 if (memo1[x] != 0)
	return memo1[x];

	 if (0==x)
	result = 1;
	 else
	result = gi_memo_memo(x-1,p+1) - 2 * emme_memo_memo(x-1,p+1);

	 memo1[x] = result;
	 return result;
}

int emme_memo_memo(int x, int p)
{
	 int result = 0;
	 traccia(x,p);

	 /* se gia' l'ho calcolato lo prendo dal vettore */
	 if (memo[x] != 0)
	return memo[x];
	 
	 if (0==x)
	result = 0;
	 else
	result = emme_memo_memo(x-1,p+1) + 2 * gi_memo_memo(x,p+1);
	
	 memo[x] = result;
	 return result;
}

/*************************************************************************/
/*
 * Minimo Comune Multiplo calcolato ricorsivamente 
 * usando l'algoritmo di Eulero
 */
int GCD(int x, int y, int p) {
	 traccia2(x, y, p);
	 
	 if (x == 0)
	return y;
	 else
	return GCD(y%x,x,p+1);
}



simple bucket-sort.c
/*
	 HomeWork2: simple bucket-sort
*/
#include <stdio.h>
#define NVAL 20
#define MIN -84
#define MAX 531
int main(int argc, char * argv[]) {
	 /* dichiarazioni */
	 int frequenze[MAX-MIN+1] = { 0 };
	 int i = 0, j = 0;
	 int valore = 0;

	 /* lettura dei valori dall'input */
	 for (i=0 ; i < NVAL ; i++) {
		  scanf("%d",&valore);
		  frequenze[valore-MIN]++;
	 }
	 /* ciclo di stampa */
	 for (i=0 ; i < MAX-MIN+1 ; i++)
	 for (j=0 ; j < frequenze[i] ; j++)
		  printf("%d\n",i+MIN);
	 return 0;
}