STRUTTURE DATI

Ogni software che si rispetti gestisce dati. Essi possono essere anche i 
parametri di configurazione dello stesso software, piuttosto che dati per
l'utente oppure per velocizzare certe funzioni. Gli esempi si sprecano
e man mano che affronterò un algoritmo cercherò validi esempi.

Gli algoritmi che vado a mostrarvi sono quattro:

 - code
 - stack
 - liste (semplice o concatenata)
 - alberi
 - tabelle hash

Le code sono sono elenchi di informazioni che si basano sul principio FIFO 
(First In - First Out). Un esepio di codice è questo:

--- inizio ---
#define MAX 100

char *coda[MAX];
int inizio, fine;

int coda_store(char *str) {
  if(fine==MAX) return 1;
  coda[fine]=str;
  fine++;
  return 0;
}

char *coda_retrieve(void) {
  if(inizio==fine) return NULL;
  inizio++;
  return coda[inizio-1];
}
--- fine ---

Facile intuire che l'utilizzo della coda è abbastanza limitato in questo modo.
Conviene sicuramente farla circolare in modo da avere sempre la totalità della
sua dimensione utilizzabile.
Il codice è questo:

--- inizio ---
#define MAX 100

char *coda[MAX];
int inizio, fine;

int coda_store(char *str) {
  if(fine==inizio-1 || (fine==MAX && !inizio)) return 1;
  coda[fine]=str;
  if(fine==MAX) fine=0;
  return 0;
}

char *coda_retrieve(void) {
  if(inizio==MAX) inizio=0;
  if(inizio==fine) return NULL;
  inizio++;
  return coda[inizio-1];
}
--- fine ---

La coda si definise finita quando la fine è l'inizio oppure, dato che la 
circolarità è solo fittizia, quando la fine è reale e l'inizio è a 0.

Nulla vieta però di complicare le cose e di creare una struttura coda di questo
tipo:

typedef char TYPE;

/* CODA */
typedef struct {
 TYPE *array;
 int testa;
 int coda;
 int n_elementi;
} coda;

Ho creato il TYPE in modo che non dobbiate più dipendere solo dai char ma
possiate decidere anche di usare gli int o altri tipi di variabili.

Poi funzioni più elaborate di gestione delle code rispetto a quelle mostrate
prima. Eccole:

--- inizio ---
coda *coda_init(int n);
int coda_push(coda **stuttura,TYPE elemento);
TYPE coda_pop(coda **stuttura);
int coda_empty(coda *stuttura);
int coda_full(coda *stuttura);
void coda_free(coda *stuttura);


/* Inizializzo una struttura */
coda *coda_init(int n) {
 coda *tmp;

 if((tmp=(coda *)malloc(sizeof(coda)))==NULL) return NULL;
 
 if((tmp->array=(TYPE *)malloc(n * sizeof(TYPE)))==NULL) {
  free(tmp);
  return NULL;
 }
 
 tmp->testa=-1;
 tmp->coda=0;
 tmp->n_elementi=n;
 return tmp;
}

/* Inserisco un valore */
int coda_push(coda **struttura, TYPE elemento) {

 if(coda_full(*struttura)) return 1;
 
 if((*struttura)->coda==(*struttura)->n_elementi) (*struttura)->coda=0;
 (*struttura)->array[(*struttura)->coda]=elemento;
 (*struttura)->coda++;
 
 return 0;
}

/* Cancello un valore */
TYPE coda_pop(coda **struttura) {

 if(!coda_empty(*struttura)) return -1;
 
 if((*struttura)->testa==(*struttura)->n_elementi-1) (*struttura)->testa=0;
 else                                                (*struttura)->testa++;

 return (*struttura)->array[(*struttura)->testa];
}

/* Controlla se e' pieno o no l'array */
int coda_full(coda *struttura) {
 if((struttura->testa==-1 && struttura->coda==struttura->n_elementi) ||
                                  struttura->coda==struttura->testa-1) 
   return 1;
 return 0;
}

