Partage
  • Partager sur Facebook
  • Partager sur Twitter

Implémentation des listes chainées

    12 avril 2022 à 13:01:28

    Bonjour,

    J'aurais besoin d'aide pour vérifier que mon implémentation des listes chainées fonctionne correctement.

    Pour le moment, je n'ai créé que des listes chainées d'entiers (int) et il y a possibilité d'initialiser cette liste soit avec un entier, soit avec un tableau d'entiers, et aussi d'ajouter des éléments en fin de liste après sa création.

    Merci d'avance pour votre aide :)

    Voici, dans l'ordre, mon header et mon code source: 

    liste_chainee.h :

    #ifndef LISTE_CHAINEE_H_INCLUDED
    #define LISTE_CHAINEE_H_INCLUDED
    
    typedef struct Element Element;
    struct Element
    {
        int nombre;
        Element *suivant;
    };
    
    typedef struct IntList IntList;
    struct IntList
    {
        Element *premier;
        int len;
    };
    
    IntList *initintlist(int nombre);
    
    IntList *inittablist(int *tableau);
    
    void appendint(IntList *liste, int nombre);
    
    #endif // LISTE_CHAINEE_H_INCLUDED

    liste_chainee.c :

    #include <stdio.h>
    #include <stdlib.h>
    #include "liste_chainee.h"
    
    IntList *initintlist(int nombre)
    {
        /* L'espace memoire necessaire est alloue*/
        IntList *liste = malloc(sizeof(*liste));
        Element *element = malloc(sizeof(*element));
    
        if (liste == NULL || element == NULL)
        {
            exit(EXIT_FAILURE);
        }
    
        /* Creation d'une liste chainee a 1 element,
        contenant le nombre passe en parametre
        */
        element->nombre = nombre;
        element->suivant = NULL;
        liste->premier = element;
        liste->len = 1;
    
        return liste;
    }
    
    IntList *inittablist(int *tableau)
    {
        /* L'espace memoire necessaire est alloue*/
        IntList *liste = malloc(sizeof(*liste));
        Element *element = malloc(sizeof(*element));
    
        if (liste == NULL || element == NULL)
        {
            exit(EXIT_FAILURE);
        }
    
        /* Ajoute succesivement les elements du tableau passe
        en parametre a la liste chainee en utilisant la
        fonction (void appendint(IntList *liste, int nombre))
        definie apres
        */
    
        element->nombre = tableau[0];
        element->suivant = NULL;
        liste->premier = element;
        liste->len = 1;
    
        int n = sizeof(tableau) / sizeof(tableau[0]);
    
        for (int i = 1; i<n; i++)
        {
            appendint(liste, tableau[i]);
        }
    
        return liste;
    }
    
    void appendint(IntList *liste, int nombre)
    {
        /* Grace a la boucle while, on cherche le
        dernier element de la liste chainee
        */
        Element *element = liste->premier;
    
        while (element->suivant != NULL)
        {
            element = element->suivant;
        }
    
        /* On alloue l'espace necessaire pour le nouvel element */
        Element *nouveau = malloc(sizeof(*nouveau));
    
        if (nouveau == NULL)
        {
            exit(EXIT_FAILURE);
        }
    
        /* Initialisation du nouvel element et
        mise a jour de la taille de la liste
        */
        element->suivant = nouveau;
        element->nombre = nombre;
        liste->len++;
    }



    -
    Edité par Thomatelot 12 avril 2022 à 14:04:53

    • Partager sur Facebook
    • Partager sur Twitter
      12 avril 2022 à 13:43:12

      Je n'ai pas testé ton code (l'as-tu fait ?), mais dans ta fonction IntList *inittablist(int *tableau)tu dois passer la taille du tableau, c'est à dire le nombre d'éléments qu'il comporte, car lorsque le tableau est passé en paramètre dans une fonction, ce qui est passé c'est en fait l'adresse mémoire du premier élément et pas réellement un type tableau. Autrement, la fonction n'est pas capable de déterminer cela toute seule et la seule chose que tu vas faire en faisant int n = sizeof(tableau) / sizeof(tableau[0]); dans cette fonction c'est diviser le nombre de bytes occupés en mémoire par une adresse mémoire par la taille en bytes d'un int.

      -
      Edité par Dlks 12 avril 2022 à 13:46:46

      • Partager sur Facebook
      • Partager sur Twitter
        12 avril 2022 à 13:44:28

        Bonjour,

        il y a beaucoup de choses à dire concernant ton code.

        Concernant «le code»

        Voici les messages du compilo après avoir ajouté un include sur ton header … :

        $ gcc -Wall -Wextra -fanalyzer -c liste_chainee.c
        liste_chainee.c: In function ‘inittablist’:
        liste_chainee.c:50:40: warning: division ‘sizeof (int *) / sizeof (int)’ does not compute the number of array elements [-Wsizeof-pointer-div]
           50 |     for (int i = 1; i<(sizeof(tableau) / sizeof(int)); i++))
              |                                        ^
        liste_chainee.c:28:27: note: first ‘sizeof’ operand was declared here
           28 | IntList *inittablist(int *tableau)
              |                      ~~~~~^~~~~~~
        liste_chainee.c:50:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘long unsigned int’ [-Wsign-compare]
           50 |     for (int i = 1; i<(sizeof(tableau) / sizeof(int)); i++))
              |                      ^
        liste_chainee.c:50:60: error: expected statement before ‘)’ token
           50 |     for (int i = 1; i<(sizeof(tableau) / sizeof(int)); i++))
              |                                                            ^
        liste_chainee.c:52:34: error: ‘i’ undeclared (first use in this function)
           52 |         appendint(liste, tableau[i]);
              |                                  ^
        liste_chainee.c:52:34: note: each undeclared identifier is reported only once for each function it appears in
        


        Si on supprime la parenthèse surnuméraire il reste un message important qui te rappelle qu'il est impossible de connaître le nombre d'élément d'un tableau si tu fournis uniquement un pointeur sur le premier élément (erreur classique de débutant).

        Donc : il faut commencer par lire ce que ton compilo raconte et tenir compte de ses remarques.

        Ensuite je pourrais rajouter :

        • heu … la liste vide ? tu l'as complètement zappée ?
        • nommage : si tu implémentes une structure de données, il est toujours préférable de préfixer tes primitives d'accès. Par exemple tu pourrais utiliser le préfixe intlist_ pour tout ce qui concerne des fonctions dédiées aux IntList. Ton API serait plus claire ainsi :

          #ifndef LISTE_CHAINEE_H_INCLUDED
          #define LISTE_CHAINEE_H_INCLUDED
           
          typedef struct Element Element;
          struct Element
          {
              int nombre;
              Element *suivant;
          };
           
          typedef struct IntList IntList;
          struct IntList
          {
              Element *premier;
              int len;
          };
           
          IntList *intlist_init(int nombre);
           
          IntList *intlist_init_from_array(int *tableau);
           
          void intlist_append(IntList *liste, int nombre);
           
          #endif // LISTE_CHAINEE_H_INCLUDED
        • ton API serait sans doute à revoir un peu. Par exemple, pourquoi ne pas avoir de constructeur qui renvoie une liste vide ?

          #ifndef LISTE_CHAINEE_H_INCLUDED
          #define LISTE_CHAINEE_H_INCLUDED
           
          typedef struct Element Element;
          struct Element
          {
              int value;
              Element *next;
          };
           
          typedef struct IntList IntList;
          struct IntList
          {
              Element *premier;
              int len;
          };
           
          IntList *intlist_init(void);
          
          IntList *intlist_init_from_int(int value);
           
          IntList *intlist_init_from_array(size_t size, int array[size]);
           
          void intlist_append(IntList *list, int value);
           
          #endif // LISTE_CHAINEE_H_INCLUDED
          
          ton API serait sans doute à revoir un peu. Par exemple, pourquoi ne pas avoir de constructeur qui renvoie une liste vide ?
          
          
          
          tu remarqueras que dans cette version j'ai également corrigé l'initialisation à partir d'un tableau, et nettoyé le mélange franglais.

        • Il y a beaucoup de duplication de code !!!! surtout en ce qui concerne la gestion des maillons. Il faudra refactorer cela et le placer dans un module séparé. Par exemple un couple intlist_element.h/intlist_element.c avec comme API :

          #pragma once
          
          typedef struct intlist_element intlist_element_t;
          
          intlist_element_t *intlist_element_new(int value);
          intlist_element_t *intlist_element_full(int value, intlist_element_t *next);
          
          int intlist_element_get_value(intlist_element_t *elem);
          intlist_element_t *intlist_element_get_next(intlist_element_t *elem);
          
          void intlist_element_set_value(intlist_element_t *elem, int value);
          void intlist_element_set_next(intlist_element_t *elem, intlist_element_t *next);

          Ici j'ai remplacé les include guards traditionnels par un plus moderne «#pragma once» de même effet.
          Si tu as besoin de créer un maillon tu as ce qu'il faut et c'est centralisé à un seul endroit = maintenance, debug et évolution facilités ;

        Il y a d'autres remarques mais je vais déjà te laisser réagir à celles-ci.

        • Partager sur Facebook
        • Partager sur Twitter
          12 avril 2022 à 13:54:44

          Merci de vos réponses

          Je cherchais justement le moyen d'obtenir la longueur du tableau de mon côté, mais je n'ai pas pensé à tout simplement le passer en paramètre... :p

          N'hésitez pas à me le signaler si quelques erreurs du débutant que je suis vous horrifient ! :honte:

          (Et désolé pour le franglais XD)

          -
          Edité par Thomatelot 12 avril 2022 à 14:00:27

          • Partager sur Facebook
          • Partager sur Twitter
            12 avril 2022 à 16:26:14

            Une petite remarque sans importance... Plutôt que :

            IntList *inittablist(int *tableau);

            je préfère :

            IntList *inittablist(int tableau[]);

            Oui, c'est équivalent. Mais équivalent pour l'ordinateur. L'être humain qui lit ces lignes voit deux choses qui ont un sens différent : un pointeur, un tableau. Voyant le tableau, il risque plus facilement de se dire « oups, j'ai oublié de transmettre la taille du tableau ».

            -
            Edité par robun 12 avril 2022 à 16:26:41

            • Partager sur Facebook
            • Partager sur Twitter
              12 avril 2022 à 18:40:54

              Je pense que c'est une erreur que d'initialiser une liste en lui fournissant une ou des valeurs à insérer dès le départ.
              La fonction d'initialisation "initialise" une liste vide.
              Ça te prend également une fonction qui va afficher les éléments de ta liste.
              Pour ce qui est d'ajouter des éléments, il y a plusieurs possibilités:
              + ajouter au début (la plus facile)
              + ajouter à la fin
              + ajouter à une position
              + ajouter avant ou après une valeur (liste ordonnée)

              Les trois premières pourraient appeler la même fonction.

              Exemple:

              insert(liste, valeur, 0)   ajoute au début

              insert(liste, valeur, -1)   ajoute à la fin

              insert(liste, valeur, position)   on vérifie que la position est correcte d'après le descripteur de liste
              Pour ajouter tous les éléments d'un tableau, il faut appeler la fonction d'ajout appropriée au lieu de dupliquer le code.
              Cela évitera certaines erreurs. Si ça ne marche pas, on regarde à un seul endroit.

              Il faut réduire le plus possible le nombre d'endroits où tu appelles malloc.
              Et il y aura les fonctions de suppressions correspondantes.
              Ou la modification d'un élément dans la liste.

              Et chercher un élément dans la liste et retourner soit sa position soit sa valeur.

              Quoi faire si l'élément n'est pas dans la liste ?

              -
              Edité par PierrotLeFou 12 avril 2022 à 19:05:12

              • Partager sur Facebook
              • Partager sur Twitter

              Le Tout est souvent plus grand que la somme de ses parties.

                13 avril 2022 à 7:55:07

                Il y a plusieurs approches

                • Minimaliste : on fournit un ensemble d'opérations les plus simples possible, qui suffisent (en les combinant) à tout faire 
                • Utilitaire : on fournit des opérations qui permettent de faire d'un seul coup les opérations les plus courantes dans un programme (par exemple ajouter le contenu d'une liste à la fin d'une autre)

                Si on vise la seconde approche, il faut mieux avoir écrit pas mal d'applications pour voir ce qui sera vraiment pratique à l'usage. Et aussi savoir où s'arrêter.

                • Partager sur Facebook
                • Partager sur Twitter
                  13 avril 2022 à 12:28:46

                  Ce qui est généralement rentable de faire est de suivre le principe KISS → keep it simple, stupid ← de manière non naïve.

                  Il vaut mieux avoir quelque chose de simple et fonctionnel qu'avoir tout un tas de possibilités non utilisées souvent buguées qui deviennent inutilisables. Cela permet aussi d'avoir une API évolutive sans être disruptive.

                  • Partager sur Facebook
                  • Partager sur Twitter
                    13 avril 2022 à 14:47:11

                    Je ne présenterai pas mon code ici (parce qu'il n'est pas présentable ...)
                    J'ai quelques fonctions de base pour soutenir les autres:
                    getArea qui demande de la mémoire avec malloc
                    setList qui initialise une liste vide
                    getNode qui initialise un noeud
                    ckRange pour les accès par position
                    Et les autres:
                    insert qui insère par position (comme j'avais décrit)
                    sorting qi insère en ordre
                    search qui retourne la position correspondante à une valeur
                    obtain qui retourne la valeur correspondant à une position
                    delete qui élimine une valeur
                    putout qui élimine une position
                    change qui remplace une valeur par une autre
                    modify qui remplace la valeur à une position
                    reverse qui inverse l'ordre de la chaîne.
                    display qui affiche une liste

                    Mes fonctions sont toutes très semblable mais trop différentes pour admettre une primitive commune. Je les trouve tout de même assez simples.
                    Avec ça, on peut copier un tableau dans une liste ou recopier une liste dans une autre.
                    On peut faire une fonction pop en combinant search/obtain avec delete/putout, mais ça n'est pas tout à fait efficace.

                    -
                    Edité par PierrotLeFou 13 avril 2022 à 14:51:27

                    • Partager sur Facebook
                    • Partager sur Twitter

                    Le Tout est souvent plus grand que la somme de ses parties.

                    Implémentation des listes chainées

                    × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                    • Editeur
                    • Markdown