Classes abstraites et membres de la classe. Algorithmes et structures de données

Bonjour, habitants de Khabra !

L'article suivant est un résumé de mes réflexions sur la nature des cours et de l'ADT. Ces réflexions sont complétées par des citations intéressantes tirées des livres de gourous du développement logiciel.

Introduction

Commençons par aborder progressivement la définition de l'ADT. Un ADT est avant tout un type de données, ce qui signifie :
la présence de certaines opérations disponibles sur des éléments de ce type ;
ainsi que les données sur lesquelles ces opérations sont effectuées (plage de valeurs).

Que signifie le mot « abstrait » ? Tout d’abord, le concept d’« abstraction » signifie concentrer notre attention sur quelque chose d’important et, en même temps, nous devons nous distraire des détails qui ne sont pas importants pour le moment. La définition de l'abstraction est bien couverte dans le livre de Grady Booch. La définition est la suivante :

L'abstraction est la sélection et l'attribution à un ensemble d'objets de propriétés communes qui déterminent leurs limites conceptuelles et les distinguent de tous les autres types d'objets.
En d’autres termes, l’abstraction nous permet de « faire la lumière » sur les données objets dont nous avons besoin et, en même temps, « d’ombrer » les données qui ne sont pas importantes pour nous.

Alors, que se passe-t-il si vous fusionnez les concepts de « type de données » et d’« abstraction » ? Nous recevrons un type de données qui nous fournit un certain ensemble d'opérations qui assurent le comportement des objets de ce type de données, et ce type de données masquera également les données avec lesquelles ce comportement est implémenté. Nous arrivons donc au concept d’ADT :

Un ADT est un type de données qui cache son implémentation interne aux clients.
Ce qui est étonnant, c'est qu'en appliquant l'abstraction, ADT nous permet de ne pas nous soucier des détails d'implémentation de bas niveau, mais de travailler avec l'essence de haut niveau du monde réel (Steve McConnell).

Je pense que lors du développement d'un ADT, vous devez d'abord définir une interface, car l'interface ne doit pas dépendre de la représentation interne des données dans l'ADT. Après avoir défini les opérations qui composent l'interface, vous devez vous concentrer sur les données qui mettront en œuvre le comportement spécifié de l'ADT. En conséquence, nous obtiendrons une certaine structure de données - un mécanisme qui nous permet de stocker et de traiter des données. En même temps, la beauté d'ADT est que si nous voulons modifier la représentation interne des données, nous n'avons pas besoin de parcourir tout le programme et de modifier chaque ligne de code qui dépend des données que nous voulons modifier. Un ADT encapsule ces données, ce qui vous permet de modifier le fonctionnement des objets de ce type, plutôt que l'ensemble du programme.

Avantages de l'ATD

Utiliser un ADT présente de nombreux avantages (tous les avantages décrits se trouvent dans le livre "Perfect Code" de Steve McConnell) :

• Encapsulation des détails de mise en œuvre.
  Cela signifie qu'une fois que nous avons encapsulé les détails d'implémentation de l'ADT, nous fournissons au client une interface avec laquelle il peut interagir avec l'ADT. En modifiant les détails de mise en œuvre, la perception des clients de l'opération ADT ne changera pas.

• Complexité réduite.
  En faisant abstraction des détails d'implémentation, nous nous concentrons sur l'interface, c'est-à-dire sur ce que l'ADT peut faire, plutôt que sur la manière dont cela est fait. De plus, ADT nous permet de travailler avec l'essence du monde réel.

• Limiter la portée de l’utilisation des données.
  En utilisant un ADT, nous pouvons être sûrs que les données représentant la structure interne de l'ADT ne dépendront pas d'autres parties du code. Dans ce cas, « l’indépendance » de l’ADT est réalisée.

• Interface très informative.
  ADT vous permet de présenter l'intégralité de l'interface en termes d'entités de domaine, ce qui, voyez-vous, augmente la lisibilité et le caractère informatif de l'interface.

Steve McConnell recommande de représenter les types de données de bas niveau, tels qu'une pile ou une liste, en tant qu'ADT. Demandez-vous ce que représente cette liste. S'il s'agit d'une liste d'employés de banque, considérez alors l'ATD comme une liste d'employés de banque.

Nous avons donc compris ce qu'est l'ADT et nommé les avantages de son utilisation. Il convient maintenant de noter que lors du développement de cours en POO, vous devez d'abord penser à l'ADT. En même temps, comme le disait Steve McConnell, on ne programme pas dans un langage, mais avec l'aide d'un langage. Autrement dit, vous programmerez au-delà des limites du langage, sans vous limiter à penser en termes de tableaux ou de types de données simples. Au lieu de cela, vous penserez à un niveau élevé d’abstraction (par exemple, en termes de feuilles de calcul ou de listes d’employés). Une classe n'est rien de plus qu'un ajout et un moyen de mettre en œuvre le concept ADT. On peut même représenter la classe sous forme de formule :
Classe = ADT + Héritage + Polymorphisme.
Alors pourquoi devriez-vous penser à ADT lors du développement de cours ? Car il faut d’abord décider quelles opérations constitueront l’interface de la future classe, quelles données masquer et lesquelles donner accès au public. Nous devons réfléchir à la manière de rendre l'interface hautement informative, de rendre le code facile à optimiser et à tester, et à la manière dont nous pouvons fournir la bonne abstraction afin que nous puissions penser aux entités du monde réel plutôt qu'aux détails d'implémentation de bas niveau. Je crois que c'est après avoir défini l'ADT qu'il faut réfléchir aux questions d'héritage et de polymorphisme.

Il convient de noter que le concept d'ADT a trouvé une large application en POO, car c'est ce concept qui complète la POO et permet de réduire la complexité des programmes dans le monde en évolution rapide des exigences logicielles.

J'ai écrit cet article afin d'attirer l'attention des développeurs sur ADT afin d'améliorer la qualité du travail et du développement logiciel.

Sources utilisées :

Steve McConnell - « Code parfait » ;
Robert Sedgwick - « Algorithmes en Java ».

Dernière mise à jour : 08/04/2018

En plus des cours réguliers, C# a cours abstraits. Une classe abstraite est similaire à une classe normale. Il peut également avoir des variables, des méthodes, des constructeurs, des propriétés. La seule chose est que lors de la définition des classes abstraites, le mot-clé abstract est utilisé :

Classe abstraite Humain ( public int Longueur ( get; set; ) public double Weight ( get; set; ) )

Mais la principale différence est que nous ne pouvons pas utiliser le constructeur d’une classe abstraite pour créer son objet. Par exemple, comme suit :

Humain h = new Human();

Pourquoi les cours abstraits sont-ils nécessaires ? Disons que dans notre programme pour le secteur bancaire, nous pouvons définir deux entités principales : un client de banque et un employé de banque. Chacune de ces entités sera différente, par exemple, pour un employé il faut déterminer sa position, et pour un client - le montant du compte. En conséquence, le client et l'employé formeront des classes distinctes Client et Employé. Dans le même temps, ces deux entités peuvent avoir quelque chose en commun, par exemple un prénom et un nom, ou une autre fonctionnalité commune. Et il est préférable de déplacer cette fonctionnalité générale dans une classe distincte, par exemple Person, qui décrit une personne. Autrement dit, les classes Employee (employé) et Client (client de la banque) seront dérivées de la classe Person. Et comme tous les objets de notre système représenteront soit un employé de banque, soit un client, nous ne créerons pas directement d'objets à partir de la classe Personne. Il est donc logique de le rendre abstrait :

