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

le contraire de L'ADT est le type de données concrètes (CDT), où il contient une implémentation de L'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 de Surtout ADTs.

exemple concret:

Le livre est Abstrait (L'annuaire téléphonique est une implémentation)

Type de données Absact article de Wikipédia a beaucoup de choses à dire.

en informatique, un type de données abstraites (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 abstrait de données est définie indirectement, uniquement par les opérations qui peuvent être réalisées et en mathématique des contraintes sur les effets (et éventuellement le coût) de ces opérations.

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

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

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

sac est aussi connu sous le nom de 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 y a un ensemble unique qui contient les éléments a et b et aucun autre, mais il y a beaucoup de multisets avec cette propriété, comme 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 sera une collection qui implémente une interface très simple. Vous avez seulement besoin d'être en mesure d'ajouter des éléments à un sac, vérifiez sa taille, et d'itérer sur les éléments qu'il contient. Voir le Sac.java pour un exemple de mise en œuvre (à partir de Sedgewick & Wayne algorithmes 4e édition).

un type de données vraiment abstrait décrit les propriétés de ses instances sans engagement envers leur représentation ou opérations particulières. Par exemple, l'entier de type abstrait (mathématique) est un ensemble d'instances discrètes, illimitées, ordonnées linéairement. 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 is implementaion est cachée à l'utilisateur.seulement l'interface est déclarée .Cela signifie que L'ADT est de différentes façons

simplement le type de données abstraites n'est rien mais un ensemble d'opérations et de données est utilisé pour stocker certaines autres données efficacement dans la machine. Il n'est pas nécessaire de faire une déclaration de type particulier. Il suffit d'une mise en œuvre de L'ADT.

résumé le type de données est un module mathématique qui inclut des données avec diverses opérations. Les détails de la mise en œuvre sont cachés et c'est pourquoi on les appelle abstraits. 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é par l'encapsulation, les données et les opérations sont représentées, ou à la liste déclaré, dans une seule unité syntaxique, et cacher des informations, seules les opérations concernées sont visibles pour l'utilisateur de l'ADT, l'ADT interface, de la même manière qu'un type de données normal langage de programmation. C'est une abstraction parce que la représentation interne des données et la mise en œuvre des opérations ne concernent pas L'utilisateur ADT.

Avant de définir types de données abstraites, considérons les différentes 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.) soutenir des opérations de base telles que 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 les opérations. La mise en œuvre de ces opérations peuvent être fait lorsque nous voulons utiliser ils. Cela signifie en général, types de données sont définis ainsi que leurs opérations.

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

usually used ADT'S sont les suivantes: Liste Liée, Piles, Files, Arbres Binaires, Dictionnaires, ensembles disjoints (Union et find), tables de hachage et de nombreux les autres.

ADT's se composent de deux types:

1. Déclaration de données.

2. Déclaration de l'opération.

pour résoudre les problèmes, nous combinons la structure des 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 les plus couramment utilisés sont les listes de liens, les empilements, les Files d'attente, les Files D'attente de priorité, les arbres, etc. Lors de la définition des ADTs, nous n'avons pas besoin de nous soucier des détels de mise en œuvre. Ils viennent en image seulement lorsque l'on veut utiliser.

résumé type de données sont 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 son résumé. par exemple. Liste,Tableau, Pile, File D'Attente. Sur la pile, nous pouvons effectuer des fonctions comme Push, Pop, mais nous ne sommes pas sûrs de la façon dont il est mis en œuvre derrière les rideaux.

ADT est un ensemble d'objets et d'opérations, Non où dans les définitions D'un ADT il n'y a aucune mention de la façon dont l'ensemble des opérations est mis en œuvre. Les programmeurs qui utilisent les collections n'ont besoin que de savoir 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, à partir d'un point de vue utilisateur, une collection est une abstraction, et pour cette raison, en informatique, certaines collections sont appelés abstrait types de données (ADTs). L'utilisateur est seul souci avec l'apprentissage de son interface, ou de l'ensemble de ses opérations effectue...plus

Notation du type de données abstraites (ADT)

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

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

une implémentation d'un ADT est la traduction en déclarations de un langage de programmation de la déclaration qui définit une variable de être que ADT, plus une procédure dans cette langue pour chaque le fonctionnement de cette ADT. La mise en œuvre de l'ADT choisit un structure des données 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 un ensemble 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 mis en œuvre utilisation d'une structure de données matérielle et logicielle particulière. Terme "type abstrait de données" renvoie au concept mathématique de base qui définit le 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 effet, le defination de ADT n'est pas concerné avec implementaion détail. Il n'est peut-être même pas possible de mettre en œuvre un particulier ADT sur un morceau de matériel ou à l'aide d'un logiciel système. Par exemple, nous avons déjà vu qu'un ADT entier n'est pas universellement applicables.

Pour illustrer le concept de ADT et ma méthode de spécification, envisager l' ADT RATIONAL qui correspond à la mathématique concept d'un nombre rationnel. Un nombre rationnel est un nombre qui peut soit exprimé comme le quotient de deux entiers. Les opérations sur les nombres rationnels que nous définissons sont les la création d'un nombre rationnel de deux entiers, l'addition, la multiplication et le test pour l'égalité. Voici une première spécification 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];

ADT se compose de deux parties:-

1) Définition de la valeur

2) définition de L'opération

1) Définition De La Valeur: -

la définition de la valeur définit la collecte de valeurs pour L'ADT et se compose de deux parties:

1) Clause De Définition

2) Clause De Condition

par exemple, la définition de la valeur pour le ADT RATIONNELLE des états qui une valeur RATIONNELLE se compose de deux entiers, la deuxième pas égal à 0.

le mot-clé abstract typedef introduit une définition des valeurs et la la condition de mot-clé est utilisée pour préciser toutes les conditions sur le nouveau type de données défini. Dans cette définition, l'état indique que le le dénominateur peut ne pas être 0. La clause de définition est nécessaire, mais la 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 à trois parties.

1)en-Tête

2)facultatif Conditions préalables

3)En Option Postconditions

par exemple, la définition de l'opérateur de la logique ADT inclut opérations de création (makerational), ajout (add) et la multiplication (mult) ainsi qu'un test d'égalité (égalité). Laissez-nous considérer la spécification de la multiplication d'abord, depuis, c'est le la plus simple. Il contient un en-tête et des post-conditions, mais aucun conditions préalables.

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 la première deux 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 post-condition 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 égale entier produit des numérateurs des deux entrées et le dénominateur est égal au produit plus petit de deux dénominateurs.

Liste

En informatique, une liste ou une séquence est un type abstrait de données que représente un dénombrable nombre 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 séquence finie; la (potentiellement) infini analogique 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 fois, 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 mettre en œuvre des listes abstraites, en particulier des listes liées.

Image D'une liste

Sac

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

l'Image d'un Sac

Collecte

une collection dans le sens de Java se réfère à toute classe qui met en œuvre le Interface de collecte. Une collection dans un sens générique est juste un groupe de objets.

Image des collections

Abstract le type de données est la collecte de valeurs et toute opération sur ces valeurs le rend abstrait le type de données exemple: Chaîne de caractères étant donné qu'il s'agit d'un type de données non primitif, nous pouvons l'inclure dans les types de données abstraites

en un mot simple: un type de données abstraites est un ensemble 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 changer les données. Le mot "données" dans "Type de données abstraites" est utilisé de façon vague. Un ADT peut être une fenêtre graphique avec toutes les opérations qui l'affectent, un fichier et des opérations de fichiers, une table de taux d'assurance et les opérations sur elle, ou quelque chose d'autre.

à partir de code complet 2 livre