Chaque type de données se résume-t-il simplement aux nœuds avec des pointeurs?

21

Un tableau ou un vecteur n'est qu'une séquence de valeurs. Ils peuvent sûrement être mis en œuvre avec une liste chaînée. Ce n'est qu'un groupe de nœuds avec des pointeurs vers le nœud suivant.

Les piles et les files d'attente sont deux types de données abstraits couramment enseignés dans les cours Intro CS. Quelque part dans la classe, les étudiants doivent souvent implémenter des piles et des files d'attente en utilisant une liste chaînée comme structure de données sous-jacente, ce qui signifie que nous revenons à la même idée de "collection de nœuds".

Les files d'attente prioritaires peuvent être créées à l'aide d'un tas. Un tas peut être considéré comme un arbre avec la valeur min à la racine. Les arbres de toutes sortes, y compris les BST, les AVL, les tas peuvent être considérés comme une collection de nœuds reliés par des bords. Ces nœuds sont reliés entre eux là où un nœud pointe vers un autre.

Il semble que chaque concept de données puisse toujours se résumer à seulement des nœuds avec des pointeurs vers un autre nœud approprié. Est-ce correct? Si c'est aussi simple, pourquoi les manuels n'expliquent-ils pas que les données ne sont qu'un groupe de nœuds avec des pointeurs? Comment passer des nœuds au code binaire?

derekchen14
la source
5
La structure de données fondamentale à laquelle vous faites allusion est appelée "cellule de contre"; vous pouvez en créer n'importe quelle structure de données que vous aimez. Si vous voulez savoir pourquoi un auteur de manuel donné n'a pas choisi d'expliquer les cellules contre, demandez à cet auteur pourquoi il a fait ce choix. Passer d'une description d'un arrangement de nœuds à un code binaire s'appelle "compilation" et est la tâche d'un "compilateur".
Eric Lippert
18
Vous pouvez également faire valoir que toutes les structures de données se résument à un tableau. Après tout, ils se retrouvent tous dans la mémoire, qui n'est qu'un très grand tableau.
BlueRaja - Danny Pflughoeft
10
Vous ne pouvez pas implémenter un tableau à l'aide d'une liste chaînée si vous souhaitez conserver l'indexation . O(1)
svick
5
Désolé, mais parler de "nœuds et pointeurs" signifie que vous avez déjà succombé à manger des quiches. " Comme tous les vrais programmeurs le savent, la seule structure de données utile est le tableau. Chaînes, listes, structures, ensembles - ce sont tous des cas particuliers de tableaux et peuvent être traités de cette façon tout aussi facilement sans gâcher votre langage de programmation avec toutes sortes de complications. "Réf:" Les vrais programmeurs n'utilisent pas Pascal ", de web.mit.edu/humor/Computers/real.programmers
alephzero
3
... mais plus sérieusement, l'important à propos des structures de données est ce que vous pouvez en faire , pas comment elles sont mises en œuvre. Au 21e siècle, les mettre en œuvre vous-même n'est qu'un exercice de programmation - et pour les éducateurs paresseux, le fait que ces exercices soient faciles à noter l'emporte sur le fait qu'ils sont au mieux inutiles et au pire positivement nocifs s'ils encouragent les élèves à penser que " réinventer les roues "est une activité utile dans la programmation du monde réel.
alephzero

Réponses:

14

Eh bien, c'est essentiellement ce à quoi toutes les structures de données se résument. Données avec connexions. Les nœuds sont tous artificiels - ils n'existent pas réellement physiquement. C'est là que la partie binaire entre en jeu. Vous devez créer quelques structures de données en C ++ et vérifier où vos objets atterrissent en mémoire. Il peut être très intéressant de savoir comment les données sont disposées en mémoire.

La raison principale de tant de structures différentes est qu'elles se spécialisent toutes dans une chose ou une autre. Par exemple, il est généralement plus rapide de parcourir un vecteur au lieu d'une liste liée, en raison de la façon dont les pages sont extraites de la mémoire. Une liste chaînée est préférable de stocker des types de plus grande taille car les vecteurs doivent allouer de l'espace supplémentaire pour les emplacements inutilisés (cela est requis dans la conception d'un vecteur).

En guise de remarque, une structure de données intéressante que vous voudrez peut-être examiner est une table de hachage. Il ne suit pas tout à fait le système Nodes and Pointers que vous décrivez.

TL; DR: Conteneurs essentiellement tous les nœuds et pointeurs, mais ont des utilisations très spécifiques et sont meilleurs pour quelque chose et pire pour d'autres.

