Discussion :

[ncheboi]

Bonjour.
Je suis en train d'implémenter un tas de Fibonacci (mon problème n'a pas de lien avec cette structure, donc pas de souci si vous ne la connaissez pas).
En bref c'est un type d'arbre (en très bref).
Je veux créer une librairie de sorte que ma structure puisse être utilisé pour gérer des int, char, float, etc...
J'ai deux solutions:

soit dans la déclaration de ma structure j'utilise:

typedef int valeur;

par défaut j'ai int mais si quelqu'un veut utiliser autre chose, il suffit de changer int en char, ou quoi que ce soit. Le souci c'est que là, la librairies doit être modifiée par l'utilisateur et recompilée pour qu'il puisse s'en servir.

Sinon, je viens de découvrir l'existence de void* . J'ai cherché pour voir mais j'arrive pas à savoir si cela va pouvoir m'aider ou pas.

Je résume mon problème:
créer une struct générique qui peut être utilisé pour contenir différents types d'élements....

J'espere avoir été clair!!!

[Invité(e)]

Bonjour,

Une solution simple serait d'utiliser un union comme type de base. Ce n'est pas optimisé en terme de mémoire, mais c'est un premier pas vers la généricité.

[diogene]

Tu peux envisager une structure Noeud pour chaque noeud de ton arbre contenant :
- les informations de chainage nécessaires à la construction de l'arbre (et qui sont indépendantes de l'information associée au noeud).
- un pointeur void* qui va pointer sur l'information associée à chaque noeud. Cette information peut être représentée par n'importe quel type de données T adapté à la situation (int, float, structure, tableaux...)

La création d'un nouveau noeud implique
- de construire la nouvelle structure Noeud
- de placer l'adresse de l'objet de type T, contenant l'information à associer à ce noeud, dans le pointeur void*. Le plus souvent, cet objet sera construit par allocation dynamique.
- de placer la structure Noeud obtenue dans l'arbre.

La contrainte est que chaque fois que tu auras besoin d'accéder à l'information associée à un Noeud, tu devras transtyper le pointeur void * du noeud en un pointeur de type T* avant de pouvoir le déréférencer.

[ncheboi]

Bonjour,

Une solution simple serait d'utiliser un union comme type de base. Ce n'est pas optimisé en terme de mémoire, mais c'est un premier pas vers la généricité.

Pour le union, le problème c'est qu'il faut déclarer tous les types envisageable dedans. Vu qu'il y en a une infinité.... Par exemple, si un jour on décide d'utiliser un type structure nouvellement créé....

Tu peux envisager une structure Noeud pour chaque noeud de ton arbre contenant :
- les informations de chainage nécessaires à la construction de l'arbre (et qui sont indépendantes de l'information associée au noeud).
- un pointeur void* qui va pointer sur l'information associée à chaque noeud. Cette information peut être représentée par n'importe quel type de données T adapté à la situation (int, float, structure, tableaux...)

La création d'un nouveau noeud implique
- de construire la nouvelle structure Noeud
- de placer l'adresse de l'objet de type T, contenant l'information à associer à ce noeud, dans le pointeur void*. Le plus souvent, cet objet sera construit par allocation dynamique.
- de placer la structure Noeud obtenue dans l'arbre.

La contrainte est que chaque fois que tu auras besoin d'accéder à l'information associée à un Noeud, tu devras transtyper le pointeur void * du noeud en un pointeur de type T* avant de pouvoir le déréférencer.

C'est effectivement une structure de noeud que j'avais envisagé (de toute façon obligatoire pour un tas de fibonacci). Donc si je comprends bien le void* peut répondre à mon problème. Par contre, je ne suis pas sur de comprendre la contrainte dont tu parles. Elle va s'appliquer à la personne qui utilise ma librairie c'est ça? Cette personne sera obligée de faire un cast pour accéder à la valeur d'un noeud? Si c'est le cas, j'ai peur que c'est trop contraignant.
N'y existe-t-il aucune autre méthode pour obtenir ce que je souhaite?

Merci beaucoup en tout cas pour vos réponses rapides!

[valefor]

Un solution (non portable) serait alors de faire une macro qui te renvoie un pointeur sur les données de ton noeud :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
#define GET(tree, node_id, data) do { data = typeof(data)get_ptr(tree, node_id); } while(0)

Si tu veux plus de détails sur typeof http://gcc.gnu.org/onlinedocs/gcc/Typeof.html, mais encore une fois ce n'est pas portable.

[diogene]

La contrainte n'est pas si lourde et est habituelle pour des structures ou des traitements de données génériques.
Du point de vue de l'utilisateur, lorsqu'il récupère une information stockée dans le tas disons par une fonction GetData() qui renvoie un void * sur l'information souhaitée (disons de type Info) , il n'a qu'à écrire quelque chose du genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Info* p = (Info*)GetData(-----)
// Après, il fait ce qu'il veut.

Pour ajouter une information, il n'a même pas besoin de transtyper, le passage Data* à void* est fait implicitement

Par exemple, pour illustrer l'utilisation du void * :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//-----------------------------------------------------
 // fonction de la "bibliothèque"
void * GetData(void * p )
{
  return p;
}
//-----------------------------------------------------
//-----------------------------------------------------
#include <stdio.h>
#define GetInfo (Info*)GetData
typedef struct
{
  int a;
  int b;
}Info;
//-----------------------------------------------------
int main(void)
{
  Info infosource = {123, 456};
  Info infodest = *GetInfo(&infosource);
  printf("%d %d\n",infodest.a, infodest.b);
  return 0;
}

[ncheboi]

D'accord. Merci diogène, je crois que je vais prendre cette solution. Par contre, voici un autre problème. Voici mon code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
void insert_first(List* list, void* v){
	Element* element = (Element*) malloc(sizeof(*element));
	if(element == NULL)
		exit(EXIT_FAILURE);
	element->next = list->first;
	element->data = v;
 
	list->first = element;
	list->no_elements++;
}

Ici je passe un void* en paramètre. J'appelle la fonction dans mon main avec ça par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
insert_first(list,5);

Là j'ai un warning: pointer mismatch for actual parameter 2...
Du coup j'ai transtypé le 2ème paramètre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
insert_first(list,(void*)5);

C'est normal de devoir faire ça parce que pour un utilisateur, ça par contre, c'est assez contraignant...

[diogene]

Ici je passe un void* en paramètre. J'appelle la fonction dans mon main avec ça par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

insert_first(list,5);

Là j'ai un warning: pointer mismatch for actual parameter 2...
Du coup j'ai transtypé le 2ème paramètre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

insert_first(list,(void*)5);

- Tu ne peux pas écrire 5, qui n'est pas une adresse
- Tu ne peux pas écrire &5, puisque 5 n'est pas un objet
- Tu ne dois pas avoir le réflexe de transtyper un pointeur génant. En règle générale, ceci va masquer ce qui est en fait une erreur que le compilateur t'avait complaisamment signalée.

Ta fonction insert_first() est donc faite pour insérer une nouvelle adresse dans ton tas. Puisque tu stockes l'adresse de la donnée, celle-ci doit être contenue dans un objet et l'argument void* doit être son adresse.
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
int i = 5 ;
insert_first(list, &i);
 
int * p = malloc(sizeof *p);
*p = 5;
insert_first(list, p);

[Médinoc]

Ce que je conseillerais, c'est d'utiliser un intptr_t au lieu d'un void* pour le champ "data" de ta liste.

[diogene]

Ce que je conseillerais, c'est d'utiliser un intptr_t au lieu d'un void* pour le champ "data" de ta liste.

Quel est l'intérêt ?

[Médinoc]

Eh bien, s'il veut une liste chaînée générique, autant en faire une où l'on peut mettre aussi bien mettre des entiers que des pointeurs...

Ensuite reste à savoir si la liste chaînée générique est bien la réponse à ses problèmes...

[ncheboi]

Je ne connais pas le type intptr_t en C. De ce que vous avez écrit, dois-je comprendre que c'est un type de donnée qui fonctionne comme un pointeur mais où l'on peut stocker des entiers?

[diogene]

C'est un type entier (signé) optionnel. Un pointeur sur void, void*, peut être converti en intptr_t et lorsque ce intptr_t est reconverti en void *, on retrouve la valeur d'origine du pointeur. On peut s'en servir pour stocker un void * dans un entier, moyennant cette gymnastique.
Dans le genre, il y a aussi la version entier non signé uintptr_t.

A mon avis, si tu l'utilises, ta bibliothèque dépend de l'existence de ce type et sa gestion devient plus difficile : La grandeur stockée est quelquefois considérée comme un entier signé (de ce type) et quelquefois comme un pointeur.
Dans cette optique qui accepte une ambiguité sur le type exact de la grandeur stockée, je préfèrerai, sans doute, utiliser une union comportant les entiers signés et non signés, un float, un double, un void*. Au moins on peut traiter un plus grand nombre de types différents.

[ncheboi]

Bonjour.
Bon j'ai enfin fini d'écrire les différentes fonctions de mon tas. Par contre, je ne vois pas trop comment écrire l'algo qui pourrait l'afficher.

Le tas consiste en une liste circulaire doublement chainée d'éléments. Chaque élément peut avoir des enfants qui eux aussi sont dans une liste chainée et ainsi de suite.

J'ai pensé à faire un affichage du genre:

a -> b(b' - > b'' -> b''' (b1 -> b2 ) ) -> c -> d.

Ici les élements racines sont a, b , c et d.
b a 3 enfants b',b'', et b''' et b''' à 2 enfants (b1 et b2)...
Le nombre de niveaux varient...

J'ai pensé à faire de la récursivité mais je ne vois vraiment pas comment je peux m'en sortir.
Des idées???
Merci

[diogene]

La récursivité simplifie les choses.
On peut suivre le schéma suivant en pseudo-code C :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void AfficherListe (type * liste)
{
  if(liste != NULL}
  {
     type * p = liste
     printf("(");
     do
     {	 
         Afficher le noeud p ;
         AfficherListe(liste des enfants de p);
         p = frere de p;
         if(p != liste) printf("->");
     } while(p != liste);
     printf(")");
  }
}

[ncheboi]

Merci.
J'ai utilisé ton pseudo code pour modifier ce que j'avais commencé à faire. J'ai modifié un peu pour afficher un message dans le cas où la liste est vide. voici ce que ça donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
static void printHeap(Heap_Element* root){
    Heap_Element* iterator;
    printf("(");
    if(root != NULL){
        iterator = root;
 
        do{
            printf("%i",iterator->key);
                if(iterator->child != NULL){
                    printHeap(iterator->child);
                }
            iterator = iterator->right_sib;
            if(iterator!= root)
                printf(" -> ");
        }while(iterator != root);
 
    }
    else printf("this is an empty heap\n");
    printf(")");
}

[ncheboi]

J'ai un "problème" trop con là. C'est pour faire un retour à la ligne après l'affichage du tas. Vu que c'est une fonction récursive, si je mets mon retour dans la fonction, ça m'en fait à chaque appelle de la fonction... Y a-t-il un moyen simple de l'intégrer à la fonction?
Sinon je peux écrire une autre fonction qui appelle celle là puis renvoie à la ligne...

[diogene]

Sinon je peux écrire une autre fonction qui appelle celle là puis renvoie à la ligne....

C'est le plus simple. De plus cela te permet d'ajuster la mise en forme de l'affichage à ta guise.