# #######################################################################
		EXERCICE 1 
# #######################################################################

1. a=1, b=3
2. a=5, b=6
3. a=5, b=3
4. a=6, b=12
5. a=18, b=12


# #######################################################################
		EXERCICE 2 
# #######################################################################

Partie 1 
========

Q1. fichier dico.h

#define P 256
#define N 27

typedef int Dico[P] ;   // Dico est le type tableau de booleen indice de 0 a 255
typedef char Chaine[N]; // Chaine est le type tableau de caracteres indice de 0 a 26

// Ici le type Dico est un type "tableau de chaines de caracteres"
// Pour passer un parametre de type Dico en mode "donnee", "resultat" ou
// "donnee-resultat" il suffit d'utilier un parametre de type D
// (tous les passages se font en mode donnee-resultat) 

void Vide (Dico D) ;
int estVide(Dico D)
void Inserer (Chaine s ; Dico D) ;
void Supprimer (Chaine s ; Dico D) ;
int estPresent(Chaine s ; Dico D) ;

Q2. fichier dico.h


void Vide (Dico D) {
  int i;
  for (i=0; i<P ; i++) {
      D[i] = 0 ;  / on initialise D[i] a faux
  } 
}

int estVide (Dico D) {
  int i;
  i = 0 ;
  while (i<P && !D[i]) {
     i=i+1 ;
  }
  if (i<P) {
    return 0 ;  // D contient au moins une valeur true 
  } else {
    return 1 ;  // D contient que des valeurs false, donc D est vide
  }
}


void Inserer (Chaine s ; Dico D) {
	D[hash(s)] = 1 ;
} 

void Supprimer (Chaine s ; Dico D) {
	D[hash(s)] = 0 ;
} 

int estPresent(Chaine s ; Dico D) {
	return D[hash(s)] ;
}

Q3. Pour implementer une table de hachage "parfaite" comportant 135 000 mots
il faudrait un tableaux de taille 135 000 * 26 caracteres (ce qui est gros !).
De plus, la fonction de hachage serait difficile a obtenir (a moins d'enumerer 
les 135 000 mots pour leur donner un code unique a chacun ...).

Partie 2
========

Q4.

int main () {

 char s[26], s1[26] ;
 Dico D ;
 char c ;

 Vide (D) ;
 for (i=1 ; i<= 10 ; i++) {
	 scanf("%s", s) ;
	 Inserer (s, D) ;
 } ;

 scanf("%s", s1) ;
 if (estPresent (s1, D)) {
	Supprimer(s1, D) ;
 } else { 
	Inserer(s1, D) ;
 } ;
 return 0 ;
}

Q5.

1. fichier hash.h
   
  int hash(Chaine s) ; 

2. fichier Makefile

test_dico: main.o dico.o hash.o 
	gcc -Wall main.o dico.o hash.o -o test_dico

main.o: main.c dico.h  
	gcc -Wall -c main.c 

dico.o: dico.c dico.h hash.h 
	gcc -Wall -c dico.c 

hash.o: hash.c 
	gcc -Wall -c hash.c 


Partie 3
========

Q6. 

1. nouveau fichier dico.h

#define P 256
#define N 27

typedef char Chaine[N]; // Chaine est le type tableau de caracteres indice de 0 a 26

typedef struct cellule {
   Chaine s;
   struct cellule *suivant;
} Cellule ;

typedef *Cellule Dico[P] ;   // Dico est le type tableau de pointeurs sur Cellule indice de 0 a 255

2. nouveau corps des fonctions


void Vide (Dico D) {
  int i;
  for (i=0; i<P ; i++) {
      D[i] = NULL ;  / on initialise D[i] a Nil ...
  } 
}

int estVide (Dico D) {
  int i;
  i = 0 ;
  while (i<P && D[i]==NUL) {
     i=i+1 ;
  }
  if (i<P) {
    return 0 ;  // D contient au moins une valeur non Nil
  } else {
    return 1 ;  // D contient que des valeurs Nil, donc D est vide
  }
}


void Inserer (Chaine s ; Dico D) {
   int i ;
   Cellule *tmp ;

	i = hash(s) ;

    // insertion d'une cellule contenant s en tete de la liste D[i] 
	tmp = (Cellule) malloc(sizeof(Cellule)) ; 
    strcpy (tmp->s, s) ; // on copie la chaine s dans le champ s de la nouvelle cellule tmp 
    tmp->suivant = D[i] ;
    D[i] = tmp ;  
} 

void Supprimer (Chaine s ; Dico D) {
   int i ;
   Cellule *pred, *cour ;

    // suppression de la cellule contenant s dans la liste D[i]
    if (estPresent(s, S) {
       i = hash(s) ;
       if (!strcmp (D[i].s, s)) { 
         // suppresion de l'element de tete 
   	     pred = D[i] ;
         D[i] = D[i].suivant ;
         free(pred) ; 
       } else {
         // suppresion d'un element non en tete
   	     pred = D[i] ;
         cour = D[i].suivant ;
         while (strcmp(cour.s, s) != 0) {
              pred = cour ;
              cour = cour->suivant ;
         } ;
         // cour contient la cellule a supprimer et pred son predecesseur
         pred->suiv = cour->suiv ;
         free(cour) ;
    } ;
}
         
int estPresent(Chaine s ; Dico D) {
   int i ;
   Cellule *cour ;

   i = hash(s) ;

   // recherche dans D[i] d'une cellule contenant s
  cour = D[i] ;
  while (cour != NULL && strcmp(cour.s, s) != 0) {
		cour = cour->suiv ;
  } ;
  return (cour != NULL) ;
} 

		
Q7. 

int hash(Chaine s) {
   int r  ;
   int i ;
   
   i=0; r=0 ;
   while (s[i] != '\0')
      r = r+s[i] ;
   return r % P ;
}

Partie 4
=========

Autre representation pour le type Dico ?

On peut choisir une liste chainee de chaines de caracteres, avec une recherche
sequentielle. Le fichier dico.h devient alors :

typedef char Chaine[N]; // Chaine est le type tableau de caracteres indice de 0 a 26

typedef struct cellule {
   Chaine s;
   struct cellule *suivant;
} Cellule ;

typedef Cellule *Dico ;   // Dico est le type pointeur sur Cellule 

void Vide (Dico *D) {
	*D = NULL ;
}

void Inserer (Chaine s ; Dico *D) {
   int i ;
   Cellule *tmp ;

    // insertion d'une cellule contenant s en tete de la liste D 
	tmp = (Cellule) malloc(sizeof(Cellule)) ; 
    strcpy (tmp->s, s) ; // on copie la chaine s dans le champ s de la nouvelle cellule tmp 
    tmp->suivant = *D ;
    *D = tmp ;  
}