Bonjour à tous,

Aujourd'hui je cherche à créer une table de hachage comme expliqué dans la dernière partie du cours sur le langage C d'openclassroom.

Mon problème tient au fait que je ne sais pas comment attribuer le nombreHache de la fonction de hachage en indice d'un tableau qui fera appel aux informations d'un tableau de structure.

Ci-dessous dans le code j'attribue dans la fonction init() les prénoms, notes et ages des élèves.
Jusqu'ici tout va bien et la fonction de hachage renvoie bien le nombre haché des prénoms.
J'aurai souhaité concaténer les noms dans la chaine avec strcat(prenom1, nom1) en donnant 100 cases au tableau de chaque prénoms pour contenir leurs noms mais je n'ai pas réussi et ce n'est pas le souci principal.

Comment lier l'indice haché à un tableau pour faire appel aux infos du tableau de structure selon vous ?

Actuellement voici le code complet (j'ai enlevé mes essais sur l'attribution des valeurs à l'indice haché car je n'y arrive pas).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int hachage(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i] + i*chaine[i];
    }
    nombreHache %= 100;

    return nombreHache;
}

struct Eleve
{
        char prenom[100];
        char nom[100];
        int age;
        int notes;
};
typedef struct Eleve Eleve;

void init()
{
    struct Eleve eleves[3];

    char prenom1[] = "Luc",  prenom2[] = "Jeanne", prenom3[] = "Jacques";
    int taillePrenom1 = strlen(prenom1), taillePrenom2 = strlen(prenom2), taillePrenom3 = strlen(prenom3);

    for (int j = 0; j<taillePrenom1; j++)
    {
        eleves[0].prenom[j] = prenom1[j];
    }
    for (int j = 0; j<taillePrenom2; j++)
    {
        eleves[1].prenom[j] = prenom2[j];
    }
    for (int j = 0; j<taillePrenom3; j++)
    {
        eleves[2].prenom[j] = prenom3[j];
    }

    eleves[0].age = 17;
    eleves[0].notes = 18;
    eleves[1].age = 18;
    eleves[1].notes = 16;
    eleves[2].age = 18;
    eleves[2].notes = 15;
    for (int i = 0; i<3; i++)
    {
        printf("(Eleve %s : hash %d) -- Age : %d -- Notes : %d/20 \n", eleves[i].prenom, hachage(eleves[i].prenom), eleves[i].age, eleves[i].notes);
    }
}

int main ( int argc, char** argv )
{
    init();

    //infosSurLuc = rechercheTableHachage(tableau, "Luc Doncieux");

    return 0;
}

Merci d'avance pour votre aide

-
Edité par S kO 26 octobre 2022 à 9:20:23

Salut S kO,

Je pense que tu te réfères à cette page : https://openclassrooms.com/fr/courses/19980-apprenez-a-programmer-en-c/19978-stockez-et-retrouvez-des-donnees-grace-aux-tables-de-hachage

Avant d'aborder tes questions concernant le fonctionnement du hachage, il y a un gros problème sur ton code C que tu devrais corriger : pour affecter des chaînes à un tableau de char, il est inutile de faire une boucle for, (de plus fausse car tu ne copies pas le caractère de fin de chaîne), tu devrais utiliser strcpy() ou strncpy().

Dans la page ci-dessus, le hachage est fait sur le prénom et le nom et pour retrouver les valeurs indiquées sur le cours, tu pourrais utiliser le même calcul pour le hachage et pas celui que tu fais qui est différent.

Pour initialiser une struct avec des données de test, tu peux te passer de variables intermédiaires et de strcpy() et faire comme ceci.

        struct eleve e1 = {
                .prenom = "Luc",
                .nom    = "Doncieux",
                .age    = 18,
                .notes  = 11
        };
        struct eleve e2 = {
                .prenom = "Yann",
                .nom    = "Martinez",
                .age    = 18,
                .notes  = 17
        };

Ensuite, si tu veux reproduire ce qui est indiqué dans le cours, la difficulté est que la chaîne hachée est composée du Prénom et Nom séparés par un espace. Or, tu disposes de ces informations sous forme de champs différents dans ta struct.

Pour résoudre ce problème, tu peux te faire une fonction auxiliaire qui compose la chaîne à hacher sur la base d'une struct.

int hachage_chaine(char * chaine) {
        int nombreHache = 0;

        for (int i = 0 ; chaine[i] != '\0' ; i++)
                nombreHache += chaine[i];

        return nombreHache % 100;
}

int hachage_eleve(struct eleve * e) {
        int hachage = 0;

        char * chaine = malloc(strlen(e->prenom) + 1 + strlen(e->nom) + 1);

        sprintf(chaine, "%s %s", e->prenom, e->nom);
        hachage = hachage_chaine(chaine);

        free(chaine);

        return hachage;
}

Maintenant, tu peux vérifier que hachage_eleve(&e1) et hachage_chaine("Luc Doncieux") renvoient tous deux 50, comme dans le cours.

Tu alors te servir de ce nombre comme indice pour ton tableau et écrire les lignes suivantes :

        /* stockage des élèves dans le tableau de pointeurs à l'indice indiqué 
         * par la fonction de hachage */
        eleves[hachage_eleve(&e1)] = &e1;
        eleves[hachage_eleve(&e2)] = &e2;

        // si tu veux vérifier que le calcul donne 50 et 80 comme dans le cours
        //printf("Hachage Luc Doncieux = %d\n", hachage_eleve(&e1));
        //printf("Hachage Yann Martinez = %d\n", hachage_eleve(&e2));

        /* récupération d'un élève à partir de la chaîne composée 
         * d'un prénom et nom séparés par un espace */
        struct eleve * un_eleve = eleves[hachage_chaine("Luc Doncieux")];

        printf("Le hachage de la chaîne \"Luc Doncieux\" a permis de trouver cet élève :\n"
                        ".prenom = %s\n"
                        ".nom = %s\n"
                        ".age = %d\n"
                        ".notes = %d\n", 
                        un_eleve->prenom, un_eleve->nom, un_eleve->age, un_eleve->notes);

Le même indice permet de récupérer les données.

Il ne te reste plus qu'à gérer les collisions :-)

-
Edité par Dlks 26 octobre 2022 à 14:21:56

Dlks a écrit:

Dans la page ci-dessus, le hachage est fait sur le prénom et le nom et pour retrouver les valeurs indiquées sur le cours, tu pourrais utiliser le même calcul pour le hachage et pas celui que tu fais qui est différent.

Pour initialiser une struct avec des données de test, tu peux te passer de variables intermédiaires et de strcpy() et faire comme ceci.

        struct eleve e1 = {
                .prenom = "Luc",
                .nom    = "Doncieux",
                .age    = 18,
                .notes  = 11
        };
        struct eleve e2 = {
                .prenom = "Yann",
                .nom    = "Martinez",
                .age    = 18,
                .notes  = 17
        };

Ensuite, si tu veux reproduire ce qui est indiqué dans le cours, la difficulté est que la chaîne hachée est composée du Prénom et Nom séparés par un espace. Or, tu disposes de ces informations sous forme de champs différents dans ta struct.

Pour résoudre ce problème, tu peux te faire une fonction auxiliaire qui compose la chaîne à hacher sur la base d'une struct.

int hachage_chaine(char * chaine) {
        int nombreHache = 0;

        for (int i = 0 ; chaine[i] != '\0' ; i++)
                nombreHache += chaine[i];

        return nombreHache % 100;
}

int hachage_eleve(struct eleve * e) {
        int hachage = 0;

        char * chaine = malloc(strlen(e->prenom) + 1 + strlen(e->nom) + 1);

        sprintf(chaine, "%s %s", e->prenom, e->nom);
        hachage = hachage_chaine(chaine);

        free(chaine);

        return hachage;
}

Maintenant, tu peux vérifier que hachage_eleve(&e1) et hachage_chaine("Luc Doncieux") renvoient tous deux 50, comme dans le cours.

