Type de données abstrait et structure de données

Il m'est assez difficile de comprendre ces termes. J'ai cherché sur google et lu un peu sur Wikipedia mais je ne suis toujours pas sûr. J'ai déterminé jusqu'à présent que:

Le type de données abstrait est une définition d'un nouveau type, décrit ses propriétés et ses opérations.

La structure de données est une implémentation d'ADT. De nombreux ADT peuvent être implémentés comme la même structure de données.

Si je pense bien, tableau comme ADT signifie une collection d'éléments et comme structure de données, comment il est stocké dans une mémoire. La pile est ADT avec des opérations push, pop, mais pouvons-nous dire sur la structure des données de la pile si je veux dire que j'ai utilisé la pile implémentée comme un tableau dans mon algorithme? Et pourquoi le tas n'est-il pas ADT? Il peut être implémenté sous forme d'arbre ou de tableau.

Autrement dit, un ADT (Abstract Data Type) est plus une description logique, tandis qu'une structure de données est concrète.

Considérez un ADT comme une image des données et des opérations pour les manipuler et les modifier.

Une structure de données est la chose réelle et concrète . Il peut être implémenté et utilisé dans un algorithme.

ADT est à une interface ( ce qu'elle fait ) ce qu'est une structure de données à une classe ( comment elle le fait ).

Quelques exemples:

ADT: List
DS:  ArrayList, LinkedList...

ADT: Map
DS:  HashMap, TreeMap...

Je suppose que vous comprenez.

Type de données abstrait: ADT peut être défini comme un ensemble de valeurs de données et d'opérations associées qui sont spécifiées avec précision indépendamment de toute mise en œuvre particulière. Ainsi, un type de données abstrait est une collection organisée d'informations et un ensemble d'opérations utilisées pour gérer ces informations. L'ensemble des opérations définit l'interface de l'ADT. Tant que l'ADT remplit les conditions de l'interface, peu importe comment l'ADT est implémenté. Étant donné que dans ADT, les valeurs des données et les opérations sont définies avec une précision mathématique plutôt que comme une implémentation dans un langage informatique, nous pouvons raisonner sur les effets des opérations, les relations avec d'autres types de données abstraits si un programme implémente le type de données, etc.

La différence fondamentale entre le type de données abstrait (ADT) et le type de données concret est que ces derniers nous permettent de regarder la représentation concrète, tandis que les premiers nous cachent la représentation. Un ADT peut être pur ADT ou ADT modifiable. Un ADT pur est celui où toutes les opérations sont de pures fonctions. Cela signifie que les opérations n'ont pas d'effets secondaires. En particulier, ils n'y modifient ni ne mettent à jour les arguments d'entrée. Ils utilisent simplement ces arguments pour générer une sortie, qui sont de nouvelles valeurs d'ADT (ou d'autres types). La plupart des types de béton sont purs. Par exemple, aucune opération sur des entiers ne modifie réellement un entier. Au lieu de cela, toutes les opérations comme «+» produisent de nouvelles sorties.

Un ADT pouvant être mis à jour est celui où certaines opérations modifient réellement les valeurs de l'ADT. Par exemple, supposons que nous ayons eu une opération appelée «pop» qui a pris une pile comme argument et l'a modifiée. («En place», «destructivement») en supprimant l'élément de priorité la plus élevée. Cette opération serait considérée comme impure et l'ensemble de l'ADT serait également impur. Un ADT peut être ADT défini par l'utilisateur.

Nous savons qu'un type de données abstrait est un type de données qui satisfait aux deux conditions suivantes:

1. La représentation, ou définition, du type et des opérations est contenue dans une seule unité syntaxique.

2. La représentation des objets du type est cachée aux unités de programme qui utilisent le type, donc seules les opérations directes possibles sur ces objets sont celles fournies dans la définition du type.

Un type de données abstrait défini par l'utilisateur doit fournir:

1. Une définition de type qui permet aux unités de programme de déclarer des variables du type, mais masque la représentation de ces variables.

2. Un ensemble d'opérations pour manipuler des objets du type.

Un exemple de type de données abstrait défini par l'utilisateur est la structure. 'C' fournit quatre types de base: int, char, float et double. Cependant, «C» donne également au programmeur la possibilité de définir ses propres types. La structure en est un exemple. Une structure est un agrégat de différentes parties, chaque partie étant d'un type existant.

struct abc

{int x;

float y;

};

La définition de structure ci-dessus ne crée aucune variable, mais crée plutôt un nouveau type. Les variables de ce type peuvent être créées de la même manière que les variables d'un type intégré.

struct abc a;

Le mot-clé typedef nous permet de créer de nouveaux noms de types pour nos nouveaux types.

Par exemple:

typedef struct abc AB;

où AB est un nouveau nom de type qui peut désormais être utilisé pour créer de nouveaux types.

AB b;

Structures de données: Voici les caractéristiques des structures de données:

1. Il contient des éléments de données de composants, qui peuvent être atomiques ou une autre structure de données (toujours un domaine).

2. Un ensemble d'opérations sur un ou plusieurs des éléments de composant.

3. Définit des règles sur la façon dont les composants sont liés les uns aux autres et à la structure dans son ensemble (assertions).

Structures de données:

Une structure de données peut être statique ou dynamique. Une structure de données statique a une taille fixe. Cette signification est différente de la signification du modificateur statique. Les tableaux sont statiques; une fois que nous avons défini le nombre d'éléments qu'il peut contenir, le nombre ne change pas. Une structure de données dynamique croît et se rétrécit au moment de l'exécution, comme l'exige son contenu. Une structure de données dynamique est implémentée à l'aide de liens.

Les structures de données peuvent en outre être classées en structures de données linéaires et structures de données non linéaires. Dans les structures de données linéaires, chaque composant a un prédécesseur et un successeur uniques, à l'exception du premier et du dernier élément, alors que dans le cas des structures de données non linéaires, aucune restriction de ce type n'existe car les éléments peuvent être arrangés de la manière souhaitée restreinte par la façon dont nous les utilisons pour représentent de tels types.

Tout d'abord, les terminologies dans les structures de données peuvent être très déroutantes.

L'ADT est comme une théorie ou un modèle ou une directive, etc. qui indique comment une structure de données doit se comporter, quel type d'opérations elle doit prendre en charge, etc. Trois types de données abstraits fondamentaux sont les conteneurs, les dictionnaires et les files d'attente prioritaires. Par exemple, dictionnaire, il nous dit que chaque structure de données qui implémente ce dictionnaire ADT doit prendre en charge les paires clé-valeur, la recherche basée sur les clés, l'insertion d'éléments, la recherche du successeur et du prédécesseur d'une clé donnée, etc.

Maintenant, tout le reste qui implémente cela au-dessus d'ADT est la structure de données (DS) , la structure de données sont des choses réelles que vous implémentez dans vos problèmes et que vous trouvez dans les bibliothèques. En cas de dictionnaire, vous pouvez choisir de l'implémenter via un tableau ou une liste liée.

Je pense qu'une véritable confusion survient lorsque quelqu'un nomme son DS comme ADT, par exemple certaines personnes appellent leur DS susmentionné comme `` dictionnaire '' au lieu de DictImplementation qui est parfaitement légal, cela provoque juste une certaine confusion.

Ref: Skiena: Le manuel de conception d'algorithmes