Déclaration et définition struct récursive

Bonjour à tous.

je ne connais rien au language C, mais je suis en train d'essayer de comprendre un code qui l'utilise.

J'ai pu lire que :

Code:

---

typedef struct maStructure

---

est une définition de maStructure

et que

Code:

---

struct maStructure* structure1

---

est une déclaration du pointeur structure1 de type maStructure définie ci-avant.

Dans le code suivante :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

typedef struct quadTreeNode { struct quadTreeNode* northWest; struct quadTreeNode* northEast; struct quadTreeNode* southWest; struct quadTreeNode* southEast; TBBoundingBox boundary; TBQuadTreeNodeData *points; int count; int bucketCapacity; } TBQuadTreeNode; TBQuadTreeNode* TBQuadTreeNodeMake(TBBoundingBox boundary, int bucketCapacity);

---

à priori la structure de quadTreeNode comprend les champs
- boundary
- *points
- count
- bucketCapacity

Qu'en est-il de northWest, northEast, southWest et southEast ? Ces champs appartiennent-ils à la structure ?

Il semble que ce soit un code récursif.

Si oui, n'est-on pas dans une boucle infinie où chaque instance de quadTreeNode crée un quadTreeNode de niveau inférieur qui lui même en crée un supplémentaire et ainsi de suite ?

Merci pour votre éclairage.

Citation:

---

Envoyé par KonTiKI

Qu'en est-il de northWest, northEast, southWest et southEast ? Ces champs appartiennent-ils à la structure ?

---

Bien évidemment qu'ils lui appartiennent, ce sont des pointeurs vers des objets du type que l'on est en train de définir.

Citation:

---

Envoyé par KonTiKI

Il semble que ce soit un code récursif.

---

Il s'agit en effet d'une structure de données récursive. Après tout, n'est-ce pas un quad tree qui est une spécialisation d'arbre ? Un nœud référence ses enfants potentiels, qui sont eux-même des nœuds.

Citation:

---

Envoyé par KonTiKI

Si oui, n'est-on pas dans une boucle infinie où chaque instance de quadTreeNode crée un quadTreeNode de niveau inférieur qui lui même en crée un supplémentaire et ainsi de suite ?

---

Attention : un objet de ce type ne fait que référencer d'autres objets du même type.

Le compilateur requiert au préalable les définitions complètes des types de tous les membres de la structure, plus précisément de leur taille en mémoire. Et c'est le cas ici ! Regarde-bien : il s'agit de pointeurs vers des struct quadTreeNode, hors la taille d'un pointeur vers un objet (i.e. : pas une fonction) est toujours la même, et est parfaitement connue. sizeof(struct quadTreeNode *) == sizeof(int *) == ... == sizeof(void *) est vérifié.

Citation:

---

Envoyé par KonTiKI

Qu'en est-il de northWest, northEast, southWest et southEast ? Ces champs appartiennent-ils à la structure ?

---

Oui

Citation:

---

Envoyé par KonTiKI

Il semble que ce soit un code récursif.

Si oui, n'est-on pas dans une boucle infinie où chaque instance de quadTreeNode crée un quadTreeNode de niveau inférieur qui lui même en crée un supplémentaire et ainsi de suite ?

---

Non ce n'est pas une fonction récursif et encore moins une boucle infinie !
En gros cela permet juste de déclarer une structure (donc une sorte de plusieurs variable personnalisable grosso modo )

'quadTreeNode'ce n'est qu'une structure qui peut pointer sur d'autre structure semblable a elle même tout simplement.
(Après peut être que si tu connais pas le C la notion de pointeur peut te sembler obscur).

Merci à vous deux.

Sur le récursif, visiblement vos avis divergent mais ce n'était là qu'un aparté dans ma question.

Alors oui, fondamentalement une structure arborescente doit bien avoir un rapport à ses enfants.

L'important dans vos réponses est que l'on est face à une référence (l'adresse donnée par le pointeur) et non - comme je le comprenais de façon erronée - à une instanciation.

Vu comme cela c'est beaucoup plus compréhensible... et ça me fait avancer d'un cran.

Merci encore.

Bonjour

En fait, quand tu commences à donner un nom à ta structure struct quadTreeNode alors ici le C sait qu'il va exister quelque chose qui se nommera "struct quadTreeNode". Il ne connait pas encore le détail de ce truc, mais il connait son étiquette.
Ensuite, quand tu déclares un pointeur sur cette étiquette struct quadTreeNode* northWest tu ne fais que déclarer un pointeur. Or un pointeur ça reste une bête adresse donc un bête nombre (4 octets). Mais l'étiquette étant maintenant connue, tu as alors le droit de déclarer un pointeur dessus. Tu aurais du mal à obtenir un sizeof(*northWest) mais ça c'est une instruction et les instructions ne s'écrivent pas à cet endroit.

Ensuite, quand tu termine ta structure } TBQuadTreeNode là elle est définitivement connue. Et donc plus tard, tu pourras utiliser *northWest puisque le label correspondant sera connu intégralement.

Ce qui n'aurait pas été possible ça aurait de demander une variable de type "struct quadTreeNode" alors que la structure n'est pas terminée

Code:

---

1 2 3

typedef struct quadTreeNode { struct quadTreeNode toto; // ne peut pas fonctionner parce que là, on ne demande pas un pointeur mais une variable d'un type pas encore finalisé... }

---

...

Je pense que Kannagi a simplement voulu relever que « boucle infinie » n'est pas adapté au contexte présent (une instance peut-elle être composée d'instances du même type ?). Ce terme désigne en général une boucle dont aucune condition de sortie n'est jamais vérifiée à l'exécution.