Tu alors te servir de ce nombre comme indice pour ton tableau et écrire les lignes suivantes :

        /* stockage des élèves dans le tableau de pointeurs à l'indice indiqué 
         * par la fonction de hachage */
        eleves[hachage_eleve(&e1)] = &e1;
        eleves[hachage_eleve(&e2)] = &e2;

        // si tu veux vérifier que le calcul donne 50 et 80 comme dans le cours
        //printf("Hachage Luc Doncieux = %d\n", hachage_eleve(&e1));
        //printf("Hachage Yann Martinez = %d\n", hachage_eleve(&e2));

        /* récupération d'un élève à partir de la chaîne composée 
         * d'un prénom et nom séparés par un espace */
        struct eleve * un_eleve = eleves[hachage_chaine("Luc Doncieux")];

        printf("Le hachage de la chaîne \"Luc Doncieux\" a permis de trouver cet élève :\n"
                        ".prenom = %s\n"
                        ".nom = %s\n"
                        ".age = %d\n"
                        ".notes = %d\n", 
                        un_eleve->prenom, un_eleve->nom, un_eleve->age, un_eleve->notes);

Personnellement je trouve que ce n'est pas une bonne idée de retourner un nombre modulo 100 dans la fonction de hachage. On "perd de l'entropie".  Peut être que le 100 vient d'une taille de tableau plus loin, mais ce n'est pas l'endroit de s'en occuper. Utiliser une fonction/expression qui, ensuite, fait le modulo par la taille du tableau (attention aux négatifs...)

tableau[hachage_eleve(&e1) % taille_tableau] = e1;

Un souci avec le hachage par somme 

nombreHache += chaine[i];

c'est que l'addition ça commute. Donc "martin" et "tarmin" => même hashcode.

Ce qui se fait souvent c'est de combiner comme ça

nombreHache += 3 * nombreHache + chaine[i];

 ou , au lieu de 3, 5, 9, 17, 31, bref une puissance de 2 plus 1.   L'idée c'est que la puissance de 2 décale ce qu'on a déjà vers la gauche, et le + 1 fait en sorte qu'on garde quand même une trace de l'ancien nombreHache dans la partie droite du nouveau. Autrement dit, si on change un bit dans un octet de la chaine, alors on est sur que ça va changer un bit parmi les 8 de droites du hashcode.

Pour la hachage d'une structure, par la peine de d'allouer et construire une chaine (c'est très couteux), il suffit de faire une formule de Perlimpinpin avec le hachage des champs

int hachage_eleve(const struct eleve *e) {
   return 3 * hachage_chaine(e->nom) 
        + 5 * hachage_chaine(e->prenom);
}

EDIT: il y a un certain temps, j'avais pondu des trucs là dessus : https://mbillaud.fr/docs/Conteneurs/conteneurs.html#ensemble-de-cha%C3%AEnes-hachage

même principe, au lieu de stocker les chaines, on stocke des structures en utilisant les chaines comme clé.

-
Edité par michelbillaud 27 octobre 2022 à 13:53:56

Merci c'est génial Dlks c'est beaucoup plus clair.

Je vais travailler avec ta proposition pour maitriser les tableaux, les pointeurs, les structures et ensuite gérer les collisions avec les listes chainées ou peut-être l'adressage ouvert (pour l'adressage ouvert c'est moins sur car il n'y a pas de mode opératoire dans le cours).

#include <stdio.h>
#include <stdlib.h>

int hachageChaine(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i];
    }
    nombreHache %= 100;

    return nombreHache;
}

struct Eleve
{
        char prenom[100];
        char nom[100];
        int age;
        int notes;
};
typedef struct Eleve Eleve;

int hachageEleve(struct Eleve * e) {
        int hachage = 0;

        char * chaine = malloc(strlen(e->prenom) + 1 + strlen(e->nom) + 1);

        sprintf(chaine, "%s %s", e->prenom, e->nom);
        hachage = hachageChaine(chaine);

        free(chaine);

        return hachage;
}

int main ( int argc, char** argv )
{
        struct Eleve e1 = {
        .prenom = "Luc",
        .nom    = "Doncieux",
        .age    = 18,
        .notes  = 11
};
    struct Eleve e2 = {
        .prenom = "Yann",
        .nom    = "Martinez",
        .age    = 18,
        .notes  = 17
};
    struct Eleve e3 = {
        .prenom = "Aurélie",
        .nom    = "Bassoli",
        .age    = 20,
        .notes  = 15
};
    struct Eleve e4 = {
        .prenom = "Julien",
        .nom    = "Lefebvre",
        .age    = 21,
        .notes  = 14
};

    printf("Hachage Eleve1 (Luc Doncieux) = %d \n", hachageEleve(&e1));
    printf("Hachage Luc Doncieux = %d \n", hachageChaine("Luc Doncieux"));

    /* stockage des élèves dans le tableau de pointeurs à l'indice indiqué
    ** par la fonction de hachage */
    char *eleves[100];
    eleves[hachageEleve(&e1)] = &e1;
    eleves[hachageEleve(&e2)] = &e2;
    eleves[hachageEleve(&e3)] = &e3;
    eleves[hachageEleve(&e4)] = &e4;

    /* récupération d'un élève à partir de la chaîne composée
    ** d'un prénom et nom séparés par un espace */
    struct Eleve * un_eleve = eleves[hachageChaine("Luc Doncieux")];

    printf("Le hachage de la chaîne \"Luc Doncieux\" a permis de trouver cet eleve :\n"
                ".prenom = %s\n"
                ".nom = %s\n"
                ".age = %d\n"
                ".notes = %d\n",
                un_eleve->prenom, un_eleve->nom, un_eleve->age, un_eleve->notes);

    return 0;
}

Encore merci pour ton temps
Au plaisir

EDIT suite au poste de michelbillaud:

Merci également michelbillaud j'ai donc remplacé le modulo 100 par nombreHache %= taille_tableau; après avoir fait un #define taille_tableau 100 et ait remplacé la taille max du tableau dans le tableau de pointeurs char *eleves[taille_tableau];

J'ai également modifié la fonction de hachage de chaine comme tu me le suggères pour éviter les collisions dues aux anagrammes nombreHache += 3 * nombreHache + chaine[i];

En revanche pour la fonction de hachage d'élèves la formule de perlimpinpin en return me fait planter le programme :

int hachageEleve(struct Eleve *e) {
   return 3 * hachageChaine(e->nom)
        + 5 * hachageChaine(e->prenom);
}

De plus tu parles d'éviter d'utiliser le modulo pour ne pas réduire l'entropie de la formule, donc tu penses qu'utiliser un tableau de pointeurs de taille énorme serait mieux ? Car mine de rien avec des prénoms et noms de 100 caractères et une formule de hachage avec des multiplicateurs ça risque vite de faire un nombre énorme (le hache de Luc Doncieux devient 471 215 580)

Merci encore

-
Edité par S kO 26 octobre 2022 à 15:53:11

@Michel: merci, ton polycopié a l'air super. Bien sûr, il y a plein de trucs qu'on pourrait mieux faire, là je voulais juste mettre S kO sur les rails du contenu du cours qu'il indique suivre, pour qu'il retrouve ses petits. Une fois qu'il aura maîtrisé ce contenu très basique, la lecture de ton poly lui sera profitable.

Pour la hachage d'une structure, par la peine de d'allouer et construire une chaine (c'est très couteux), il suffit de faire une formule de Perlimpinpin avec le hachage des champs int hachage_eleve(const struct eleve *e) { return 3 * hachage_chaine(e->nom) + 5 * hachage_chaine(e->prenom); }

Oui, tu as raison, malloc / free ne sont pas nécessaires. Si on reste sur un sprintf() pour composer la chaîne, un tableau statique avec une taille suffisante suffirait et on n'a pas besoin des strlen() non plus.

Dans ta proposition alternative de formule magique, il me semble que tu ne prends pas en compte dans le calcul l'espace entre les deux afin que le hachage de la struct soit identique à celui de la chaîne "Prénom NOM" (dans la mesure où on prend l'hypothèse que la clef serait une chaîne constituée du Prénom et du NOM séparés par un espace) ?

@S kO: tu as changé le type du tableau de hachage d'une façon erronée

    char *eleves[100];
    eleves[hachageEleve(&e1)] = &e1;

le tableau ne peut pas être de type pointeur sur char si tu y mets un pointeur sur struct eleves.

Ton compilateur a dû te dire des choses avec des Warnings. Compile toujours avec les Warnings, comprend les et prend les en compte.

-
Edité par Dlks 26 octobre 2022 à 19:12:39

Merci de ta réponse Dlks

