Forum Programmation.c implémentation d'une liste chaînée en langage c

Posté par  . Licence CC By‑SA.
Étiquettes :
0
20
avr.
2023

bonjour,
je me suis acheté un bouquin: "Maîtrise des algorithmes en C" de Kyle Loudon.
j'arrive au 5eme chapitre qui parle des listes chaînées… je comprends l'algorithme, mais lors qu'il s'agit de le faire fonctionner, je tombe sur une erreur de libération de pointeur.

L'algorithme est le suivant:

list.h:

        #ifndef __LIST
        #define __LIST

        typedef struct ListElmt_{
            void *data;
            struct ListElmt_ *next;
        } ListElmt;

        typedef struct List_{
            int size;
            ListElmt *head;
            ListElmt *tail;
            int (*compare)(void *a, void *b);
            void (*destroy)(void *data);

        } List;

        void list_init(List* list, void (*destroy)(void *data));
        int list_destroy(List *list);
        int list_ins_next(List* list, ListElmt *element, void* data);
        int list_rem_next(List* list, ListElmt *element, void** data);

        #define list_next(element) ((element)->next)
        #define list_head(list) ((list)->head)
        #define list_tail(list) ((list)->tail)
        #define list_is_head(list, element) \
            ((element) == ((list)->head)?1:0)
        #define list_is_tail(element)\
            ((element)->next == NULL?1:0)
        #define list_data(element) (element)->data
        #define list_size(list) (list)->size

        #endif

et list.c:

        #include<stdlib.h>
        #include<string.h>
        #include"list.h"

        void list_init(List* list, void (*destroy)(void *data))
        {
            list->size = 0;
            list->head=NULL;
            list->tail= NULL;
            list->destroy = destroy;
        }

        int list_destroy(List *list)
        {
            void *data;
            while(list_size(list) > 0)
            {
                if(list_rem_next(list, NULL, (void**) &data) == 0 && list->destroy != NULL)
                {
                    list->destroy(data);
                }
            }
            memset(list, 0, sizeof(list));
            return 0;
        }

        int list_ins_next(List * list, ListElmt * element, void * data)
        {
            ListElmt * newElmt;

            if((newElmt = (ListElmt*) malloc(sizeof(ListElmt))) == NULL)
                return -1;
            newElmt->data = (void*) data;

            if(element == NULL)
            {
                if(list_size(list) == 0)
                    list->tail = newElmt;

                newElmt->next = list->head;
                list->head = newElmt;
            }else{
                if(element->next = NULL)
                    list->tail = newElmt;

                newElmt->next = element->next;
                element->next = newElmt;
            }

            list->size++;
            return 0;
        }

        int list_rem_next(List *list, ListElmt *element, void **data)
        {
            ListElmt * lastElmt;

            if(list_size(list) == 0)
                return -1;

            if(element == NULL)
            {
                *data = list->head->data;
                lastElmt = list_head(list);
                list->head=list_head(list)->next;
                if(list_size(list) == 1)
                    list->tail = NULL;
            }else{
                if(element->next == NULL)
                    return -1;

                *data = element->next->data;
                lastElmt = element->next;
                element->next = element->next->next;

                if(element->next == NULL)
                    list->tail = element;
            }
            free(lastElmt);
            list->size--;
            return 0;
        }

et voici comment j'essaie de le faire fonctionner:

        #include<stdio.h>
        #include"list.h"
        #include<time.h>
        #include<stdlib.h>

        int main()
        {
            int a[4] = {9,2,1,7};
            List list;
            list_init(&list, NULL);
            for(int i = 0; i < 4; i++)
                list_ins_next(&list, NULL, &a[i]);
            printf("%d\n", *((int*)(list_head(&list)->data)));
            int *num = malloc(sizeof(int));
            srand(time(NULL));
            int p = rand() % (list_size(&list) - 1);
            ListElmt *le;
            for(int i = 0; i < p; i++)
            {
                if(!i)
                    le = NULL;
                else if(i == 1)
                    le = list_head(&list);
                else
                    le = list_next(le);
            }
            list_rem_next(&list, le, (void**)&num);
            printf("list_rem_next => %d\n", *(int*)num);
            free(num); // ici se trouve l'erreur
            return 0;
        }