/* Controlla se e' vuoto o no l'array 
 * Torna 0 se e' vuoto
 * Torna 1 se non lo e'.
 */
int coda_empty(coda *struttura) {
 if(struttura->testa==struttura->coda-1) return 0;
 return 1;
}

/* Libera la struttura */
void coda_free(coda *struttura) {
 free(struttura->array);
 free(struttura);
}
--- fine ---

Un esempio di una struttura dati come questa può essere una agenda di 
appuntamenti. Messi in ordine gli appuntamenti sono tutti sequenziali.

STACK

Gli stack sono dei contenitori di dati basati sul LIFO (Last In - First Out).
Sono usati ovunque, pure la ram dei vostri programmi è usata secondo algoritmi
di stack.

Ecco come potrebbe essere una implementazione di uno stack modificando
la coda sopra mostrata:

--- inizio ---
/* STACK */
typedef struct {
 TYPE *array;
 int coda;
 int n_elementi;
} stack;


stack *stack_init(int n);
int stack_push(stack **stuttura,TYPE elemento);
TYPE stack_pop(stack **stuttura);
int stack_empty(stack *stuttura);
int stack_full(stack *stuttura);
void stack_free(stack *stuttura);

/* Inizializzo una struttura */
stack *stack_init(int n) {
 stack *tmp;

 if((tmp=(stack *)malloc(sizeof(stack)))==NULL) return NULL;
 
 if((tmp->array=(TYPE *)malloc(n * sizeof(TYPE)))==NULL) {
  free(tmp);
  return NULL;
 }
 
 tmp->coda=0;
 tmp->n_elementi=n;
 return tmp;
}

/* Inserisco un valore */
int stack_push(stack **struttura, TYPE elemento) {

 if(stack_full(*struttura)) return 1;
 
 (*struttura)->array[(*struttura)->coda]=elemento;
 (*struttura)->coda++;
 
 return 0;
}

/* Cancello un valore */
TYPE stack_pop(stack **struttura) {
 if(!stack_empty(*struttura)) return -1;

 (*struttura)->coda--;
 return (*struttura)->array[(*struttura)->coda];
}

/* Controlla se e' pieno o no l'array */
int stack_full(stack *struttura) {
 if(struttura->coda==struttura->n_elementi) return 1;
 return 0;
}

/* Controlla se e' vuoto o no l'array 
 * Torna 0 se e' vuoto
 * Torna 1 se non lo e'.
 */
int stack_empty(stack *struttura) {
 if(struttura->coda) return 0;
 return 1;
}

/* Libera la struttura */
void stack_free(stack *struttura) {
 free(struttura->array);
 free(struttura);
}
--- fine ---

Lo stack non è affatto complesso e non mi ci soffermo.

LISTE

Algoritmi enormemente più interessanti sono le liste.
Grazie ad una struttura simile a questa:

typedef struct lista_s1 {
 char nome[MAX];
 struct lista_s1 *next;
} lista_s;

Posso creare N strutture una linkata all'altra grazie ad un puntatore.
Imposto il puntatore struct lista_s1 *next; alla struttura successiva
e in questo modo creo liste di strutture unite.

Ecco qui delle funzioni che possono esserci utili:

--- inizio ---
int lista_s_insert(char *nome, lista_s **inzio, lista_s **fine);
lista_s *lista_s_search(char *nome, lista_s *inizio);
void lista_s_delete(lista_s *lista, lista_s **inizio, lista_s **fine);

/* Inserisce una nuova struttura non ordinando */
int lista_s_insert(char *nome, lista_s **inizio, lista_s **fine) {
 lista_s *tmp;

 if((tmp=(lista_s *)malloc(sizeof(lista_s)))==NULL) return 1;

 strcpy(tmp->nome,nome);
 tmp->next=NULL;
 
 if(*inizio==NULL) *fine=NULL;
 
 if(*fine==NULL) {
  *fine=tmp;
  *inizio=tmp;
  return 0;
 } 

 (*fine)->next=tmp;
 *fine=tmp;
 return 0;
 
}

