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

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?

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.

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.

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:\mathbb{R} \rightarrow \mathbb{R}$

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.

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

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.

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 .

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.

$n$$n$$\Theta(n)$$\Theta(\log n)$$\Theta(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.

$\Theta(n)$$\Theta(1)$$\Theta(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.

$\Theta(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 .

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".