Classe abstraite Personne ( public string Name ( get; set; ) public Person(string name) ( Name = name; ) public void Display() ( Console.WriteLine(Name); ) ) class Client: Person ( public int Sum ( get ; set; ) // montant du compte public Client(string name, int sum) : base(name) ( Sum = sum; ) ) class Employee: Person ( public string Position ( get; set; ) // position public Employee( string nom, position de la chaîne) : base(nom) ( Position = position; ) )

On peut alors utiliser ces classes :

Client client = nouveau Client("Tom", 500); Employé employé = nouvel Employé("Bob", "Apple"); client.Display(); employé.Display();

Ou même comme ça :

Personne client = nouveau Client("Tom", 500); Personne employé = nouvel employé("Bob", "Opérateur");

Mais nous ne pouvons PAS créer un objet Person en utilisant le constructeur de classe Person :

Personne personne = new Personne("Facture");

Cependant, malgré le fait que nous ne pouvons pas appeler directement le constructeur de la classe Person pour créer un objet, le constructeur dans les classes abstraites peut néanmoins jouer un rôle important, en particulier initialiser certaines variables et propriétés communes aux classes dérivées, comme dans le cas de la propriété Nom. Bien que le constructeur de la classe Person ne soit pas appelé dans l'exemple ci-dessus, les classes dérivées Client et Employee peuvent toujours y accéder.

Membres de la classe abstraite

En plus des propriétés et méthodes habituelles, une classe abstraite peut avoir des membres de classe abstraite, qui sont définis à l'aide du mot-clé abstract et n'ont aucune fonctionnalité. En particulier, les abstraits peuvent être :

• Propriétés

  Indexeurs

Les membres de la classe abstraite ne doivent pas avoir le modificateur privé. Dans ce cas, la classe dérivée doit redéfinir et implémenter toutes les méthodes et propriétés abstraites présentes dans la classe abstraite de base. En cas de substitution dans une classe dérivée, une telle méthode ou propriété est également déclarée avec le modificateur override (comme pour la substitution normale des méthodes et propriétés virtuelles). Il convient également de noter que si une classe possède au moins une méthode abstraite (ou propriété abstraite, indexeur, événement), alors cette classe doit être définie comme abstraite.

Les membres abstraits, comme les membres virtuels, font partie d'une interface polymorphe. Mais si dans le cas des méthodes virtuelles nous disons que la classe héritière hérite de l'implémentation, alors dans le cas des méthodes abstraites, l'interface représentée par ces méthodes abstraites est héritée.

Méthodes abstraites

Par exemple, rendons la méthode Display abstraite dans l'exemple ci-dessus :

Classe abstraite Personne ( public string Name ( get; set; ) public Person(string name) ( Name = name; ) public abstract void Display(); ) class Client: Person ( public int Sum ( get; set; ) // somme sur le compte public Client(string name, int sum) : base(name) ( Sum = sum; ) public override void Display() ( Console.WriteLine($"(Name) a un compte sur le montant (Sum)") ; ) ) class Employee: Person ( public string Position ( get; set; ) // position public Employee(string name, string position) : base(name) ( Position = position; ) public override void Display() ( Console.WriteLine ($" (Position) (Nom)");

Propriétés abstraites

Notez l'utilisation de propriétés abstraites. Leur définition est similaire à celle des propriétés automobiles. Par exemple:

Classe abstraite Personne ( chaîne abstraite publique Nom ( get; set; ) ) classe Client: Personne ( nom de chaîne privée; chaîne de remplacement publique Nom ( get ( return "M./Mme. " + nom; ) set ( nom = valeur; ) ) ) classe Employé : Personne (chaîne de remplacement publique Nom ( get; set; ) )

La classe Person définit une propriété abstraite appelée Name. Cela ressemble à une propriété automobile, mais ce n’est pas une propriété automobile. Puisque cette propriété ne doit pas avoir d’implémentation, elle n’a que des blocs get et set vides. Dans les classes dérivées, nous pouvons surcharger cette propriété, en en faisant une propriété à part entière (comme dans la classe Client) ou en la rendant automatique (comme dans la classe Employee).

Éviter la mise en œuvre de membres abstraits

La classe dérivée doit implémenter tous les membres abstraits de la classe de base. Cependant, nous pouvons choisir de ne pas l'implémenter, mais dans ce cas la classe dérivée doit également être définie comme abstraite :

Classe abstraite Personne ( chaîne abstraite publique Nom ( get; set; ) ) classe abstraite Gestionnaire : Personne ( )

Exemple de classe abstraite

Un exemple classique est un système de figures géométriques. En réalité, il n’existe pas de figure géométrique en tant que telle. Il y a un cercle, un rectangle, un carré, mais il n’y a tout simplement pas de figure. Cependant, le cercle et le rectangle ont quelque chose en commun et sont des figures :

// classe abstraite d'une figure classe abstraite Figure ( // méthode abstraite pour obtenir le périmètre public abstract float Perimeter(); // méthode abstraite pour obtenir la zone public abstract float Area(); ) // classe dérivée d'une classe rectangle Rectangle : Figure ( public float width ( get; set; ) public float Height ( get; set; ) public Rectangle(float width, float height) ( this.Width = width; this.Height = height; ) // remplace l'obtention du périmètre public override float Perimeter() ( return width * 2 + Height * 2; ) // remplace l'obtention de la zone public override float Area() ( return width * height; ) )

Type de données abstrait Dispositions générales sur les données Type de données abstrait dispositions générales spécification, représentation, mise en œuvre 1

Que sont les données ? Un ensemble de divers objets d'information sur lesquels certaines actions sont effectuées par les opérateurs du programme est appelé données. Les données sont un attribut indispensable de tout programme. Il peut s'agir : - de bits individuels ; - séquence de bits indépendants ; -les nombres sous différentes formes de représentation ; -octets et groupes d'octets indépendants ; -des tableaux de nombres ; - listes chaînées ; -fichiers individuels et systèmes de fichiers. 2

Une représentation universelle de cette variété de données est difficile et peu pratique. Il convient de les diviser en 3 types.

Qu'est-ce qu'un type de données ? Le type de données est déterminé par : – Le format de représentation en mémoire de l'ordinateur selon certaines conventions du langage algorithmique, mais sans nécessité de calculs ; – L’ensemble des valeurs valides que peut prendre une variable ou une constante appartenant au type sélectionné ; – L'ensemble des opérations valides applicables à ce type. 4

Exemples de types de données Types entiers Type réel Type booléen Type caractère Type énuméré Type intervalle Pointeurs 5

Types d'entiers Il existe cinq types d'entiers prédéfinis : Shortint, Integer, Longint, Byte et Word. Chaque type désigne un sous-ensemble spécifique d'entiers. Une valeur d'un type intégral peut être explicitement convertie en un autre type intégral à l'aide d'un transtypage. 6

Type réel Le type réel est un sous-ensemble de nombres représentés au format à virgule flottante et avec un nombre fixe de chiffres. L'écriture d'une valeur au format à virgule flottante implique généralement trois valeurs - m, b et e - telles que m * b ^ e = n, où b vaut toujours 2 et m et e sont des valeurs entières dans la plage réelle. Ces valeurs de m et e déterminent en outre la plage de représentation et la précision du type réel. Exemple : 0,143 E+22, où m - 0,143 ; b = 2 (implicite), e = 22. Il existe cinq types de types réels : Real, Single, Double, Extended et Comp. 7

Type logique Il existe 4 types logiques (booléens) prédéfinis : Booléen, Octet. Bool, Word. Booléen et Long. Bool. Les valeurs booléennes sont désignées par les identifiants constants intégrés False et True. Les variables booléennes peuvent être utilisées pour stocker les résultats de tout calcul logique. Pour les variables booléennes, seules 2 opérations de comparaison sont autorisées : "=" (égal) et "" (inégal). 8

Type de caractère Le jeu de valeurs de ce type est constitué de caractères classés selon le jeu de caractères ASCII étendu. Ce sont les lettres ["A". . . "Z", "a". . . "z"], chiffres ["0". . . "9"], signes de ponctuation et caractères spéciaux. Une variable de ce type occupe un octet en mémoire. 9

Type énuméré Les types énumérés définissent des ensembles ordonnés de valeurs en énumérant les identifiants qui représentent ces valeurs. Les ensembles sont classés selon l'ordre dans lequel les identifiants sont répertoriés. Type Semaine = (lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche) ; 10

Type d'intervalle Un type d'intervalle représente une plage de valeurs d'un type ordinal. La définition du type d'intervalle inclut la valeur la plus petite et la plus grande d'une sous-plage. Tapez Intervalle = 0. . . 1000 ; Cette déclaration de type indique au compilateur que seuls les nombres compris dans la plage spécifiée sont valides pour les variables de ce type. Ainsi, le programme peut vérifier automatiquement l'exactitude des opérations d'affectation pour ces variables. 11

Commun aux types de données Chaque type de données est associé à un certain nombre d'opérations simples. Opérations INTEGER +, -, *, div, mod REAL - opérations + , -, *, / BOOLEAN - opérations - conjonction (et), disjonction V (ou), négation (non) opérations CHAR ORD (c) -N : ( C en ASCII), CHR (I) I-ième caractère en ASCII À mesure que le volume et la complexité de la représentation de l'information augmentent, le besoin se fait sentir de formes pratiques de sa présentation, de son stockage et de son traitement. 12

Définition : Un type de données abstrait (ATD ou type de données abstrait, ou ADT) est un ensemble d'objets abstraits représentant des éléments de données, et des ensembles d'opérations définis sur celui-ci qui peuvent être effectués sur les éléments de cet ensemble. 13

ADT - généralisation des types de données Les types de données abstraits (ADT) peuvent être considérés comme un moyen d'étendre les langages de programmation. Comparons un type de données abstrait avec un concept aussi familier qu'une procédure. Une procédure peut être considérée comme une notion généralisée d’opérateur. Deux traits caractéristiques des procédures, la généralisation et l'encapsulation, caractérisent parfaitement les types de données abstraits. Un ADT peut être considéré comme une généralisation de types de données simples (entiers, réels, etc.), tout comme une procédure est une généralisation d'opérateurs simples (+, -, etc.) 14

Avantages d'ADT Les structures de données abstraites sont conçues pour un stockage et un accès pratiques aux informations. Ils fournissent une interface pratique pour les opérations courantes avec les objets stockés, tout en cachant les détails d'implémentation à l'utilisateur. Bien sûr, cela est très pratique et permet d'obtenir une plus grande modularité du programme. 15

Exemple Pour le contrôle automatisé de la température dans diverses pièces d'un grand bâtiment, un ADT utile serait le THERMOSTAT. Un programme peut avoir de nombreuses variables de type THERMOSTAT correspondant aux thermostats réels dans différentes zones du bâtiment. Un ADT peut être décrit par son nom, son ensemble de valeurs et ses opérations valides, comme n'importe quel autre type de données. Description du type THERMOSTAT : – Type de données : THERMOSTAT – Plage de valeurs : la température peut varier de 0 à 50 degrés (Celsius). – Opérations : haut, bas, réglage, contrôle, alarme. (Vous pouvez proposer de nombreuses opérations utiles, mais trop d'entre elles dégradent l'abstraction) 16

Niveaux d'abstraction Les niveaux d'abstraction sont comme des couches de logiciels. Les niveaux d'abstraction les plus élevés reflètent la compréhension par l'utilisateur de la solution au problème. Les niveaux d'abstraction inférieurs correspondent aux capacités du langage de programmation. 17

Exemple d'abstraction au niveau utilisateur Un architecte représente une maison sous forme de murs, sols, fenêtres, portes, etc. Dans ce cas, le type de données est Dessin. Les portes feraient un bon type abstrait. Type de données : Dessin. Opérations de porte : dessiner. Effacement de porte. Tirage de porte. Double. Porte ……. Dessin. Les portes sont une abstraction de haut niveau qui reflète la vision du problème par l'utilisateur 18

Exemple d'abstraction au niveau du programmeur Le programmeur peut proposer un autre niveau d'abstraction pour ces objets, comme un rectangle. Type de données : Rectangle Opérations : Dessiner. Effacement rectangulaire. Division rectangulaire. Rectangle. Sur. Parties……. Le rectangle est une abstraction de niveau inférieur car il est plus proche de l'implémentation. 19

Constructeurs ADT Chaque ADT doit contenir des opérations pour construire des valeurs de son type. De telles opérations sont appelées constructeurs. Il doit y avoir suffisamment de constructeurs pour générer l'ensemble des valeurs d'un type donné. Un ADT qui satisfait cette propriété est appelé complet. Un ADT incomplet est une erreur de conception. 20

Recommandations pour la sélection des opérations d'un type de données abstrait Il convient d'inclure les opérations suivantes : – les opérations de constructeur, – les opérations de vérification, – les opérations de conversion de type, – les opérations d'entrée-sortie, – les opérations de copie, – les opérations de sélecteur. Essayez de réduire le nombre d'opérations au minimum. L'ADT simple est plus facile à comprendre. Maintenir les opérations associées à l’abstraction de type sélectionné. 21

Constructeur principal Les opérations qui créent de nouvelles valeurs d'un ADT quelle que soit sa valeur précédente sont appelées constructeurs principaux. Chaque ADT comprend au moins un constructeur principal : sans lui, il est impossible de générer la valeur initiale. 22

Utilisation des types cachés Il est préférable de déclarer les types de données abstraits comme types cachés. Cela permet de déplacer la description de la structure des données vers le module d'implémentation, où elle est principalement utilisée. Ils offrent également la possibilité d'empêcher l'accès direct aux composants de type par l'importateur. Puisqu'un type caché est toujours implémenté à l'aide d'un pointeur, trois opérations doivent être incluses dans l'ADT. – Créer - une opération qui crée un nœud de la structure correspondante. – Destroy est une opération permettant de libérer la mémoire d’un nœud de type caché. – Attribuer - l'opération de copie des champs de la structure dynamique d'un nœud de type caché. 23

Qu'est-ce que la spécification et l'implémentation d'un type de données abstrait ? Un type de données abstrait est une manière de définir un certain concept sous la forme d'une classe d'objets avec certaines propriétés et opérations. Dans un langage de programmation, une telle définition est formalisée comme une construction syntaxique spéciale, appelée dans différents langages capsule, module, cluster, classe, package, formulaire, etc. Cette construction dans sa forme la plus développée contient : une spécification de type de données , comprenant une description de l'interface (le nom du type défini, les noms des opérations indiquant leurs profils) et une description abstraite des opérations et des objets avec lesquels elles travaillent, à l'aide de certains moyens de spécification ; une implémentation d'un type de données, comprenant une description spécifique des mêmes opérations et objets. 24

Classification des types de données selon la méthode de description et de protection conditionnée, si la description du type de données est collectée en un seul endroit (dans un seul package), c'est-à-dire que ses objets et opérations sont combinés en un seul concept ; il a une définition, qui ne peut cependant contenir que sa mise en œuvre ; encapsulé, si le type de données est empaqueté, sa définition contient une description et une implémentation de l'interface, et l'encapsulation de l'implémentation est également fournie ; abstract si le type de données est encapsulé et que sa spécification inclut une description abstraite. 25

Composantes d'une spécification La programmation, en tant que processus, commence par un énoncé du problème (sa définition) ou une spécification du problème. Plus loin dans le texte, des spécifications composées de six éléments sont utilisées : – Titre - le nom du problème à résoudre ; – Description - plusieurs phrases décrivant l'essence de la tâche ; – Entrée - une description détaillée de la forme attendue des données d'entrée ; – Sortie – une description détaillée de la forme attendue des données de sortie ; – Erreurs - une liste détaillée des situations qui surviennent lorsque les données d'entrée sont incorrectes ; – Exemple - un exemple d'exécution en termes d'entrées-sorties. 26

Exemple de spécification Type de données abstrait STACK, implémentant une structure de données bien connue, caractérisée par le fait que vous pouvez « y mettre » un élément et « sélectionner » l'élément le plus récemment placé là-bas. La partie syntaxique de la spécification du type de données STACK ressemble à la spécification du type STACK : CREATE : function () return (@); INSÉRER : fonction (entier ; @) return (@ ); SUPPRIMER : fonction (@) return (@); TOP : fonction (@) retour (entier) ; VIDE : fonction (@) return (booléen) ; spécification finale ; Ici, l'opération CREATE produit une pile vide, INSERT - une pile avec son élément ajouté au "top", DELETE - une pile avec l'élément "top" supprimé, TOP - la valeur de l'élément "top" de la pile, VIDE - un signe que la pile est vide. Les éléments de la pile ici ne peuvent être que des entiers. 27

IMPLÉMENTATION D'UN TYPE DE DONNÉES ABSTRAIT L'implémentation est plus facilement réalisée à l'aide de langages de programmation orientés objet, tels que C++ ou Java, dans lesquels les types de données abstraits sont pris en charge à l'aide de classes. L'implémentation d'un ADT comprend une description spécifique des objets d'un type et d'une implémentation définis. d'opérations de ce type. Cela signifie que les objets sont décrits soit comme des données de types simples, soit comme des tableaux, des enregistrements ou des unions. De plus, des types de données prédéfinis ou des ADT définis précédemment sont utilisés. La mise en œuvre des opérations consiste à décrire des sous-programmes qui effectuent les actions nécessaires avec des objets spécifiés. Par exemple, les opérations +, *, =. . etc., mais en même temps la mise en œuvre même de ces opérations est cachée. 28

Annexe au programme de travail de la discipline « Structures et algorithmes pour le traitement des données par ordinateur »

Type de données abstrait "Liste".

Liste– une séquence d’éléments d’un certain type un1 , un2 , ..., un n, Où n https://pandia.ru/text/78/308/images/image001_307.gif" width="13" height="16">1, puis un1

Appelé le premier élément, et un– le dernier élément de la liste. Les éléments d'une liste sont ordonnés linéairement en fonction de leur position dans la liste. élément ai précèdeélément ai+1 Pour je = 1,2, n-1 Et ai devrait pour ai-1 Pour je = 2,3, n. Chaque élément de la liste ai a position je, je=1,2, n. Il y a une position dans la liste , ce qui signifie la fin de la liste - néant. Il suit le dernier élément de la liste.

Opérateurs de la « Liste » ATD :

1.INSÉRER( x, r,L). Cette instruction insère un objet X en position r sur la liste L, déplacer les éléments de la position p puis vers la position immédiatement supérieure. Donc si la liste L se compose d'éléments un1 , un2 , ..., UNn a1, a2, ..., ar-1, x, ar, ..., unn.. Si p prend la valeur néant, alors nous aurons un1 , un2 , ..., unn , ,X. Si sur la liste L pas de poste p, alors le résultat de l'exécution de cette instruction n'est pas défini.

2. SITUER(x , L ). Cette fonction renvoie la position de l'objet X sur la liste L. Si l'objet est dans la liste x se produit plusieurs fois, la position du premier objet depuis le début de la liste est renvoyée X. Si l'objet X pas sur la liste L, puis revient néant.

3. RÉCUPÉRER(p , L ). Cette fonction renvoie l'élément qui est à la position r sur la liste L. Le résultat n'est pas défini si p = néant ou dans la liste L pas de poste r.

4. SUPPRIMER(p , L ). Cet opérateur supprime l'élément à la position r liste L. Donc, si la liste L se compose d'éléments un1 , un2 , ..., UNn, puis après avoir exécuté cet opérateur, cela ressemblera à a1, a2, ...,, ap- je , ap+ je, ..., UN n. Le résultat n'est pas défini si dans la liste L pas de poste r ou r = néant.

5. SUIVANT( p, L ) Et PRÉCÉDENT(p, L ). Ces fonctions renvoient respectivement les positions suivante et précédente à partir de la position r sur la liste L. Si r- dernière position dans la liste L, puis SUIVANT (p, L) = néant. La fonction NEXT n'est pas définie lorsque p=néant. La fonction PREVIOUS n'est pas définie si p = 1. Les deux fonctions ne sont pas définies si elles sont dans la liste L pas de poste r.

6. MAKENULL( L ) . Cette fonction fait une liste L vide et renvoie la position néant.

7. D'ABORD(L ). Cette fonction renvoie la première position de la liste L. Si la liste est vide, alors la position est renvoyée néant.

8. IMPRIMER LISTE(L ). Imprime les éléments de la liste L dans l'ordre dans lequel ils apparaissent dans la liste.

Représenter une liste à l'aide d'un tableau :

Vue de liste en utilisant liste chaînée unique :

Désignations :

· – pointeur vers le début de la liste,

· dernier - pointeur vers le dernier élément de la liste ,

· longueur maximale – longueur maximale (nombre d'éléments) dans la liste.

Représenter une liste à l'aide d'une liste doublement chaînée :

Exercices :

1. Écrire des programmes pour insérer, supprimer et rechercher des éléments d'une liste triée, en utilisant pour implémenter la liste

§ tableau,

§ pointeurs.

2. Écrivez un programme de fusion

§ deux listes chaînées triées,

§ n listes chaînées triées,

3. Étant donné un polynôme de la forme

p(x) = c1 xe1 + c2 xe2 + + AvecnXn, Où e1 > e2 > ... > en> 0.

Un tel polynôme peut être représenté comme une liste chaînée, où chaque élément possède trois champs : un pour le coefficient Avecje la seconde est pour l'exposant eje le troisième est pour un pointeur vers l’élément suivant. Pour la représentation décrite des polynômes, écrivez un programme pour additionner et multiplier des polynômes en utilisant cette représentation.

4. Implémentez un LIST ADT pour tout type de données et ses opérateurs INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST :

§ la liste est spécifiée sous forme de tableau,

§ la liste est spécifiée comme une liste à chaînage unique,

§ La liste est spécifiée comme une liste doublement chaînée.

Programme de travail section 2.1.2

Type de données abstrait "Pile".

Empiler - est un type spécial de liste dans laquelle toutes les insertions et suppressions sont effectuées à une seule extrémité, appelée haut , (haut). La méthode d'accès utilisée pour la pile est LIFO(dernier entré, premier sorti - dernier entré - premier sorti).

Opérateurs d'ATD "Stack":

1. MAKENULL(S). Rend la pile de S vide.

2. HAUT(S). Renvoie l'élément du haut de la pile S. Généralement, le haut de la pile est identifié par la position 1, alors TOP(S) peut être écrit en termes d'opérateurs de liste communs comme RETRIEVE(FIRST(S), S).

3. POPULAIRE(S). Supprime un élément du haut de la pile (le fait sortir de la pile), en termes d'opérateurs de liste, cet opérateur peut être écrit sous la forme DELETE(FIRST(S), S).

4. POUSSER(x, S ). Insère un élément X en haut de la pile S (pousse un élément sur la pile). L'élément précédemment en haut de la pile devient l'élément à côté du haut, et ainsi de suite. En termes d'opérateurs de liste courants, cette instruction peut être écrite sous la forme INSERT(;c, FIRST(S), S).

5. VIDE(S) . Cette fonction renvoie vrai si la pile S vide, et faux sinon.

tableau:

Vue de pile utilisant liste chaînée unique :

Exercices :

Implémentez le STACK ADT pour tout type de données et ses opérateurs MAKENULL, TOP, POP, PUSH, EMPTY.

§ la pile est spécifiée sous forme de tableau,

§ La pile est spécifiée comme une liste à chaînage unique.

Programme de travail section 2.1.2

Type de données abstrait "File d'attente".

File d'attente (file d'attente) est un type spécial de liste où les éléments sont insérés à une extrémité, appelé arrière (arrière), mais sont éloignés l'un de l'autre, devant (devant). Les files d'attente sont également appelées « listes FIFO » (FIFO signifie premier entré, premier sorti). Les opérateurs effectués sur les files d'attente sont similaires aux opérateurs de pile. La différence significative entre eux est que l'insertion de nouveaux éléments s'effectue dans fin de liste , et non au début, comme dans les piles.

Opérateurs d'ATD "Queue":

1. MAKENULL(Q) efface la file d'attente Q , le rendant vide.

2. DEVANT(Q) - une fonction qui renvoie le premier élément de la file d'attente Q. Vous pouvez implémenter cette fonction en utilisant des opérateurs de liste comme RETRIEVE(FIRST(Q), Q ).

3. MISE EN QUEUE(un, Q) insère un élément Xà la fin de la file d'attente Q.

À l'aide d'opérateurs de liste, cette instruction peut être exécutée comme suit : INSERT(x, END(Q), Q ).

4. DEQUEUE(Q) supprime le premier élément de la file d'attente Q . Nous pouvons également l'implémenter en utilisant des opérateurs de liste comme DELETE(FIRST(Q), Q).

5. VIDE(Q) renvoie vrai si et seulement si Q est une file d'attente vide.

cyclique tableau:

Désignations :

Q- file d'attente,

Q. devant– pointeur vers le début de la file d'attente,

Q. arrière- pointeur vers la fin de la file d'attente.

Représenter une file d'attente en utilisant liste chaînée unique :

Exercices :

Implémentez le QUEUE ADT pour tout type de données et ses opérateurs MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY.

§ la file d'attente est spécifiée sous forme de tableau cyclique,

§ La file d'attente est spécifiée comme une liste doublement chaînée.

Type de données abstrait "Arbre".

Arbre est une collection d'éléments appelés nœuds (dont l'un est défini comme racine ), et les relations (« parent ») qui forment une structure hiérarchique de nœuds. Les nœuds, comme les éléments de liste, peuvent être des éléments de n'importe quel type. Formellement, un arbre peut être défini de manière récursive comme suit.

1. Un nœud est un arbre. Ce même nœud est également la racine de cet arbre.

2. Laissez p- c'est un nœud, un T1 , T2, ...,Merci- des arbres avec des racines n1 . n2 , ..., nk respectivement. Vous pouvez construire un nouvel arbre en faisant n parent des nœuds n1 . n2 , ..., nk. Dans cet arbre n sera la racine, un T1 , T2, ...,Merci - sous-arbres cette racine. Nœuds n1 . n2 , ..., nk sont appelés fils nœud p.

Cette définition inclut souvent le concept arbre zéro , c'est-à-dire un « arbre » sans nœuds, un tel arbre est désigné par le mot nul .

Exemple : O Le chapitre d'un livre peut être schématiquement représenté par un arbre. La relation parent-fils est représentée par une ligne. Les arbres sont généralement dessinés de haut en bas, les parents étant au-dessus des « enfants ».

DIV_ADBLOCK135">

Hauteur du nœud d'un arbre est la longueur du chemin le plus long de ce nœud à n'importe quelle feuille. Dans l'exemple, la hauteur du nœud Chapitre 1égal à 1, nœud Chapitre 2 - 2, et les nœuds Ch. Z-0. Hauteur de l'arbre coïncide avec la hauteur de la racine. Profondeur du nœud est défini comme la longueur du chemin (c'est le seul) de la racine à ce nœud.

Les enfants d'un nœud sont généralement classés de gauche à droite. Par conséquent, les deux arbres de la figure sont différents, puisque l’ordre des enfants d’un nœud UN différent. Si l'ordre des fils est ignoré, alors un tel arbre est appelé désordonné , sinon l'arbre s'appelle ordonné .

Opérateurs de l'ATD "Arbre" :

1. MÈRE(n, T). Cette fonction renvoie le parent du nœud n dans l'arbre T. Si n est une racine qui n'a pas de parent, alors dans ce cas elle renvoie nul. Ici nul indique qu'il y a eu une sortie en dehors de l'arbre.

2. LE PLUS À GAUCHE__ ENFANT(n , T). Cette fonction renvoie l'enfant le plus à gauche du nœud n dans l'arbre T. Si n est une feuille (et n'a donc pas de fils), puis renvoie nul.

3. DROITE_ FRÈRE ET SŒUR(n , T). Cette fonction renvoie le frère droit du nœud n dans l'arbre T ou le sens nul.s'il n'existe pas. C'est à cela que sert le parent r nœud n et tous les fils du nœud p, puis parmi ces fils se trouve le nœud situé immédiatement à droite de. nœud p.

4. ÉTIQUETTE(n , T ). Renvoie l'étiquette du nœud n. arbre T. Cette fonction nécessite que les nœuds de l'arborescence aient des étiquettes définies.

5. CRÉER(v , T 1 , T 2 , ..., Ti ,) est une famille de fonctions qui pour chaque i = 0, 1, 2,... créent une nouvelle racine r avec étiquette v et puis pour cette racine crée des fils, qui deviennent les racines des sous-arbres T1 , T2, ....Ti;. Ces fonctions renvoient un arbre enraciné r. Notez que si i = 0, alors un nœud est renvoyé r, qui est à la fois une racine et une feuille.

6. RACINE(T ) renvoie le nœud qui est la racine de l'arbre T, Si T- arbre vide, puis revient nul.

7. MAKENULL(T ). Cet opérateur crée un arbre T un arbre vide.

Représenter un arbre à l'aide d'un tableau de parents :

Représenter un arbre à l'aide de listes chaînées :

Représentation d'un arbre au moyen de fils de gauche et de frères de droite.

Désignations sur la figure :

espace de nœuds – tableau de nœuds d'arbre,

étiquette – étiquette de nœud, en-tête – index du fils de gauche dans la liste des fils,

cellulesespace – un tableau de listes d'enfants de nœuds,

nœud – pointeur vers un nœud du tableauespace de nœuds , suivant – index du bon fils dans la liste des fils.

Exercices :

1. Étant donné un arbre :

DIV_ADBLOCK137">

§ l'arbre est spécifié comme un tableau d'enregistrements de nœuds contenant l'index du fils le plus à gauche, l'index du frère droit et une étiquette,

§ Un arbre binaire connecté est défini à l'aide de pointeurs vers les fils gauche et droit.

4. Écrivez des fonctions pour parcourir un arbre binaire dans un ordre avant, arrière et symétrique.

Programme de travail section 2.1.3

Type de données abstrait "Set".

Beaucoup généralement représenté comme une séquence de ses éléments entourés d'accolades, par exemple (1, 4) désigne un ensemble composé de deux éléments - les nombres 1 et 4. L'ordre dans lequel les éléments de l'ensemble sont écrits n'est pas significatif, vous peut écrire (4, 1) de la même manière que (1, 4), en écrivant le même ensemble. Un ensemble n'est pas une liste (du moins basée sur l'ordre arbitraire dans lequel les éléments sont écrits). L'ensemble n'a aucun élément répétitif ((1, 4, 1) n'est pas un ensemble).

Le concept fondamental de la théorie des ensembles est le concept de relation appartenant à l'ensemble , désigné par le symbole. Donc l'entrée X X n'appartient pas à l'ensemble UN", c'est-à-dire X n'est pas un élément de l'ensemble UN. Il existe un ensemble spécial, désigné par le symbole, appelé vide, beaucoup , et qui n'a aucun élément. Définir DIV_ADBLOCK138">

On dit qu'il y en a beaucoup UN contenu en abondance DANS(ou s'allume dans la multitude DANS), est écrit UN DANS ou DANS UN, si un élément de l'ensemble UN est également un élément de l'ensemble DANS. Au cas où UN DANS ils disent aussi qu'il y en a beaucoup UN est un sous-ensemble de l'ensemble DANS.

Par exemple, (1, 2) https://pandia.ru/text/78/308/images/image019_36.gif" width="15" height="15 src="> DANS et A B, alors l'ensemble A est appelé propre, vrai ou sous-ensemble strict ensembles DANS.

Les principales opérations effectuées sur les ensembles sont les opérations d'union, d'intersection et de différence. Association ensembles UN Et DANS(noté UN DANS) est un ensemble constitué d'éléments appartenant à au moins un des ensembles UN Et DANS.

En traversant ensembles UN Et DANS(noté UN DANS) est un ensemble composé uniquement des éléments qui appartiennent à l'ensemble UN, et bien d'autres DANS. Par différence ensembles UN Et DANS(noté UN\ B) est un ensemble composé uniquement des éléments de l'ensemble UN, qui n'appartiennent pas à l'ensemble DANS.

Par exemple, si A = (a, b, c) et B = (b, a), alors A B = (a, b, c, d), A B = ( b ) et A \ B = (a, c ) .

Opérateurs d’ATD « Multiple » :

1. UNION(UN, B, C) UN Et DANS AVEC,égal UN DANS.

2. INTERSECTION(UN, B, C) a comme arguments "d'entrée" un ensemble UN Et DANS, et par conséquent - l'ensemble "sortie" AVEC,égal UN DANS..

3. DIFFÉRENCE(UN, B, C) a comme arguments "d'entrée" un ensemble UN Et DANS, et par conséquent - l'ensemble "sortie" AVEC,égal A\B.

4. FUSIONNER( UN , B, C) l'opérateur exécute fusionnement (fusionner), ou union d'ensembles disjoints . Cet opérateur n'est pas différent de l'opérateur. UNION, mais ici on suppose que l'opérande définit ne pas se croiser (c'est-à-dire qu'ils n'ont pas d'éléments communs). L'opérateur affecte à un ensemble AVEC signification UN DANS, mais le résultat ne sera pas déterminé si A Dans , c'est à dire dans le cas où les ensembles UN Et DANS ont des éléments communs.

5. membre(X, A ) a de nombreux arguments UN et objet X du même type que les éléments de l'ensemble UN, et renvoie une valeur booléenne vrai(vrai), si X a", "b", "c"))= "UN". L'opérateur est défini de la même manière MAXIMUM.

11.ÉGAL(UN , DANS ) renvoie la valeur vrai si et seulement si les ensembles UN Et DANS sont constitués des mêmes éléments.

12. TROUVER(x ) fonctionne dans un environnement où il existe un ensemble d’ensembles disjoints. Il renvoie le nom (unique) de l'ensemble qui contient l'élément X.

Représentation définie :

Un ensemble peut être spécifié à l'aide d'un tableau ou d'une liste chaînée.

Exercices :

1. Deux ensembles A = (1, 2, 3) et B = (3, 4, 5) sont donnés. Quel sera le résultat de l’exécution des instructions suivantes ?

UNION(A.V.C),

INTERSECTION(A, B, C),

DIFFÉRENCE (A. V. C),

MEMBRE(l. A),

INSÉRER(1,A),

SUPPRIMER(1, A),

2. Implémentez l'ADT « Set » pour tout type de données et ses opérateurs MAKENULL, UNION, INTERSECTION, MEMBER, MIN.

· l'ensemble est défini à l'aide d'un tableau de longueur fixe et d'un pointeur vers la dernière position occupée dans le tableau,

· l'ensemble est défini à l'aide d'une liste chaînée non triée,

· l'ensemble est défini à l'aide d'une liste chaînée triée,

Programme de travail section 2.1.3

Types spéciaux d'ensembles

Type de données abstrait « Arbre de recherche binaire »

Arbre de recherche binaire - une structure de données pour représenter des ensembles dont les éléments sont ordonnés par une relation d'ordre linéaire. Les opérateurs d'ensemble peuvent être implémentés dans des arbres de recherche binaires INSÉRER, SUPPRIMER, MEMBRE Et MINIMUM, et leur temps d'exécution est en moyenne de l'ordre de O (log n) pour les ensembles constitués de néléments.

Une caractéristique d'un arbre de recherche binaire est que ses nœuds sont étiquetés avec des éléments d'ensemble (les nœuds de l'arbre contiennent des éléments d'ensemble). De plus, tous les éléments stockés dans les nœuds du sous-arbre gauche de n'importe quel nœud X, inférieur à l'élément contenu dans le nœud X, et tous les éléments stockés dans les nœuds du sous-arbre droit du nœud X, supérieur à l'élément contenu dans le nœud X.

Exemples d'arbre binaire :

https://pandia.ru/text/78/308/images/image023_7.jpg" width="277" height="122 src=">

La représentation arborescente AVL n'est pas différente de la représentation arborescente binaire.

Une autre variante de l'arbre de recherche équilibré est 2-3 arbres. La structure d'un arbre 2-3 est différente de la structure d'un arbre de recherche binaire. Un arbre 2-3 se caractérise par le fait que tous les nœuds ont 2 ou 3 enfants, tous les chemins de la racine à une feuille ont la même longueur. , et tous les éléments de l'ensemble sont contenus dans les feuilles. Les nœuds 2-3 de l'arbre sont divisés en internes et terminaux (feuilles). Les nœuds internes sont utilisés uniquement pour les recherches de routage dans l'arborescence. Chaque nœud interne contient les clés des plus petits éléments des deuxième et troisième fils (s'il y a un troisième fils) et des pointeurs vers les nœuds des fils.

Représentation de l'arbre de recherche binaire lié :

Représentation d'un arbre 2-3 connecté équilibré :

Exercices :

1. Dessinez tous les arbres de recherche binaires possibles pour les quatre éléments 1, 2, 3 et 4.

2. Insérez les entiers 7, 2, 9, 0, 5, 6, 8, 1 dans l'arbre de recherche binaire vide.

3. Montrez le résultat de la suppression du chiffre 7 puis du chiffre 2 de l'arbre obtenu lors de l'exercice précédent.

4. Dessinez un arbre 2-3 résultant de l'insertion des éléments 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 dans l'ensemble vide (représenté par un arbre 2-3).

5. Montrez le résultat de la suppression de l'élément 3 de l'arbre 2-3 obtenu dans l'exercice précédent.

3. Implémentez l'ADT « Search Tree » pour tout type de données et ses opérateurs INSERT, DELETE, MEMBER et MIN.

· l'arbre est spécifié comme un arbre binaire connecté

· l'arbre est spécifié comme 2-3 arbres

Programme de travail section 2.1.3

Type de données abstrait "Dictionnaire".

Dictionnaire – un ensemble destiné à stocker des objets « courants » avec insertion ou suppression périodique de certains d’entre eux. De temps en temps, il est également nécessaire de savoir si un élément particulier est présent dans un ensemble donné. Le dictionnaire est implémenté à l'aide du Dictionary ADT avec des opérateurs INSÉRERSUPPRIMER Et MEMBRE. L'ensemble des opérateurs de dictionnaire comprend également l'opérateur MAKENULL pour initialiser les structures de données ADT.

Un dictionnaire peut être représenté à l'aide d'une table de hachage. Le tableau est construit sur la base de l'idée suivante : un ensemble potentiel d'éléments (éventuellement infini) est divisé en un nombre fini de classes. Pour DANS classes numérotées de 0 à B-1, en cours de construction fonction de hachage h tel que pour tout élément X fonction de l'ensemble d'origine h(x) prend une valeur entière de l'intervalle 0, ..., DANS - 1, qui correspond à la classe à laquelle appartient l'élément X.Élément X souvent appelé clé, h( x) - hacher-valeur x, et "cours" - segments . Comment résoudre les collisions de hachage (deux éléments d'un ensemble ont la même valeur h(x)) un hachage ouvert et fermé est utilisé.

table de hachage ouverte

Un tableau appelé table de segments et indexé numéros de segments 0, 1,...,B - 1 , contient des en-têtes pour DANS listes chaînées. Élément je La liste est un élément de l'ensemble original pour lequel h(.x :) =je.

Représenter un dictionnaire en utilisant table de hachage privée

La table de segments stocke directement les éléments du dictionnaire. Par conséquent, chaque segment ne peut stocker qu’un seul élément de dictionnaire. Avec le hachage fermé, la technique est utilisée re-hachage . Lorsque vous essayez de placer un élément x dans le segment avec le numéro h ( x ) , qui est déjà occupé par un autre élément, une séquence de numéros de segment est sélectionnée h 1 ( x ) ,h 2 ( x ) , … , où vous pouvez placer l'élément. L'occupation de chacun de ces segments est vérifiée séquentiellement jusqu'à ce qu'un segment libre soit trouvé. Il contient un élément x . Diverses méthodes de résolution de collision sont utilisées pour définir les numéros de segment lors du rehachage. Par exemple, méthode de hachage linéaire, méthode du carré médian, méthode de hachage aléatoire

Exercices :

1. Supposons que la fonction de hachage h(i) = i % 7 soit utilisée pour hacher des entiers dans une table de hachage à 7 segments.

· donner la table de hachage résultante si les cubes exacts 1, 8, 27,64,125, 216,343 y sont insérés ;

· répétez le point précédent pour une table de hachage fermée avec une technique de résolution de collision linéaire.

2. Supposons qu'il existe une table de hachage fermée avec 5 segments, une fonction de hachage h(i) = i % 5 et une technique de résolution de collision linéaire. Afficher le résultat de l'insertion de la séquence de nombres 23, 48, 35, 4, 10 dans une table de hachage initialement vide.

3. Implémentez un dictionnaire ADT pour les chaînes de texte et ses instructions INSERT , SUPPRIMER, MEMBRE et MAKENULL

· le dictionnaire est spécifié à l'aide d'une table de hachage ouverte,

· le dictionnaire est spécifié à l'aide d'une table de hachage fermée avec une technique de résolution de collision linéaire,

Programme de travail section 2.1.3

Type de données abstrait "Affichage".

Afficher - il s'agit d'un ensemble sur les éléments duquel est définie une fonction d'affichage d'éléments de même type ( domaine de définition ) à des éléments d'un autre type ( plage de valeurs ) d'un autre type. Afficher M. correspond à un élément d tapez domaintype à partir de la portée de l'élément r tapez rangetype à partir de la plage de valeurs : M.(d) = r.Affichage vide ne contient aucun élément

Opérateurs d'ADT "Affichage" :

1. MAKENULL(M. ). Fait un affichage M. vide.

2. ATTRIBUER(M. d,r). Fait M.(d) égal r peu importe comment M.(d) a été préalablement définie.

3. CALCULER( M, d, r). Renvoie vrai et attribue à la variable r la valeur M.(d), si ce dernier est défini, et renvoie false sinon.

Vue d'affichage : le mappage peut être implémenté efficacement à l'aide de tables de hachage. Ici x spécifie une valeur de la zone de définition d'affichage et l'élément de table avec un numéro h ( x ) – élément de la plage de valeurs.

Programme de travail section 2.1.3

Type de données abstrait « File d'attente prioritaire »

File d'attente prioritaire - il s'agit d'un ensemble pour lequel une fonction prioritaire est spécifiée, c'est-à-dire pour chaque élément x défini, vous pouvez calculer la fonction p( x )- priorité de l'élément x , qui prend généralement des valeurs dans l'ensemble des nombres réels ou, plus généralement, dans un ensemble ordonné linéairement.

ADT « File d’attente prioritaire » basé sur l’ADT « Set » avec les opérateurs INSÉRER Et SUPPRIMER, ainsi qu'avec l'opérateur MAKENULL pour initialiser la structure des données. Opérateur INSÉRER pour une file d'attente prioritaire s'entend dans le sens habituel, alors que SUPPRIMER est une fonction qui renvoie l'élément avec la priorité la plus basse et, comme effet secondaire, le supprime de l'ensemble.

Représenter une file d'attente en utilisant liste doublement chaînée ordonnée.

Représenter une file d'attente en utilisant arbre connecté partiellement ordonné :

L'idée principale de cette implémentation est d'organiser les éléments de la file d'attente sous la forme d'un arbre binaire. A un niveau inférieur, où certaines feuilles peuvent manquer, toutes les feuilles manquantes peuvent être situées juste à droite des feuilles du niveau inférieur présentes. Plus important encore, l'arbre partiellement commandé . Cela signifie que la priorité du nœud v pas supérieur à la priorité de tout enfant du nœud v, où la priorité du nœud est la valeur de priorité de l'élément stocké dans ce nœud. La figure montre que les petites valeurs de priorité ne peuvent pas apparaître à un niveau supérieur là où il existe de grandes valeurs de priorité.

La fonction DELETEMIN renvoie l'élément de priorité minimale, qui doit être la racine de l'arborescence. Pour éviter de détruire l'arborescence et conserver un ordre partiel des valeurs de priorité sur l'arborescence après suppression de la racine, les actions suivantes sont effectuées : le nœud le plus à droite est situé au niveau le plus bas et est temporairement placé à la racine de l'arborescence. Cet élément descend ensuite les branches de l'arbre (vers les niveaux inférieurs), changeant de place en cours de route, ses fils ayant une priorité inférieure, jusqu'à ce que cet élément devienne une feuille ou se trouve dans une position où ses fils n'ont au moins pas moins de priorité.

Représenter une file d'attente à l'aide d'un tableau contenant les nœuds d'un arbre partiellement ordonné :

Dans le tableau UN d'abord n les postes correspondent n nœuds de l'arbre. Élément UN contient la racine de l'arbre. Fils gauche d'un nœud d'arbre UN[ je], s'il existe, il est dans la cellule UN, et le bon fils, s'il existe, est dans la cellule UN. Et vice versa, si le fils est en cellule UN[ je], alors son parent est dans la cellule UN[ je%2] . Les nœuds de l'arbre remplissent les cellules UN, UN, … UN[ n] séquentiellement niveau par niveau, en commençant par la racine et à l'intérieur du niveau - de gauche à droite. L'arbre ci-dessus sera représenté dans le tableau par la séquence suivante de ses nœuds : 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

Exercices :

1. Dessinez un arbre partiellement ordonné résultant de l'insertion des entiers 5, 6, 4, 9, 3, 1 et 7 dans un arbre vide. Quel serait le résultat de l'application séquentielle de trois instructions DELETEMIN à cet arbre ?

2. Implémentez l'ADT de file d'attente prioritaire pour tout type de données et ses opérateurs INSERT, DELETEMIN et MAKENULL

§ un arbre partiellement ordonné est implémenté à l'aide de pointeurs,

§ Un arbre partiellement ordonné est implémenté à l'aide d'un tableau.

Programme de travail section 2.1.3

Type de données abstrait "Union d'ensembles".

Un ADT est une union d’objets, dont chacun constitue un ensemble. Les principales actions effectuées sur un tel ensemble consistent à combiner des ensembles dans un certain ordre, ainsi qu'à vérifier si un certain objet appartient à un ensemble spécifique. Ces problèmes sont résolus à l'aide d'opérateurs FUSIONNER(Vidange) et TROUVER(Trouver). FUSIONNER( UN, B, C) fait beaucoup AVECégal à l'union des ensembles UN Et DANS, si ces ensembles ne se coupent pas (c'est-à-dire qu'ils n'ont pas d'éléments communs) ; cet opérateur n'est pas défini si les ensembles UN Et DANS couper. Fonction TROUVER( x) renvoie l'ensemble auquel appartient l'élément X ; au cas où X appartient à plusieurs ensembles ou n'appartient à aucun, la valeur de cette fonction n'est pas définie.

Opérateurs de l'ADT « Union des ensembles » :

1. FUSIONNER(UN , DANS) combine des composants UN Et . DANS, le résultat est affecté soit à A, soit à DANS.

2. TROUVER(x ) - une fonction qui renvoie le nom du composant auquel il appartient X.

3. INITIAL(UN , X ) crée un composant nommé A contenant uniquement l'élément X.

Représentation de la combinaison d'ensembles à l'aide de tableaux :

Le nom de l'ensemble correspond à la valeur de l'index du tableau en-têtes ( nom 0 )

Désignations :

en-têtes – tableau d'en-têtes d'ensemble :

§ Avec compte – nombre d'éléments dans l'ensemble,

§ premier élément – indice du tableaunomsavec le premier élément de l'ensemble,

noms – tableau de listes d'éléments d'ensemble :

nom de l'ensemble - le nom de l'ensemble auquel appartient l'élément, élément suivant – index de l'élément suivant dans la liste d'un ensemble donné (la valeur d'index 0 est utilisée comme fin de liste).

Programme de travail section 2.1.3

Type de données abstrait “ Graphique orienté"

Définitions de base :

Graphique orienté (digraphe ) G = (V, E) se compose de nombreux sommets V et des ensembles d'arcs E. Les sommets sont également appelés nœuds , et des arcs - bords orientés . Un arc peut être représenté comme une paire ordonnée de sommets ( toi, w), où est le sommet Et appelé le début , un w - la fin arcs.

On dit aussi que l'arc Et -> w mène de haut en haut w, et le dessus w adjacent avec dessus v.

Exemple 1 digramme :

Les sommets d'un digraphe peuvent être utilisés pour représenter des objets et les arcs peuvent être utilisés pour représenter des relations entre des objets.

Par dans un digraphe, la séquence de sommets est appelée v1 , v2 , … , vn , , pour quels arcs existent v1 -> v2 , v2 , -> v3, , ..., vn-1 , -> vn. Ce chemin commence au sommet v1 et, en passant par les sommets v2 , v3 , ..., vn-1 se termine en haut vn. Longueur du chemin - le nombre d'arcs qui composent le chemin, dans ce cas la longueur du chemin est p- 1 . Comme cas particulier de chemin, considérons un sommet v comme un chemin de longueur 0 à partir du haut vÀ ce même sommet v. Sur la figure, la séquence de sommets 1, 2, 4 forme un chemin de longueur 2 du sommet 1 au sommet 4.

Le chemin s'appelle simple , si tous les sommets, à l'exception possible du premier et du dernier, sont différents. Faire du vélo - est un chemin simple de longueur au moins 1 qui commence et se termine au même sommet. Sur la figure, les sommets 3, 2, 4, 3 forment un cycle de longueur 3.

Dans de nombreuses applications, il est pratique d’attacher certaines informations aux sommets et aux arcs d’un digraphe. À ces fins, il est utilisé digraphe étiqueté , c'est-à-dire un digraphe dans lequel chaque arc et/ou chaque sommet a des étiquettes correspondantes. L'étiquette peut être un nom, un poids ou une valeur (arc), ou une valeur de données d'un type spécifié.

Exemple 2 d'un digraphe étiqueté :

DIV_ADBLOCK149">

3. Algorithme de fermeture transitive (algorithme Warshall) :

Pour le compte G = (V, E) l'algorithme calcule la matrice de transitivité T, dont chaque élément T[je, j] = 1 seulement quand il y a un chemin depuis le sommet je vers le haut j Et T[ je, j] = 0 sinon.

4. Algorithme pour trouver le centre d'un digraphe :

Laisser Et - sommet arbitraire d'un digraphe G = (V,E). Excentricité (enlèvement maximum) pics Et défini comme

max(longueur minimale du chemin à partir du haut w vers le haut v }

w V

Centre du digraphe G appelé sommet avec une excentricité minimale. En d’autres termes, le centre du digraphe est le sommet pour lequel la distance maximale (longueur du chemin) par rapport aux autres sommets est minimale.

Exemple: Le centre du digraphe est le sommet d

		Excentrique-t

5. Algorithme de parcours d'un digraphe en profondeur (recherche en profondeur d'abord) :

De nombreux problèmes impliquant des graphes orientés nécessitent une méthode efficace pour parcourir systématiquement les sommets et les arcs des digraphes. Cette méthode est ce qu'on appelle première recherche en profondeur - généralisation de la méthode de traversée d'arbre vers l'avant. La recherche en profondeur commence par la sélection d'un sommet de départ v graphique G, ce sommet est marqué d'une étiquette visité (visité). Puis pour chaque sommet adjacent au sommet v et qui n'a jamais été visité auparavant, une recherche en profondeur d'abord est appliquée de manière récursive. Quand tous les sommets accessibles depuis le sommet v, sera "honoré" d'une visite, la recherche se termine. Si certains sommets ne sont pas visités, alors l'un d'entre eux est sélectionné et la recherche est répétée. Ce processus se poursuit jusqu'à ce que tous les sommets du digraphe soient couverts par le parcours. G.

6. Algorithme de construction d'un arbre couvrant profond d'un graphe :

Lors du parcours d'un graphique à l'aide d'une recherche en profondeur d'abord, seuls certains arcs mènent à des sommets non visités. De tels arcs menant à de nouveaux sommets sont appelés arcs d'arbre et forment le graphe forêt couvrante construite à l'aide de la méthode de recherche en profondeur d'abord – forêt profonde . Lors de la construction d'une forêt, il existe 3 types d'arcs : inversé, droit et transversal. Arcs inversés - de tels arcs qui, dans la forêt étendue, vont des descendants aux ancêtres. Arcs droits sont appelés arcs qui vont des ancêtres aux vrais descendants, mais qui ne sont pas des arcs d'arbre.

Les arcs reliant les sommets qui ne sont ni ancêtres ni descendants les uns des autres sont appelés arcs transversaux . Si, lors de la construction d'un arbre couvrant, les fils d'un sommet sont situés de gauche à droite dans l'ordre dans lequel ils sont visités, et si de nouveaux arbres sont ajoutés à la forêt également de gauche à droite, alors tous les arcs transversaux vont de droite à gauche. .

Par exemple, les arcs D->C et G->D– transversal, arc C-> UN– inverse, il n’y a pas d’arcs directs.

Lors de la traversée d’un arbre en profondeur, il est souvent pratique de numéroter les sommets dans l’ordre dans lequel ils sont visités. De tels nombres sont appelés profonds.

Représentation digraphique :

§ Représentation d'un digraphe à l'aide d'une matrice d'adjacence :

Matrice de contiguïté pour un digraphe G- c'est une matrice UN taille n n avec des valeurs booléennes, où UN[ je, j] = vrai si et seulement s'il y a un arc à partir du sommet je au sommet j. Souvent, dans les matrices de contiguïté, la valeur vrai est remplacé par 1, et la valeur FAUX- à 0.

Une généralisation de la représentation d'un digraphe utilisant une matrice d'adjacence peut être considérée comme la représentation d'un digraphe étiqueté utilisant également une matrice d'adjacence, mais dont l'élément UN[ je, j] égal à l'étiquette de l'arc je ->j. Si les arcs proviennent du sommet je vers le haut j n'existe pas, alors la valeur de A[ je, j] ne peut pas être la valeur d'une étiquette valide, mais peut être traité comme une cellule "vide".

Matrice de contiguïté pour un digraphe étiqueté (exemple 2) :

§ Représentation d'un digraphe à l'aide de listes de contiguïté :

Liste de contiguïté pour un sommet je est une liste de tous les sommets adjacents à un sommet je, et ordonné d'une certaine manière. Digraphe G peut être représenté à l'aide d'un tableau TÊTE(Titre) dont l'élément TÊTE[je] est un pointeur vers la liste de contiguïté d'un sommet je.

Opérateurs d’ATD « Orgraf » :

Les opérateurs les plus courants exécutés sur les graphes orientés incluent les opérateurs permettant de lire les étiquettes de sommets et d'arcs, d'insérer et de supprimer des sommets et des arcs et de se déplacer dans des séquences d'arcs.

Pour afficher un ensemble de sommets adjacents, les trois opérateurs suivants sont requis.

1. PREMIER( v) renvoie l'index du premier sommet adjacent au sommet v. Si le haut v n’a pas de sommets adjacents, alors le sommet « zéro » est renvoyé néant.

2.SUIVANT( v, je) renvoie l'index du sommet adjacent au sommet v,à côté de l'index je. Si je- c'est l'indice du dernier sommet adjacent au sommet v, puis ça revient néant.

3. SOMMET( v,je) renvoie le sommet avec index je de l'ensemble des sommets adjacents à v.

Exercices :

Étant donné un graphe orienté (digraphe) :

https://pandia.ru/text/78/308/images/image043_12.gif" width="125" height="100 src=">

Exemple de graphique déconnecté :

Faire du vélo (simple) est un chemin (simple) d'une longueur d'au moins 3 depuis n'importe quel sommet jusqu'à lui-même. Le graphique s'appelle cyclique , s'il a au moins un cycle. Un graphe acyclique connexe, qui est un « arbre sans racine », est appelé arbre gratuit . La deuxième figure ci-dessus montre un graphique composé de deux composants connectés, dont chacun est un arbre libre. Un arbre libre peut être transformé en un arbre « normal » si un sommet est désigné comme racine et si toutes les arêtes sont orientées dans la direction de cette racine.

Les arbres libres ont deux propriétés importantes :

1. Chaque arbre libre avec le nombre de sommets n, n > 1 , a exactement n - 1 côtes

2. Si vous ajoutez une nouvelle arête à un arbre libre, vous obtiendrez certainement un cycle.

Laisser G = (V, E) - graphe connexe dans lequel chaque arête ( r, w) marqué d'un numéro Avec(v, w), qui s'appelle coût des côtes . arbre couvrant graphique G un arbre libre contenant tous les sommets s'appelle V colonne G. Prix L'arbre couvrant est calculé comme la somme des coûts de toutes les arêtes incluses dans cet arbre.

Algorithmes de base pour le traitement des graphes non orientés :

1. Construction d'un arbre couvrant à coût minimum (algorithme de Prim) :

De nombreux sommets sont en construction U, à partir duquel l'arbre couvrant « grandit ». Laisser V = (1, 2, ...,n}. D'abord U = (1). A chaque étape de l'algorithme, l'arête du moindre coût est trouvée ( toi,v) tel que toi U Et v V\U, puis le haut v transféré depuis l'ensemble V\U dans la multitude U. Ce processus se poursuit jusqu'à ce que de nombreux U ne sera pas égal à l'ensemble V.

La séquence de construction d’un arbre couvrant est donnée ci-dessous.

https://pandia.ru/text/78/308/images/image048_12.gif" width="501" height="384 src=">

3. Parcours de graphiques non orientés à l'aide d'une recherche en profondeur :

La recherche en profondeur est utilisée pour parcourir systématiquement tous les sommets d'un graphique. L'algorithme de recherche en profondeur d'abord est similaire à l'algorithme de parcours des sommets d'un digraphe. Ce dernier est également utilisé pour les graphes non orientés, puisqu'une arête non orientée (v, w) peut être représenté comme une paire d'arcs orientés v -> w Et w -> v.

Le parcours en profondeur d'abord peut être utilisé pour construire un arbre couvrant.

Le graphique et l'arbre couvrant obtenus en parcourant ses sommets à l'aide de la méthode de recherche en profondeur d'abord sont donnés ci-dessous :

4. Parcours de graphiques non orientés à l'aide d'une recherche en largeur d'abord

Une autre méthode pour parcourir systématiquement les sommets d'un graphe est appelée première recherche en largeur . Il doit son nom au fait que lorsqu'on atteint un sommet en se promenant v alors tous les sommets adjacents au sommet sont considérés v, c'est-à-dire que les sommets sont vus « en largeur d'abord ». Cette méthode peut également être appliquée aux graphes orientés.

Tout comme lors de l'application d'une recherche en profondeur d'abord, en utilisant la méthode de recherche en largeur d'abord, une forêt couvrante est créée lors du parcours du graphique. Si après avoir atteint le sommet X lors de l'examen de la côte (x, y) sommet à n'a pas été visité auparavant, alors cette lisière est considérée comme une lisière de l'arbre. Si le haut à a déjà été visité auparavant, alors le bord (x, y) sera une arête transversale, car elle relie les sommets qui ne sont pas connectés par héritage les uns aux autres.

L'arbre couvrant obtenu à l'aide de la méthode de recherche en largeur d'abord est présenté ci-dessous.

Représentation d'un graphe non orienté à l'aide d'une matrice de contiguïté :

Pour représenter des graphiques non orientés, vous pouvez utiliser les mêmes méthodes que pour représenter des graphiques orientés, si l'arête non orientée entre les sommets v Et w traité comme deux arcs orientés à partir du sommet v à haut w et du haut w vers le haut v.

https://pandia.ru/text/78/308/images/image051_12.gif" width="159" height="106">

Représentation d'un graphe non orienté à l'aide de listes de contiguïté :

https://pandia.ru/text/78/308/images/image053_12.gif" width="339" height="115 src=">

1. Construire :

arbre couvrant à coût minimum utilisant l'algorithme de Prim ;

arbre couvrant à coût minimum utilisant l'algorithme de Kruskal ;

arbre couvrant utilisant une recherche en profondeur d'abord, à partir des sommets a et d ;

arbre couvrant en utilisant la recherche en largeur d'abord, en commençant par les sommets a et d.

2. Implémentez les algorithmes Prim et Kruskal.

3. Implémenter la construction d'un arbre couvrant en utilisant la méthode de recherche en profondeur d'abord

§ pour un graphe non orienté représenté à l'aide d'une matrice de contiguïté,

§ pour un graphe non orienté représenté à l'aide de listes de contiguïté.

4. Implémenter la construction d'un arbre couvrant en utilisant la méthode de recherche en largeur d'abord

§ pour un graphe non orienté représenté à l'aide d'une matrice de contiguïté,

§ pour un graphe non orienté représenté à l'aide de listes de contiguïté.

Résumé est généralement appelé un type de données qui n'est pas explicitement présent dans un langage de programmation ; en ce sens, il s'agit d'un concept relatif : un type de données absent dans un langage de programmation peut être présent dans un autre.

Type de données abstrait (ATD) est défini quelle que soit la méthode de sa mise en œuvre :

ensemble de valeurs possibles de ce type,

et un ensemble d'opérations avec des valeurs de ce type.

L'utilisation d'ADT peut être limitée à la phase de développement logiciel, mais pour son utilisation explicite dans un programme, il est nécessaire que son implémentation soit basée sur des types de données existants (et préalablement implémentés) dans le langage de programmation :

une manière de représenter des valeurs de ce type,

et mise en œuvre d'opérations avec des valeurs de ce type.

ADT n'est pas prédéfini dans un langage de programmation, et de plus, les opérations de construction de tels types, prédéfinies dans le langage, déplacent vers le développeur-programmeur la question de savoir comment représenter des valeurs de ce type et mettre en œuvre des opérations avec des valeurs de ce type. Par conséquent, pour de tels types de données, la question est de choisir des définitions et des méthodes pour mettre en œuvre des opérations de la forme constructeur (valeurs et magasins de données) de ce type, sélecteur Et modificateur les composants (valeurs et magasins de données) de ce type appartiennent au développeur programmeur.

Dans le concept ADT, les concepts ont un statut particulier interface , ouvert à l'utilisateur, et mise en œuvre , caché de lui. Le rôle particulier de ces concepts dans le concept d'ADT est associé à la position fondamentale sur l'indépendance du concept d'ADT par rapport à la méthode de sa mise en œuvre.

Dans les « langages de programmation pratiques » modernes, une opération de construction de type prédéfinie est généralement utilisée pour construire un ADT. classe , qui donne au développeur-programmeur non seulement les moyens de regrouper les données et les opérations (avec ces données) en un seul tout, mais également les moyens d'encapsulation, d'héritage et de polymorphisme pour contrôler la façon dont ces données sont construites et accessibles. Notez qu'une classe décrit une implémentation possible d'un ADT, le mappage d'une classe à un ADT est exprimé par une fonction d'abstraction, mais la relation inverse n'est généralement pas fonctionnelle il peut y avoir plusieurs implémentations du même ADT ;

Dans la recherche sur les types de données abstraits, le rôle important du concept " paramétrage de type " En effet, par exemple, l'ADT « Stack » ne dépend pas du type d'éléments de la pile, mais il est impossible d'implémenter cet ADT en pointant sur des « éléments d'un type identique ». Dans le langage de programmation Ada, des outils appropriés pour construire des types de données paramétrés ont été initialement inclus, et dans les « langages de programmation pratiques » modernes, ces outils ne sont apparus que depuis l'avènement du développement utilisant la bibliothèque STL. Aujourd'hui, le concept de « programmation généralisée » occupe une place importante dans la programmation pratique en raison de son inclusion dans les « langages de programmation pratiques ». des outils de construction de types de données paramétrés (modèles, modèle , générique) .

Tout ce qui précède signifie que d’un point de vue méthodologique et théorique, une définition plus précise et plus détaillée de la notion de « type de données abstrait » est nécessaire. En théorie, le concept de « type de données abstrait » est généralement défini comme système algébrique multi-trié (multi-base) , dans lequel, en plus de l'ensemble des valeurs possibles (porteuse) et de l'ensemble des opérations sur ces valeurs, les concepts suivants sont mis en évidence :

Tri et signature - ces concepts vous permettent de classer à la fois les éléments multimédias et les opérations avec eux selon leurs types (pour les opérations - selon les types de leurs arguments et de leur valeur de retour).

Les prédicats sont des relations sur des éléments du porteur. Cela vous permet de déterminer la plage de valeurs possibles en imposant des restrictions (exigences) sur les valeurs autorisées, ainsi que de travailler avec des expressions logiques arbitraires dans une interprétation naturelle, sans être obligé de les interpréter comme des fonctions d'appartenance à des ensembles ou comme multi -opérations valorisées.

Sur cette base, il est possible de considérer les types de données abstraits d'un seul point de vue logico-algébrique holistique, y compris des questions sur les constructeurs (de types et de valeurs), les sélecteurs et les modificateurs de propriétés pour les objets de ce type.

Les concepts de « structure de données » et de « type de données abstrait » sont très proches à certains égards. On peut bien sûr supposer que ces concepts ne sont que deux visions d’une même chose. La manière dont un ADT représente les valeurs repose toujours sur une structure de données, plus ou moins complexe, et la mise en œuvre d'opérations sur de telles valeurs dépend naturellement de cette structure de données choisie. En revanche, si nous le voulons vraiment, nous pouvons toujours concevoir la structure de données qui nous intéresse en tant qu'ADT.

Mais nous distinguerons quand même ces deux concepts en tenant compte :

Type de données abstrait - implique un certain niveau d'abstraction afin de fixer un type de données d'application (orienté domaine), quelles que soient les méthodes de sa mise en œuvre, et il est possible d'inclure ce type de données dans une bibliothèque d'application, au moins pour le développement spécifique d'un système logiciel spécifique. Un ADT peut avoir plusieurs implémentations alternatives basées sur différentes structures de données.

Une structure de données est plutôt un schéma d'organisation et de gestion de données, qui nécessite des spécifications appropriées lorsqu'il est utilisé dans des situations spécifiques pour résoudre des problèmes spécifiques.

Les types de données abstraites incluent principalement naturellement les systèmes algébriques mathématiques de base - séquences, ensembles, relations et mappages (relations fonctionnelles, fonctions). Mais en programmation, l'avant-plan n'est pas l'étude des propriétés générales de ces concepts mathématiques, mais la possibilité de les utiliser dans le développement de modèles pour résoudre des problèmes dans le domaine, d'algorithmes pour résoudre ces problèmes et la mise en œuvre efficace des algorithmes développés. Par conséquent, dans la programmation sous forme d'ADT, d'une part, des versions limitées de ces systèmes algébriques de base sont généralement formalisées et, d'autre part, élargies avec des ensembles d'opérations spécialisées qui présentent un intérêt pragmatique du point de vue de l'utilisateur. champ d'application.