/* Cerca una struttura */
lista_s *lista_s_search(char *nome, lista_s *inizio) {

 if(inizio==NULL) return NULL;

 while(inizio) {
  if(!strcmp(inizio->nome,nome)) return inizio;
  inizio=inizio->next;
 }
 return NULL;
}

/* Cancella una struttura */
void lista_s_delete(lista_s *lista, lista_s **inizio, lista_s **fine) {
 
 lista_s *tmp;

 if(lista==NULL)   return;
 if(*fine==NULL)   return;
 if(*inizio==NULL) return;

 if(lista==*inizio) {
  *inizio=lista->next;
  free(lista);
  return;
 }

 tmp=*inizio;

 while(tmp->next) {
  if(!strcmp(tmp->next->nome,lista->nome)) {
   if(tmp->next==*fine) {
    tmp->next=NULL;
    *fine=tmp;
    free(lista);
    return;
   }
   tmp->next=lista->next;
   free(lista);
   return;
  }
  tmp=tmp->next;
 }

 *fine=tmp;
 free(lista);
}
--- fine ---

Queste funzioni sono abbastanza intuitive.
Non lo è affatto una funzione che vuole ordinare la struttura che si vuole
inserire:

/* Inserisce una nuova struttura ordinando */
int lista_s_insert_order(char *nome, lista_s **inizio, lista_s **fine) {
 lista_s *tmp, *a, *b;

 if((tmp=(lista_s *)malloc(sizeof(lista_s)))==NULL) return 1;

 strcpy(tmp->nome,nome);
 
 if(*inizio==NULL) *fine=NULL;

 if(*fine==NULL) {
  tmp->next=NULL;
  *fine=tmp;
  *inizio=tmp;
  return 0;
 }

 a=*inizio;
 b=NULL;
 while(a) {
  if(strcmp(a->nome, tmp->nome)<0) {
   b=a;
   a=a->next;
  } else {
   if(b) {
    b->next=tmp;
    tmp->next=a;
    return 0;
   }
   tmp->next=a;
   *inizio=tmp;
   return 0;
  }
 }

 (*fine)->next=tmp;
 tmp->next=NULL;
 *fine=tmp;
 return 0;
}

Questo tipo di lista è raffiguarabile in questo modo:

STRUTTURA NUOVA

STRUTTURA 1 --> STRUTTURA 2 --> STRUTTURA 3 ...

La struttura NUOVA può essere prima di tutto:
   tmp->next=a;
   *inizio=tmp;

a metà:
    b->next=tmp;
    tmp->next=a;

al fondo:
 (*fine)->next=tmp;
 tmp->next=NULL;
 *fine=tmp;

o la prima di tutti gli inserimenti:
 if(*fine==NULL) {
  tmp->next=NULL;
  *fine=tmp;
  *inizio=tmp;
  return 0;
 }

Con una struttura ordinata posso iniziare ad appilare infiniti elementi
avendo solo un puntatore al primo e all'ultimo. Se poi dopo creo un ordinamento
pure decrescente modificando la struttura in questo modo:

typedef struct lista_c1 {
 char nome[MAX];
 struct lista_c1 *next;
 struct lista_c1 *prior;
} lista_d;

posso salire e scendere liberamente dalla lista.

Ecco le funzioni:

--- inizio ---
/* Inserisce una nuova struttura non ordinando */
int lista_d_insert(char *nome, lista_d **inizio, lista_d **fine) {
 lista_d *tmp;

 if((tmp=(lista_d *)malloc(sizeof(lista_d)))==NULL) return 1;

 strcpy(tmp->nome,nome);
 tmp->next=NULL;
 
 if(*inizio==NULL) *fine=NULL;

 if(*fine==NULL) {
  tmp->prior=NULL;
  *fine=tmp;
  *inizio=tmp;
  return 0;
 }

 (*fine)->next=tmp;
 tmp->prior=*fine;
 *fine=tmp;
 return 0;
}


