Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 6 sur 6
  1. #1
    Invité de passage
    Homme Profil pro
    Inscrit en
    janvier 2013
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : janvier 2013
    Messages : 7
    Points : 1
    Points
    1

    Par défaut Table de Hachage suppression

    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.

  2. #2
    Expert Confirmé Sénior Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2005
    Messages
    24 012
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2005
    Messages : 24 012
    Points : 32 153
    Points
    32 153

    Par défaut

    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é.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  3. #3
    Responsable Modération
    Avatar de diogene
    Homme Profil pro Patrick Gonord
    Enseignant Chercheur
    Inscrit en
    juin 2005
    Messages
    5 664
    Détails du profil
    Informations personnelles :
    Nom : Homme Patrick Gonord
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : juin 2005
    Messages : 5 664
    Points : 12 539
    Points
    12 539

    Par défaut

    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)
    Publication : Concepts en C

    Mon avatar : Glenn Gould

    --------------------------------------------------------------------------
    Une réponse vous a été utile ? Remerciez son auteur en cliquant le pouce vert !

  4. #4
    Invité de passage
    Homme Profil pro
    Inscrit en
    janvier 2013
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : janvier 2013
    Messages : 7
    Points : 1
    Points
    1

    Par défaut

    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.

  5. #5
    Expert Confirmé Sénior Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    septembre 2005
    Messages
    24 012
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 30
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2005
    Messages : 24 012
    Points : 32 153
    Points
    32 153

    Par défaut

    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.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  6. #6
    Invité de passage
    Homme Profil pro
    Inscrit en
    janvier 2013
    Messages
    7
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : janvier 2013
    Messages : 7
    Points : 1
    Points
    1

    Par défaut

    Merci tout est claire maintenant.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •