Liste chainée et pointeur générique ?

Signaler
Messages postés
122
Date d'inscription
mercredi 16 avril 2003
Statut
Membre
Dernière intervention
22 juillet 2006
-
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
-
Bonjour,


J'essaie de coder une liste chainée dont la valeur à stockée est matérialisé par un
pointeur sur void de façon rendre mon code générique:


typedef void* PVOID; //définit un pointeur générique


typedef struct{


    PVOID data; //pointeur générique
    struct ELEMENT *next;//pointe sur l'élément suivant
    struct ELEMENT *prev;//pointe sur l'élément précédent
} ELEMENT;


typedef ELEMENT*  PELEMENT; //définit un pointeur sur une structure ELEMENT


typedef struct{


   PELEMENT head; //pointe sur le 1er élément
   PELEMENT tail;   //pointe sur le dernier élément
   PELEMENT curr; //pointe sur l'élément courant
   UINT nbElem;  //nombre d'éléments dans la liste
} LIST;


//Fonctions relatives à la gestion de la liste add, remove etc......
//  code.............


Supposons que je veuille créer une liste chainée qui manipulerait des int.
Imaginons que la fonction addElem(PVOID data) ajoute un nouvel élément à la liste
et y stocke la valeur 'data' (donc un int dans mon cas).
Comment faire pour passer ma valeur à placer dans la liste ?


Y a bien ça:


int a = 25;
addElem(&25);


mais ça n'a aucun interêt puisqu'il faut créer une variable int pour chaque élément
de la liste.


Ce que j'aimerais faire c'est une utilisation simple du genre:
addElem(25);
mais bien sûr ça ne peut pas marcher.


Aussi, j'aimerais savoir quel est la méthode pour utiliser des liste chainée génériques.
(j'ai regardé comment était conçues les listes dans GTK+ mais j'ai pas tout compris)


Merci d'avance

Tintin 72

10 réponses

Messages postés
2023
Date d'inscription
mardi 24 septembre 2002
Statut
Membre
Dernière intervention
28 juillet 2008
5
Bas en C++, on pourrait faire une fonction template

template <class U>

void addElement(const U & object)


Mais en C, je pense pas que tu es une solution relativement propre. Tu peux toujours créer une fonction pour chaque type.

addElement(int);

addElement(float);

...
Messages postés
122
Date d'inscription
mercredi 16 avril 2003
Statut
Membre
Dernière intervention
22 juillet 2006

Oui j'y avais pensé, mais ça fait vraiment beaucoup de code.
Je sais qu'il y a une solution (complexe!) avec des macros, mais j'ai pas encore tout compris.

Ce que je pige pas avec l'histoire du pointeur générique c'est que, ok, il pointe sur n'importe quel type (char, int etc....)  mais comment il stocke cette valeur ?
Il fais une allocation dynamique ? (comment il fait pour le sizeof() selon si c'est un int un char ou une structure qui est passé en paramètre ?)

Tintin 72
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
3
Ton type generique est tres bien.  Cependant il ne faut pas faire &25 mais &a.
Comme tu as choisi (et tu as raison) d'implementer les listes generiquement, il faut faire une allocation memoire pour ton int :
int *data;
data = malloc(sizeof(int));
*data = 25;
addElement(data);

puis pour la liberation :
free(delElement(list));


L'inconvenient ici c'est que tu alloue un int pour rien, comme un int (32 bits) tient en memoire dans un pointeur (32 bits aussi) il tu suffit de faire :


addElement((void*)25);
en fait tu enregistres le pointeur qui pointe a l'adresse 25 de la memoire.




Pourquoi faire simple quand on peut faire compliqué ?
Messages postés
122
Date d'inscription
mercredi 16 avril 2003
Statut
Membre
Dernière intervention
22 juillet 2006

Merci beaucoup pour ta réponse


Je ne savais pas qu'on pouvait passer une valeur littérale à un pointeur générique.
Par contre comment ferais tu pour récupérer cette valeur ?

Tintin 72
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
3
En fait tu utilise la memoire que tu a alloué pour le champs data de la structure ELEMENT, donc tu te donnes la convention que le pointeur qui pointe a l'adresse 25 est en fait le nombre 25, je dis bien que c'est une convention, i.e. que pour apres recupere la valeur il faut suivre cette convention, donc si tu a l'element <elem>, tu peux avoir la valeur du "PVOID data" correspondant a l'element <elem> par <elem->data>, ensuite si tu veux le nombre, il te suffit donc de faire <nombre=(int)(elem->data)>


 


 






Pourquoi faire simple quand on peut faire compliqué ?
Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Statut
Membre
Dernière intervention
11 août 2006
3
C'est franchement pas une bonne solution.

Si la structure possède un attribut de type void* c'est au code de la
liste de se charger de l'allocation lors de l'insertion d'une cellule
et de la désallocation lors de la suppression de cellule. Il faut dans
ce cas ajouter un attribut qui stocke la taille d'un élément.

Sinon il y a aussi la solution avec une macro pour faire générer le
code parametrable selon le type, mais c'est pas super au niveau de la
maintenance.
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
3
alors ca c'est absolument pas vrai du tout, car la plupart du temps <data> pointe sur une structure (par exemple TOTO), donc l'allocation de TOTO est faite a l'exterieur, et on peut utiliser 10 fois la liste, sans a avoir a chaque fois besoin de reallouer TOTO. D'ailleurs c'est pas deleteElem, mais plutot removeElem, on enleve seulement l'element, et surtout on ne le supprime pas a coup de free(data). (en revanche il faut faire free(elem)).
Le gestionnaire des listes n'a pas a s'occuper de ce qu'est en realite <data>, en plus <data> peut pointer sur un tableau de la pile, ou quelque chose d'autre , et alors il ne faudra surtout pas faire free(data)

Pourquoi faire simple quand on peut faire compliqué ?
Messages postés
475
Date d'inscription
dimanche 3 octobre 2004
Statut
Membre
Dernière intervention
11 août 2006
3
Tu n'as pas compris, c'est infiniment plus simple à l'utilisation si le
conteneur "semble" stocker des valeurs plutot que des "references",
sinons il faut tenir compte de la durée de vie de chaque objet contenue
et ca devient trés vite ingérable.

Pour chaque insertion on alloue et on copie, indépendamment du type d'allocation de l'objet.
Messages postés
2671
Date d'inscription
vendredi 25 janvier 2002
Statut
Membre
Dernière intervention
6 février 2013
2
Eh ben il y en a qui aime bien se prendre la tete ....


Comme steve l'a fait remarquer, c'est au gestionnaire de liste de gérer les allocations. Je suis d'avis pour utiliser un deuxième paramètre indiquant la taille de la variable utilisé.
Allouer en dohors du gestionnaire, puis passé ensuite le pointeur sur cette allocation ne peut etre que source d'erreur et de bug!
Mieux vaut privilégier un code simple et sure, qu'un code qui risque d'etre ingérable par la suite.

Shell
Messages postés
1138
Date d'inscription
mardi 10 juin 2003
Statut
Membre
Dernière intervention
25 janvier 2009
3
le programme va alors passer son temps a copier des structures... de plus cette methode impose que <data> soit toujours une allocation memoire... pas evident.

Pourquoi faire simple quand on peut faire compliqué ?