Le problème quand je ne rajoute pas char *eleves[100]; ça ne compile pas et j'ai l'erreur ligne 81 qui m'indique qu'eleves n'a jamais été déclaré.

81|error: 'eleves' undeclared (first use in this function); did you mean 'Eleve'?|

J'ai lu le polycopié de michelbillaud mais je n'ai retenu que : - Lorsqu'il y a collision, on double la taille du tableau par le déplacement de la première liste chainée ce qui permet de ne déplacer qu'une fois la structure et d'allouer suffisamment d'espace au tableau pour éviter les collisions fortuites.

Je serais curieux de simplifier la fonction de hashageEleve comme l'indique michelbillaud avec une formule dans le return mais je n'ai pas réussi à la faire fonctionner.

Je vais me pencher sur le code du polycopié pour essayer de comprendre comment et surtout à quel moment gérer les collisions.

Vous êtes une source de savoir inépuisable c'est vraiment chouette d'avoir des aides aussi précieuses

Tu dois déclarer ton tableau avec le bon type. Puisqu'on met des pointeurs sur struct eleve, une déclaration serait :

struct eleve * eleves[100] = { NULL };

Il y a différente façons d'utiliser le hachage, dans mes trucs c'est un tableau de listes (buckets). C'est ce qui est utilisé pour les HashMaps de Java.

Un élément va dans la liste dont l'indice est le hashcode modulo la taille du tableau. La tableau est assez grand pour qu'en moyenne, il y ait moins d'un élément par liste (0,75), donc en moyenne il se produira peu de collisions.

-
Edité par michelbillaud 22 décembre 2022 à 7:42:52

D'accord je comprends Dlks ça a plus de sens.

michelbillaud j'ai essayé de lire ça mais tu n'as pas mis de fonction main ?

Dans tout les cas je pense commencer par appliquer ce que j'ai vu dans le cours sur les chaines listées pour gérer les éventuelles collisions, mais comme j'ai élargi mon tableau à 100 000 le modulo du nombre généré de la taille du tableau donne un nombre de plusieurs milliers ce qui devrait éviter les collisions.

Si collision il devait y avoir comment je devrais commencer par gérer ce cas ? Par un test conditionnel du genre : if(strcmp(un_eleve, deux_eleve) == 0) alors je fait l'allocation de la seconde chaine deux_eleve vers une liste chainée ?

struct Eleve * un_eleve = eleve[hachageChaine("Luc Doncieux")];
struct Eleve * deux_eleve = eleve[hachageChaine("Yann Martinez")];

Ou bien doit-on prévoir qu'il y aura d'éventuelles collisions et donc créer pour chaque case du tableau de pointeurs sur structure des liste chainée de plusieurs éléments ?

Merci à vous

-
Edité par S kO 27 octobre 2022 à 0:15:11

Il est indispensable de prévoir qu'il y aura des collisions.

Deux types de solutions :

• Soit que le hashcode serve d'indice dans un tableau (modulo la taille) de Collections (liste, tableau, arbrebinaire,...) d'objets 
• Soit avoir une famille de fonctions qui, à partir du hashcode, indique l'endroit où on devrait trouver l'élément, sinon un autre indice si le premier est occupé, soit un troisieme etc.

Pas de main : Parce que c'est un module destiné à être utilisé dans divers programmes. Il y a certainement eu un main pour faire des tests unitaires quand je l'ai écrit, quant à savoir oū j'ai bien pu ranger ça....

-
Edité par michelbillaud 27 octobre 2022 à 7:38:28

Hello michelbillaud je lis tes solutions mais une liste ne possède pas d'indice il me semble, c'est qu'on ajoute un nombre à la suite de la liste qui peut être un hashcode.

Pour deux hashcodes identiques (je reprend la fonction de hashage qui génère le même hashcode pour un anagramme :

nombreHache += chaine[i];

si dans nos 4 élèves les 2 premiers s'appellent

    struct Eleve * un_eleve = eleves[hachageChaine("Luc Doncieux")];
    struct Eleve * deux_eleve = eleves[hachageChaine("Luc Dnocieux")];

j'ai le même hashcode (55).

Après avoir comparé les valeurs des pointeurs je vais devoir gérer la collision.

if (un_eleve == deux_eleve)
    {

En reprenant les fonctions du cours d'openclassroom sur les listes chainées
https://openclassrooms.com/fr/courses/19980-apprenez-a-programmer-en-c/19733-stockez-les-donnees-avec-les-listes-chainees

je peux initialiser une liste lorsqu'il y a collision et insérer le hashcode en bout de chaine :

struct Liste *collision1 = initialisation();
        insertion(collision1, hachageChaine("Luc Dnocieux"));

Je pense qu'à ce moment il faudrait redéfinir l'indice du deuxième élève de la structure vers le dernier élément de la liste

eleves[hachageEleve(&e2)] = &e2;       <-- n'est plus vrai sinon on reste sur une collision

 Et pour récupérer les infos de l'élève on devra également redéfinir où pointe *deux_eleve (idéalement vers le dernier élément de la liste)

struct Eleve * deux_eleve = eleves[hachageChaine("Luc Dnocieux")];

Pour l'instant ça me pose soucis car si je dois tester toute les possibilités de collisions avec chaque entrées ça risque d'être un bloc imbuvable

>  bloc imbuvable

Ecris-le d'abord, tu verras ensuite

• Si l'idée est viable 
• Si le code est si horrible que ça (et ne peut absolument pas être nettoyé)

Les exercices, c'est pour essayer des trucs, et ca part à la poubelle de toutes façons 

---

même hachage pour "Luc Doncieux" et "Duc Loncieux" : déjà expliqué, c'est parce que tu fais une somme des valeurs des caractères, et que l'addition est commutative....

ne pas employer le résultat du hachage tel quel comme indice parce qu'il peut être plus grand que le tableau. Faire un modulo, où un masquage si la taille du tableau est une puissance de 2.

Pendant qu'on y est, faire en sorte que les fonctions de hachage retournent un unsigned int, (ou unsigned long), ça évite les accidents avec le modulo.

-
Edité par michelbillaud 27 octobre 2022 à 13:52:35

@S kO :

En initialisant le tableau de pointeurs sur struct comme proposé

struct eleve * eleves[100] = { NULL };

Les pointeurs de ce tableau sont mis à 0 (pointeur NULL).

Pour vérifier si une nouvelle entrée entre en collision avec un emplacement déjà occupé, il suffit de vérifier, avant d'y mettre le pointeur vers la struct, si l'emplacement est déjà occupé, ou s'il est inoccupé (le pointeur contient NULL).

Dlks a écrit:

@S kO :

En initialisant le tableau de pointeurs sur struct comme proposé

struct eleve * eleves[100] = { NULL };

Les pointeurs de ce tableau sont mis à 0 (pointeur NULL).

Pour vérifier si une nouvelle entrée entre en collision avec un emplacement déjà occupé, il suffit de vérifier, avant d'y mettre le pointeur vers la struct, si l'emplacement est déjà occupé, ou s'il est inoccupé (le pointeur contient NULL).

Ce qui revient à l'ajouter (si pas déjà présent) à la liste des élèves qui est (qui = la liste) à cet emplacement.

(changement de point de vue : ce n'est pas un tableau d'élèves, mais un tableau de listes d'élèves, en raison du chainage des élèves entre eux.  Les élèves dont le hashcode est h vont dans la liste d'indice h modulo taille )

-
Edité par michelbillaud 22 décembre 2022 à 7:43:46

Comme évoqué par Michel, si tu gères les collisions avec des listes, tu peux faire un tableau de maillons de listes.

Concrètement, cela peut être une struct qui encapsule une struc eleve et qui contient un champ eleve_suivant qui reste à NULL s'il n'y a pas besoin de gérer une collision, et qui pointe vers l'élément suivant de la liste si nécessaire. Par exemple.

Concrètement, un tableau de listes d'élèves,  c'est un tableau de pointeurs sur des maillons chaînés entre eux.

Les maillons peuvent contenir 

• Soit une structure eleve
• Soit un pointeur sur une structure eleve

selon qu'on décide d'avoir une sémantique de valeur ou d'entité : est ce qu'un élève est représenté par une structure unique, ou est-ce que les structures contiennent des copies des informations relatives à un élève. Ça se gâte.

Autrement dit si je veux avoir, d'un côté, un indexage par nom prénom, et un autre par numéro reçu, est qu'il y a 2 enregistrements éleve ou un seul .?

C'est pas des considerations métaphysiques, derrière se pose la question de qui possède les struct eleve. Problèmes de fuites mémoire en vue. 

-
Edité par michelbillaud 22 décembre 2022 à 7:44:35

Salut, alors j'ai bidouillé quelque chose qui tient la route dans le sens où j'ai l'affichage des 4 élèves dont 2 sont censés entrer en collision avec le premier.

Qu'en pensez-vous ?

#include <stdio.h>
#include <stdlib.h>
#define taille_tableau 100

int hachageChaine(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i];
    }
    nombreHache %= taille_tableau;

    return nombreHache;
}

