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 totof2000 . É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.
tu la perds ici :
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 dalfab . É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 dansnum
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 delist_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 gunsailor . É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 Barnabé . É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 Tonton Th (Mastodon) . Évalué à 6. Dernière modification le 21 avril 2023 à 22:19.
Il faut faire du Yoda programming !
Et là, tu te fait gronder par le jedi-compilateur…
[^] # Re: Coquille méchante
Posté par gunsailor . Évalué à 2.
Bonsoir Tonton Th,
je vais prendre cette habitude désormais…
Merci!
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.