user3853544
la source
1
Ma conclusion est que la plupart des données peuvent en effet être représentées comme un groupe de nœuds avec des pointeurs. Cependant, ce n'est pas parce que (a) au niveau physique, ce n'est pas ce qui se passe et (b) au niveau conceptuel, penser les valeurs comme une liste chaînée n'est pas aussi utile pour raisonner sur les données sous-jacentes. De toute façon, ce ne sont que des abstractions pour simplifier notre réflexion, aussi bien choisir la meilleure abstraction pour une situation même si une autre pourrait éventuellement fonctionner.
derekchen14
13

Il semble que chaque concept de données puisse toujours se résumer à seulement des nœuds avec des pointeurs vers un autre nœud approprié.

Oh, cher non. Tu me fais mal.

Comme j'ai essayé d'expliquer ailleurs (" Quelle est la différence entre un arbre de recherche binaire et un tas binaire? "), Même pour une structure de données fixe, il existe plusieurs niveaux pour la comprendre.

Comme la file d'attente prioritaire que vous mentionnez, si vous souhaitez uniquement l'utiliser, il s'agit d'un type de données abstrait. Vous l'utilisez en sachant quel type d'objets il stocke et quelles questions vous pouvez lui poser. C'est plus de structures de données comme un sac d'articles. Au niveau suivant, sa célèbre implémentation, le tas binaire, peut être comprise comme un arbre binaire, mais le dernier niveau est pour des raisons d'efficacité implémenté sous forme de tableau. Pas de nœuds et pointeurs là-bas.

Et aussi pour les graphiques par exemple, qui ressemblent certainement à des nœuds et des pointeurs (bords), vous avez deux représentations de base, un tableau d'adjacence et des listes d'adjacence. Pas tous les pointeurs que j'imagine.

Lorsque vous essayez vraiment de comprendre les structures de données, vous devez étudier leurs bons points et leurs faiblesses. Parfois, une représentation utilise un tableau pour l'efficacité (espace ou temps), parfois il y a des pointeurs (pour plus de flexibilité). Cela vaut même lorsque vous avez de bonnes implémentations "en conserve" comme le C ++ STL, car là aussi, vous pouvez parfois choisir les représentations sous-jacentes. Il y a toujours un compromis.

Hendrik Jan
la source
10

Faisons une analogie avec les mathématiques. Considérez la phrase suivante: " est une fonction continue". Les fonctions sont vraiment définies en termes de relations, qui sont définies en termes d'ensembles. L'ensemble des nombres réels est le champ unique totalement ordonné complet: tous ces concepts ont des définitions en termes plus simples. Pour parler de continuité, il faut le concept de voisinage, qui se définit par rapport à une topologie ... et ainsi de suite jusqu'aux axiomes de ZFC.F:RR

Personne ne s'attend à ce que vous disiez tout cela juste pour définir une fonction continue, sinon personne ne serait en mesure de faire du travail. Nous avons juste "confiance" que quelqu'un a fait le travail ennuyeux pour nous.

Chaque structure de données à laquelle vous pouvez penser se résume aux objets de base avec lesquels votre modèle de calcul sous-jacent traite, des nombres entiers dans certains registres si vous utilisez une machine à accès aléatoire ou des symboles sur une bande si vous utilisez une machine de Turing.

Nous utilisons des abstractions car elles libèrent notre esprit de questions triviales, nous permettant de parler de problèmes plus complexes. Il est parfaitement raisonnable de simplement "faire confiance" au fonctionnement de ces structures: la spirale dans chaque détail est - à moins que vous n'ayez une raison spécifique de le faire - un exercice futile qui n'ajoute rien à votre argument.

tri rapide
la source
10

Voici un contre-exemple: en λ-calcul, chaque type de données se résume à des fonctions. Le λ-calcul n'a pas de nœuds ou de pointeurs, il n'a que des fonctions, donc tout doit être implémenté à l'aide de fonctions.

Voici un exemple d'encodage de booléens en tant que fonctions, écrit en ECMAScript:

const T   = (thn, _  ) => thn,
      F   = (_  , els) => els,
      or  = (a  , b  ) => a(a, b),
      and = (a  , b  ) => a(b, a),
      not = a          => a(F, T),
      xor = (a  , b  ) => a(not(b), b),
      iff = (cnd, thn, els) => cnd(thn, els)();

Et voici une liste des inconvénients:

const cons = (hd, tl) => which => which(hd, tl),
      first  = list => list(T),
      rest   = list => list(F);

Les nombres naturels peuvent être implémentés en tant que fonctions d'itérateur.