/* Inserisce una nuova struttura ordinando */
int lista_d_insert_order(char *nome, lista_d **inizio, lista_d **fine) {
 lista_d *tmp, *a, *b;

 if((tmp=(lista_d *)malloc(sizeof(lista_d)))==NULL) return 1;

 strcpy(tmp->nome,nome);
 
 if(*inizio==NULL) *fine=NULL;

 if(*fine==NULL) {
  tmp->next=NULL;
  tmp->prior=NULL;
  *fine=tmp;
  *inizio=tmp;
  return 0;
 }

 a=*inizio;
 b=NULL;
 while(a) {
  if(strcmp(a->nome, tmp->nome)<0) {
   b=a;
   a=a->next;
  } else {
   if(a->prior) {
    a->prior->next=tmp;
    tmp->next=a;
    tmp->prior=a->prior;
    a->prior=tmp;
    return 0;
   }
   tmp->next=a;
   tmp->prior=NULL;
   a->prior=tmp;
   *inizio=tmp;
   return 0;
  }
 }

 tmp->next=NULL;
 tmp->prior=b;
 (*fine)->next=tmp;
 *fine=tmp;
 return 0;
}

/* Cerca una struttura */
lista_d *lista_d_search(char *nome, lista_d *inizio) {

 if(inizio==NULL) return NULL;

 while(inizio) {
  if(!strcmp(inizio->nome,nome)) return inizio;
  inizio=inizio->next;
 }
 return NULL;
}

/* Cancella una struttura */
void lista_d_delete(lista_d *lista, lista_d **inizio, lista_d **fine) {
 
 if(!lista) return;

 if(lista->prior) lista->prior->next=lista->next;
 else {
  *inizio=lista->next;
  if(*inizio) (*inizio)->prior=NULL;
 }

 if(lista->next) lista->next->prior=lista->prior;
 else *fine=lista->prior;

 free(lista);
}
--- fine ---

Le liste sono usate in moltissimi casi. Uno per tutti nei programmi di foglio
elettronico. Non esistono tutte le caselle che si vedono sullo schermo, quella
è grafica. In verità esistono solo le caselle che sono riempite di qualcosa
attraverso liste oppure tabelle di hashing che vediamo adesso.

HASHING o GRAFICI

I grafici sono delle strutture dati molto complesse. Si basano su liste di
puntatori a liste. Graficamente posso mostrarvele così:

Lista:

A  --> 1 -> 2 -> 3 -> 4 ...
|
B  --> 1 -> 2 -> 3 -> 4 ...
|
C  --> 1 -> 2 -> 3 -> 4 ...
|
D  --> 1 -> 2 -> 3 -> 4 ...
|
...

Esiste la lista A->B->C->D ... e poi per ogni nodo di questa nasce una nuova
lista.

I grafici poi possono essere adibiti a calcoli di distanza. Pensate ad esempio
alle tratte aeree oppure ai piani di viaggio dei treni.

AOSTA    --> torino alle 8.30 -> bari alle 10.00 -> firenze alle 15.56 -> ...
BARI     --> lecce alle 4.23  -> milano alle 5.12 -> ...
GENOVA   --> etc -> etc ...
FIRENZE
LECCE
MILANO
ROMA
TORINO
VENEZIA

Se lo si vuole vedere come grafico verrebbe:

                                 AOSTA
                                  /| \
                                /  |   \
                          TORINO FIRENZE BARI
                           / | \         /  | \ TORINO
                                      LECCE MILANO

Un elenco di tutte le stazioni e poi un elenco di ogni treno per esse.

typedef struct grafo_node1 {
 TYPE info;
 struct grafo_node1 *node_next;
 struct grafo_link1 *link_next;
 int flag; /* Flag per le visite */
 int distance;
} grafo_node;

typedef struct grafo_link1 {
 TYPE info;
 struct grafo_link1 *link_next;
 int flag; /* Flag per le visite */
 int distance;
} grafo_link;

Queste potrebbero essere strutture utili per il nostro caso.