typedef struct Eleve Eleve;
struct Eleve
{
        char prenom[100];
        char nom[100];
        int age;
        int notes;
};


int hachageEleve(struct Eleve * e) {
        int hachage = 0;

        char * chaine = malloc(strlen(e->prenom) + 1 + strlen(e->nom) + 1);

        sprintf(chaine, "%s %s", e->prenom, e->nom);
        hachage = hachageChaine(chaine);

        free(chaine);

        return hachage;
}

typedef struct Element Element;
    struct Element
    {
        int tableau[taille_tableau];
        Element *suivant;
        Eleve *eleves_suivant[taille_tableau];
    };

typedef struct Liste Liste;
    struct Liste
    {
        Liste *premier;
    };

Liste *initialisation()
{
    Element *element = malloc(sizeof(*element));
    Liste *liste = malloc(sizeof(*liste));
    Eleve *eleves_suivant[taille_tableau] = {0};
    if (liste == NULL || element == NULL)
    {
        exit(EXIT_FAILURE);
    }
    for (int i = 0; i<taille_tableau; i++)
    {
    element->tableau[i] = 0;
    }
    element->suivant = NULL;
    liste->premier = element;

    return liste;
}

void insertion(Liste *liste, int nvNombre, Eleve *e[nvNombre])
{
    Element *nouveau = malloc(sizeof(*nouveau));
    Eleve *eleves_suivant[taille_tableau] = {0};
    if (nouveau == NULL || liste == NULL)
    {
        exit(EXIT_FAILURE);
    }
    nouveau->tableau[nvNombre] = nvNombre;
    nouveau->suivant = liste->premier;
    liste->premier = nouveau;
    eleves_suivant[nvNombre] = e[nvNombre];
}

void afficherListe(Liste *liste, int nombre, Eleve *e)
{
    if (liste == NULL)
    {
        exit(EXIT_FAILURE);
    }

    struct Element *actuel = liste->premier;

    printf("%d -> \n", actuel->tableau[nombre]);
    printf(".prenom %s\n.nom %s\n.age%d\n.notes %d\n", e->prenom, e->nom, e->age, e->notes);
    printf("\n");
}

int main ( int argc, char** argv )
{
        struct Eleve e1 = {
        .prenom = "Luc",
        .nom    = "Doncieux",
        .age    = 18,
        .notes  = 11
};
    struct Eleve e2 = {
        .prenom = "Luc",
        .nom    = "Donceuix",
        .age    = 18,
        .notes  = 17
};
    struct Eleve e3 = {
        .prenom = "Luc",
        .nom    = "Dieuxcon",
        .age    = 20,
        .notes  = 15
};
    struct Eleve e4 = {
        .prenom = "Julien",
        .nom    = "Lefebvre",
        .age    = 21,
        .notes  = 14
};

    struct Eleve * eleves[100] = { NULL };
    int collision = 0;

    printf("Hachage Eleve2 (Luc Donceuix) = %d \n", hachageEleve(&e2));
    printf("Hachage Luc Doncieux = %d \n", hachageChaine("Luc Doncieux"));

    /* stockage des élèves dans le tableau de pointeurs à l'indice indiqué
    ** par la fonction de hachage */
    eleves[hachageEleve(&e1)] = &e1;
    struct Eleve * un_eleve = eleves[hachageChaine("Luc Doncieux")];
    printf("\nLe hachage de la chaine \"Luc Doncieux\" a permis de trouver cet eleve :\n"
            ".prenom = %s\n"
            ".nom = %s\n"
            ".age = %d\n"
            ".notes = %d\n\n",
            un_eleve->prenom, un_eleve->nom, un_eleve->age, un_eleve->notes);

    if (eleves[hachageEleve(&e2)] == 0 )
    {
    eleves[hachageEleve(&e2)] = &e2;
    /* récupération d'un élève à partir de la chaîne composée
    ** d'un prénom et nom séparés par un espace */
    struct Eleve * deux_eleve = eleves[hachageChaine("Luc Dnocieux")];
    printf("\nLe hachage de la chaine \"Luc Dnocieux\" a permis de trouver cet eleve :\n"
                ".prenom = %s\n"
                ".nom = %s\n"
                ".age = %d\n"
                ".notes = %d\n\n",
                deux_eleve->prenom, deux_eleve->nom, deux_eleve->age, deux_eleve->notes);
    }
    else
    {
    collision++;
    struct Eleve *eleve_suivant[collision];
    eleve_suivant[collision] = &e2;
    Liste *listeCollision = initialisation();
    insertion(listeCollision, collision, eleve_suivant[collision]);
    afficherListe(listeCollision, collision, &e2);
    }

    if (eleves[hachageEleve(&e3)] == 0 )
    {
    eleves[hachageEleve(&e3)] = &e3;
    struct Eleve * trois_eleve = eleves[hachageChaine("Luc Dieuxcon")];
    printf("\nLe hachage de la chaine \"Luc Doncieux\" a permis de trouver cet eleve :\n"
            ".prenom = %s\n"
            ".nom = %s\n"
            ".age = %d\n"
            ".notes = %d\n\n",
            trois_eleve->prenom, trois_eleve->nom, trois_eleve->age, trois_eleve->notes);
    }
    else
    {
    collision++;
    struct Eleve *eleve_suivant[collision];
    eleve_suivant[collision] = &e3;
    Liste *listeCollision = initialisation();
    insertion(listeCollision, collision, eleve_suivant);
    afficherListe(listeCollision, collision, &e3);
    }

    if (eleves[hachageEleve(&e4)] == 0 )
    {
    eleves[hachageEleve(&e4)] = &e4;
    struct Eleve * quatre_eleve = eleves[hachageChaine("Julien Lefebvre")];
    printf("\nLe hachage de la chaine \"Julien Lefebvre\" a permis de trouver cet eleve :\n"
            ".prenom = %s\n"
            ".nom = %s\n"
            ".age = %d\n"
            ".notes = %d\n\n",
            quatre_eleve->prenom, quatre_eleve->nom, quatre_eleve->age, quatre_eleve->notes);
    }
    else
    {
    collision++;
    struct Eleve *eleve_suivant[collision];
    eleve_suivant[collision] = &e4;
    Liste *listeCollision = initialisation();
    insertion(listeCollision, collision, eleve_suivant);
    afficherListe(listeCollision, collision, &e4);
    }

    return 0;
}

Je veux bien savoir s'il y a des abbérations ou des doublons qui ne nécessitent pas d'être là afin de simplifier le tout.

Merci encore ! Je crois qu'on avance

-
Edité par S kO 30 octobre 2022 à 15:54:21

Ta structure de données est bizarre, en tout cas tu ne fais pas ceci : https://openclassrooms.com/forum/sujet/creation-dune-table-de-hachage#message-94755963

Au lieu de

    struct Eleve * eleves[100] = { NULL };

Tu peux déclarer

    struct maillonEleve * eleves[100] = { NULL };