Un ensemble est la même chose que sa fonction caractéristique (c'est-à-dire la containsméthode).

Notez que le Church Encoding of Booleans ci-dessus est en fait la façon dont les conditions sont implémentées dans les langages OO comme Smalltalk, qui n'ont pas de booléens, de conditions ou de boucles en tant que constructions de langage et les implémentent purement comme une fonctionnalité de bibliothèque. Un exemple à Scala:

sealed abstract trait Boolean {
  def apply[T, U <: T, V <: T](thn: => U)(els: => V): T
  def(other: => Boolean): Boolean
  def(other: => Boolean): Boolean
  val ¬ : Boolean

  final val unary_! = ¬
  final def &(other: => Boolean) =(other)
  final def |(other: => Boolean) =(other)
}

case object True extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): U = thn
  override def(other: => Boolean) = other
  override def(other: => Boolean): this.type = this
  override final val ¬ = False
}

case object False extends Boolean {
  override def apply[T, U <: T, V <: T](thn: => U)(els: => V): V = els
  override def(other: => Boolean): this.type = this
  override def(other: => Boolean) = other
  override final val ¬ = True
}

object BooleanExtension {
  import scala.language.implicitConversions
  implicit def boolean2Boolean(b: => scala.Boolean) = if (b) True else False
}

import BooleanExtension._

(2 < 3) { println("2 is less than 3") } { println("2 is greater than 3") }
// 2 is less than 3
Jörg W Mittag
la source
2
@Hamsteriffic: Essayez ceci: c'est en fait ainsi que les conditions sont implémentées dans les langages OO comme Smalltalk. Smalltalk n'a pas de booléens, de conditions ou de boucles comme construction de langage. Tous ces éléments sont purement implémentés en tant que bibliothèques. L'esprit n'est toujours pas soufflé? William Cook souligne quelque chose qui aurait dû être évident il y a longtemps mais qui n'a pas vraiment été remarqué: puisque OO est une question d'abstraction comportementale et que l'abstraction comportementale est le seul type d'abstraction qui existe dans le λ-calcul, il s'ensuit que tous les programmes écrits en Les λ-calculs sont par nécessité OO. Ergo, le λ-calcul est le plus ancien et…
Jörg W Mittag
… La langue OO la plus pure!
Jörg W Mittag
1
Une mauvaise journée avec Smalltalk bat une bonne journée avec C ++ :-)
Bob Jarvis - Reinstate Monica
@ JörgWMittag Je ne pense pas que votre conclusion découle de votre hypothèse, je ne pense pas que votre hypothèse soit même vraie, et je ne pense certainement pas que votre conclusion soit vraie.
Miles Rout
4

De nombreuses (la plupart?) Structures de données sont constituées de nœuds et de pointeurs. Les tableaux sont un autre élément essentiel de certaines structures de données.

En fin de compte, chaque structure de données n'est qu'un tas de mots en mémoire, ou juste un tas de bits. C'est la façon dont ils sont structurés et comment nous les interprétons et les utilisons qui importe.

DW
la source
2
En fin de compte, les bits sont un tas de signaux électriques sur un fil, ou des signaux lumineux dans un câble à fibre optique, ou des particules magnétisées spécifiquement sur un plateau, ou des ondes radio de longueur d'onde particulière, ou, ou, ou. La question est donc de savoir à quelle profondeur voulez-vous aller? :)
Wildcard
2

La mise en œuvre des structures de données se résume toujours aux nœuds et aux pointeurs, oui.

Mais pourquoi s'arrêter là? L'implémentation des nœuds et des pointeurs se résume à des bits.

La mise en œuvre des bits se résume aux signaux électriques, au stockage magnétique, peut-être aux câbles à fibres optiques, etc. (En un mot, la physique.)

Il s'agit de la reductio ad absurdum de l'énoncé «Toutes les structures de données se résument aux nœuds et aux pointeurs». C'est vrai, mais cela ne concerne que la mise en œuvre.


Chris Date sait très bien faire la différence entre l' implémentation et le modèle , bien que son essai vise en particulier les bases de données.

Nous pouvons aller un peu plus loin si nous réalisons qu'il n'y a pas une seule ligne de démarcation entre le modèle et la mise en œuvre. Ceci est similaire (sinon identique) au concept de «couches d'abstraction».

À une couche d'abstraction donnée, les couches "en dessous" de vous (les couches sur lesquelles vous construisez) ne sont que des "détails d'implémentation" pour l'abstraction ou le modèle auquel vous vous adressez.

Cependant, les couches d'abstraction inférieures elles - mêmes ont des détails d'implémentation.