Mentre le funzioni sono queste:
int grafo_insert_node(TYPE info, grafo_node **inizio, grafo_node **fine);
int grafo_insert_order_node(TYPE info, grafo_node **inizio, grafo_node **fine);
grafo_node *grafo_search_node(TYPE info, grafo_node *inizio);
void grafo_delete_node(grafo_node *lista, grafo_node **inizio,
                                           grafo_node **fine);
int grafo_insert_link(TYPE dest, grafo_node **lista);
int grafo_insert_order_link(TYPE dest, grafo_node **lista);
grafo_link *grafo_search_link(TYPE info, grafo_node *inizio);
void grafo_delete_link(grafo_link *lista, grafo_node **inizio);

Scritte qui:
--- inizio ---
/* Inserisce una nuova struttura nodo non ordinando
 * 
 * Riceve l'info e la testa e la coda della lista concatenata degli indici
 */
int grafo_insert_node(TYPE info, grafo_node **inizio, grafo_node **fine) {
 grafo_node *tmp;

 if((tmp=grafo_search_node(info, *inizio))!=NULL)         return 1;
 if((tmp=(grafo_node *)malloc(sizeof(grafo_node)))==NULL) return 1;

 tmp->info=info;
 tmp->link_next=NULL;
 tmp->node_next=NULL;
 
 if(*inizio==NULL) *fine=NULL;
 
 if(*fine==NULL) {
  *fine=tmp;
  *inizio=tmp;
  return 0;
 } 

 (*fine)->node_next=tmp;
 *fine=tmp;
 return 0;
}

/* Inserisce una nuova struttura nodo ordinando */
int grafo_insert_order_node(TYPE info, grafo_node **inizio, grafo_node **fine) {
 grafo_node *tmp, *a, *b;

 if((tmp=grafo_search_node(info, *inizio))!=NULL)         return 1;
 if((tmp=(grafo_node *)malloc(sizeof(grafo_node)))==NULL) return 0;

 tmp->info=info;
 tmp->link_next=NULL;
 
 if(*inizio==NULL) *fine=NULL;

 if(*fine==NULL) {
  tmp->node_next=NULL;
  *fine=tmp;
  *inizio=tmp;
  return 0;
 }

 a=*inizio;
 b=NULL;
 while(a) {
  if(a->info<tmp->info) {
   b=a;
   a=a->node_next;
  } else {
   if(b) {
    b->node_next=tmp;
    tmp->node_next=a;
    return 0;
   }
   tmp->node_next=a;
   *inizio=tmp;
   return 0;
  }
 }

 (*fine)->node_next=tmp;
 tmp->node_next=NULL;
 *fine=tmp;
 return 0;
}

/* Cerca una struttura nodo
 *
 * Necessita dell'info e dell'inizio degli indici.
 */
grafo_node *grafo_search_node(TYPE info, grafo_node *inizio) {

 if(inizio==NULL) return NULL;

 while(inizio) {
  if(inizio->info==info) return inizio;
  inizio=inizio->node_next;
 }
 return NULL;
}

/* Cancella una struttura nodo */
void grafo_delete_node(grafo_node *lista, grafo_node **inizio,
                                          grafo_node **fine) {
 
 grafo_node *tmp;
 grafo_link *a, *b;

 if(lista==NULL)   return;
 if(*fine==NULL)   return;
 if(*inizio==NULL) return;

 b=a=NULL;
 if(lista->link_next) a=lista->link_next;
 while(a) {
  b=a;
  a=a->link_next;
  free(b);
 }

 if(lista==*inizio) {
  *inizio=lista->node_next;
  free(lista);
  return;
 }

 tmp=*inizio;

 while(tmp->node_next) {
  if(tmp->node_next->info==lista->info) {
   if(tmp->node_next==*fine) {
    tmp->node_next=NULL;
    *fine=tmp;
    free(lista);
    return;
   }
   tmp->node_next=lista->node_next;
   free(lista);
   return;
  }
  tmp=tmp->node_next;
 }

 *fine=tmp;
 free(lista);
}