et (si tu poursuis comme jusqu'à présent en ne faisant pas une copie des données, mais en insérant des pointeurs sur struct), tu peux définir struct maillonEleve comme ceci :

    struct maillonEleve {
        struct Eleve * eleve;
        struct Eleve * eleveSuivant;
};

cela est suffisant pour gérer un tableau de maillons, chaque maillon étant susceptible de démarrer une liste.

Pour y voir plus clair dans ton code, et éviter les répétitions, tu devrais te faire une fonction qui gère l'insertion dans la table de hachage :

• qui insère l'entrée dans la table si l'emplacement est vide et en mettant eleveSuivant à NULL
• ou qui gère le doublon en poursuivant la liste pour le cas où l'emplacement est occupé.

Ensuite, il te faut aussi une fonction pour récupérer les données à l'aide de la clef composée du prénom et nom séparés par un espace :

• qui retourne l'entrée eleve se trouvant directement dans le tableau s'il n'y a pas de maillons suivants (si eleveSuivant est égal à NULL, cela veut dire qu'il n'y a pas collisions)
• s'il y a des maillons suivants (eleveSuivant est différent de NULL), qui vérifie si l'entrée se trouvant dans le tableau correspond à la clef composée du prénom et nom séparés par un espace, et, autrement, qui effectue cette vérification dans la liste chaînée en parcourant les éléments de la liste

-
Edité par Dlks 31 octobre 2022 à 12:24:02

Ecoute merci de ta réponse Dlks mais je n'y arrive pas et je désespère un peu.

Je débute dans la manipulation des pointeurs donc des pointeurs de structure alors j'ai rafraichit le code pour ne garder que le strict nécessaire et ai implémenté ce que tu m'a proposé.

Comme je ne suis pas pressé si on peux essayer de voir step by step la fonction insertionEleve ça m'irait bien.
Je voulais mettre la condition qui évalue si la case du tableau de pointeurs est utilisé directement dans la fonction mais je n'ai pas pu car sinon je devrai déclarer la structure dans la fonction, et je ne pourrais pas appeler l'affichage des informations dans ce cas.

#include <stdlib.h>
#define taille_tableau 100

int hachageChaine(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i];
    }
    nombreHache %= taille_tableau;

    return nombreHache;
}

struct Eleve
{
        char prenom[100];
        char nom[100];
        int age;
        int notes;
};
typedef struct Eleve Eleve;

struct MaillonEleve
{
        struct Eleve *eleve;
        struct Eleve *eleveSuivant;
};
typedef struct MaillonEleve MaillonEleve;


int hachageEleve(struct Eleve * e) {
        int hachage = 0;

        char * chaine = malloc(strlen(e->prenom) + 1 + strlen(e->nom) + 1);

        sprintf(chaine, "%s %s", e->prenom, e->nom);
        hachage = hachageChaine(chaine);

        free(chaine);

        return hachage;
}

int insertionEleve(struct Eleve elv)
{
    printf("Collision de %s %s %d %d \n", elv.prenom, elv.nom, elv.age, elv.notes);
    struct MaillonEleve *nouveau = malloc(sizeof(*nouveau));
    nouveau->eleve = &elv;
}

int main ( int argc, char** argv )
{
    struct Eleve e1 = {
        .prenom = "Luc",
        .nom    = "Doncieux",
        .age    = 18,
        .notes  = 11
};
    struct Eleve e2 = {
        .prenom = "Luc",
        .nom    = "Donceuix",
        .age    = 18,
        .notes  = 17
};

    struct Eleve e3 = {
        .prenom = "Luc",
        .nom    = "Dieuxcon",
        .age    = 20,
        .notes  = 15
};

struct MaillonEleve *eleves[100] = { NULL };

    if(eleves[hachageEleve(&e1)] == 0)
    {
    printf("Absence de collision \n");
    eleves[hachageEleve(&e1)] = &e1;
    }
    else
    {
        insertionEleve(e1);
    }

    if(eleves[hachageEleve(&e2)] == 0)
    {
    printf("Absence de collision \n");
    eleves[hachageEleve(&e2)] = &e2;
    }
    else
    {
        insertionEleve(e2);
    }

    if(eleves[hachageEleve(&e3)] == 0)
    {
    printf("Absence de collision \n");
    eleves[hachageEleve(&e3)] = &e3;
    }
    else
    {
        insertionEleve(e3);
    }

    return 0;
}

Je continue à regarder ce que je pourrait faire mais déjà est-ce nécessaire d'avoir 2 pointeurs sur Eleve dans cette structure ?

struct MaillonEleve
{
        struct Eleve *eleve;
        struct Eleve *eleveSuivant;
};

Merci encore

-
Edité par S kO 2 novembre 2022 à 16:21:22

S kO a écrit:

Je continue à regarder ce que je pourrait faire mais déjà est-ce nécessaire d'avoir 2 pointeurs sur Eleve dans cette structure ?

struct MaillonEleve
{
        struct Eleve *eleve;
        struct Eleve *eleveSuivant;
};

Merci encore

-
Edité par S kO il y a 36 minutes

Ca ressemble à une petite erreur. D'habitude dans un Maillon, il y a l'adresse du Maillon suivant (de la même liste)

struct MaillonEleve
{
        struct Eleve *eleve;
        struct MaillonEleve *MaillonSuivant;  // proposition de correction
};

K merci michel

Pas besoin de structure de contrôle pour faire pointer le nouveau maillon (qu'on peut nommer premier) vers les suivants ?

-
Edité par michelbillaud 2 novembre 2022 à 22:37:38

michelbillaud a écrit:

A toi de voir.

-
Edité par michelbillaud il y a environ 17 heures

Je pense que oui autrement on ne peut identifier le maillon de début, le maillon de fin pointant vers NULL.

Autrement je voulais créer des fonctions pour éviter les redondances dans les appels d'insertion/affichage mais déjà la fonction insertion merdouille, elle me répond que la case du premier élève que je rentre est prise alors que je simule 2 collisions sur la première entrée, et en plus elle me dit que la dernière entrée ne fait pas de collision.

J'ai aussi une question sur la fonction affichage, si j'initialise struct MaillonEleve *eleves[taille_tableau] = { NULL } dans la fonction insererEleve, comment je vais faire pour appeler les élèves dans une fonction afficherEleve(char *chaine) ?

#include <stdio.h>
#include <stdlib.h>
#define taille_tableau 100

int hachageChaine(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i];
    }
    nombreHache %= taille_tableau;

    return nombreHache;
}

typedef struct Eleve Eleve;
struct Eleve
{
        char prenom[100];
        char nom[100];
        int age;
        int notes;
};

typedef struct MaillonEleve MaillonEleve;
struct MaillonEleve
{
    struct Eleve *eleve;
    struct MaillonEleve *suivant;
};

typedef struct ListeEleve ListeEleve;
struct ListeEleve
{
    struct MaillonEleve *premier;
};


int hachageEleve(struct Eleve * e) {
        int hachage = 0;

        char * chaine = malloc(strlen(e->prenom) + 1 + strlen(e->nom) + 1);

        sprintf(chaine, "%s %s", e->prenom, e->nom);
        hachage = hachageChaine(chaine);

        free(chaine);

        return hachage;
}

void insererEleve(struct Eleve *elv)
{
    struct MaillonEleve *eleves[taille_tableau] = {NULL};

    if (eleves[hachageEleve(&elv)] == NULL)
    {
        eleves[hachageEleve(&elv)] = &elv;
    }
    else
    {
        printf("Collision de %s %s %d %d \n", elv->prenom, elv->nom, elv->age, elv->notes);
    }
}

void afficherEleve(char *chaine)
{
    int hachage = hachageChaine(chaine);

    printf("Hashcode : %d \n", hachage);
}

int main ( int argc, char** argv )
{
        struct Eleve e1 = {
        .prenom = "Luc",
        .nom    = "Doncieux",
        .age    = 18,
        .notes  = 11
};
    struct Eleve e2 = {
        .prenom = "Luc",
        .nom    = "Donceuix",
        .age    = 18,
        .notes  = 17
};
    struct Eleve e3 = {
        .prenom = "Luc",
        .nom    = "Dieuxcon",
        .age    = 20,
        .notes  = 15
};

insererEleve(&e1);
afficherEleve("Luc Doncieux");
insererEleve(&e2);
afficherEleve("Luc Donceuix");
insererEleve(&e3);
afficherEleve("Luc Dieuxcon");

    return 0;
}

Retour console :

Collision de Luc Doncieux 18 11
Hashcode : 55
Collision de Luc Donceuix 18 17
Hashcode : 55
Hashcode : 55

Merci d'avance

S kO a écrit:

michelbillaud a écrit:

A toi de voir.

-
Edité par michelbillaud il y a environ 17 heures

1. Je pense que oui autrement on ne peut identifier le maillon de début, le maillon de fin pointant vers NULL.

