Table de Hachage suppression

Version imprimable

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 
#define TAILLE_NOM 20
#define TAILLE_TABLE 20
#define TAILLE_PRENOM 20
 
struct personne{
    struct personne *succ;
    char nom[TAILLE_NOM];
    char prenom[TAILLE_PRENOM];
    struct personne *pred;
};
typedef struct personne personne_t;
 
 
/* --- variable globales --- */
personne_t *table_hachage[TAILLE_TABLE];
 
 
/* --- fonction hachage --- */
int code_hachage(char clef[])
{
    int tmp, i, res=0, taille;
    taille = strlen(clef);
 
    for(i=0; i<taille; i++)
    {
        res = (res<<4) + clef[i];
 
        if(tmp = (res & 0xf0000000))
        {
            res = res ^ (tmp>>24);
            res = res ^ tmp;
        }
    }
    return res % TAILLE_TABLE;
}
 
 
/* --- suppression d'un element dans la table --- */
void suppression_element(personne_t *element_a_supprimer)
{
    int code;
    personne_t *pt_succ, *pt_pred;
 
    pt_succ = element_a_supprimer->succ;
    pt_pred = element_a_supprimer->pred;
 
    if(pt_succ != NULL) /* il y a un successeur dans la liste */
    {
        pt_succ->pred = pt_pred;
    }
 
    if(pt_pred != NULL) /* il y a un predecesseur dans la liste */
    {
        pt_pred->succ = pt_succ;
    }
 
    else /* c'est le premier de la liste */
    {
        code = code_hachage(element_a_supprimer->nom);
        table_hachage[ code] = pt_succ;
    }
 
    free(element_a_supprimer);}

Bonjour je ne comprend pas tres bien la fonction suppression j'aimerais avoir quelque explication la dessus.
merci encore.

18/01/2013, 11h39
Médinoc
La fonction de suppression repose sur le fait que dans une liste doublement chaînée, un chaînon peut se supprimer de manière complètement indépendante sauf s'il est le premier de la liste; s'il est le premier, il doit modifier le pointeur "premier chaînon" de la liste.
Note: S'il y a aussi un pointeur "dernier élément" pour la liste, le même problème se pose.

Ici, les listes sont accessibles dans un tableau global: La seule chose nécessaire pour retrouver le pointeur "premier élément", c'est re-hacher la clé. De plus, il n'y a pas de pointeur "dernier élément".

Ainsi, la fonction de suppression fait trois choses:
1. Modifier les éléments alentours pour les faire pointer l'un sur l'autre, détachant l'élément de la chaîne.
2. Si l'élément est le premier de la liste (donc s'il n'a pas de précédent), il retrouve la liste et modifie le pointeur "premier élément".
3. L'élément étant à présent détaché, il peut maintenant être supprimé.

La fonction supprime un élément d'une des listes doublement chainées de la table de hachage. On doit donc réaliser avant destruction de l'élément (le free() ligne 64) le nouveau chainage qui permet de relier ce qui précède (pt_pred ligne 46) dans la liste l'élément à supprimer avec ce qui le suit (pt_succ ligne 45).

Schématiquement (en rouge, l'élément à supprimer) :
Avant :
                    table_hachage
                        ...
          NULL        personne_t----->personne_t---->personne_t---->personne_t---...--->NULL
             \        /    \          /    \         /    \         /   \
              <-------       <--------      <--------     <---------     <-------
                       ....    
Changement du chainage
                     table_hachage
                        ...                     ------------------>
                                               /                   \
          NULL        personne_t----->personne_t     personne_t---->personne_t---...--->NULL
             \        /    \          /    \         /              /   \
              <-------      <---------      \<-------              /     <-----
                        ...                  <--------------------       
Destruction
                    table_hachage
                        ...                     ------------------>
                                               /                   \
          NULL        personne_t----->personne_t                    personne_t---...--->NULL
             \        /    \          /    \                        /   \
              <-------      <---------      \                      /     <-----
                        ...                  <--------------------
Si il y a un élément qui suit ( if(pt_succ != NULL) ligne 48) alors son nouveau précédent est le précédent de l'élément à enlever ( pt_succ->pred = pt_pred; ligne 50)

Si il y a un élément qui précède ( if(pt_pred != NULL) ligne 53) alors son nouveau successeur est le successeur de l'élément à enlever ( pt_pred->succ = pt_succ; ligne 55)

Si c'est le premier élément de la liste (pas de précédent, ligne58), son adresse figure dans la table de hachage comme début de la liste et il faut changer cette valeur pour celle du nouvel élément de début de la liste, son successeur(ligne 60 et 61)

On peut maintenant détruire l'élément qui est sorti du chainage de la liste et du tableau de hachage (ligne 64)

Merci à vous je comprend beaucoup mieux la fonction suppression,comme les tables de hachages sont considéré un comme un concept et non comme un aspect du langage c.C'est pas évident d'avoir des exemples concrets une dernière questions pour le code suivant.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 /***************************************************************/ personne_t* recherche_element(char clef[]) /***************************************************************/ { int code1, termine=0; personne_t *element; code1 = hachage(clef); element = table_hachage[code1]; while(!termine) { if(element == NULL) { termine = 1; } else if(strcmp(element->nom, clef)==0) { termine = 1; } else { element = element->suiv; } } return element; }
De ce que j'ai compris la fonction recherche,permet retrouver la table de hachage grâce aux fonctions que l'on a créé avant,et ce par rapport à la clé généré par la clé.
j'aimerais savoir un peu plus en détail le fonctionnement de cette fonction s'il vous plait.

19/01/2013, 10h27
Médinoc
La fonction a deux étapes:
1. Hache la clé passée en paramètre pour déterminer quel "seau" de la table de hachage contient (ou non) l'élement.
2. Le "seau" en question est une liste chaînée: La fonction parcoure donc la liste chaînée, comparant à chaque fois la clé complète, jusqu'à trouver l'élement voulu.
Note: Dans les exemples d'école, les "seaux" sont toujours des listes chaînées; mais il est possible d'utiliser d'autres types de collection à la place, comme des arbres binaires de recherche, ou (quand la table est en lecture seule) de simples tableaux.
19/01/2013, 22h44
urameshi

Merci tout est claire maintenant.