Différences entre les structures de données statiques et dynamiques

Question

Quelles sont les principales différences, avantages et inconvénients entre les structures de données statiques et dynamiques?

Sous quelles catégories les structures de données les plus courantes tombent-elles?

Comment savoir dans quelle situation utiliser chacun?

Answer 1

Pour commencer par un simplisme:

Il y a seulement quelques types de base de structures de données: tableaux, listes et arbres. Tout le reste peut être composé en utilisant différents types de ces deux structures (par exemple, une table de hachage peut être implémentée avec un tableau pour les valeurs de hachage et une liste pour chaque valeur de hachage pour gérer les collisions). Parmi ces structures, les matrices sont statiques (c'est-à-dire que leur empreinte mémoire ne varie pas avec le temps au fur et à mesure des opérations) et tout le reste est dynamique (dans le cas général, l'empreinte mémoire change).

Les différences entre les deux types de structures peuvent être dérivées de ce qui précède:

• statique a besoin de la taille maximale être connue à l'avance, alors que dynamique peut adapter à la volée
• statique ne réaffecte pas mémoire, peu importe quoi, vous pouvez donc avoir garanti des besoins en mémoire

Il y a aussi d'autres différences, qui cependant n'entrent en jeu si vos données peuvent être triées. Je ne peux pas donner une liste exhaustive, car il existe de nombreuses structures de données dynamiques qui présentent différentes caractéristiques de performance pour différentes opérations ("ajouter", "supprimer", "trouver") et ne peuvent donc pas être placées sous le même toit. Une différence très visible est que les tableaux triés nécessitent de déplacer (peut-être beaucoup) de choses en mémoire pour toute opération autre que «trouver», tandis que les structures dynamiques effectuent généralement moins de travail.

Donc, pour récapituler:

1. Si vous avez besoin d'une garantie sur l'utilisation de la mémoire, vous avez pas d'autre choix qu'un tableau.
2. Si vous avez une limite supérieure stricte pour la taille de vos données, pensez à utiliser une matrice. Les tableaux peuvent convenir aux problèmes qui nécessitent principalement des opérations d'ajout/suppression (maintenir le tableau non trié) et pour ceux qui nécessitent principalement des opérations de recherche (garder le tableau trié), mais pas pour les deux en même temps.
3. Si vous n'avez pas de limite supérieure stricte, ou si vous avez besoin de tout ajouter/supprimer/trouver pour être rapide, utilisez un type de structure dynamique approprié.

Edit: je ne mentionnais pas des graphiques, un autre type de structure de données dynamique qui sans doute ne peut pas être composé de parties plus simples (par définition, un arbre a exactement un lien allant « dans » un nœud à l'exception de la racine, alors que les graphiques peuvent en avoir plus d'un). Cependant, les graphiques ne peuvent pas vraiment être comparés à d'autres structures dans un scénario «quoi de mieux à utiliser», parce que vous devez utiliser un graphique ou pas (d'autres structures peuvent présenter des performances différentes, mais à la fin, elles soutiennent toutes même ensemble d'opérations).

Answer 2

C'est toujours l'inverse, si vous allez avec statique alors vous perdez de la mémoire alors qu'en dynamique, les performances seront diminuées. Une meilleure conception utiliserait les structures de données efficacement, il n'y a pas de réponse parfaite.

Answer 3

Les structures de données statiques (SDS) sont de taille fixe (par exemple, Arrays), la quantité de mémoire qui leur est allouée ne peut pas changer à l'exécution tandis que les structures de données dynamiques (DDS) ont une taille flexible. ou rétrécir au besoin pour contenir les données à stocker. Les SDS sont des structures de données linéaires qui permettent un accès rapide aux éléments qui y sont stockés mais les opérations d'insertion/suppression sont coûteuses par rapport à DDS où l'accès aux éléments est plus lent mais l'insertion/suppression est plus rapide.

La plupart des DS sont Dynamic DS. Si l'espace SDS est alloué avant l'insertion des données, l'espace peut être gaspillé ou peut être insuffisant à certains moments, ils ne doivent donc être utilisés que si la quantité exacte de données à insérer est connue à l'avance, si cela doit être connu au moment de l'exécution DDS devrait être utilisé.

Answer 4

conseils simples

structures de données dynamiques présentent les caractéristiques suivantes:

• Possibilité d'ajouter efficacement, supprimer ou modifier des éléments
• taille flexible
• Utilisation efficace des ressources - parce que les ressources sont alloués au moment de l'exécution, selon les besoins.
• ralentissement de l'accès à des éléments (en comparaison avec les structures de données statiques)

structures de données statiques présentent les caractéristiques suivantes:

• ajouter, supprimer ou modifier les éléments ne sont pas directement possible. Si c'est fait, c'est un processus consommateur de ressources.
• Taille fixe.
• Ressources allouées à la création de la structure de données, même si les éléments ne contiennent aucune valeur.
• Un accès plus rapide aux éléments (par rapport à des structures de données dynamiques)

En résumé, il est efficace d'utiliser des structures dynamiques pour stocker un ensemble de données qui est connu, pour ne pas changer. L'utilisation d'une structure de données statique dans un tel cas permettra d'économiser des ressources système et de fournir également un accès plus rapide aux éléments. Si la taille des données est connue pour changer d'un autre côté, utilisez des structures dynamiques.