Cours informatique implémentation des structures de données

Type de base <-> type structuré :

•type de base: une valeur par variable
•type structuré une collection de valeurs par variable
Exemples:
VAR k: INTEGER; (* k peut contenir 1 valeur entière *)
tab: ARRAY 10 OF INTEGER; (*tab peut contenir 10 valeurs entières *)
rec: RECORD (* rec peut contenir r: REAL; une valeur de type réel i: INTEGER; et une valeur de type entier *) END
Type statique <-> type dynamique
•statique: la place mémoire est allouée à l’initialisation.
•dynamique (pointeur): la mémoire est allouée à la demande, en cours d’exécution du programme (avec l’opération NEW)
•une structure de type dynamique peut croître “infiniment” pendant l’exécution du programme; elle peut se réduire aussi
•chaque variable allouée dynamiquement est référencée par une variable de type pointeur
Déclaration d’une variable de type pointeur et création de la variable dynamique
•la déclaration d’une variable de type pointeur indique de quel type sera la variable allouée dynamiquement (appelé “type de base”). Exemple:
•La déclaration ne crée pas la variable dynamique ellemême. La création doit se faire explicitement avec l’instruction
NEW(p)
•La variable ainsi crée n’est pas désignée par un identificateur: elle est anonyme. Pour y accéder, on utilisera la variable de type pointeur (p)
•On appelles plus simplement les variables de type pointeur “pointeurs” ou “références”
TYPE String = ARRAY 32 OF CHAR;
VAR p: POINTER TO PERSONNE;
PERSONNE = RECORD nom, prénom: String; END;
La référence
•Référence ≡ variable de type pointeur (POINTER)
•La référence contient l’adresse mémoire où réside un enregistrement ou, en toute généralité, une unité d’information
•Exemple: deux enregistrements représentant chacun une coordonnée (x,y) de l’écran; ils sont référencés par trois références: point1, point2 et point3:
Déclaration de la référence, création et suppression des enregistrements référencés
•La déclaration d’une référence se fait de la même manière que celle des autres types de variable
•Pour indiquer qu’il s’agit d’une référence on utilise le mot réservé POINTER
•Aprés la déclaration de la référence, sa valeur est NIL
•La création (allocation de la mémoire) d’un enregistrement référencé se fait à l’aide de la procédure NEW; la valeur de la référence devient#NIL
•Lorsqu’un enregistrement n’est plus référencé, il n’y a plus moyen d’y accéder; l’enregistrement est alors candidat à la suppression automatique par le ramasseur de miette (garbage collection)
Remarque: – En Oberon il est également possible de référencer des tableaux
TYPE Point = POINTER TO
VAR point1: Point; BEGIN
RECORD x, y: INTEGER END;
… NEW(point1); point1
point1

NIL
L’opérateur flèche (^) et l’opérateur point (.)
•L’opérateur flèche (^) sert à “déréférencer” la référence, càd à accéder à l’enregistrement référencé. Attention: la référence doit être # NIL
•L’opérateur point (.) sert à accéder aux champs de l’enregistrement; nous verrons aux chap. 2 et 3 que les champs peuvent aussi représenter des méthodes
•Pour alléger l’écriture, l’opérateur (^) est facultatif lorsqu’on accède aux champs d’un enregistrement référencé. On peut écrire
point1.x au lieu de point1^.x
Exemple:
TYPE Point = POINTER TO RECORD x, y: INTEGER END; VAR point1, point2, point3: Point; BEGIN … NEW(point1); point1.x:=1; point1.y:=1; point3:=point1; (* affectation de la référence -> point3 se réfère au même enregistrement que point1*) NEW(point2); point2^:=point1^; (* affectation de l’enregistrement *) … point1 1 1 point  point3
La signification de :=
Soit l’instruction d’affectation g:=d • L’affectation (:=) entre deux variables primitives, disons de type INTEGER, a pour effet de copier la valeur de la variable de droite dans la variable de gauche. • L’affectation entre deux références a exactement le même effet: la valeur de la variable de droite est copiée dans la variable gauche. Comme la valeur est une adresse mémoire, après l’affectation la variable de gauche va se référer au même enregistrement (ou objet) que la variable de droite.
Les affectations ci-dessous sont-elles légales ?
point1 1 1point3
P.e. après l’affectation p3:=p1
TYPE String = ARRAY 32 OF CHAR;
Noeud = RECORD clé: String; suivant: NoeudListe; END; VAR liste: NoeudListe; noeud: Noeud; NoeudListe = POINTER TO Noeud; BEGIN … NEW(liste); noeud := liste; noeud := liste^; noeud^.suivant := liste; noeud.suivant := liste; noeud.suivant := liste.suivant; …
• Deux références sont égale au sens de l’opérateur (=) si elles se réfèrent au même enregistrement (ou objet)
• Mais deux références p1 et p2 qui se réfèrent à deux enregistrements différents ne sont pas égales, même si tous les champs des enregistrements sont égaux deux à deux p1 p2

Lire sur cLicours.com :  The Programming Language Modula-2 and its Environment

Cours gratuitTélécharger le cours complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.