From 11e3fc37d14d479410154881f80f2397da2ecbd3 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Thu, 30 Mar 2017 22:27:32 +0200 Subject: [PATCH] TP6: More and more K&R coding style MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- TP6/hachage/lineaire/hachage_lineaire.c | 178 +++++++++++++++--------- 1 file changed, 112 insertions(+), 66 deletions(-) diff --git a/TP6/hachage/lineaire/hachage_lineaire.c b/TP6/hachage/lineaire/hachage_lineaire.c index 58fcb5c..c8ac848 100644 --- a/TP6/hachage/lineaire/hachage_lineaire.c +++ b/TP6/hachage/lineaire/hachage_lineaire.c @@ -10,86 +10,133 @@ #define LIBERE -1 #define M 10 -typedef struct {int cle; - int etat; - } t_elem; - -void affiche_tab(t_elem *tab) -{int i; - for (i = 0 ; i ",tab[i].cle,tab[i].etat); - printf("\n"); +typedef struct { + int cle; + int etat; +} t_elem; + +void affiche_tab(t_elem * tab) +{ + int i; + + for (i = 0; i < M; i++) + printf("<%2d,%2d>", tab[i].cle, tab[i].etat); + printf("\n"); } -int h(int x) /* mauvaise fonction de hachage - juste pour tester */ -{return x%M;} +int h(int x) +{ /* mauvaise fonction de hachage - juste pour tester */ + return x % M; +} -int rechercher(int x,t_elem *tab) +int rechercher(int x, t_elem * tab) /* retourne l'indice de x dans la table si x est present, -1 sinon */ -{int i=0,v=h(x); - while (i=M) v=0; - }; - -if ((tab[v].etat==OCCUPE) && (tab[v].cle==x)) /* x présent */ return v; - else /* x absent */ return -1; +{ + int i = 0, v = h(x); + + while (i < M) + if ((tab[v].etat == VIDE) || ((tab[v].etat == OCCUPE) && + (tab[v].cle == x))) + break; + else { + i++; + v++; + if (v >= M) + v = 0; + }; + + if ((tab[v].etat == OCCUPE) && (tab[v].cle == x)) /* x présent */ + return v; + else /* x absent */ + return -1; } -int supprimer(int x,t_elem *tab) +int supprimer(int x, t_elem * tab) /* supprime x de la table, s'il est présent (et alors retourne son indice), - et ne fait rien si x est absent (et alors retourne -1) -*/ -{int v = rechercher(x,tab); - if (v!=-1) /*x present */ {tab[v].etat=LIBERE; return v; - } - else /* x absent */ return -1; + et ne fait rien si x est absent (et alors retourne -1) */ +{ + int v = rechercher(x, tab); + + if (v != -1) { /*x present */ + tab[v].etat = LIBERE; + return v; + } else /* x absent */ + return -1; } - -int inserer(int x,t_elem *tab) + +int inserer(int x, t_elem * tab) /* si x n'est pas dans la table, on l'insère a la première place vide ou liberee rencontrée au cours des essais successifs (et on retourne son indice); si x est déjà dans la table, on ne fait rien (et on retourne son indice); si le tableau est plein, c'est que x n'a pu être insèré et on retourne -1 */ -{int i=0,lib=-1,v=h(x); - while (i=M) v=0; - /* on continue tant qu'on ne trouve pas x ou une place vide */ - } - - if (tab[v].etat==VIDE) - if (lib==-1) {tab[v].cle=x;tab[v].etat=OCCUPE;return v;} - else {tab[lib].cle=x;tab[lib].etat=OCCUPE;return lib;} - else return -1; +{ + int i = 0, lib = -1, v = h(x); + + while (i < M) { + if (tab[v].etat == VIDE) + break; + /*x absent, on arrête le parcours du tableau */ + if ((tab[v].etat == OCCUPE) && (tab[v].cle == x)) + return v; + /* x déjà présent, on ne fait rien */ + if ((tab[v].etat == LIBERE) && (lib == -1)) + lib = v; + /* on mémorise l'indice de la première place libérée */ + i++; + v++; + if (v >= M) + v = 0; + /* on continue tant qu'on ne trouve pas x ou une place vide */ + } + + if (tab[v].etat == VIDE) + if (lib == -1) { + tab[v].cle = x; + tab[v].etat = OCCUPE; + return v; + } else { + tab[lib].cle = x; + tab[lib].etat = OCCUPE; + return lib; + } else + return -1; } -int main () -{int i; - t_elem *tab; - -tab = (t_elem *)calloc((M),sizeof(t_elem)); -if (tab == NULL) {printf("memoire insuffisante\n"); exit(-1); } - -for (i=0;i <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> <0,0> 3 @@ -112,4 +159,3 @@ printf("%d\n",inserer(3,tab)); affiche_tab(tab); <19,1> <0,0> <0,0> <23,1> <13,1> <5,1> <3,1> <0,0> <0,0> <9,1> *****************************************************************************/ - -- 2.34.1