S'inscrire au signal RSS Se connecter pour voir ses MP Aller  l'index Aller au portail du forum Faire une recherche. FAQ S'inscrire au forum Connexion

:: [ESC] Cour --> 2ème IAG --->Algorithmique et Structures de D ::

 
Poster un nouveau sujet   Répondre au sujet    Portail Des Etudiants Index du Forum -> Espace des étudiants -> Cour, TD, TP & Mémoire -> Cour ESC
Sujet précédent :: Sujet suivant  
Auteur Message
x
Invité

Hors ligne




MessagePosté le: 15/11/2005 18:00:08    Sujet du message: [ESC] Cour --> 2ème IAG --->Algorithmique et Structures de D Répondre en citant

----------------------------------------------------------------------------------
Notes de Cours

Algorithmique et Structures de Données

Elaborées par Malek GHENIMA

Niveau : 2ème année MIAGE

Université de la Manouba
Ecole Supérieure de Commerce de Tunis

Année Universitaire 2005-2006
-----------------------------------------------------------------------------------
Introduction

Vers les années 70, la programmation des ordinateurs fut reconnue comme une discipline dont la maîtrise était fondamentale et indispensable au succès de bien des projets scientifiques et techniques et qui était susceptible d'être traitée et présentée scientifiquement. Elle passa du stade de l'artisanat à celui de l'enseignement académique. Les contributions essentielles de Dijkstra et Hoare ne sont pas étrangères à cette évolution.
• Dijkstra : "Notes on Structured Programming".
• Hoare : "An Axiomatic Basis for Computer Programming".
Ces deux articles concentrent leur attention principalement sur la structure des algorithmes représentés par les textes des programmes. Cette nouvelle méthodologie de la programmation a clairement montré que l'aspect de structuration, d'organisation des données lui était intimement lié.
Les programmes sont la formulation concrète d'algorithmes abstraits basés sur une représentation et une structure particulière des données. A ce niveau il faut mentionner la contribution importante de Hoare : "Notes on Data Structuring".
Il a montré qu'il est impossible de structurer correctement un ensemble de données si l'on n'a pas la connaissance de l'algorithme qui va s'appliquer sur ces données et que, réciproquement, le choix de l'algorithme peut dépendre fortement de la structure des données. En conclusion, développement de programmes (d'algorithmes) et structuration des données sont intimement liés.
Dans les chapitres qui suivent, il y aura donc des exemples d'algorithmes illustrant la construction et l'utilisation des structures de données décrites. Dans l'espoir de rendre ces exemples plus lisibles, les symboles utilisés sont formés de plusieurs mots accolés dont les initiales sont en majuscule (par exemple SommetDeDepart). De plus, tout ce qui est programme ou extrait de programme utilise une police de caractères à chasse fixe et répond aux conventions d'indentation suivantes :
• pour une instruction composée, le mot réservé begin est placé en fin de ligne et les instructions qui suivent sont indentées de deux caractères, y compris le mot réservé end qui termine l'instruction composée. Par exemple :
• if UneExpressionBooléenne then begin
• { suite d'instructions }
• end
• else begin
• { suite d'instructions }
• end; { if }
• si une instruction simple ne tient pas sur une seule ligne, la deuxième ligne est indentée de deux caractères si elle correspond à une instruction complète, comme :
• if UneExpressionBooléenne then
• { une instruction très longue };
•
• while UneExpressionBooléenne do
• { une instruction très longue };
ou justifiée à droite si c'est le complément de la première ligne :
UneVariableDuProgramme :=
UneTropLongueExpression;
1. Notion de typage
Définition : Le typage est l'association, à un objet (une variable), d'un ensemble de valeurs possibles ainsi que d'un ensemble d'opérations admissibles sur ces valeurs. C'est aussi, pour ce qui concerne les aspects de sécurité, un mécanisme des langages de programmation qui a pour but de vérifier d'une part que les valeurs fournies lors d'une opération sont compatibles avec le(s) type(s) correspondant à l'opération et d'autre part que le résultat d'une opération ne transgresse aucune contrainte liée au type de cette opération.
1.1. Différence de typage selon les langages
Les langages non-typés sont très peu nombreux. Les plus courants sont les langages machine, c'est-à-dire les ensembles de valeurs numériques correspondants aux jeux d'instructions de différentes machines. Il va sans dire que ces langages ne sont quasiment plus jamais utilisés de nos jours, si ce n'est par l'unité centrale de tout ordinateur.
Les langages assembleurs permettent d'associer des mnémoniques aux différentes opérations que le processeur central d'un ordinateur peut effectuer et peuvent être considérés comme très faiblement typés puisqu'ils admettent généralement la déclaration de constantes entières dans différentes bases, des constantes caractère ou liste chaînée de caractères et éventuellement des constantes en virgule flottante. Il n'est toutefois fait aucun contrôle quant à la correspondance entre le type de la constante et l'opération à effectuer.
Certains langages tels LISP ou PROLOG peuvent être considérés comme faiblement typés car, s'ils associent un type au contenu des variables qu'ils manipulent, ce type n'est pas déterminé à l'avance par le programmeur mais plutôt déterminé à l'exécution, par le contexte, lors de l'attribution d'une nouvelle valeur à une variable. Une variable peut donc changer de type au cours de l'exécution du programme; aucun contrôle n'est fait quant à la validité de l'opération.
D'autres langages dits de "haut niveau" tels que FORTRAN, BASIC peuvent être considérés comme moyennement typés car, si un type permanent est associé à chaque variable d'un programme (parfois implicitement), aucun contrôle n'est fait quant à la correspondance entre les opérations effectuées et le type des variables sur lesquelles ces opérations agissent.
La tendance des langages généraux de ces dernières années (ALGOL-1968, PASCAL-1971, MODULA 2-1980, ADA-1980) va vers des langages fortement typés. Dans ces langages toute variable utilisée dans un programme doit avoir un type associé et un contrôle est effectué lors de la compilation et lors de l'exécution pour s'assurer que toute modification de variable ou tout passage de paramètres à des procédures respecte les contraintes de typage, de façon à pouvoir détecter, au plus tôt dans le processus de mise au point d'un programme, un maximum d'erreurs qui peuvent s'y être glissées. Pour ce faire, on augmente la redondance des informations contenues dans les programmes pour pouvoir déceler les éventuelles incohérences
1.2. Contrôle de typage
Il existe deux approches au contrôle de typage qui est effectué par un compilateur pour un langage fortement typé lorsque deux objets différents sont mis en correspondance (lors d'une affectation, d'une comparaison ou d'un passage de paramètre) : l'équivalence de nom et l'équivalence de structure.
1.2.1 Equivalence de nom
Avec l'équivalence de nom, il faut que deux variables (ou paramètres) aient été déclarées en utilisant le même identificateur de type pour qu'elles puissent être considérées comme compatibles.
Exemple
type T = record
PeuImporte: Quelconque;
end; { T }

var X, Y: T;

Z: record
PeuImporte: Quelconque;
end; { Z }
X et Y sont compatibles, mais Z n'est compatible ni avec X, ni avec Y. De même, si l'on a :
type T = ...;
MemeT = T;

var U: T;
V: MemeT;
U et V sont incompatibles.
Un problème lié à l'équivalence de nom est qu'il devient plus difficile d'écrire des sous-programmes d'utilité générale. Par exemple, un sous-programme qui aurait comme paramètre formel un entier ne pourrait pas être utilisé avec un paramètre effectif de type intervalle d'entier.
1.2.2 Equivalence de structure
Avec l'équivalence de structure, pour considérer deux variables comme compatibles, il suffit que l'on ait identité des déclarations de type où l'on aurait remplacé tout identificateur de type déclaré par l'utilisateur par la déclaration de type correspondante.
Dans les exemples vus plus haut, X, Y et Z sont compatibles. Il en est de même pour U et V.
Les problèmes liés à l'équivalence de structure sont une plus grande complexité de contrôle du typage à la compilation et une ambiguïté possible des déclarations. Par exemple, avec les déclarations suivantes :
type Complex1 = record
PartieReelle,
PartieImaginaire: real;
end; { Complex1 }

Complex2 = record
PartieImaginaire,
PartieReelle: real;
end; { Complex2 }
Complex1 et Complex2 sont compatibles. Toutefois, lors d'une affectation impliquant les deux types, la correspondance des champs devrait-elle se faire en fonction de leurs positions relatives ou en fonction de leur nom ? Le mécanisme devant fonctionner même si les noms des champs sont différents, c'est une correspondance positionnelle qui est utilisée.
1.2.3. Cas de quelques langages d'usage courant
1.2.3.1. Pascal
Dans sa spécification du langage Pascal, Wirth reste assez vague sur le sujet. Dans son manuel du Pascal, il dit que, pour l'affectation, l'expression doit être de même type que la variable. Il dit aussi qu'un type de donnée est spécifié soit par la déclaration de variable, soit par un identificateur. Ceci est suffisamment ambigu pour être sujet à interprétation. Dans un grand nombre d'implantations, c'est l'équivalence de structure qui est utilisée. Le type de chaque composante d'une des structures doit être le même que la composante correspondante de l'autre structure.
1.2.3.2. Ada
En Ada, c'est une variante de l'équivalence de nom qui est utilisée. Ada fait, en effet, la distinction entre type de base, type dérivé et sous-type. Un type de base correspond soit à une déclaration de type utilisant un constructeur (enregistrement, tableau, énumération), soit à un type prédéfini du langage (integer, boolean, . . .).
Un type dérivé fait référence à un type de base en y apportant une restriction éventuelle. Un type dérivé bénéficie des mêmes primitives (opérations prédéfinies, sous-programmes utilisant le type de base en paramètre) que le type de base, mais est incompatible avec ce type de base.
Un sous-type fait lui aussi référence à un type de base en y apportant une restriction éventuelle. Ce sous-type reste toutefois compatible avec le type de base pour autant que l'opération impliquant le type de base et son sous-type ne transgresse pas la restriction du sous-type.
La distinction entre ces trois cas se fait dans la déclaration :
type <NomDuTypeDeBase> is
<TypePredefiniOuConstructeur>;

type <NomDuTypeDerive> is
new <NomDuTypeDeBase>
<RestrictionEventuelle>;

subtype <NomDuSousType> is
<TypeDeBase> <RestrictionEventuelle>;
1.2.3.3. Modula-2
Modula-2 utilise une variante de l'équivalence de nom plus laxiste qu'Ada. Si l'on reprend les exemples vus dans le paragraphe sur l'équivalence de nom, comme pour Ada, X et Y sont considérés comme compatibles, mais Z n'est compatible ni avec X, ni avec Y. Par contre, contrairement à Ada, U et V sont considérés comme compatibles.
1.3. Nomenclature
Au vu des langages préalablement cités ci-dessus, on peut ébaucher une nomenclature de typage, tous langages confondus (cette nomenclature est sûrement incomplète) :
• Les types de base (scalaires)
o discrets :
 entiers
 énumérés
 intervalles
o réels:
 virgule flottante
 virgule fixe
• Les types structurés (composés)
o structures statiques
 tableaux
 enregistrements
 chaînes de caractères
 ensembles
o structures dynamiques
 structures non récursives : les fichiers séquentiels
 structures récursives
 structures récursives linéaires : (liste chaînées, anneaux, liste chaînées bidirectionnelles, anneaux bidirectionnels)
 structures récursives non-linéaires : (les listes, les arbres, les graphes, les réseaux)
• Les types exécutables
o procédures (Modula 2)
o tâches (Ada)
o prédicats (Prolog)
Comme on le verra par la suite, dans un langage donné, certains de ces types sont prédéfinis et certains autres doivent être construits par le programmeur. Par exemple, les listes sont prédéfinies en Prolog ou en Lisp alors qu'elles doivent être construites en Pascal. Certains types ne pourront toutefois pas être construits par le programmeur; ainsi, il est difficile, voire impossible, d'implanter les types exécutables dans un langage qui n'a rien de prévu à cet effet.
Pour la suite de ce cours, nous nous baserons principalement sur le langage PASCAL, nous n'aborderons donc pas dans le détail les types exécutables.
2. Les types scalaires

Les types scalaires sont les types de données (généralement prédéfinis dans le langage de programmation) ne contenant qu'une seule information élémentaire. Ils se partagent en deux groupes : les types discrets et les réels.
2.1. Les types discrets
Ils représentent des objets dont les valeurs possibles sont énumérables, en y ajoutant la contrainte d'un nombre fini de valeurs.
2.1.1 Les entiers
Ils représentent des valeurs numériques signées ne comportant pas de partie fractionnaire. Le nombre de valeurs représentables sur un ordinateur étant fini, les entiers sont généralement limités à un intervalle de valeurs possibles : de -MaxInt-1 à MaxInt, MaxInt étant donc le plus grand nombre entier représentable. Pour beaucoup d'implantations sur micro-ordinateurs, MaxInt vaudra 32767. Pour les implantations sur plus grosses machines, on aura une valeur beaucoup plus grande, typiquement 232.
Les opérations possibles sur des entiers sont : l'addition, la soustraction, la multiplication, la division, le modulo et la comparaison ( =, >, >=, <, <=, <> ).
En MODULA-2, il existe un type prédéfini d'entiers non signés (CARDINAL).
2.1.2 Les types énumérés
2.1.2.1 Les booléens
Les objets de type booléen ne peuvent prendre que deux valeurs possibles : true et false. Les expressions comportant des valeurs booléens sont appelées des expressions logiques. Les opérations possibles sont : and, or, not (opérateur monadique) et la comparaison ( =, <> ).
Il est à noter que les opérateurs de comparaison donnent un résultat booléen, même si les opérandes sont d'un autre type.
Exemple
1 < 3 résultat vrai ou faux
'a' < 'c' "
1.5 > 3.6 "
true = false "
Sur certaines implantations, une variable logique non initialisée peut avoir une valeur illégale.
2.1.2.2. Les caractères
Le jeu de caractères d'une machine est sensé être l'énumération, dans un certain ordre, des lettres et signes affichables sur un écran ou imprimables sur papier. Il existe une norme (ASCII) pour un jeu de 128 caractères comprenant non seulement des caractères imprimables mais aussi des caractères de "contrôle". Cette norme ne comporte pas de lettres accentuées.
Sur la plupart des machines, on utilise un octet pour représenter un caractère; il est donc possible d'en énumérer 256 différents. Si les 128 premiers caractères sont presque toujours ceux de la norme ASCII, chaque constructeur a ses propres conventions pour les 128 caractères restants.
Les opérations possibles sont principalement les comparaisons : =, <>, >, <, <=, >= et la fonction de conversion entier ->caractère : chr().
2.1.2.3. Les énumérations définies par l'utilisateur
Il est possible de déclarer une suite ordonnée de symboles qui ont un sens particulier pour l'utilisateur. Par exemple, on peut déclarer un
type semaine = (Dimanche, Lundi, Mardi,
Mercredi, Jeudi, Vendredi,
Samedi).
Toute variable du type Semaine pourra prendre une de ces sept valeurs (et aucune autre valeur ne sera légale). Il est à noter que la plupart des implantations du PASCAL ne permettent pas d'imprimer, lors de l'exécution, la valeur (le symbole) d'une variable de ce type.
Comme pour les caractères, les opérations possibles sont les comparaisons ( =, <>, <, >, <=, >= ).
2.1.3. Les intervalles
Les intervalles ne forment pas, à proprement parler, un type de base. Il s'agit plutôt de types générés en restreignant l'ensemble des valeurs possibles d'un des types de base vus précédemment.
Exemple
type JourOuvrable = Lundi .. Vendredi;
Minuscule = 'a' .. 'z';
Naturel = 0 .. MaxInt;
Toutes les opérations applicables au type de base sont applicables au type intervalle qui en est dérivé. L'intérêt de l'utilisation des intervalles réside dans l'amélioration de la lisibilité des programmes (on voit plus clairement quelles sont les valeurs possibles) et l'augmentation de la sécurité de programmation (des valeurs illégales peuvent être automatiquement détectées à l'exécution).
2.2. Fonctions prédéfinies sur les types discrets
Pour l'ensemble des types discrets, il existe en Pascal des fonctions prédéfinies :
• ord() pour donner la position relative de l'argument par rapport à la première valeur de l'énumération.
Exemple ord(Lundi) = 1
ord(false) = 0
ord('A') = 65
pour un entier i, ord(i) = i !!
La plupart du temps la fonction "ord" n'est pas implantée mais simplement considérée comme une notation de conversion de type. Ceci explique le fait que la fonction "ord", avec pour paramètre un nombre entier négatif, puisse retourner un résultat négatif.
• pred() pour donner l'élément qui précède l'argument dans l'énumération. Un appel à la fonction, avec pour argument le premier élément de l'énumération, provoque une erreur à l'exécution.
Exemple pred(Lundi) = Dimanche
pred(Dimanche) n'existe pas
pred('b') = 'a'
pred(i) = i-1

• succ() pour donner l'élément qui suit l'argument dans l'énumération. Un appel à la fonction, avec pour argument le dernier élément de l'énumération, provoque une erreur à l'exécution.
Exemple succ(Dimanche) = Lundi
succ(Samedi) n'existe pas
succ('a') = 'b'
succ(i) = i+1

2.3. Les réels
De tous les types de base, ce sont les nombres réels qui posent le plus de problèmes de représentation. L'ensemble des nombres réels étant, par définition, infini et indénombrable, il est impossible de le représenter avec une totale exactitude dans un ordinateur. La représentation qui en est faite ne peut donc constituer qu'une approximation. Il existe d'ailleurs plusieurs techniques de représentation, chacune ayant ses avantages et ses inconvénients.
2.3.1. Représentation en virgule flottante
La représentation en virgule flottante consiste à représenter un nombre réel à l'aide de 3 composantes : le signe (S), l'exposant (E) et la mantisse (M). L'on considère que la virgule décimale est placée juste à gauche de la mantisse et que le bit de poids le plus élevé de la mantisse est à 1 (sauf pour représenter 0.0), de façon que la mantisse représente toujours un nombre compris dans l'intervalle [0.5,1.0] (valeur normalisée). Le nombre réel représenté correspond alors à S*(M*2E).
Exemple : représentation de valeurs décimales en binaire

Une valeur normalisée est une valeur dont la mantisse a le bit de plus fort poids à 1 (sauf pour représenter la valeur 0). Dans l'exemple précédent, la représentation (S, M, E) était à chaque fois normalisée. Il existe différentes variantes pour ce qui est de la manière de représenter des exposants négatifs ou des réels négatifs, mais quelle que soit la manière, les qualités et inconvénients restent à peu près les mêmes.

Exemples de représentation de nombres et d'exposants négatifs:
• sur une certaine variété de machines ayant des mots machine de 36 bits, les nombres réels en simple précision ont 1 bit de signe, 8 bits d'exposant et 27 bits de mantisse. La représentation est en complément à un avec un exposant biaisé. Cela signifie que,
pour un exposant de 0, le champ E contiendra 128,
pour un exposant de 127, le champ E contiendra 255 et
pour un exposant de -128, le champ E contiendra 0.
Si le nombre a un signe négatif, l'ensemble des bits sont inversés.
• sur un co-processeur arithmétique couramment utilisé dans des micro-ordinateurs, les nombres réels sont représentés sur 32 bits avec un bit de signe, un exposant de sept bits en complément à deux et une mantisse en valeur absolue.
Les principales qualités de la représentation en virgule flottante sont :
• l'utilisation optimale de la représentation binaire d'un ordinateur (si les nombres sont normalisés et
• une répartition très étalée de la "gamme" de nombres représentables (typiquement 1040 pour de la simple précision et 101000 pour de la double précision).
Les principaux inconvénients étant que :
• il n'y a pas moyen d'éviter des erreurs d'arrondi à chaque calcul et
• les opérations arithmétiques sont plus complexes que sur des nombres entiers.
Par exemple, il n'est pas du tout certain que l'expression logique
sqr( sqrt(2.0) ) = 2.0
correspondant à soit vraie
2.3.2. Représentation en virgule fixe
La représentation en virgule fixe consiste à utiliser une représentation similaire aux nombres entiers en attribuant un nombre de "bits" fixes à la partie fractionnaire et un autre nombre de "bits" à la partie entière.
L'avantage principal de cette représentation étant de pouvoir utiliser les opérations arithmétiques des nombres entiers auxquelles s'ajoute l'opération de décalage. Ces opérations sont très efficaces et accélèrent d'autant le calcul.
Les principaux inconvénients sont que la répartition de la "gamme" de nombres représentables est beaucoup plus étroite que pour la virgule flottante (typiquement 1010 à 1020) et que les erreurs d'arrondis sont aussi inévitables et même s'accumulent beaucoup plus vite.
Exemple : pour des nombres tenant sur 32 bits, on pourrait avoir 1 bit de signe, 23 bits pour la partie entière et 8 bits pour la partie fractionnaire. Le plus grand nombre représentable serait environ 223 soit inférieur à 108 et le plus petit nombre représentable serait 2-8 soit environ 10-2.
2.3.2.1. Représentation BCD
Il existe une variante de la représentation en virgule fixe qui s'appelle la représentation BCD (Binary Coded Decimal). Elle est surtout utilisée dans les langages à usage commercial (tel que COBOL) et permet de représenter des nombres comme une suite de chiffres allant de 0 à 9, l'emplacement de la virgule étant fourni séparément. L'idée de cette représentation étant de ne pas avoir d'erreur d'arrondi tant que l'on se limite à utiliser des nombres en base 10 ayant un nombre limité de chiffres.
Exemple

Fig.2.1. Représentation BCD.
Ce qu'il faut retenir de tout cela, c'est que les nombres réels, tels qu'ils sont représentés en machine, n'ont pas les mêmes propriétés qu'en mathématique. Par exemple, (X/Y)*Y n'est pas forcément égal à X.
Les langages FORTRAN, PASCAL et MODULA II, ainsi que beaucoup d'autres langages, n'offrent que la représentation en virgule flottante. ADA et COBOL offrent les deux possibilités. Pour la représentation en virgule fixe, COBOL permet de spécifier le nombre de chiffres significatifs alors que ADA permet de définir l'intervalle de valeurs possibles ainsi que l'écart entre deux valeurs consécutives.
2.4. Compatibilité et conversion de types
Lors d'une affectation, de l'évaluation d'expressions ou du passage de paramètres à une procédure, on peut être en présence d'objets (variables, constantes ou littéraux) de types différents. Cette combinaison de types pourra être acceptable ou non selon certaines règles qui dépendent du langage. Pour le langage PASCAL, les règles sont les suivantes :
2.4.1. Compatibilité
• Affectation : le tableau ci-dessous indique quel peut être le type de l'expression affectée à une variable.
type de la variable à gauche de l'affectation type de l'expression à droite de l'affectation
réel
discret
intervalle entier ou intervalle d'entiers
même type discret ou intervalle
type de base de l'intervalle
• Evaluation d'expression : le tableau ci-dessous montre quel est le type associé à une expression en fonction du type de ses composants.
type de l'expression type des composants
entier
réel
discret entier ou intervalle d'entier
réel & entier ou intervalle d'entier,
réel discret, intervalle du même type
• Il est à noter que les opérateurs de comparaison admettent des arguments de n'importe quel type de base pourvu que les types des deux arguments soient compatibles au sens de l'affectation; le résultat, lui, est toujours de type booléen. A cause de cela, l'utilisation des parenthèses est parfois nécessaire pour ôter certaines ambiguïtés dans l'expression.
Exemple d'expression ambiguë : A = B and C = D
A = B and C = D pourrait être interprété comme ((A=B) and C) = D, ce qui impliquerait que C et D soient booléens pour que l'expression soit valide;
une autre interprétation serait A = (B and (C=D)), qui serait valide si A et B étaient booléens;
une troisième interprétation serait A = ((B and C) = D), ce qui impliquerait que A, B, C et D soient booléens;
finalement, une quatrième interprétation serait (A=B) and (C=D), ce qui impliquerait que A soit de type compatible avec B et C compatible avec D.
Cette ambiguïté est parfois levée par la spécification de règles de précédence indiquant dans quel ordre les opérations d'une expression doivent être évaluées.
• passage de paramètre
Les règles sont les mêmes que pour l'affectation, avec, au lieu de la variable à gauche de l'affectation, le paramètre formel et, au lieu de l'expression à droite, le paramètre effectif.
2.4.2. Conversion de type
La conversion de type, en PASCAL, est généralement faite explicitement à l'aide de fonctions de conversions. Seule la conversion entier ->réel est faite implicitement lorsque c'est nécessaire. Les fonctions de conversions prédéfinies sont :
fonction type de l'argument type de résultat
ord discret entier
chr entier caractère
trunc réel entier
round réel entier
Le langage ADA impose, quant à lui, des contraintes beaucoup plus strictes. Il fait la distinction entre types dérivés et sous-types. Un sous-type, de même qu'un type dérivé, consiste en une restriction apportée à un type de base. Un sous-type reste compatible avec son type de base alors qu'un type dérivé est incompatible avec son type de base.
Exemples
subtype OneDigit is integer range 0..9;
subtype JourOuvrable is Semaine
range Lundi..Vendredi;
type Entier is new integer;
type MilieuDeSemaine is new Semaine
range Mardi..Jeudi;
Dans les exemples qui précèdent,
OneDigit est compatible avec integer,
JourOuvrable est compatible avec Semaine,
mais Entier n'est pas compatible avec integer
et MilieuDeSemaine n'est pas compatible avec Semaine.
Il est toutefois possible de faire une conversion explicite d'un type dérivé vers son type de base (ou vice-versa) en préfixant l'objet du type à convertir par le type du résultat. Par exemple, si Jour est une variable de type Semaine, MilieuDeSemaine(Jour) est de type MilieuDeSemaine (il y aura erreur si la valeur associée à la variable Jour n'est pas comprise dans l'ensemble des valeurs possibles pour le type MilieuDeSemaine ).
L'intérêt de cette distinction entre types dérivés et sous-types est une fois encore au niveau de la sécurité de programmation. Par exemple, si une variable est sensée représenter une superficie et une autre variable sensée représenter une longueur, cela n'aurait pas beaucoup de sens de vouloir les additionner, même si elles sont toutes les deux des valeurs numériques entières.
Modula-2, quant à lui, est très similaire au Pascal sur ce plan, au détail près qu'il n'a pas de conversion explicite d'entiers en réels. A la place, il faut utiliser une fonction de conversion(float).
3. Les structures statiques

3.1. Structures cartésiennes simples
Les structures cartésiennes simples sont des structures regroupant plusieurs composantes de type de base. Nous verrons ici trois types de structures cartésiennes simples :
• les tableaux,
• les enregistrements,
• les ensembles.
Des variables ayant ces structures fondamentales ne changent que de valeurs, jamais de structure ou d'ensemble de valeurs de base. Conséquence : l'espace qu'elles occupent en mémoire reste constant.
3.1.1. Les tableaux
Les tableaux sont constitués d'un regroupement de données homogènes (ayant le même type) de type quelconque. Les données individuelles sont repérées par un sélecteur que l'on nomme indice du tableau. L'indice d'un tableau doit être de type énuméré. Cela pourra donc être un type défini par l'utilisateur, un intervalle d'entiers, de caractères ou de booléens.
Exemple
type Index = 0..9;
Semaine = (Dimanche, Lundi, Mardi,
Mercredi, Jeudi, Vendredi,
Samedi);
T1 = array [Index] of integer;
T2 = array [0..9] of integer;
T3 = array [boolean] of char;
T4 = array [false..true] of char;
T5 = array [char] of integer;
T6 = array [Semaine] of integer;

var HeuresDeTravail : T6;

begin
...
HeuresDeTravail[Lundi] := 8;
...
end

Les opérations possibles se limitent à la manipulation des composantes individuelles (affectation, comparaison...). Seul le passage de paramètre permet de manipuler un tableau dans sa totalité. Pas de constantes "tableau" possibles en Pascal; en Ada, c'est toutefois possible, les valeurs sont énumérées entre parenthèses, par exemple ainsi : (Constante1, Constante2 . . . ) ou (Indicem . . Indicen => Constante1, . . . ).
3.1.2. Les enregistrements
Les enregistrements sont constitués d'un regroupement de données hétérogènes (de types différents) de type quelconque. Les données individuelles sont repérées par un sélecteur que l'on nomme champ de l'enregistrement. L'identificateur de champ doit être un identificateur conforme aux règles lexicales du Pascal.

Exemple
type Individu = record
Nom, Prenom: string;
Age: integer;
rikiki: (Feminin, Masculin);
end; { Individu }

var Lui: Individu;

begin
. . .
Lui.Age := 15;
. . .
end

Les opérations possibles sur les enregistrements dans leur globalité sont : l'affectation et la comparaison ( =, <> ). Les opérations possibles sur les différents champs d'un enregistrement sont celles associées au type du champ.
Pas de constantes "enregistrement" possibles en Pascal; en Ada, c'est toutefois possible (agrégats) : les valeurs sont énumérées entre parenthèses, dans l'ordre des champs ou en indiquant explicitement le nom du champ avant chaque valeur, par exemple (Constante1, Constante2 . . . ) ou (Champi => Constantei, . . . ).

3.1.3. Les ensembles
Les ensembles sont des structures que l'on ne retrouve quasiment qu'en Pascal. Modula 2 en restreint nettement l'utilisation et Ada ne l'offre pas de manière prédéfinie. Les ensembles se rappochent beaucoup de la notion mathématique d'ensembles. Ils sont construits à partir de types de bases énumérés et permettent d'indiquer, pour chacune des valeurs du type de base, si cette valeur est présente ou absente de l'ensemble en question. Il n'y a pas de sélecteur possible.
Exemple
var S, Voyelles, Consonnes: set of char;
. . .
S := []; { ensemble vide }
Voyelles := ['a','e','i','o','u','y'];
Consonnes := ['b'..'d','f'..'h','j'..'n',
'p'..'t','v'..'x' ,'z'];
S := [ 'b'..c ]; { noter le fait que c
est une variable }

Les opérations sur les ensembles ne sont possibles que globalement. On dispose de l'affectation, l'union (+), l'intersection (*), la diffé rence (-), la comparaison ( =, <> ), le test d'appartenance d'une valeur du type de base ( in ) et l'inclusion (<).
N.B. L'expression a S sera notée : not (a in S).

3.2. Cardinalité
Définition : La cardinalité est le nombre de valeurs distinctes appartenant à un type T. Un objet de ce type T ne pourra bien entendu avoir qu'une seule de ces valeurs à un instant donné
Exemple
type Forme = (Carré, Rectangle, Cercle,
Ellipse);
Monnaie = (Franc, Livre, Dollar,
Lire, Yen, Mark);
Genre = (Feminin, Masculin);
card(Forme) = 4
card(Monnaie) = 6
card(Genre) = 2
type SmallInteger = 1..100;
type Vecteur=array[1..3] of SmallInteger;
card (SmallInteger) = 100
card (Vecteur) = 1003

card (boolean) = 2
card (integer) = 2*(MaxInt+1) { pour le langage Pascal }

card (real) = 2n-1 pour une représentation normalisée, où n est le nombre de bits utilisés pour représenter les nombres réels. Le premier bit de la mantisse étant toujours à 1, sauf pour la valeur 0.0, certaines architectures ne mémorisent pas ce premier bit et ont, par conséquent, une cardinalité de 2n pour les nombres réels.
On peut résumer les principales caractéristiques des structures cartésiennes simples dans le tableau suivant :
Structure : Tableau Enregistrement Ensemble
Déclaration a : array of To r : record
S1 : T1; S2 : T2; Sn : Tn;
end; set of To
Sélecteur : a (i I)
r.s (S S1,...Sn )
aucun
Accès aux
composantes: par le sélecteur
et le calcul de l'indice par le sélecteur avec le nom
déclaré d'un élément Test d'appartenance avec l'opérateur de relation in
Type des
composantes: Toutes ident. de type To Peuvent être différents Toutes ident. et de type scalaire To
Cardinalité : Card(To)Card(I

produit cartésien 2Card(TO)
Ces structures simples peuvent être combinées pour former des structures plus complexes .
3.3. Structures cartésiennes complexes 3.3.1. Tableaux multidimensionnés

Déclaration :
type Matrices = array[Ligne] of
array[Colonne] of To;
(ou : Matrices = array[Ligne,Colonne] of To)
Sélecteur :
var m : Matrices;
m[j] ou m
Cardinalité :
card(m) =card(To)card(Ligne).card(Colonne)
Déclaration :
type Esp3D:array[Profondeur] of Matrices;
(ou : array [Profondeur, Ligne, Colonne] of To).
Sélecteur :
var e : Espace3D;
e[p] [j] ou e[p] ou e[p,i],[j] ou e[p, i, j]
Cardinalité :
card(e)=card(To)card(Profondeur).card(Ligne).card(Colonne)
Le nombre de dimensions d'un tableau n'est, dans la plupart des langages, pas limité !
3.3.2. Tableaux d'enregistrements
Déclaration :
type Point = record
X, Y: integer;
end; { Point }

Suite = array[1..Max] of Point;
var S1, S2 : Suite;
Sélecteur :
a. L'abscisse du premier point de la suite S1: S1[1].X
b. Ecrire tous les points de la deuxième suite dont l'ordonnée est supérieure à 10
for i := 1 to Max do
if S2.Y > 10.0 then
writeln (S2.X, S2.Y);
Cardinalité :
card(S1) = card(integer)2.Max
3.3.3. Enregistrement de tableaux
Déclaration :

const Max = . . . ;
AlfaLong = 15;
type Alfa = packed array[1..AlfaLong]
of char;
Service = (Actif, Reserviste,
Complementaire, Reforme);
{ Il n'est pas dans les intentions des
auteurs d'être sexiste }

Adulte = record
Nom: Alfa;
Prenoms: array [1..3] of Alfa;
case rikiki:(Feminin,Masculin) of
Feminin:(NomDeJeuneFille: Alfa);
Masculin:(Incorporation:Service);
end; { Adulte }
var L1, L2: array[1..Max] of Adulte;


Sélecteur :
le deuxième prénom de la première personne de la liste L1:
L1[1].Prenoms[2]
Cardinalité :
card(L1) = ( card(char)4.15. (card(char)15 + card(Service)) )Max
N.B. : la cardinalité d'un enregistrement avec variant est égale à :
card. des compos. avant variant . ( card.de chaque variante)
On peut de la même manière construire des tableaux d'ensembles et des enregistrements contenant des ensembles.
3.3.4. Les chaînes de caractères 3.3.4.1. Chaînes de longueur fixe

Les chaînes de caractères telles qu'elles sont définies par N. Wirth dans son manuel du Pascal sont disponibles dans la quasi-totalité des implantations du Pascal. Leur déclaration se fait de la manière suivante :
Variable:packed array[intervalle] of char;
L'intervalle spécifié dans la déclaration ci-dessus est généralement de la forme 1..Longueur, mais cela n'est pas obligatoire; n'importe quel intervalle d'entiers est admissible.
Des chaînes constantes sont spécifiées de la manière suivante :
'suite de caractères'
Si l'on désire une apostrophe dans la suite de caractères, il faut en mettre deux qui se suivent, comme dans :
'c''est un exemple'.
Les primitives de manipulation de chaînes de caractères sont les suivantes :
• affectation : VariableChaîne1:= VariableChaîne2;
VariableChaîne:= ChaîneConstante;
Les chaînes doivent être de même longueur. Certaines implantations admettent que la chaîne constante soit plus courte que la variable à laquelle elle est affectée. La chaîne constante est alors complétée par des blancs en fin de chaîne.
• lecture : elle n'est pas possible en tant qu'opération de base (sauf pour certaines variantes d'implantation). Il faut lire dans un tableau de caractères non compacté puis utiliser la procédure prédéfinie pack.

• écriture : write(VariableChaîne);
write(ChaîneConstante);
• comparaison : <, >, =, <>. La comparaison se fait sur tous les caractères, entre chaînes de même longueur. Là aussi, si un des opérandes est une chaîne constante plus courte que l'autre opérande, certaines implantations complètent la chaîne par des blancs.
• construction et décomposition : pour pouvoir manipuler individuellement les caractères d'une chaîne, il faut utiliser les procédures prédéfinies pack et unpack. Ces procédures permettent de convertir un simple tableau de caractères en une chaîne de caractères et vice-versa.
3.3.4.2. Chaînes de longueur variable
Cette variante est propre à certaines implantations telles que Pascal UCSD et Turbo Pascal. Elle permet de disposer d'un jeu plus complet de primitives de manipulation et, surtout, de pouvoir faire varier la longueur effective de la chaîne durant l'exécution. La déclaration se fait de la manière suivante :
string[NbCarMax];
ou string; { correspond à string[80] }
NbCarMax indiquant la longueur maximale que pourra avoir la chaîne.
Les chaînes constantes sont spécifiées de la même manière que des chaînes de longueur fixe.
Pour pouvoir déterminer quelle est la longueur effective d'une chaîne de caractères, un attribut de longueur est associé à chaque variable de ce type. De plus, les caractères composant la chaîne sont accessibles individuellement comme pour un tableau de caractères : si S est déclaré de type string, le premier caractère de la chaîne sera stocké en S[1]. Le nombre de caractères effectivement stockés est généralement indiqué par S[0]. L'attribut de longueur doit toujours appartenir à l'intervalle [CHR(0)..CHR(NbCarMax)].
Les primitives de manipulation sont les suivantes :
• affectation : S:=S2; ou S:='suite de caractères'; si la longueur de la chaîne à droite de l'affectation ne dépasse pas la longueur maximale de S. On peut aussi avoir C:=S; ou S:=C; si C est de type CHAR et i une expression donnant un résultat entier positif inférieur ou égal à la longueur réelle de S.
• lecture : read(S); on ne peut lire qu'une chaîne par ligne. Si le nombre de caractères disponibles sur la ligne courante est plus grand que la taille maximale de la chaîne, les caractères en trop sont perdus. S'il y a moins de caractères que la chaîne ne peut en contenir, l'attribut de longueur de la chaîne est ajusté en conséquence.
• écriture : write(S); ne sont écrits que les caractères correspondant à la longueur réelle de la chaîne.
• comparaison : <, >, =, <>. La comparaison tient compte de la longueur réelle des chaînes. Si les longueurs sont différentes, la plus courte est complétée par des blancs. La relation d'ordre correspond à l'ordre alphabétique.
• un ensemble de procédures et de fonctions prédéfinies:



function length(S: string): integer;
retourne l'ordinal de l'attribut de longueur de la chaîne.
procedure insert(Insertion: string;
VAR Destination: string;
Position: integer);
Insertion doit être un string non-vide; Position doit appartenir à l'intervalle [1..length(Destination)+1]. Après l'insertion, le premier caractère de Insertion se trouvera en Destination[Position].
procedure delete(VAR S: string;
Position, Longueur: integer);
Position et (Position+Longueur-1) doivent appartenir à l'intervalle [1..length(S)].
function copy(S: string;
Position, Longueur: integer): string;
fournit, en sortie, la partie de S commençant en Position et ayant Longueur caractères. Les restrictions concernant les valeurs de Position et Longueur sont les mêmes que pour DELETE.
function concat(S1,S2...:string): string;
peut avoir un nombre variable de paramètres. Fournit, en sortie, la concaténation des différentes chaînes passées en paramètre.
function pos(SousChaîne,Chaîne: string): integer;
recherche la sous-chaîne à l'intérieur de la chaîne et indique en quelle position elle commence (0 = pas trouvé).
procedure str(Valeur: integer; VAR Chaîne: string);
convertit un entier en chaîne de caractères. La longueur de la chaîne correspondra au minimum nécessaire pour représenter la valeur en question.
Ce modèle de chaînes de caractères de longueur variable comporte certaines inconsistances. Il est en effet à noter que les fonctions COPY et CONCAT ne répondent pas à la syntaxe du Pascal, puisqu'une fonction de l'utilisateur ne peut pas fournir une valeur de retour de type string, ni avoir un nombre variable de paramètres. Tout programme devant être portable devra donc éviter d'utiliser ces deux primitives, puisqu'elles ne peuvent pas être facilement remplacées par des fonctions de l'utilisateur.
Ce modèle comporte aussi certains pièges. Chaque fois que l'on accède à un "string", l'attribut de longueur est contrôlé. Le principal problème que l'on peut rencontrer en utilisant des strings peut seposer si l'on passe un string par référence à une procédure. En effet, lors de la déclaration des paramètres formels, on est obligé de spécifier la longueur maximale du string; or cette longueur peut ne pas coïncider avec la longueur maximale du paramètre réel. D'où un contrôle erroné des indices qui déjoue les mécanismes de sécurité généralement associés au langage Pascal.
Exemple
type ChaîneCourte = string;
ChaîneLongue = string[255];

var Chaîne: ChaîneCourte;

procedure Remplis(VAR S: ChaîneLongue);
begin
...
S := ...;{ expression fournissant une }
{ chaîne de plus de 80 car. }
...
end; { Remplis }

begin { programme principal }
Remplis(Chaîne);{va "écraser" les}
end. {positions mémoires}
{qui sont après Chaîne}
3.4. Structures paquetées
Les abstractions que l'on manipule dans un programme par l'intermédiaire des variables permettent de concevoir, comprendre, vérifier les programmes sur la base des lois qui gouvernent les abstractions.
Exemple : un programme manipulant les abstractions de nature économique peut être entièrement conçu, compris et vérifié en considérant uniquement des lois économiques).
Cependant, si la connaissance exacte des principes de fonctionnement d'un ordinateur ou d'un langage n'est pas indispensable (sauf pour les professionnels que sont les informaticiens), il est bon d'avoir ponctuellement une idée plus précise de comment un programme écrit dans langage s'exécute en machine. Dans le domaine qui nous intéresse, ici les structures de données, il est important de savoir comment sont représentées des structures fondamentales telles que :
• les tableaux.
• les enregistrements.
Le problème de la représentation des structures de données revient à faire correspondre, à l'abstraction que représente la structure, une organisation particulière de la mémoire centrale de la machine. En première approximation, la mémoire centrale d'une machine est un tableau de cellules élémentaires appelées mots. Les indices de ces mots sont appelés adresses.
var Memoire : array [Adresses] of Mots;
Les cardinalités d'adresses et de mots varient fortement d'une machine à l'autre. Par exemple :
quelques milliers < card(Adresse) < plusieurs millions
3.4.1. Cas des tableaux
La conversion indice Æ adresse pour la j-ème composante d'un tableau s'effectue de la manière suivante :
i = i0 + (j-1) * S
avec : i0 = adresse de la première composante
S = nombre de mots qu'occupe une composante (ce nombre peut être fractionnaire)
Le cas idéal serait : S = 1, mais ce n'est pas souvent le cas; alors S est arrondi à l'entier supérieur le plus proche. Donc, chaque composante occupera S' mots, avec S'-S laissé inoccupé.
Cette méthode, qui consiste à arrondir le nombre exact de mots nécessaires à l'entier supérieur, est appelée remplissage (padding).
Exemple

Fig. .3.1 Remplissage
Le facteur d'utilisation est donné par :
U = S / S'
l'objectif étant d'avoir un facteur n aussi proche que possible de 1. Notons que :
U > 0,5 si S > 0,5 mot
Cependant, si S 0,5, le facteur d'utilisation peut être largement amélioré si l'on met plusieurs composantes du tableau dans un seul mot. Cette méthode est appelée compactage : si n composantes sont compactées dans un seul mot, le facteur d'utilisation est :
U = (n * S) / (n * S)' avec (n*S)' = 1 géné
Exemple

Fig. 3.2. Compactage
L'accès à la j-ème composante d'un tableau compacté suppose :
a. le calcul de l'adresse i du mot contenant cette composante
i = (j-1) div n
b. le calcul de la position k qu'occupe la composante à l'intérieur du mot.
k = ((j-1) mod n) +1 = j - (i * n)
Ce compactage, l'utilisateur doit pouvoir l'exiger si nécessaire sans avoir à se préoccuper de son mécanisme. C'est pourquoi le langage Pascal introduit deux variantes aux structures tableaux et enregistrements qui sont :
packed array [...]
packed record ...
Exemple (chaînes de longueur fixe)
type alfa = packed array [1..n] of char;
Si la structure occupe moins de place en mémoire, ses composantes deviennent, par contre, plus difficiles d'accès. Pour un tableau compacté, en Pascal, il faudra passer par les procédures pack et unpack pour manipuler les composantes individuelles; par contre, on pourra utiliser l'affectation sur le tableau complet.
C'est pour des raisons de compromis entre efficacité d'implantation et occupation en mémoire que les structures compactées ont la contrainte de ne pas avoir de composante de taille inférieure à un mot machine qui soit à cheval sur deux mots machine. C'est pourquoi il est généralement exigé que dans l'exemple vu plus haut, n soit un nombre entier.
3.4.2. Cas des enregistrements
Les différentes composantes d'un enregistrement sont stockées les unes à la suite des autres. Dans un enregistrement non paqueté, chaque composante doit commencer au début d'un nouveau mot machine. Pour les mêmes raisons de compromis entre efficacité du code et occupation de la mémoire, dans un enregistrement paqueté, les composantes de taille supérieure à un mot doivent commencer au début d'un mot et seules les composantes de taille inférieure à un mot pour lesquelles il y aurait encore de la place dans le dernier mot utilisé seront placées au milieu d'un mot (pas de composante à cheval sur deux mots). On emploie donc simultanément les techniques de remplissage et de compactage.
Pour un enregistrement, il n'y a pas de changement dans l'utilisation (pas de décompactage nécessaire), seul le temps d'accès sera plus long, car le compilateur devra générer un code plus complexe pour accéder à l'information.
Exemple

Fig. 3.3. Enregistrement paqueté

4. Les types abstraits
Un type abstrait est une structure qui n'est pas définie en terme d'implantation en mémoire ou par une explicitation de ses composantes, mais plutôt en termes d'opérations et de propriétés sémantiques. La spécification d'un type abstrait est indépendante de toute représentation de la (ou des) structure(s) en machine et de l'implantation des opérations associées. Ceci a pour intérêt d'empêcher l'utilisateur d'une telle structure de modifier directement la structure avec le risque de la rendre éventuellement incohérente. Une autre conséquence intéressante est l'amélioration de la portabilité qui découle de l'indépendance entre les manipulations de la structure et la méthode d'implantation choisie.
Il existe différentes approches et langages pour la spécification d'un type abstrait. Quelle que soit l'approche, la spécification d'un type abstrait comporte deux parties : la structure logique et les opérations.
La spécification de la structure logique décrit une instance du type abstrait, les relations qui peuvent exister entre les éventuelles composantes de cette instance et les assertions invariantes qui décrivent les restrictions à apporter à ces relations.
La spécification des opérations décrit la syntaxe et la sémantique des primitives de manipulation du type abstrait. Si un langage formel est utilisé pour cette spécification, une description de ce langage doit accompagner la description du type abstrait.
La plupart des structures que nous avons déjà vues, ainsi que la plupart des structures que nous verrons plus loin, peuvent être décrites en termes de types abstraits. Bien qu'il existe des formalismes algébriques permettant de décrire des types abstraits, dans les exemples qui suivent, nous nous contenterons de décrire les types abstraits en langage naturel sans faire de séparation explicite entre les différentes parties de la spécification. Le but des spécifications qui seront données plus loin est principalement d'améliorer la compréhension des différentes structures décrites plutôt que de prouver la complétude ou la consistance de leur implantation.
4.1. Exemple : les tableaux
La spécification de la structure de tableau peut se faire de la manière suivante :
• leur déclaration spécifie un intervalle d'indices et un type de base. Ceci détermine indirectement la taille du tableau. Une variante pourrait être que la déclaration spécifie la taille du tableau et le type de base, en supposant que l'indice est de type entier et que la borne inférieure est égale à 1 (cas du langage FORTRAN, si l'on suppose que l'initiale de l'identificateur de tableau sert à la spécification du type de base, en l'absence de déclaration explicite).
• le rôle du tableau est de conserver pour chaque valeur d'indice une valeur de type de base associée.
• une seule valeur du type de base peut être associée à chaque valeur d'indice.
• les primitives de manipulations sont
1. associer une valeur du type de base à une certaine valeur d'indice,
2. fournir la valeur de type de base associée à une certaine valeur d'indice.
3. en fonction de la déclaration, diagnostiquer la validité de l'indice fourni.
• On peut envisager de pouvoir associer, lors de la déclaration d'un tableau, une valeur initiale à quelques (ou toutes les) valeurs d'indices. C'est le cas du langage Ada, par exemple.
On peut noter qu'il n'a pas été spécifié de primitive permettant de tester si une valeur a été associée à un certain indice. On peut aussi noter que l'utilisation d'un intervalle d'indices induit un séquencement implicite des valeurs de type de base associées à ces indices. Ainsi, l'on pourra dire que deux valeurs se suivent dans le tableau si les valeurs des indices auxquels elles sont associées se suivent dans la séquence des indices. Cela ne signifie pas pour autant que ces valeurs de type de base seront effectivement stockées dans des zones contiguës de la mémoire (même si c'est presque toujours le cas en réalité, pour des raisons d'efficacité).
4.2. Exemple : les ensembles
• leur déclaration spécifie un type de base qui doit être un type énuméré.
• le rôle d'un ensemble est d'indiquer la présence ou l'absence de chacune des valeurs possibles du type de base dans cet ensemble.
• les primitives de manipulations sont :
1. regroupement d'une ou plusieurs valeurs de type de base sous forme d'ensemble,
2. est d'appartenance d'une valeur de type de base à un ensemble,
3. l'affectation d'un ensemble à une variable de type ensemble compatible,
4. la comparaison de deux ensembles,
5. le test d'inclusion d'un ensemble dans un autre,
6. union de deux ensembles,
7. intersection de deux ensembles,
8. différence de deux ensembles.
Ces quatre dernières primitives pourraient être construites à partir des trois premières. De plus, les trois dernières sont redondantes entre elles car chacune peut être facilement définie à l'aide des deux autres. On pourrait donc omettre l'une d'entre elles, voire les quatre, sans réduire la fonctionnalité du type abstrait "ensemble".
On peut noter qu'il n'est pas nécessaire d'inclure le test de non-appartenance à un ensemble, car il suffit pour cela de prendre la négation du test d'appartenance.
4.3. Exemple : chaînes de caractères de longueur variable.
• leur déclaration spécifie éventuellement une longueur maximale. Ceci est toutefois une contrainte d'implantation qui n'est pas indispensable.
• leur rôle est de stocker une séquence de caractères de longueur arbitraire.
• les primitives de manipulations sont :
1. constituer une chaîne de caractères à partir d'une séquence de zéro, un ou plusieurs caractères.
2. l'affectation d'une chaîne à une variable de type compatible,
3. fournir la longueur d'une chaîne,
4. fournir le caractère se trouvant à une certaine position,
5. redéfinir le caractère se trouvant à une certaine position,
6. insérer une chaîne dans une autre à partir d'une certaine position
7. détruire une portion d'une chaîne, à une certaine position et sur une certaine longueur,
8. concaténer deux chaînes,
9. extraire une sous-chaîne d'une chaîne,
10. trouver la position de la première occurrence d'une sous-chaîne
On pourrait constituer un modèle nettement simplifié en reprenant les primitives 1 à 5 et en y ajoutant la possibilité d'insérer un caractère en fin de chaîne. Toutes les autres primitives pourraient alors être construites à partir de cette version simplifiée. L'avantage de construire un modèle plus complexe est que l'implantation que l'on en fera pourra être plus efficace.
Le langage Pascal ne permet pas la réalisation complète de tous les aspects des types abstraits, principalement par le fait qu'il ne permet pas de cacher les détails d'implantation. Des langages plus récents, tel que Ada, permettent de construire ces types abstraits d'une manière beaucoup plus sûre, par le biais de la modularisation et de l'utilisation de types privés. Ce langage fait même la distinction entre type privé, sur lequel l'affectation et la comparaison sont encore possibles, et type privé limité, sur lequel aucune opération n'est possible (il ne peut alors plus servir que de paramètre de procédure
5. Les structures dynamiques
Les structures statiques sont toutes caractérisées par une cardinalité finie. Cependant des structures plus élaborées sont caractérisées par une cardinalité infinie. Ce sont les structures de données dynamiques telles que : les chaînes, les listes, les arbres, les graphes, etc.
L'objectif principal des structures de données est de permettre à l'utilisateur de développer une solution informatique à un problème qui soit conceptuellement aussi proche du problème que possible. Prenons par exemple, un système de réservation pour une compagnie aérienne. On peut distinguer trois niveaux de traitement :
domaine du problème implantation du système Niveau mémoire
 horaires
 vols
 dates
 destinations
 réservations  fichiers
 tableaux
 Enregistrements
 chaînes de caractères
 structures de données plus complexe  octets
 suites de mots mémoires
 pages
Nous nous intéresserons plus particulièrement au niveau intermédiaire. C'est celui où l'on met en oeuvre les concepts généraux des structures de données et où l'on développe des algorithmes permettant de gérer ces structures efficacement, indépendamment du problème pour lequel elles seraient utilisées.
Définition : une structure dynamique est une structure dont la taille (le nombre de composantes) peut varier en cours d'exécution.
On distingue généralement deux sortes de structures dynamiques : les fichiers et les structures récursives. Les structures dynamiques peuvent être subdivisées en deux catégories : les structures linéaires et les structures non-linéaires
structures dynamiques linéaires fichier structures non-récursives
chaînes structures récursives
structures dynamiques non-linéaires listes
arbres
graphes
Une structure récursive est une structure (en général basée sur un enregistrement) dont la définition comporte une référence à elle même. S'il n'y a qu'une seule référence, cette structure est linéaire; s'il y en a plusieurs, cette structure est non-linéaire. Pour beaucoup de langages procéduraux, ces références se font à l'aide du type pointeur
5.1. Les pointeurs
Une variable de type pointeur est une variable dont le contenu (adresse) peut indiquer l'emplacement en mémoire d'une autre variable, créée dynamiquement lors de l'exécution et ayant un type de base précis (objet pointé). Ceci constitue la principale différence entre la notion de pointeur dans un langage de haut niveau et la notion d'adresse en assembleur.
On peut décrire les pointeurs en terme de type abstrait de la manière suivante :
• le rôle d'un pointeur est de permettre l'accès à une structure qui serait créée lors de l'exécution.
• la déclaration doit spécifier le type de base de l'objet qui pourra être accessible à l'aide du pointeur.
• primitives de manipulation :
1. associer à un pointeur un objet (de type de base) qui sera accessible à l'aide de ce pointeur (ceci ne définit pas pour autant la valeur qui sera associée à l'objet),
2. détruire l'objet accessible à l'aide du pointeur,
3. indiquer l'absence d'objet à accéder,
4. permettre à un pointeur d'accéder au même objet qu'un autre pointeur,
5. associer une valeur de type de base à l'objet accessible par un pointeur,
6. fournir la valeur de type de base associée à l'objet accessible par un pointeur (diagnostiquer le cas où il n'y a pas d'objet à accéder),
7. comparer deux pointeurs de même type de base pour savoir s'ils permettent d'accéder au même objet.
Ce modèle ne spécifie pas ce qu'il advient d'un éventuel objet précédemment accessible à l'aide d'un pointeur lorsque l'on demande la création d'un nouvel objet accessible à l'aide de ce même pointeur sans avoir détruit, au préalable, l'objet précédemment accessible. Il ne spécifie pas non plus ce qui se passe si l'on essaye d'accéder à l'objet sensé être accessible à l'aide d'un pointeur si l'on n'a jamais associé d'objet à ce pointeur, ni indiqué l'absence d'objet accessible (pas d'initialisation du pointeur).
Dans ce qui suit, nous allons voir la manière dont les pointeurs sont implantés en Pascal. La déclaration a la forme :
VAR P: ^TypeDeBase;
Si l'on désire qu'un pointeur n'indique l'emplacement d'aucun objet (primitive 3), on peut lui affecter la constante prédéfinie NIL (quel que soit le type de base).
Lorsqu'une variable de type pointeur est déclarée dans un programme ou une procédure, le contenu (adresse) est indéterminé au moment de l'activation du programme ou de la procédure (pas forcément NIL). Pour définir le contenu d'une variable de type pointeur, on a trois possibilités:
• lui affecter la valeur NIL ( P := NIL; ) (primitive 3)
• lui affecter le contenu d'une autre variable du même type ( P := Q; ) (primitive 4)
• passer la variable en paramètre aux procédures prédéfinies NEW ou DISPOSE (p.ex. NEW(P); )
(primitives 1 et 2)
La procédure NEW (primitive 1) a pour tâche :
• de trouver un emplacement libre en mémoire suffisamment grand pour contenir un objet de type TypeDeBase,
• de réserver la place nécessaire et
• de mettre l'adresse de cet emplacement dans la variable de type pointeur qui lui est fournie en paramètre (P).
Après l'appel, on aura donc deux objets accessibles :
• P (le pointeur), qui contient une adresse (généralement 1 mot machine), et
• P^ (l'objet pointé ne possédant pas d'identificateur propre), qui contient une information de type TypeDeBase.
L'opérateur postfixé "^" permet d'implanter les primitives 5 et 6; la 5 en affectant une valeur à P^ (P^ := valeur_de_type_TypeDeBase) et la 6 en utilisant P^ dans une expression (par exemple dans une expression logique : if P^ = valeur_de_type_TypeDeBase then . . . ).
La procédure DISPOSE (primitive 2) a pour tâche :
• de libérer la place occupée par l'objet pointé (P^) et
• de mettre la variable pointeur (P), qui lui est passée en paramètre, à NIL pour indiquer qu'elle ne pointe plus vers rien.
Si l'on utilise l'affectation pour redéfinir le contenu d'une variable de type pointeur (primitive 4), il faut bien faire attention au cas où la variable pointait préalablement sur un objet


Revenir en haut
Publicité






MessagePosté le: 15/11/2005 18:00:08    Sujet du message: Publicité

PublicitéSupprimer les publicités ?
Revenir en haut
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    Portail Des Etudiants Index du Forum -> Espace des étudiants -> Cour, TD, TP & Mémoire -> Cour ESC Toutes les heures sont au format GMT + 1 Heure
Page 1 sur 1

 
Sauter vers:  

Portail | Index | Panneau d’administration | Créer un forum | Forum gratuit d’entraide | Annuaire des forums gratuits | Signaler une violation | Conditions générales d'utilisation
Flowers of Evil © original theme by larme d'ange 2006 | complètement modifié par Carbanion pour le Forum WS-ESC - 2008-09©
Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com