2. Autrement je voulais créer des fonctions pour éviter les redondances dans les appels d'insertion/affichage mais déjà la fonction insertion merdouille, elle me répond que la case du premier élève que je rentre est prise alors que je simule 2 collisions sur la première entrée, et en plus elle me dit que la dernière entrée ne fait pas de collision.

3. J'ai aussi une question sur la fonction affichage, si j'initialise struct MaillonEleve *eleves[taille_tableau] = { NULL } dans la fonction insererEleve, comment je vais faire pour appeler les élèves dans une fonction afficherEleve(char *chaine) ?

• 1. ne pense pas trop, écris le code, et teste-le.
• 2. un problème à la fois, corrige ton insertion si elle ne marche pas.
• 3. Qu'entends-tu par "appeler les élèves dans afficherEleve" ? Désigner celui que tu veux afficher ? Il te faut le nom et le prénom (si ça suffit pour constituer un identifiant unique).

J'ai transposé le problème des listes chainées pour incrémenter les doublons dans une chaine sauf que :

1) Comme la liste est créée dans chaque bloc conditionnel c'est une nouvelle liste bien qu'elle porte le même nom, donc au final ça ne ressemble pas à une liste.

2) Je n'ai pas créé la fonction afficherListe comme on le souhaite car je me demande comment rechercher l'élève en passant par une chaine dans une fonction du style :

void afficherListe(ListeEleve *liste, char *chaine)

Donc lumière éteinte j'ai tapé pied nu dans la plupart des meubles à la recherche de la punaise sur le sol et j'ai sorti un clou :

#include <stdio.h>
#include <stdlib.h>
#define taille_tableau 100

int hachageChaine(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i];
    }
    nombreHache %= taille_tableau;

    return nombreHache;
}

typedef struct Eleve Eleve;
struct Eleve
{
        char prenom[100];
        char nom[100];
        int age;
        int notes;
};

typedef struct MaillonEleve MaillonEleve;
struct MaillonEleve
{
    struct Eleve *eleve;
    struct MaillonEleve *suivant;
};

typedef struct ListeEleve ListeEleve;
struct ListeEleve
{
    struct MaillonEleve *premier;
};


int hachageEleve(struct Eleve * e) {
        int hachage = 0;

        char * chaine = malloc(strlen(e->prenom) + 1 + strlen(e->nom) + 1);

        sprintf(chaine, "%s %s", e->prenom, e->nom);
        hachage = hachageChaine(chaine);

        free(chaine);

        return hachage;
}

ListeEleve *initialisation()
{
    struct ListeEleve *liste = malloc(sizeof(*liste));
    struct MaillonEleve *maillon = malloc(sizeof(*maillon));

    if (liste == NULL || maillon == NULL)
    {
        exit(EXIT_FAILURE);
    }

    maillon->eleve = 0;
    maillon->suivant = NULL;
    liste->premier = maillon;

    return liste;
}

void insertion(ListeEleve *liste, MaillonEleve *elv)
{
    /* Création du nouvel élément */
    struct MaillonEleve *nouveau = malloc(sizeof(*nouveau));
    if (liste == NULL || nouveau == NULL)
    {
        exit(EXIT_FAILURE);
    }
    nouveau->eleve = elv;

    /* Insertion de l'élément au début de la liste */
    nouveau->suivant = liste->premier;
    liste->premier = nouveau;
}

void afficherListe(ListeEleve *liste)
{
    if (liste == NULL)
    {
        exit(EXIT_FAILURE);
    }

    struct MaillonEleve *actuel = liste->premier;

    while (actuel != NULL)
    {
        printf("%s %s Age: %d Notes: %d \n", actuel->eleve->prenom, actuel->eleve->nom, actuel->eleve->age, actuel->eleve->notes);
        actuel = actuel->suivant->eleve;
    }
}

int main ( int argc, char** argv )
{
        struct Eleve e1 = {
        .prenom = "Luc",
        .nom    = "Doncieux",
        .age    = 18,
        .notes  = 11
};
    struct Eleve e2 = {
        .prenom = "Luc",
        .nom    = "Donceuix",
        .age    = 18,
        .notes  = 17
};
    struct Eleve e3 = {
        .prenom = "Luc",
        .nom    = "Dieuxcon",
        .age    = 20,
        .notes  = 15
};

struct MaillonEleve *eleves[taille_tableau] = {NULL};

if (eleves[hachageEleve(&e1)] == NULL)
{
    eleves[hachageEleve(&e1)] = &e1;
    eleves[hachageEleve(&e1)]->suivant = NULL;
}
else
{
    printf("Collision de ");
    eleves[hachageEleve(&e1)]->eleve;
    ListeEleve *listeCollision = initialisation();
    insertion(listeCollision, &e1);
    afficherListe(listeCollision);
}


if (eleves[hachageEleve(&e2)] == NULL)
{
    eleves[hachageEleve(&e2)] = &e2;
    eleves[hachageEleve(&e2)]->suivant = NULL;
}
else
{
    printf("Collision de ");
    eleves[hachageEleve(&e2)]->eleve;
    ListeEleve *listeCollision = initialisation();
    insertion(listeCollision, &e2);
    afficherListe(listeCollision);
}


if (eleves[hachageEleve(&e3)] == NULL)
{
    eleves[hachageEleve(&e3)] = &e3;
    eleves[hachageEleve(&e3)]->suivant = NULL;
}
else
{
    printf("Collision de ");
    eleves[hachageEleve(&e3)]->eleve;
    ListeEleve *listeCollision = initialisation();
    insertion(listeCollision, &e3);
    afficherListe(listeCollision);
}

    return 0;
}

Amen

-
Edité par S kO 3 novembre 2022 à 22:35:10

Tu t'embrouilles à vouloir t'occuper de trop de détails techniques en même temps.

Ecris des fonctions qui font le boulot 

• Tester si un élève (donné par un pointeur) est celui que tu cherches (d'après son nom et son prenom)
• Chercher dans une liste de maillons un élève par son nom et son prenom
• Chercher dans la table de hachage (idem).

La dernière utilise la seconde, qui appelle la première.

La clé de la programmation, c'est de décomposer le truc à faire en sous actions pas trop compliquées à réaliser. On n'a pas beaucoup de neurones, et on est très  vite débordé si on essaie de s'occuper de plein de trucs à la fois. Donc on décompose et on s'organise calmement.

-
Edité par michelbillaud 22 décembre 2022 à 7:46:13

Merci de ta réponse michel.
Les détails techniques que tu mentionne c'est les fonctions initialisation, inserer et afficher ? Car sans elles je ne vois pas comment on peu incrémenter une liste puis l'instruire et tester son retour.

Les listes chainées demandent de faire pointer un bordel allant de :
Nouveau (Eleve) -> Suivant (Eleve) -> Suivant (Eleve)... -> 0 -> NULL

Le nouvel élève à rajouter prenant la place du Nouveau (Eleve) on doit faire pointer Nouveau vers le nouvel élève et Nouveau (Eleve) devient le suivant.

Idem pour l'affichage lorsqu'on a :
Actuel (Eleve) -> Suivant (Eleve) -> Suivant (Eleve)... -> 0 -> NULL

L'élève actuel à afficher est le premier de la liste qui après affichage devient le suivant de l'actuel.

Sans ce jeu de pointeurs qui sont peut-être des détails techniques ça va être compliqué de penser au reste des fonctions importantes, à savoir celles que tu mentionne.

Pour l'instant en créant un nombre de collision je peux "pousser" l'incrémentation des élèves une case plus loin à chaque nouvelle collision et afficher un résultat légitime en : Testant si un élève (donné par un pointeur) est celui recherché (d'après son nom et son prénom)

#include <stdio.h>
#include <stdlib.h>
#define taille_tableau 100

int hachageChaine(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i];
    }
    nombreHache %= taille_tableau;

    return nombreHache;
}

typedef struct Eleve Eleve;
struct Eleve
{
        char prenom[100];
        char nom[100];
        int age;
        int notes;
};

typedef struct Maillon Maillon;
struct Maillon
{
    struct Eleve *eleve;
    struct MaillonEleve *suivant;
};

typedef struct Liste Liste;
struct Liste
{
    struct MaillonEleve *premier;
};


