Abstract Data Type(ADT) est un type de données, où seul le comportement est défini mais pas l'implémentation.

En face de ADT est Concrete Data Type (CDT), où il contient une implémentation d'ADT.

Exemples:
Array, List, Map, Queue, Set, Stack, Table, Tree, and Vector sont ADTs. Chacun de ces ADT a de nombreuses implémentations, c'est-à-dire CDT. Container est un ADT de haut niveau au-dessus de tous les ADT.

Exemple Réel:
Le livre est abstrait (l'annuaire téléphonique est une implémentation)

Le Abstraite type de données article de Wikipédia a beaucoup de choses à dire.

En informatique, un type de données abstrait (ADT) est un modèle mathématique pour une certaine classe de structures de données qui ont un comportement similaire; ou pour certains types de données d'un ou plusieurs langages de programmation qui ont une sémantique similaire. Un type de données abstrait est défini indirectement, uniquement par les opérations qui peuvent y être effectuées et par des contraintes mathématiques sur les effets (et éventuellement le coût) de de ces opérations.

En termes un peu plus concrets, vous pouvez prendre Java List interface comme exemple. L'interface ne définit explicitement aucun comportement car il n'y a pas de classe concrète List. L'interface définit un ensemble de méthodes que d'autres cours (par ex. ArrayList et LinkedList) doit mettre en œuvre pour être considéré comme un List.

Une collection est un autre type de données abstraites. Dans le cas de Java Collection l'interface, c'est encore plus abstrait que List depuis

Le List interface places supplémentaires stipulations, au-delà de celles spécifiées dans le Collection interface, sur les contrats de la iterator, add, remove, equals, et hashCode méthodes.

Un sac, qui est également connu comme un multiset.

En mathématiques, la notion de multiset (ou sac) est une généralisation de la notion d'ensemble dans lequel les membres sont autorisés à apparaître plus d'une fois. Par exemple, il existe un ensemble unique qui contient les éléments a et b et aucun autre, mais il existe de nombreux multiset avec cette propriété, tels que le multiset qui contient deux copies de a et une de b ou le multiset qui contient trois copies de a et b.

En Java, un Sac serait une collection qui implémente une interface très simple. Il vous suffit de pouvoir ajouter des éléments à un sac, vérifier sa taille et parcourir les éléments qu'il contient. Voir Sac.java pour un exemple d'implémentation (à partir des algorithmes de Sedgewick & Wayne 4th edition).

Un type de données vraiment abstrait décrit les propriétés de ses instances sans engagement envers leur représentation ou leurs opérations particulières. Par exemple, l'entier de type abstrait (mathématique) est un ensemble discret, illimité et ordonné linéairement d'instances. Un type concret donne une représentation spécifique pour les instances et implémente un ensemble spécifique d'opérations.

ADT est un ensemble de valeurs de données et d'opérations associées qui sont précisément indépendantes de toute implémentation paticulaire. La force d'un ADT est implémentéeaion est caché à l'utilisateur.seule l'interface est déclarée .Cela signifie que l'ADT est de différentes manières

Le type de données simplement abstrait n'est rien d'autre qu'un ensemble d'opérations et un ensemble de données est utilisé pour stocker efficacement d'autres données dans la machine. Aucune déclaration de type perticulaire n'est nécessaire. Cela nécessite simplement une implémentation d'ADT.

Abstract Data type est un module mathématique qui inclut des données avec diverses opérations. Les détails de l'implémentation sont cachés et c'est pourquoi il est appelé abstrait. L'abstraction vous a permis d'organiser la complexité de la tâche en vous concentrant sur les propriétés logiques des données et des actions.

Dans les langages de programmation, un type est une donnée et les opérations associées. Un ADT est un agrégat de données défini par l'utilisateur et les opérations sur ces données et est caractérisé parencapsulation , les données et les opérations sont représentées, ou en liste déclarée, dans une seule unité syntaxique, etmasquage d'informations , seules les opérations pertinentes sont visibles pour l'utilisateur de l'ADT, l'interface ADT , de la même manière qu'un type de données normal dans le langage de programmation. C'est une abstraction car la représentation interne des données et la mise en œuvre des opérations ne préoccupent pas l'utilisateur ADT.

Avant de définir types de données abstraites , considérons les différents vue des types de données définis par le système. Nous savons tous que par défaut tous types de données primitives (int, float, etc.) de soutenir les opérations de base telles comme addition et soustraction. Le système fournit les implémentations pour les types de données primitifs. Pour les types de données définis par l'utilisateur, nous besoin de définir des opérations. La mise en œuvre de ces opérations peut être fait quand nous voulons réellement les utiliser. Que signifie en général, les types de données définis par l'utilisateur sont définis avec leurs opérations.

Pour simplifier le processus de résolution des problèmes, nous combinons les données structures avec leurs opérations et nous appelons cela " Données abstraites Tapez " . (ADT).

Couramment utilisé ADT comprennent: Liste chaînée, Piles, Files d'attente, Arbre binaire, Dictionnaires, Ensembles disjoints (Union et find), Tables de hachage et beaucoup les autres.

Les ADT se composent de deux types:

1. Déclaration de données.

2. Déclaration de fonctionnement.

Pour résoudre les problèmes, nous combinons la structure de données avec leurs opérations. Un ADT se compose de deux parties:

1. Déclaration des données.
2. Déclaration d'opération.

Les ADT couramment utilisés sont les listes liées, les piles, les Files d'attente, les Files d'attente prioritaires, les arbres, etc. Lors de la définition des ADT, nous n'avons pas à nous soucier des détails d'implémentation. Ils n'entrent en image que lorsque nous voulons les utiliser.

Le type de données abstrait est comme le type de données défini par l'utilisateur sur lequel nous pouvons effectuer des fonctions sans savoir ce qu'il y a à l'intérieur du type de données et comment les opérations sont effectuées sur eux . Comme l'information n'est pas exposée, elle est abstraite. par exemple. Liste, Tableau, Pile, File d'attente. Sur Stack, nous pouvons effectuer des fonctions comme Push, Pop mais nous ne savons pas comment il est mis en œuvre derrière les rideaux.

ADT est un ensemble d'objets et d'opérations, nulle part dans les définitions d'un ADT il n'y a de mention de la façon dont l'ensemble d'opérations est implémenté. Les programmeurs qui utilisent des collections doivent seulement savoir comment instancier et accéder aux données d'une manière prédéterminée, sans se soucier des détails des implémentations des collections. En d'autres termes, du point de vue d'un utilisateur, une collection est une abstraction, et pour cette raison, en informatique, certaines collections sont appelées données abstraites types (ADTs). L'utilisateur ne se préoccupe que de l'apprentissage de son interface, ou de l'ensemble des opérations qu'il effectue...plus

Notation du type de données Abstraites (ADT)

Un type de données abstrait pourrait être défini comme un modèle mathématique avec collection d'opérations définies dessus. Un exemple simple est l'ensemble des entiers avec les opérations d'union, intersection définie sur le plateau.

Les ADT sont des généralisations de type de données primitives(integer, char etc) et ils encapsulent un type de données dans le sens où la définition du type et de toutes les opérations sur ce type localisé à une section de le programme. Ils sont traités comme un type de données primitif en dehors du section dans laquelle le ADT et ses opérations sont définis.

Une implémentation d'un ADT est la traduction en énoncés de un langage de programmation de la déclaration qui définit une variable de soit de cela ADT , plus une procédure dans cette langue pour chaque fonctionnement de ce ADT . La mise en œuvre de l'ADT choisit un données structure pour représenter le ADT .

Un outil utile pour spécifier les propriétés logiques du type de données est le type de données abstraites. Fondamentalement, un type de données est une collection de des valeurs et un ensemble d'opérations sur ces valeurs. Que la collecte et le ces opérations forment une construction mathématique qui peut être implémentée utilisation d'une structure de données matérielle et logicielle particulière. Terme "type de données abstraites" fait référence au concept mathématique de base qui définit type de données.

En définissant un type de données abstrait comme concept mathématique, nous ne sommes pas concerné par l'efficacité de l'espace ou du temps. Ceux-ci sont la mise en œuvre question. En fait, la définition de ADT n'est pas concernée par implementaion détail du tout. Il peut même ne pas être possible de mettre en œuvre un particulier ADT sur un morceau particulier de matériel ou en utilisant un logiciel système. Par exemple, nous avons déjà vu qu'un ADT entier n'est pas universellement réalisable.

Pour illustrer le concept d'un ADT et ma méthode de spécification, considérons le ADT RATIONNEL qui correspond à la mathématique concept d'un nombre rationnel. Un nombre rationnel est un nombre qui peut être exprimé comme le quotient de deux entiers. Les opérations sur les nombres rationnels que nous définissons sont la création d'un nombre rationnel de deux entiers, addition, multiplication et test d'égalité. Ce qui suit est un spécification initiale de ce ADT .

                  /* Value defination */

abstract typedef <integer, integer> RATIONAL;
condition RATIONAL [1]!=0;

                 /*Operator defination*/

abstract RATIONAL makerational (a,b)
int a,b;
preconditon b!=0;
postcondition makerational [0] =a;
              makerational [1] =b;
abstract RATIONAL add [a,b]
RATIONAL a,b;
postcondition add[1] = = a[1] * b[1]
              add[0] = a[0]*b[1]+b[0]*a[1]
abstract RATIONAL mult [a, b]
RATIONAL a,b;
postcondition mult[0] = = a[0]*b[a]
              mult[1] = = a[1]*b[1]
abstract equal (a,b)
RATIONAL a,b;
postcondition equal = = |a[0] * b[1] = = b[0] * a[1];

Un ADT se compose de deux parties:-

1) définition de la Valeur