comme indiqué dans la fonction main, c'est au niveau de la libération du pointeur "num" que se situe l'erreur. Tout ça parce que je récupère sa valeur depuis "list_rem_next" où il prend le data ( du nœud que je retire ) qui est stocké dans un void*… Il y a certainement un problème d'alignement! Mais cet algorithme est censé fonctionner, alors je me dis que c'est moi qui n'ai pas compris quelque chose.

Si quelqu'un pouvait me venir en aide, ce serait chouette!!

  • # Ca me paraît normal.

    Posté par  . Évalué à 3. Dernière modification le 20 avril 2023 à 20:35.

    Sauf si j'ai raté quelque chose …. tu as rempli ta liste avec des variables déclarées sur la pile. Sauf erreur de ma part, tu as perdu la valeur allouée.

        for(int i = 0; i < 4; i++)
            list_ins_next(&list, NULL, &a[i]);
    

    tu la perds ici :

    list_rem_next(&list, le, (void**)&num);
    
    

    je ne vois d'ailleurs pas ce que tu fais de la mémoire que tu as alloué sur le tas. Mais comme je suis un peu fatigué, j'ai peut-être raté quelque chose.

  • # Bien suivre les allocations mémoire

    Posté par  . Évalué à 5.

    Je confirme, ce n'est pas la valeur allouée qui détruite.

    Quand on alloue de la mémoire, la fonction malloc() retourne un pointeur. Ce pointeur sert à 2 choses:
    - il désigne la zone où on y mettra des données
    - il ne faut pas perdre cette valeur, car il faudra la fournir à free() au moment de libérer cette mémoire.

    Ici tu mémorises dans num une zone allouée.
    Plus loin tu appelles list_rem_next(&list, le, &num);, et cette fonction va écraser ce qu'il y a dans num pour le remplacer par l'adresse de élément retiré de la liste. Les éléments insérés en *data dans la liste sont &a[0] &a[1] &a[2] &a[3], et au retour de list_rem_next(&list, le, (void**)&num);, num vaut un de ces 4 pointeurs. Eux pointent dans ton tableau qui est de la mémoire locale sans allocation, donc pas de libération à faire ici!

    Il ne faut, dans ce cas, rien allouer dans num et ne rien libérer à la fin.

    PS: et fais attention à ne pas apprendre un C trop ancien. Dans les années 80, on utilisait des macros pour optimiser des traitements courts, problème ces macros sont:
    - difficile à lire/écrire
    - sources d'erreurs : transcodage lié au principe des macros et non vérification des types.
    Depuis les années 90, on utilise à la place les fonctions inline qui n'ont pas ces handicaps, elles ont été officialisées bien après (en 1999).

    • [^] # Re: Bien suivre les allocations mémoire

      Posté par  . Évalué à 1.

      merci dalfab,
      ton commentaire m'a permis de résoudre mon problème!
      En effet, je ne vois pas pourquoi j'allouais de la mémoire…
      J'ai pris en compte aussi ta réflexion à propos des fonctions en ligne.
      Je vous remercie tous chaleureusement !!
      bonne soirée!

  • # Coquille méchante

    Posté par  . Évalué à 3.

    Le genre de coquille qui peut faire perdre du temps :

    Dans list_ins_next() tu as la ligne

    if(element->next = NULL)

    Le compilateur ne voit pas ce genre d'erreur, sauf si on lui demande, c'est une bonne habitude de compiler avec -Wall -Werror (afficher tous les warnings, et considérer les warnings comme des erreurs.

    • [^] # Re: Coquille méchante

      Posté par  (site web personnel, Mastodon) . Évalué à 6. Dernière modification le 21 avril 2023 à 22:19.

      Le compilateur ne voit pas ce genre d'erreur,

      Il faut faire du Yoda programming !

      if (NULL = element->next) 
      

      Et là, tu te fait gronder par le jedi-compilateur…

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.