int hachageEleve(struct Eleve * e) {
        int hachage = 0;

        char * chaine = malloc(strlen(e->prenom) + 1 + strlen(e->nom) + 1);

        sprintf(chaine, "%s %s", e->prenom, e->nom);
        hachage = hachageChaine(chaine);

        free(chaine);

        return hachage;
}

int main ( int argc, char** argv )
{
        struct Eleve e1 = {
        .prenom = "Luc",
        .nom    = "Doncieux",
        .age    = 18,
        .notes  = 11
};
    struct Eleve e2 = {
        .prenom = "Luc",
        .nom    = "Donceuix",
        .age    = 18,
        .notes  = 17
};
    struct Eleve e3 = {
        .prenom = "Luc",
        .nom    = "Dieuxcon",
        .age    = 20,
        .notes  = 15
};

struct MaillonEleve *eleves[taille_tableau] = {NULL};
int collision = 0;

if (eleves[hachageEleve(&e1)] == NULL)
{
    eleves[hachageEleve(&e1)] = &e1;
    struct Eleve *eleve1 = eleves[hachageChaine("Luc Doncieux")];
    printf("%s %s %d %d \n", eleve1->prenom, eleve1->nom, eleve1->age, eleve1->notes);
}
else
{
    printf("Collision de %s %s %d %d \n", e1.prenom, e1.nom, e1.age, e1.notes);
    collision++;
}


if (eleves[hachageEleve(&e2)] == NULL)
{
    eleves[hachageEleve(&e2)] = &e2;
    struct Eleve *eleve2 = eleves[hachageChaine("Luc Donceuix")];
    printf("%s %s %d %d \n", eleve2->prenom, eleve2->nom, eleve2->age, eleve2->notes);
}
else
{
    printf("Collision de %s %s %d %d \n", e2.prenom, e2.nom, e2.age, e2.notes);
    collision++;
    eleves[hachageEleve(&e2)+collision] = &e2;
    struct Eleve *eleve2 = eleves[hachageChaine("Luc Donceuix")+collision];
    printf("%s %s %d %d \n", eleve2->prenom, eleve2->nom, eleve2->age, eleve2->notes);
}


if (eleves[hachageEleve(&e3)] == NULL)
{
    eleves[hachageEleve(&e3)] = &e3;
    struct Eleve *eleve3 = eleves[hachageChaine("Luc Doncieux")];
    printf("%s %s %d %d \n", eleve3->prenom, eleve3->nom, eleve3->age, eleve3->notes);
}
else
{
    printf("Collision de %s %s %d %d \n", e3.prenom, e3.nom, e3.age, e3.notes);
    collision++;
    eleves[hachageEleve(&e3)+collision] = &e3;
    struct Eleve *eleve3 = eleves[hachageChaine("Luc Dieuxcon")+collision];
    printf("%s %s %d %d \n", eleve3->prenom, eleve3->nom, eleve3->age, eleve3->notes);
}

    return 0;
}

Mais comme ce n'est pas la solution pour chainer les collisions je refait page blanche et je continue

// EDIT :

Donc là j'ai réussi le test conditionnel dans une fonction (là où je bloquait il y a plusieurs messages) simplement en définissant la structure du tableau de pointeurs hors du bloc de la fonction main()

Pour satisfaire le point 2. de ton précédent message michel je devrait créer une fonction pour "Chercher dans une liste de maillons un élève par son nom et son prénom" à appeler dans else {..} de la fonction insererEleve ?

#include <stdio.h>
#include <stdlib.h>
#define taille_tableau 100

int hachageChaine(char *chaine)
{
    int i = 0, nombreHache = 0;

    for (i = 0 ; chaine[i] != '\0' ; i++)
    {
        nombreHache += chaine[i];
    }
    nombreHache %= taille_tableau;

    return nombreHache;
}

typedef struct Eleve Eleve;
struct Eleve
{
        char prenom[100];
        char nom[100];
        int age;
        int notes;
};

typedef struct Maillon Maillon;
struct Maillon
{
    struct Eleve *eleve;
    struct Maillon *suivant;
};

typedef struct Liste Liste;
struct Liste
{
    struct Maillon *premier;
};

struct Maillon *eleves[taille_tableau] = {NULL};

void insererEleve(Eleve *elv)
{
    if (eleves[hachageEleve(elv)] == 0)
    {
        eleves[hachageEleve(elv)] = elv;
        printf("Affichage de %s %s \n", elv->prenom, elv->nom);
        char *chaine = malloc(sizeof(strlen(elv->prenom)+1+strlen(elv->nom)+1));
        sprintf(chaine, "%s %s", elv->prenom, elv->nom);
        struct Eleve *eleveX = eleves[hachageChaine(chaine)];
        printf("Verification d'appel de %s %s \n", eleveX->prenom, eleveX->nom);
    }
    else
    {
        printf("Collision de %s %s \n", elv->prenom, elv->nom);
    }
}

int hachageEleve(struct Eleve * e) {
        int hachage = 0;

        char * chaine = malloc(strlen(e->prenom) + 1 + strlen(e->nom) + 1);

        sprintf(chaine, "%s %s", e->prenom, e->nom);
        hachage = hachageChaine(chaine);

        free(chaine);

        return hachage;
}

int main ( int argc, char** argv )
{
        struct Eleve e1 = {
        .prenom = "Luc",
        .nom    = "Doncieux",
        .age    = 18,
        .notes  = 11
};
    struct Eleve e2 = {
        .prenom = "Luc",
        .nom    = "Donceuix",
        .age    = 18,
        .notes  = 17
};
    struct Eleve e3 = {
        .prenom = "Luc",
        .nom    = "Dieuxcon",
        .age    = 20,
        .notes  = 15
};
    struct Eleve e4 = {
        .prenom = "Pantoufle",
        .nom    = "Dusec",
        .age    = 19,
        .notes  = 18
};

insererEleve(&e1);
insererEleve(&e2);
insererEleve(&e3);
insererEleve(&e4);

    return 0;
}

Merci encore de votre temps

-
Edité par S kO 4 novembre 2022 à 13:10:00

Je reprend :

Contexte : on suppose que dans un programme, on a besoin de retrouver des élèves par un identifiant (le nom + le prénom). Les infos de chaque élève sont rangées dans une structure.

On veut que l'accès soit rapide. Plus rapide que la recherche dans un tableau ou une liste où les structures sont les unes derrières les autres (temps d'accès  proportionnel au nombre d'élèves), et même que si elles étaient ordonnées (temps logarithmique).

Pour ça on choisit d'utiliser une table de hachage : au lieu d'avoir UNE liste de structures élève, on répartit les éléments dans plusieurs listes. Un TABLEAU (indicé) de listes. Et un élève sera mis dans la liste dont l'indice correspond à une valeur calculée à partir de l'identifiant. 

Illustration : Dans le monde merveilleux de l'administration, on aurait

• 26 boites de dossiers, avec des étiquettes a,b,c etc.
• un dossier va dans la boite qui correspond à la première lettre du nom

ça marche assez bien, pas compliqué de trouver la boite pour un dossier, mais léger problème on sait qu'il y a beaucoup plus de noms qui commencent par A B C ou D (par exemple) par W X Y ou Z, donc ça ne va pas être très équilibré.

Pour mieux répartir, on fait autrement : on fait un calcul tarabiscoté (le hashcode) à partir de l'identifiant, et c'est ce hashcode (modulo quelque chose) qui indique le numéro de la boite.  Comme c'est l'ordinateur qui calcule le hashcode, c'est pas grave que la formule soit tordue.

---

Retour au problème. Donc finalement, une fois qu'on a une formule pour calculer le hashcode, il nous reste à aller chercher une information (l'enregistrement élève) dans la liste dont l'indice s'obtient à partir du hashcode.  C'est tout.

Le reste, pointeur, suivant, NULL, machin truc, border, incrémenter les élèves et pousser les pointeurs c'est du détail. Si tu sais chercher/ajouter/retirer dans une liste, tu sais déjà faire. Si tu ne sais pas, la table de hachage, c'est trop gros pour toi, pour l'instant, parce que tu mélanges les détails de réalisation du hachage à ceux des listes. Exemple

> L'élève actuel à afficher est le premier de la liste qui après affichage devient le suivant de l'actuel.

pourquoi tu dis ça ? pourquoi diable l'affichage ferait-il changer quoi que ce soit au chainage des élèves ???

-
Edité par michelbillaud 4 novembre 2022 à 19:08:03