Si vous lisez un manuel pour un logiciel, vous découvrez la couche d'abstraction "présentée" par ce logiciel, sur laquelle vous pouvez créer vos propres abstractions (ou simplement effectuer des actions telles que l'envoi de messages).

Si vous apprenez les détails d'implémentation du logiciel, vous apprendrez comment les créateurs ont étayé les abstractions qu'ils ont construites. Les "détails d'implémentation" peuvent comprendre, entre autres, des structures de données et des algorithmes.

Cependant, vous ne considéreriez pas la mesure de tension comme faisant partie des «détails de mise en œuvre» pour un logiciel particulier, même si cela sous-tend le fonctionnement réel des «bits» et des «octets» et du «stockage» sur l'ordinateur physique.

En résumé, les structures de données sont une couche d'abstraction pour le raisonnement et la mise en œuvre d'algorithmes et de logiciels. Le fait que cette couche d'abstraction repose sur des détails d'implémentation de niveau inférieur tels que les nœuds et les pointeurs est vrai mais non pertinent au sein de la couche d'abstraction.


Une grande partie de la compréhension réelle d'un système consiste à comprendre comment les couches d'abstraction s'emboîtent. Il est donc important de comprendre comment les structures de données sont mises en œuvre. Mais le fait qu'elles soient implémentées ne signifie pas que l'abstraction des structures de données n'existe pas .

Caractère générique
la source
2

Un tableau ou un vecteur n'est qu'une séquence de valeurs. Ils peuvent sûrement être mis en œuvre avec une liste chaînée. Ce n'est qu'un groupe de nœuds avec des pointeurs vers le nœud suivant.

Un tableau ou un vecteur peut être implémenté avec une liste chaînée, mais ne devrait presque jamais l'être.

nnΘ(n)Θ(Journaln)Θ(1) un tableau réel(c'est-à-dire un bloc séquentiel de mémoire à accès aléatoire). De plus, sur le CPU, l'accès à la baie réelle est beaucoup plus simple à implémenter et plus rapide à exécuter, et le stockage nécessite moins de mémoire car il ne doit pas perdre d'espace sur les pointeurs entre les nœuds séparés.

Θ(n)Θ(1)Θ(1)en moyenne, au prix d'au plus un facteur constant de mémoire supplémentaire, simplement en arrondissant la taille réelle allouée de la baie jusqu'à par exemple la puissance la plus proche de 2. Mais si vous avez besoin de faire beaucoup d'insertions et / ou de suppressions de éléments au milieu de votre liste, un tableau physique peut ne pas être la meilleure implémentation pour votre structure de données. Très souvent, cependant, vous pouvez remplacer les insertions et les suppressions par des swaps, qui sont bon marché.

Si vous élargissez un peu votre portée, pour inclure des tableaux physiques contigus dans votre boîte à outils, presque toutes les structures de données pratiques peuvent en effet être mises en œuvre avec celles-ci avec des nœuds et des pointeurs.

Θ(1)opération d'inversion). En pratique, cependant, ces fonctionnalités sont rarement suffisamment utiles pour surmonter ses inconvénients, qui incluent une complexité d'implémentation supplémentaire et une incompatibilité avec les schémas de collecte de déchets standard .

Ilmari Karonen
la source
1

Si c'est aussi simple, pourquoi les manuels n'expliquent-ils pas que les données ne sont qu'un groupe de nœuds avec des pointeurs?

Parce que ce n'est pas ce que signifie "données". Vous confondez des idées abstraites avec des implémentations. «Données» est une idée très abstraite: ce n'est qu'un autre nom pour «information». Un groupe de nœuds liés avec des pointeurs (aka, une "structure de données liées") est une idée beaucoup plus concrète: c'est une façon spécifique de représenter et d'organiser l'information.

Certaines abstractions de données se prêtent très bien aux implémentations "liées". Il n'y a pas beaucoup de bons moyens pour implémenter la nature de ramification d'un arbre entièrement général sans utiliser de nœuds et de pointeurs explicites (ou, certains isomorphisme de nœuds et de pointeurs.) Mais il existe d'autres abstractions que vous ne mettriez jamais en œuvre en utilisant des nœuds et des pointeurs. Les nombres à virgule flottante me viennent à l'esprit.

Les piles et les files d'attente se situent quelque part entre les deux. Il y a des moments où il est très logique de faire une implémentation liée d'une pile. Il y a d'autres moments où il est beaucoup plus logique d'utiliser un tableau et un seul "pointeur de pile".

Solomon Slow
la source