2) définition d'Opération

1) Définition de valeur: -

La définition de valeur définit la collection de valeurs pour l'ADT et se compose de deux parties:

1) Clause de définition

2) Clause de condition

Par exemple, la valeur la définition du ADT RATIONNEL indique que une valeur RATIONNELLE se compose de deux entiers, dont le second fait pas égal à 0.

Le mot-clé abstract typedef introduit une définition de valeur et le mot clé condition est utilisé pour spécifier toutes les conditions sur le nouveau type de données défini. Dans cette définition la condition spécifie que le le dénominateur peut ne pas être 0. La clause de définition est requise, mais le condition peut ne pas être nécessaire pour chaque ADT.

2) Définition de l'opérateur: -

Chaque opérateur est défini comme une jonction abstraite avec trois parties.

1)En-tête

2)Conditions préalables facultatives

3)Postconditions facultatives

Par exemple, la définition de l'opérateur du RATIONNEL ADT comprend opérations de création (makerational), d'addition (add) et la multiplication (mult) ainsi qu'un test d'égalité (égalité). Laissez-nous considérons d'abord la spécification pour la multiplication, car c'est le la plus simple. Il contient un en-tête et des post-conditions, mais non pré-conditions.

abstract RATIONAL mult [a,b]
RATIONAL a,b;
postcondition mult[0] = a[0]*b[0]
              mult[1] = a[1]*b[1]

