Add latest implementation of tree algorithm in TP6 directory

[Algorithmic_C.git] / TP6 / hachage / chainage / hachage_chainage.c

/******************************************************************************/
/*                         Hachage par chainage                               */
/******************************************************************************/
#include <stdlib.h>
#include <stdio.h>

#define M 5 
/* on choisit M tres petit pour tester le programme, mais en realite,
   M est tres grand */

typedef int element;

typedef struct cellule {element valeur;
                        struct cellule *suivant; } Cellule, *Liste;
                        
typedef struct {Liste T[M]; } t_table;
		
int h(element x) {return x%M; } 
/* "mauvaise" fonction de hachage - juste pour tester le programme */
	       
t_table init_table() 
	{t_table t;
	 int i;       
     	 for (i=0; i<M; i++) t.T[i]=NULL;
	 return t;}
      		       

int rechercher(element x, t_table t)
      {int i=h(x); 
       Cellule *p=t.T[i];
       while (p) if (x==p->valeur) return 1;
                 else p=p->suivant;
       return 0;
      }
      		 
int inserer(element x, t_table *t) 
/* retourne 0 si x est deja dans la table */
      {int i=h(x); 
       Cellule *p=t->T[i], *preced=NULL;
       while (p) if (x==p->valeur) return 0;
                 else {preced = p; p=p->suivant; }
       if (preced==NULL) {t->T[i]=(Cellule *)malloc(sizeof(Cellule));
                          t->T[i]->valeur=x;
			  t->T[i]->suivant=NULL;
			  }
       else {preced->suivant=(Cellule *)malloc(sizeof(Cellule));
             preced->suivant->valeur=x;
	     preced->suivant->suivant=NULL;
	     }
       return 1;
      }

void visu(Liste L)
     {if (L){printf("%d\t",L->valeur);
             visu(L->suivant);
	    }
     } 
     
void afficher(t_table t)
      {Cellule *p;
       int i;
       for (i=0; i<M ; i++)
	   if (t.T[i]) {printf("t[%d]=\t",i); visu(t.T[i]); printf("\n");}
        printf("\n");
       }
       
/******************************************************************************/
int main ()
{t_table t;

t=init_table();
afficher(t);
inserer(3,&t);	afficher(t);
printf("%d\n",rechercher(3,t));
printf("%d\n",rechercher(12,t));
inserer(5,&t);	afficher(t);
inserer(13,&t); afficher(t);
inserer(9,&t); 	afficher(t);
inserer(19,&t); afficher(t);
inserer(23,&t); afficher(t);
}
/*****************************************************************************
Etat de la table a la fin du programme
-------------------------------------- 
t[0]=   5
t[3]=   3       13      23
t[4]=   9       19
*****************************************************************************/