Code cleanups

[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)
{
/* "mauvaise" fonction de hachage - juste pour tester le programme */
    return x % M;
}

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
*****************************************************************************/