/* Inserisce una nuova struttura link non ordinando 
 *
 * Necessita di una destinazione e del puntatore dell'indice da inserire.
 *
 * tmp=grafo_search_node(KEY,inizio);
 * grafo_insert_order_link(LINK,&tmp);
 */
int grafo_insert_link(TYPE dest, grafo_node **lista) {
 grafo_link *tmp, *a;


 if((tmp=grafo_search_link(dest, *lista))!=NULL)          return 1;
 if((tmp=(grafo_link *)malloc(sizeof(grafo_link)))==NULL) return 0;

 tmp->info=dest;
 tmp->link_next=NULL;

 if((*lista)->link_next==NULL) {
  (*lista)->link_next=tmp;
  return 0;
 }
 
 a=(*lista)->link_next;
 while(a) {
  if(!a->link_next) {
   a->link_next=tmp;
   return 0;
  }
  a=a->link_next;
 }
}

/* Inserisce una nuova struttura nodo ordinando */
int grafo_insert_order_link(TYPE dest, grafo_node **lista) {
 grafo_link *tmp, *a, *b;

 if((tmp=grafo_search_link(dest, *lista))!=NULL)          return 1;
 if((tmp=(grafo_link *)malloc(sizeof(grafo_link)))==NULL) return 0;

 tmp->info=dest;
 
 if((*lista)->link_next==NULL) {
  (*lista)->link_next=tmp;
  tmp->link_next=NULL;
  return 0;
 }

 a=(*lista)->link_next;
 b=NULL;
 while(a) {
  if(a->info<tmp->info) {
   b=a;
   a=a->link_next;
  } else {
   if(b) {
    b->link_next=tmp;
    tmp->link_next=a;
    return 0;
   }
   tmp->link_next=a;
   (*lista)->link_next=tmp;
   return 0;
  }
 }

 b->link_next=tmp;
 tmp->link_next=NULL;
 return 0;
}

/* Cerca una struttura nodo
 *
 * Necessita dell'info e della testa dell'indice.
 *
 * tmp=grafo_search_node(3,inizio);
 * grafo_delete_link(grafo_search_link(2,tmp),&tmp);
 */
grafo_link *grafo_search_link(TYPE info, grafo_node *inizio) {
 grafo_link *tmp;

 if(!inizio)            return NULL;
 if(!inizio->link_next) return NULL;

 tmp=inizio->link_next;
 
 while(tmp) {
  if(tmp->info==info) return tmp;
  tmp=tmp->link_next;
 }
 return NULL;
}

/* Cancella una struttura nodo */
void grafo_delete_link(grafo_link *lista, grafo_node **inizio) {
 grafo_link *tmp;

 if(lista==NULL)                return;
 if(*inizio==NULL)              return;
 if((*inizio)->link_next==NULL) return;

 if(lista==(*inizio)->link_next) {
  (*inizio)->link_next=lista->link_next;
  free(lista);
  return;
 }

 tmp=(*inizio)->link_next;

 while(tmp->link_next) {
  if(tmp->link_next->info==lista->info) {
   if(tmp->link_next->link_next==NULL) {
    tmp->link_next=NULL;
    free(lista);
    return;
   }
   tmp->link_next=lista->link_next;
   free(lista);
   return;
  }
  tmp=tmp->link_next;
 }

 free(lista);
}
--- fine ---

Esistono poi metodi per visualizzare tutti i percorsi di questi grafici. 
Ecco i principali algoritmi:

Ricerca in PROFONDITA' (depth first): Si fa un percorso fino alla conclusione
e poi se ne fa un altro.

/* Visita in profondita' */
void grafo_dfs(grafo_node *inizio) {
 grafo_node *tmp;

 tmp=inizio;
 while(tmp) {
  tmp->flag=0;
  tmp=tmp->node_next;
 }

 inizio->flag=1;
 tmp=inizio;

 while(tmp) {
  grafo_dfs_recursive(tmp, inizio);
  tmp=tmp->node_next;
 }
}

