Code/labyrinthes.c

/**********************************************************************
 ***** Pierre Hyvernat, cours info505 "Algorithmes de graphes"    *****
 *****                                                            *****
 ***** Il s'agit des définitions de quelques fonctions pour le TP *****
 ***** en salles machines...                                      *****
 ***** Les commentaires pertinents se trouvent dans le fichier    *****
 ***** "labyrinthes.h".                                           *****
 *********************************************************************/


#include "labyrinthes.h"
#include <stdlib.h>


Tile tileVide() {
 Tile T = malloc(sizeof(struct __Tile)) ;
 T->premier = NULL ;
 T->dernier = NULL ;
 return(T) ;
}

void entile(int o, int p, int b, Tile T) {

 struct __case *N = malloc(sizeof(struct __case)) ;
 N->origine = o ;
 N->poids = p ;
 N->but = b ;
 N->precedent = NULL ;
 N->suivant = T->premier ;

 if (T->dernier == NULL) { T->dernier = N ;}
 else { T->premier->precedent = N ;}

 T->premier = N ;
}


void detilePremier(Tile T, int *o, int *p, int *b) {
 if (o!=NULL) *o = T->premier->origine ;
 if (p!=NULL) *p = T->premier->poids ;
 if (b!=NULL) *b = T->premier->but ;

 if (T->premier == T->dernier) { /* la tile a un seul élément */
  free(T->premier) ;
  T->premier = NULL ;
  T->dernier = NULL ;
 }
 else {
  T->premier = T->premier->suivant ;
  free(T->premier->precedent) ;
  T->premier->precedent = NULL ;
 }
}

void detileDernier(Tile T, int *o, int *p, int *b) {
 if (o!=NULL) *o = T->dernier->origine ;
 if (p!=NULL) *p = T->dernier->poids ;
 if (b!=NULL) *b = T->dernier->but ;

 if (T->premier == T->dernier) { /* la tile a un seul élément */
  free(T->premier) ;
  T->premier = NULL ;
  T->dernier = NULL ;
 }
 else {
  T->dernier= T->dernier->precedent ;
  free(T->dernier->suivant) ;
  T->dernier->suivant = NULL ;
 }
}

void afficheTile(Tile T) {
 Tile L = T ;
 int o,p,b ;
 printf("afficheTile\n  ") ;
 while(L->premier!=NULL) {
  detilePremier(L,&o,&p,&b) ;
  printf("(%i,%i,%i)  --  ",o,p,b) ;
 }
 printf("\n") ;
}


/* fonction temproraire pour trier les voisins dans les listes d'adjacence */
static void insere(int p, int x, ListeAdj *l) {
 int q,y ;
 ListeAdj ll = *l;
 if (ll==NULL) { ll = cons(p,x,ll) ; }
 else {
  q = ll->poids ;
  y = ll->but ;
  if (p<q) { ll = cons(p,x,ll) ; }
  else {
   ll = ll->suivant ;
   insere(p,x,&ll) ;
   ll = cons(q,y,ll) ;
  }
 }
 *l = ll ;
}


GrapheListe grillePleine(void) {

 int h,l,s,p ;
 GrapheListe G = grapheListeVide(LARGEUR*HAUTEUR) ;

 struct timeval temps ;
 gettimeofday(&temps, NULL) ;
 srand(temps.tv_usec) ;

 for (h=0;h<HAUTEUR;h++)
 for (l=0;l<LARGEUR;l++) {
  s=l+h*LARGEUR ;
  if (h!=0) {
   p=rand() ;
   insere(p,s-LARGEUR,&(G->Adj[s])) ;
   insere(p,s,&(G->Adj[s-LARGEUR])) ;
  }
  if (l!=0) {
   p=rand() ;
   insere(p,s-1,&(G->Adj[s])) ;
   insere(p,s,&(G->Adj[s-1])) ;
  }
 }
 return(G) ;
}

---