Discussion :

[Reverse_]

Bonjour,

j'ai une question, sans doute idiote, mais je n'arrive pas à trouver de réponse depuis un petit moment déjà.
Pourquoi Les structures évoluées tels que : les listes chaînées, les piles, les arbres etc... Sont des pointeurs ?

Je comprends l’intérêt d'utiliser des pointeurs pour passer les structures à une fonction (éviter un temps de copie inutile).

Mais je ne comprends pas pourquoi par exemple sur le cours des Arbres on le définit en tant que pointeur :

node *Arbre = NULL;

et pourquoi ne pas faire simplement

node Arbre;

Je suis désolé si je ne suis pas très claire... Je n'arrive pas à trouver les mots exactes ...

Merci pour vos réponses !

[Matt_Houston]

Le rôle d'une structure de données est de modéliser une topologie : les relations entre les éléments qui contiennent ces données. Une relation est modélisée par une référence et en informatique la manière la plus directe de mettre en place une référence dynamique est de stocker une adresse mémoire.

Il existe d'autres manières de faire, à titre d'exemple on peut parfois préférer une structure implicite c'est-à-dire dont les relations sont directement décrites par l'organisation des données en mémoire. On peut ainsi choisir d'implémenter un arbre n-aire dans un tableau d'éléments contigus.

Pour terminer avec ton cas : un arbre vide est un arbre sans nœud, quoi de plus élégant qu'un pointeur nul pour le représenter ?

[Reverse_]

Merci de ta réponse !
Donc si je comprends bien, c'est plus par "convention" et par logique que par une quelconque obligation ?

[Obsidian]

Bonjour,

Merci de ta réponse !
Donc si je comprends bien, c'est plus par "convention" et par logique que par une quelconque obligation ?

Pas tout-à-fait. C'est nécessaire justement parce qu'en C, on n'avait pas encore introduit le concept de « référence », qui a été introduit naturellement avec les langages des générations suivantes, comme le C++, puis avec certains langages interprétés ou utilisant du bytecode.

Lorsque tu fais une liste chaînée, chaque maillon doit comporter un pointeur vers le maillon suivant, ce qui te permet effectivement de faire une chaîne de longueur indéterminée. Si tu écrivais « maillon next » au lieu d'écrire « maillon *next », cela voudrait dire que chaque maillon serait contenu en entier dans le précédent. Et puisqu'on se réfère au même type de donnée, on obtiendrait une structure de taille infinie.

Maintenant, tout l'intérêt d'une liste chaînée est pouvoir insérer ou supprimer facilement des maillons, mais également des morceaux de chaîne entiers, en reliant le premier maillon de la liste au « précédent » et le dernier au « suivant ». Dans le même esprit, on peut rattacher la fin d'une chaîne au début d'une autre pour les concaténer. Dans cet esprit, une « liste » entière — ou un arbre, cela revient au même — est en fait représentée par son premier maillon.

Or, il est nécessaire de passer aux fonctions de traitement une référence sur le maillon lui-même car autrement, il serait passé par valeur : la fonction obtiendrait certes son contenu (et donc l'adresse du maillon suivant), mais serait incapable de déterminer l'adresse propre du maillon en question, pourtant nécessaire pour renseigner ce qui vont le pointer.

Et c'est à cause de cela que dans la majorité des cours d'algorithmique, on constate une pratique détestable consistant à masquer le pointeur derrière un typedef : « typedef noeud * arbre ». Cela donne l'illusion qu'un nœud est un nœud et qu'un arbre est un arbre, et que l'on peut faire totalement abstraction des pointeurs en émulant les références de cette façon, mais c'est un leurre : même caché par son alias, un pointeur reste un pointeur et il faut l'utiliser comme il se doit, en pensant à initialiser ce qui se trouve derrière et, notamment, en utilisant « -> » à la place de « . » lorsque l'on pointe des structures.

[Matt_Houston]

J'ajoute que cette pratique : implémenter 'par défaut' une structure sous une forme chaînée est caractéristique du milieu éducatif qui veut que les étudiants comprennent bien l'organisation appliquée aux données comme modèle relationnel par analogie avec la théorie mathématique sous-jacente.

En pratique, comme toujours, lorsque d'autres représentations sont possibles tout dépend du cas d'utilisation. Si tu as une pile d'entiers ou de petites struct à mettre en place, ben tu vas le faire avec un tableau statique et un curseur entier qui pointe sur le sommet comme tout le monde. Dans ce cas c'est beaucoup plus simple à écrire, à débugger et bien plus efficace.

[Reverse_]

D'accord, merci pour vos réponses, ça me paraît plus claire maintenant !

[sambia39]

Bonjour ‬
‪Je suis réticent sur certains points de la réponse donnée ci-dessous.

Le rôle d'une structure de données est de modéliser une topologie : les relations entre les éléments qui contiennent ces données. Une relation est modélisée par une référence et en informatique la manière la plus directe de mettre en place une référence dynamique est de stocker une adresse mémoire.

Il existe d'autres manières de faire, à titre d'exemple on peut parfois préférer une structure implicite c'est-à-dire dont les relations sont directement décrites par l'organisation des données en mémoire. On peut ainsi choisir d'implémenter un arbre n-aire dans un tableau d'éléments contigus.

Pour terminer avec ton cas : un arbre vide est un arbre sans nœud, quoi de plus élégant qu'un pointeur nul pour le représenter ?

Le rôle d'une structure de données n'est pas de modéliser une topologie, mais a pour rôle de regrouper sous un seul nom plusieurs données, des types d’éléments simples ou complexes. La structure de données est donc une structure logique destinée à contenir des données et de ce fait, elle représente par implémentation un type abstrait.‬
‪La modélisation d'une topologie ou encore les relations modélisées par référence, si je peux ainsi dire, n'est pas caractérisée et définie dans la nature même d'une structure de données. Je m'explique : partant d'une structure en informatique (du Langage C) justifiée par la définition suivante qu'une structure est un ensemble comprenant une ou plusieurs variables sous un même nom. Essayons à présent de mettre en place une récursivité au sein même de notre structure de données on remarque très vite que cela nous est interdit car il est dû au fait qu'une structure ne peut se contenir elle-même, mais, en utilisant une variable qui pointe sur une autre structure nous contournons le problème (et là, une structure de données reste comme tel). La référence ou la mise en relation des différents éléments prend toute sa définition dans un concept algorithmique, c'est-à-dire l'implémentation d'un algorithme, exemple : Une liste simplement chaînée (ou doublement chaînée, arbre..) est une structure de données qui peut contenir un ou plusieurs éléments pointant vers l'élément suivant ou précédent (une autre structure de données).‬

On parlera de la topologie modélisée par les relations des membres de la structure de données, quand il s'agit d'espace ou de vue globale pour ainsi dire. Une liste chainée simple a une topologie car certain membre de sa structure de données pointe vers une autre structure créant ainsi une relation dont la dernière structure a un élément pointant sur "nulle" représentant la limite de la liste ou fin de liste ( d'un autre côté on comprend que si une variable pointe sur une structure, tout calcul sur la variable tient compte de la véritable taille de la structure mais n'aller pas comprendre ou supposer que la taille d'une structure est égale à la somme des tailles de ses membres).

à bientôt.