void grafo_dfs_recursive(grafo_node *a, grafo_node *inizio) {
 grafo_link *tmp;

 if(!a->flag) {
  a->flag++;
  tmp=a->link_next;
  while(tmp) {
   grafo_dfs_recursive(grafo_search_node(tmp->info, inizio), inizio);
   tmp=tmp->link_next;
  }
 } else return;
}

Funzione ricorsiva che viaggia all'interno del grafico fino a toccare tutti i
nodi. 
                 A
                / \
              B     C
            /  \   /  \
          D     E F    G

Ordine: ABDEBACFCG

/* Visita in ampiezza */
void grafo_bfs(grafo_node *root, grafo_node *inizio) {

 while(root) {
  grafo_link *a;

  if(root->flag) break;
  a=root->link_next;
  while(a) {
   grafo_node *b;

   b=grafo_search_node(root->info, inizio);
   if(!b->flag) b->flag=1;
   a=a->link_next;
  }
  root=root->node_next;
 }
}

/* Inizializzazione buffer di backtrack */
grafo_node *grafo_tsp_init_backtrack(int n) {
 grafo_node *tmp;
 
 if((tmp=(grafo_node *)malloc(n*sizeof(grafo_node)))==NULL) return NULL;
 return tmp;
}

/* TSP */
int grafo_tsp(grafo_node *start, grafo_node *inizio, grafo_node *buffer) {
 grafo_link *a;
 grafo_node *tmp;
 int d0,d1,n;

 tmp=inizio;
 n=0;
 while(tmp) {
  n++;
  tmp->flag=0;
  tmp=tmp->node_next;
 }

 d0=0;
 a=start->link_next;
 while(a) {
  if(a->link_next) {
   tmp=grafo_search_node(a->link_next->info,inizio);
   tmp->flag=1;
   d1=grafo_tsp_recursive(tmp, inizio, buffer);
  }
  
  if(d0) {
   if(d1<d0) {
    d0=d1;
    buffer=tmp;
   }
  } else d0=d1;

  a=a->link_next;
 }
 return d0;
}

int grafo_tsp_recursive(grafo_node *start, grafo_node *inizio,
                                         grafo_node *buffer) {
 grafo_link *a;
 grafo_node *tmp;
 int d0,d1;

 d0=0;
 a=start->link_next;
 if(!a) return 0;

 *buffer++;

 while(a) {
  if(a->link_next) {
   tmp=grafo_search_node(a->link_next->info,inizio);
   if(!tmp->flag) {
    tmp->flag=1;
    d1=grafo_tsp_recursive(tmp, inizio, buffer);
   } 
  } else d1=a->distance;

  if(d0) {
   if(d1<d0) {
    d0=d1;
    buffer=tmp;
    *buffer++;
   }
  } else d0=d1;

  a=a->link_next;
 }
 return d0;
}

Un algoritmo di visita in ampiezza si basa su: Si controlla ogni nodo sullo
stesso livello e poi si scende a quelli minori.
Sul grafico di prima l'ordine sarebbe stato:

ABCBDEBCFG

Avete notato che questo algoritmo riesce a fornare la strada che ha fatto
attraverso algoritmi di backstrack.

Meglio uno o meglio altro? Dipende dai dati che si hanno a disposizione. 
Il programmatore sa che dati sta giostrando e sa quale algoritmo è meglio.
Se si vuole il massimo della funzionalità a scapito delle velocità, sarebbe
meglio testarli entrambi e vedere i risultati migliori. Questo però non è
sempre prossibile.

Entra nel discorso le informazioni euristiche: più si sa di che informazioni
si sta parlando, più si può calcolare il modo migliore per raggiungere 
l'obiettivo. Sappiate che esistono programmi, specialmente database, che 
a seconda dei dati caricati e delle query fatte da chi li consulta, fanno
calcoli statistici e di previsione in modo da usare o uno, o l'altro o altri
ancora che qui non tratteremo.

ALBERI

L'ultima struttura dati che tratterò sarà l'albero. Moltro simile al 
precedente, si basa su concetti di liste più grafici.