Coucou michelbillaud

Alors j'ai potassé cet après-midi et je crois avoir pondu quelque chose qui tourne.

Évidement il y a quelques if à rajouter dans les fonctions qui gèrent les éléments & listes.

Qu'en penses-tu ? On peut rechercher un pseudo même si la fonction de hachage retourne le même indice

/*
Contexte : on suppose que dans un programme, on a besoin de retrouver des élèves par un identifiant (le nom + le prénom). Les infos de chaque élève sont rangées dans une structure.

On veut que l'accès soit rapide. Plus rapide que la recherche dans un tableau ou une liste où les structures sont les unes derrières les autres (temps d'accès  proportionnel au nombre d'élèves),
et même que si elles étaient ordonnées (temps logarithmique).

Pour ça on choisit d'utiliser une table de hachage : au lieu d'avoir UNE liste de structures élève, on répartit les éléments dans plusieurs listes. Un TABLEAU (indicé) de listes.
Et un élève sera mis dans la liste dont l'indice correspond à une valeur calculée à partir de l'identifiant.

Illustration : Dans le monde merveilleux de l'administration, on aurait

    26 boites de dossiers, avec des étiquettes a,b,c etc.
    un dossier va dans la boite qui correspond à la première lettre du nom

ça marche assez bien, pas compliqué de trouver la boite pour un dossier, mais léger problème on sait qu'il y a beaucoup plus de noms qui commencent par A B C ou D (par exemple) que par W X Y ou Z,
donc ça ne va pas être très équilibré.

Pour mieux répartir, on fait autrement : on fait un calcul tarabiscoté (le hashcode) à partir de l'identifiant, et c'est ce hashcode (modulo quelque chose) qui indique le numéro de la boite.
Comme c'est l'ordinateur qui calcule le hashcode, c'est pas grave que la formule soit tordue.

---

Retour au problème. Donc finalement, une fois qu'on a une formule pour calculer le hashcode, il nous reste à aller chercher une information (l'enregistrement élève)
dans la liste dont l'indice s'obtient à partir du hashcode.  C'est tout.
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

//Création de la structure joueur
typedef struct Joueur Joueur;
struct Joueur
{
    char pseudo[100];
    int score;
};
//Création de la structure Element
typedef struct Element Element;
struct Element
{
    int indice;
    struct Joueur *maillon;
    struct Element *suivant;
};
//Création de la structure Liste
typedef struct Liste Liste;
struct Liste
{
    struct Element *premier;
};
//Création de la table de hachage des noms
int hachageNom(char *nom)
{
    int nombreHache = 0;
    for (int i = 0 ; nom[i] != '\0' ; i++)
    {
        nombreHache += nom[i];
    }
    nombreHache %= 100;

    return nombreHache;
}
//Création de la table de hachage des pseudo
int hachageJoueur(struct Joueur *j) {
        int nombreHachage = 0;
        char *nom = malloc(strlen(j->pseudo) + 1);
        strcpy(nom, j->pseudo);
        nombreHachage = hachageNom(nom);
        free(nom);

        return nombreHachage;
}
//Création de la fonction pour initialiser la liste
Liste *initialiser()
{
    Element *premier = malloc(sizeof(*premier));
    Liste *liste = malloc(sizeof(*liste));
    premier->indice = 0;
    premier->suivant = NULL;

    return liste;
}
//Création de la fonction pour ajouter un indice dans la liste
void ajoutListe(Liste *liste, int nvIndice, Joueur *j)
{
    Element *nouveau = malloc(sizeof(*nouveau));
    nouveau->indice = nvIndice;
    nouveau->maillon = j;
    nouveau->suivant = liste->premier;
    liste->premier = nouveau;
}
//Création de la fonction pour enlever un indice de la liste
int enleverListe(Liste *liste)
{
    int nombreDeliste = 0;
    Element *elementDeliste = liste->premier;
    nombreDeliste = elementDeliste->indice;
    liste->premier = elementDeliste->suivant;
    free(elementDeliste);

    return nombreDeliste;
}
//Création de la fonction pour afficher la liste
void afficherListe(Liste *liste)
{
    Element *actuel = liste->premier;
    if(liste != NULL || liste->premier != NULL)
    {
        printf("%d\n", actuel->indice);
    }
    printf("\n");
}


void rechercheNom(Liste *liste, char *nom)
{
    Element *recherche = liste->premier;
    if(liste->premier != NULL)
    {
        recherche->indice = hachageNom(nom);
        printf(".pseudo = %s\n", recherche->maillon->pseudo);
        printf(".score = %d\n", recherche->maillon->score);
    }
}


int main(void)
{
//Création du joueur1
    Joueur joueur1 =
    {
        .pseudo = "Henry",
        .score = 66
    };
//Création du joueur2
    Joueur joueur2 =
    {
        .pseudo = "Hnery",
        .score = 77
    };
//Création du joueur3
    Joueur joueur3 =
    {
        .pseudo = "Hneyr",
        .score = 88
    };

//Affichage de la valeur du hash du pseudo du joueur1 & joueur2
    //printf("Valeur hash pseudo du joueur1: %d\n", hachageJoueur(&joueur1));
    //printf("Valeur hash pseudo du joueur2: %d\n", hachageJoueur(&joueur2));
//Affichage de la valeur du hash des noms Henry & Hnery
    //printf("Valeur hash nom Henry : %d\n", hachageNom("Henry"));
    //printf("Valeur hash nom Hnery : %d\n", hachageNom("Hnery"));
//Création du tableau d'indice où seront stockés les valeurs des indices générés par les pseudos des joueurs
    struct Joueur *joueurs[100] = { NULL };
//Création de la liste pour gérer les collisions
    Liste *listeCollision = initialiser();
//Si l'indice du tableau est disponible (vide), on intègre la valeur de l'indice généré par le pseudo du joueur
    if(joueurs[hachageJoueur(&joueur1)] == 0)
    {
        joueurs[hachageJoueur(&joueur1)] = &joueur1;
        struct Joueur *joueur_un = joueurs[hachageNom("Henry")];
        printf("\nLe hachage de la chaine \"Henry\" a permis de trouver cet eleve :\n"
                ".pseudo = %s\n"
                ".score = %d\n",
                joueur_un->pseudo, joueur_un->score);
    }
//Sinon on affiche une collision et on pose l'indice dans la liste
        else
        {
            //puts("Collision du joueur1");
            ajoutListe(listeCollision, hachageJoueur(&joueur1), &joueur1);
            //afficherListe(listeCollision);
            printf("\nLe hachage de la chaine \"Henry\" a permis de trouver cet eleve :\n");
            rechercheNom(listeCollision, "Henry");
        }

    if(joueurs[hachageJoueur(&joueur2)] == 0)
    {
        joueurs[hachageJoueur(&joueur2)] = &joueur2;
        struct Joueur *joueur_deux = joueurs[hachageNom("Hnery")];
        printf("\nLe hachage de la chaine \"Hnery\" a permis de trouver cet eleve :\n"
                ".pseudo = %s\n"
                ".score = %d\n",
                joueur_deux->pseudo, joueur_deux->score);
    }
        else
        {
            //puts("Collision du joueur2");
            ajoutListe(listeCollision, hachageJoueur(&joueur2), &joueur2);
            //afficherListe(listeCollision);
            printf("\nLe hachage de la chaine \"Hnery\" a permis de trouver cet eleve :\n");
            rechercheNom(listeCollision, "Hnery");
        }

    if(joueurs[hachageJoueur(&joueur3)] == 0)
    {
        joueurs[hachageJoueur(&joueur3)] = &joueur3;
        struct Joueur *joueur_trois = joueurs[hachageNom("Hneyr")];
        printf("\nLe hachage de la chaine \"Hneyr\" a permis de trouver cet eleve :\n"
                ".pseudo = %s\n"
                ".score = %d\n",
                joueur_trois->pseudo, joueur_trois->score);
    }
        else
        {
            //puts("Collision du joueur2");
            ajoutListe(listeCollision, hachageJoueur(&joueur3), &joueur3);
            //afficherListe(listeCollision);
            printf("\nLe hachage de la chaine \"Hneyr\" a permis de trouver cet eleve :\n");
            rechercheNom(listeCollision, "Hneyr");
        }

    return 0;
}

Merci d'avance de ta relecture