L'en-tête de cette définition est les deux premières lignes, qui sont juste comme un en-tête de fonction C. Le mot clé abstract indique qu'il est pas une fonction C mais une définition d'opérateur ADT.

La condition post spécifie ce que fait l'opération. Dans un post-condition, le nom de la fonction (dans ce cas, mult) est utilisé pour désigner le résultat d'une opération. Ainsi, mult [0] représente numérateur de résultat et mult 1 représente le dénominateur de la résultat. C'est-à-dire qu'il spécifie, quelles conditions deviennent vraies après le l'opération est exécutée. Dans cet exemple, la condition post spécifie que le neumérateur du résultat d'une multiplication rationnelle est égal à produit entier des numérateurs des deux entrées et du dénominateur égale le produit einteger de deux dénominateur.

Liste

En informatique, une liste ou une séquence est un type de données abstrait qui représente un nombre dénombrable de valeurs ordonnées, où la même valeur peut se produire plus d'une fois. Un exemple d'une liste est un ordinateur représentation du concept mathématique d'une suite finie; (potentiellement) l'analogue infini d'une liste est un flux. Les listes sont une base exemple de conteneurs, car ils contiennent d'autres valeurs. Si la même valeur se produit plusieurs chaque occurrence est considérée comme un élément distinct

La liste de noms est également utilisée pour plusieurs structures de données concrètes qui peut être utilisé pour implémenter des listes abstraites, en particulier des listes liées.

Image d'une liste

Sac

Un sac est une collection d'objets, où vous pouvez continuer à ajouter des objets à le sac, mais vous ne pouvez pas les retirer une fois ajoutés au sac. Donc, avec un sac structure de données, vous pouvez recueillir tous les les objets, puis itérer à travers eux. Vous aurez des sacs normalement lorsque vous programmez en Java.

Image d'un Sac

Collection

Une collection au sens Java fait référence à toute classe qui implémente Interface de collecte. Une collection au sens générique n'est qu'un groupe de objets.

Image des collections

Le type de données abstrait est la collection de valeurs et tout type d'opération sur ces valeurs en fait un type de données abstrait exemple: String puisqu'il s'agit d'un type de données non primitif, nous pouvons l'inclure dans des types de données abstraits

En un mot simple: Un type de données abstrait est une collection de données et d'opérations qui fonctionnent sur ces données. Les opérations décrivent les données au reste du programme et permettent au reste du programme de modifier les données. Le mot "données" dans "type de données abstrait" est utilisé de manière lâche. Un ADT peut être une fenêtre graphique avec toutes les opérations qui l'affectent, un fichier et des opérations de fichier, une table de taux d'assurance et les opérations sur elle, ou autre chose.

à partir du code livre complet 2