typedef struct albero1 {
 TYPE info;
 struct albero1 *sx;
 struct albero1 *dx;
} albero;

Ogni struttura conosce 2 figli uno di destra e uno di sinistra. Per fortuna
non si parla di politica...
L'albero di destra è il maggiore e quello di sinistra è il minore e viceversa.

Su una struttura del genere:

    10
   /  \
  5    11
 / \
3   7

Se volessi inserire 8 dovrei farmi le seguenti domande:

E' maggiore di 10 ? No: prendo il ramo del 5.
E' maggiore di 5? Sì: vado a destra verso il 7.
E' maggiore del 7? Sì: mi metto sotto di lui come figlio di destra.

Le funzioni per gestire questo sono:

int albero_insert(TYPE info, albero **root);
int albero_delete(TYPE info, albero **root);
albero *albero_search(TYPE info,albero *root);
void albero_delete_postorder(albero *tmp);
albero *albero_maximum(albero *root);
albero *albero_minimum(albero *root);

In più ne ho scritte tre di sfogliatura dell'albero:

void albero_inorder(albero *root);
void albero_preorder(albero *root);
void albero_postorder(albero *root);

Il codice è questo:

--- inizio ---
/* Inserisce un nuovo elemento nell'albero ordinando */
int albero_insert(TYPE info, albero **root) {
 albero *tmp,*a;
 
 if((tmp=(albero *)malloc(sizeof(albero)))==NULL) return 1;
 tmp->sx=NULL;
 tmp->dx=NULL;
 tmp->info=info;

 if(!*root) {
  *root=tmp;
  return 0;
 }

 a=*root;
 while(a) {
  if(info<a->info) {
   if(a->sx==NULL) {
    a->sx=tmp;
    return 0;
   }
   a=a->sx;
  } else {
   if(a->dx==NULL) {
    a->dx=tmp;
    return 0;
   }
   a=a->dx;
  }
 }
}

/* 3 funzioni di visualizzazione */
void albero_inorder(albero *root) {
 if(!root) return;

 albero_inorder(root->sx);
 if(root->info) printf("%d",root->info);
 albero_inorder(root->dx);
}

void albero_preorder(albero *root) {
 if(!root) return;

 if(root->info) printf("%d",root->info);
 albero_preorder(root->sx);
 albero_preorder(root->dx);
}

void albero_postorder(albero *root) {
 if(!root) return;

 albero_postorder(root->sx);
 albero_postorder(root->dx);
 if(root->info) printf("%d",root->info);
}

/* Ricerca */
albero *albero_search(TYPE info, albero *root) {
 if(!root) return NULL;

 while(root->info!=info) {
  if(info<root->info) root=root->sx;
  else                root=root->dx;
  if(!root) break;
 }
 return root;
}

/* Cancellazione albero */
int albero_delete(TYPE info, albero **root) {
 albero *tmp, *old;

 if(!root) return 1;

 tmp=*root;
 old=NULL;
 while(tmp) {
  if(info<tmp->info) {
   old=tmp;
   tmp=tmp->sx;
  } else if(info>tmp->info) {
   old=tmp;
   tmp=tmp->dx;
  } else {
   albero_delete_postorder(tmp);
   if(old) {
    if(info<tmp->info) old->sx=NULL;
    else               old->dx=NULL;
   } else *root=NULL;
   return 0;
  }
 }
 return 1;
}

/* Funzione che mi dealloca un albero */
void albero_delete_postorder(albero *root) {
 if(!root) return;

 albero_delete_postorder(root->sx);
 albero_delete_postorder(root->dx);
 free(root);
}

/* Valore massimo */
albero *albero_maximum(albero *root) {
 if(!root) return NULL;

 while(root) {
  if(root->dx) root=root->dx;
  else return root;
 }
}

/* Valore minimo */
albero *albero_minimum(albero *root) {
 if(!root) return NULL;

 while(root) {
  if(root->sx) root=root->sx;
  else return root;
 }
}
-- fine ---

Con quest'ultimo algoritmo dico conclusa la sezione dati.