Structures de données/Version imprimable
Une version à jour et éditable de ce livre est disponible sur Wikilivres,
une bibliothèque de livres pédagogiques, à l'URL :
https://fr.wikibooks.org/wiki/Structures_de_donn%C3%A9es
Introduction
Introduction
[modifier | modifier le wikicode]L'étude des structures de données fait suite à celle de l'algorithmique impérative. Une bonne connaissance stable de l'algorithmique impérative est une base essentielle à l'étude menée ici. L'étude de l'algorithmique fonctionnelle est d'une aide non-négligeable.
Nous n'avons donc utilisé jusqu'ici qu'une structure de données, le tableau. Cette structure de données pose un problème : elle occupe la mémoire en fonction de sa déclaration. Ce qui signifie que si on ignore combien l'utilisateur va nécessiter d'indice, il va falloir réserver le tableau le plus grand possible afin d'être sûr qu'il puisse contenir autant d'élément que l'utilisateur souhaitera. Il serait plus judicieux de réserver l'espace au fur et à mesure de la demande. C'est ce que l'on appelle la gestion dynamique de la mémoire (par opposition à statique).
Nous avons également vu que les tableaux sont génériques : c'est à dire qu'au moment de sa déclaration, nous pouvons dire que tous ses éléments sont d'un type donné et choisir ce type.
Nous avons vu que les tableaux sont homogènes : c'est à dire qu'un tableau donné ne peut contenir qu'un seul type d'élément (celui précisé dans la déclaration du tableau). Nous pourrions avoir besoin d'un tableau dont certain élément serait des entiers, d'autres des chaînes, d'autres encore des booléens. Il s'agit là de la problématique de l'hétérogénéité.
Note : attention à ne pas confondre la notion de généricité avec celle d'hétérogénéité. La première désigne la capacité à contenir des éléments d'un même type que l'on peut choisir en le fixant au moment de la déclaration. La seconde désigne la capacité à contenir des éléments de types différents.
Supposons maintenant que nous devions utiliser des formes d'information qui ne font pas partie de type de bases : les listes chaînées, les matrices, rationnels, les arbres, de l'génome, les couleurs, etc. Comment créer les éléments nécessaires au stockage de tel information quand un simple tableau ou un simple enregistrement ne suffisent plus ?
Dynamicité, généricité, hétérogénéité et la création de nouveau types non-élémentaires sont autant de problèmes traités dans ce wikilivre.
Problématique
[modifier | modifier le wikicode]- Comment stocker des données en mémoire en prenant de la mémoire de façon dynamique, en fonction du besoin. Ceci afin d'éviter les dépassements de mémoire et de ne pas mobiliser des ressources machines (parfois précieuses) inutilement.
- Comment stocker en mémoire une donnée si aucun type n'est intégré dans le langage ? Les langages ne peuvent intégrer toutes les structures de données possibles. Il faut parfois les implémenter soi-même.
- Comment, au sein d'une structure, gérer sa généricité, son hétérogénéité.
Pré-requis
[modifier | modifier le wikicode]- Algorithmique impérative : indispensable
- Algorithmique fonctionnelle : facultatif mais fortement conseillé (notamment pour l'implémentation de structures dynamiques)
- Architecture des ordinateurs : au moins les notions élémentaires sur la mémoire : mémoire statique/dynamique, représentation de valeurs en mémoire, codage sur un (entiers, caractères) ou plusieurs octets (chaînes de caractères), adressage (sur n bits)...
Enregistrements
Vous devez déjà être familier avec la notion de type enregistrement qui a du être abordée lors de l'étude de l'algorithmique impérative. Voici néanmoins un rappel :
Première approche
[modifier | modifier le wikicode]L'enregistrement est une façon de créer un nouveau type, ou encore un méta-type c'est-à-dire un type qui contient d'autres variables (appelées champs) de types déjà définis.
Toute variable déclarée avec ce nouveau type utilise alors une zone mémoire suffisante pour y stocker tous les champs de l'enregistrement.
Spécification
[modifier | modifier le wikicode]On déclare un nouveau type dans la partie Types comme suit :
identifiant_du_type = enregistrement identifiant_premier_champ : type_premier_champ identifiant_deuxième_champ : type_deuxième_champ ... fin
on peut ensuite déclarer les variables de ce nouveau type enregistrement normalement :
identifiant_variable : identifiant_du_type
Pour accéder à un champ de la variable enregistrement, nous utiliserons l'expression :
identifiant_variable.identifiant_champ
Cette expression est du type de identifiant_champ soit type_champ.
Exemple
[modifier | modifier le wikicode]Supposons que nous voulons un nouveau type couple (de deux entiers). Nous allons déclarer le type couple comme suit :
couple = enregistrement a : entier b : entier fin
Supposons maintenant que nous avons le lexique suivant :
Lexique c : couple
Si nous assignons :
c.a ← 1 c.b ← 2 afficher(c.a) (* affichera 1 *)
Un exemple d'implémentation : les rationnels
[modifier | modifier le wikicode]Nous souhaitons implémenter le type rationnel. Pour cela, nous allons utiliser un type enregistrement composé de deux champs de types entier : numérateur et dénominateur.
Ensuite, nous réaliserons :
- un constructeur, permettant de créer un rationnel à partir de son numérateur et de son dénominateur,
- deux "accesseurs" c'est à dire des fonctions retournant la valeur des champs d'un enregistrement. Elles renvoient le numérateur ou le dénominateur d'un rationnel passé en paramètre,
- prédicat de nullité d'un rationnel, d'égalité de deux rationnels,
- somme, différence, produit et quotient de deux rationnels,
- réduction renvoyant sous sa forme réduite un rationnel donné.
rationnel = enregistrement num : entier (* numérateur *) den : entier (* dénominateur *) fin
(* Constructeur *)
fonction creerRationnel(a, b : entiers)
lexique
nouveauRationnel : rationnel
debut
si b=0 alors
erreur("le dénominateur ne peut être nul")
sinon
nouveauRationnel.num ← a
nouveauRationnel.den ← b
finsi
fin
(* Accesseur *) fonction numerateur(r : rationnel) retourner r.num fin
(* Accesseur *) fonction dénominateur(r : rationnel) retourner r.den fin
fonction calculPgcd(a,b : entier)
lexique
t : entier
debut
si a < b alors
t ← a
a ← b
b ← t
finsi
tant que b > 1
t ← a modulo b
si t=0 alors
retourner b
finsi
a ← b
b ← t
fin tant que
retourner b
fin
(* Simplifier la fraction *)
fonction reduire(r : rationnel)
lexique
pgcd : entier
debut
pgcd ← calculPgcd(r.num, r.den)
r.num ← r.num / pgcd
r.den ← r.den / pgcd
retourner r
fin
(* Prédicat d'égalité *) fonction sontEgaux(p,q : rationnel) lexique p_reduit : rationnel (* forme réduite de p *) q_reduit : rationnel (* forme réduite de q *) début p_reduit ← reduire(p) q_reduit ← reduire(q) retourner (p_reduit.num = q_reduit.num) et (p_reduit.den = q_reduit.den) fin
(* Prédicat de nullité *) fonction estNul(r : rationnel) debut retourner (r.num = 0) fin
(* Calcul de la somme *) fonction somme(p, q : rationnel) debut (* a/b + c/d = ( a*d+c*b)/(b*d) *) retourner reduire(creerRationnel(p.num*q.den+q.num*p.den, p.den*q_den)) fin
Pointeurs
Retour sur la gestion des variables en mémoire
[modifier | modifier le wikicode]Pour aborder la notion de pointeur, il convient de revenir sur la notion de variable. Nous devons regarder de plus près ce qu'il se passe au niveau de la machine quand on déclare une variable ou qu'on l'assigne.
Faisons donc un retour sur l'architecture des ordinateurs. Les variables sont stockées dans une mémoire statique : on peut représenter cette mémoire par un tableau. Chaque ligne de ce tableau est une "case" mémoire c'est à dire une zone où l'on peut stocker une donnée atomique (par exemple un entier). Dans la machine, toutes ces cases sont numérotées sur n bits (dépend de l'architecture de la machine en question). Ce numéro, attribué de façon unique à chaque case identifie la case : c'est l'adresse mémoire de la case.
Pour la suite nous utiliserons une machine 8 bits, bien que les machines PC grand public (x86) sont aujourd'hui (2006) des machines 32 bits, 64 bits pour les plus récentes.
Nous avons donc une mémoire dont l'adresse de chaque octet est codée sur un octet, ce qui nous fait 256 cases numérotées de 0 à 255, 00 à FF en hexadécimal (qu'on utilisera pour numéroter les cases mémoires)
Que se passe-t-il quand on exécute un programme P ? Et bien le système d'exploitation qui exécute P va allouer au programme autant de place que nécessaire dans cette mémoire statique pour que toutes les variables du lexique de P puisse y être stockées. Les cases ainsi réservées seront représentées sur fond gris.
Exemple
[modifier | modifier le wikicode]Avec le programme suivant : il s'agit de l'algorithme inversion de deux variables étudié en algorithmique impérative) :
Algorithme inversion_calcul Variables a : entier b : entier ...
Voici à quoi ressemble notre mémoire statique si notre machine code les entiers sur un octet (une case mémoire). Schéma de la mémoire avec deux cases a et b réservées :
À chaque assignation d'une variable, on affecte le contenu de la case mémoire dont l'adresse est contenu dans la variable. L'identifiant de la variable est en fait une abstraction, derrière l'identifiant d'une variable se cache l'adresse mémoire de son contenu.
La mémoire dynamique
[modifier | modifier le wikicode]En plus d'allouer à chaque programme une mémoire statique, le système d'exploitation alloue au programme P une mémoire dynamique. Dans notre exemple avec l'inversion de deux variables notre programme n'utilise que la mémoire statique. Nous aurions pu omettre de représenter sur nos schémas cette mémoire.
La mémoire dynamique a les mêmes caractéristiques que le mémoire statique telle que décrite précédemment. Les cases sont numérotées (nous supposerons là encore sur 8 bits : de 00 à FF)
Nous allons apprendre comment utiliser cette mémoire dynamique. Et ce, avec cet outil que sont les pointeurs.
Les pointeurs typés
[modifier | modifier le wikicode]Le pointeur est un nouveau type au même titres que les entiers, les caractères, chaînes de caractères, booléens et autres abordés en algorithmique impérative.
Il convient cependant de distinguer les pointeurs typés des pointeurs non-typés (également appelés génériques). Nous allons d'abord nous pencher sur les premiers et réserver les seconds pour plus tard.
Un pointeur typé indique le type de la donnée qu'il pointe. Il y a donc des pointeurs vers des entiers, des pointeurs vers des caractères, etc. Il convient d'affecter à des variables de types pointeur vers T uniquement des expressions de types pointeur vers T (tout comme on doit assigner à une variable de type entier une expression entière).
Spécification
[modifier | modifier le wikicode]On déclare un pointeur vers T (T : un type) comme suit :
Lexique identifiant_du_pointeur : ^T
On accède à la valeur pointée comme suit :
identifiant_du_pointeur^
Cette expression est donc du type pointé : T
Ecrire(identifiant_du_pointeur) afficherait l'adresse mémoire ou est stockée la donné pointée (souvent en sous la forme hexadécimale) : dans notre cours ce n'est d'aucune utilité.
Utilisation
[modifier | modifier le wikicode]Pour stocker des données dans notre mémoire dynamique, il faut réserver l'espace nécessaire.
p est une variable de type pointeur (vers T, un type quelconque : entier...) :
Lexique p : ^T (* un pointeur vers des données de type T *)
Au lancement du programme, il sera réservé dans la mémoire statique l'espace permettant de stocker ce pointeur. Voici la représentation de la mémoire à cet instant :
On réserve l'espace nécessaire pour stocker une variable de type T en faisait appel à l'instruction :
new(p)
Voici l'effet produit par new sur la mémoire.
Deux choses se sont produites :
- De la mémoire a été réservée pour stocker une donnée de type T (la case pointée est grisée).
- La variable p contient l'adresse mémoire de cet espace réservé (représenté par une flèche).
p contient alors l'adresse de l'espace qui nous pourront utilisé : on peut donc stocker le contenu de t en mémoire dynamique.
Pour utiliser l'espace pointé par p, nous utiliserons l'expression p^
p^:=???
L'espace pointé contient alors la valeur de l'expression qu'on a assigné :
On peut libérer l'espace : c'est à dire indiquer au système d'exploitation que cette partie de la mémoire dynamique n'est plus utilisée et qu'il peut désormais en faire ce qu'il veut. Pour cela on utilise la procédure « réciproque » de new :
delete(p)
On remarquera qu'après un delete la donnée stockée ainsi que le pointeur restent en mémoire : la seule chose qui change est que l'espace en mémoire dynamique n'est plus réservé. La donnée pointée peut donc être écrasée. La valeur de p^ restera en mémoire tant que le système d'exploitation n'aura pas décidé d'attribuer cet espace. Remarquez que demander au processeur de supprimer les contenus qui ont été stockés serait une perte de temps puisque si cette partie de la mémoire venait à être utilisé, les données serait écrasées de toute façon.
Remarque : l'utilité de ce qui est expliqué dans cette partie « utilisation » peut échapper au lecteur. En effet, cette partie sert seulement à donner les procédures new et delete. Stocker la valeur de t dans la mémoire dynamique n'a aucun intérêt en soi puisque la valeur est déjà dans t. L'important est de comprendre comment (par new et delete) on peut stocker et lire des informations en mémoire dynamique.
Exemple avec des entiers
[modifier | modifier le wikicode]Remarque : encore une fois ce programme n'est d'aucune utilité. On pourrait en faire un équivalent sans utiliser de pointeurs. Le but est d'expliquer les mécanismes décrits précédemment.
Algorithme Exemple Lexique a : entier b : entier p1 : ^entier p2 : ^entier Début a:=1 new(p1) (* on réserve de l'espace pour stocker un entier *) p1^:=a (* stocke 1 dans la zone mémoire pointée par p1 *) ecrire(p1^) (* affiche 1 *) a:=2 ecrire(p1^) (* affiche 1 *) p2:=p1 (* p2 va pointer la zone mémoire pointée par p1 *) ecrire(p2^) (* affiche 1 *) p2^:=3 (* on place 3 dans la zone mémoire pointée par p2 *) ecrire(p1^) (* affiche 3 *) delete(p1) (* on libère la zone pointée par p1 et donc la zone pointée par p2 *) (* a se stade : plus aucune zone mémoire n'est réservée dans la mémoire dynamique *) new(p1) new(p2) p1^:=4 p2^:=p1^+1 ecrire(p2^) (* affiche 5 *) (* il est d'usage de libérer au maximum la mémoire dynamique : *) delete(p1) delete(p2) Fin
Les pointeurs génériques
[modifier | modifier le wikicode]Un pointeur générique est un type de pointeur particulier puisqu'il ne donne pas d'information sur ce qu'il pointe. C'est simplement une adresse vers une zone mémoire.
Spécification
[modifier | modifier le wikicode]Il suffit de déclarer un pointeur comme suit
Lexique identifiant_du_pointeur : pointeur
Utilisation
[modifier | modifier le wikicode]Les pointeurs typés sont également des adresses mémoires donc on peut assigner les uns aux autres.
Lexique p : pointeur p_T : ^T
Ces opérations sont possibles :
p:=p_T p_T:=t_T
Cependant, on ne peut utiliser les procédures new() et delete() en leur passant un pointeur générique en paramètre. En effet, le type de la donnée pointée étant inconnu le système d'exploitation de peut savoir combien d'espace réservé.
Exemple avec des entiers
[modifier | modifier le wikicode]Algorithme exemple Lexique p : pointeur p_entier : ^entier début new(p_entier) p_entier^:=1 p:=p_entier p_entier:=p ecrire(p_entier^) (* affiche 1 *) fin
Les effets de bord
[modifier | modifier le wikicode]Que se passe-t-il ?
Algorithme bogue Lexique p : pointeur p_entier : ^entier p_caractere : ^caractere début new(p_entier) p_entier^:=2645 p:=p_entier p_caractere:=p (* pas de problème : on assigne une adresse mémoire à un pointeur (typé) *) (* Jusqu'ici aucun problème nous n'avons fait que des opérations permises *) ecrire(p_caractere^) (* ???? *) fin
Ressources
Wikilivres
[modifier | modifier le wikicode]Bibliographie
[modifier | modifier le wikicode]- Algorithmes et structures de données : cours et exercices corrigés en langage C / Michel Divay. - Paris : Dunod, 1999. - 328 p. : ill. n. et bl. ; 24 cm. - (Sciences sup. Informatique). La couv. porte en plus : "2e cycle, écoles d'ingénieurs". Bibliogr. p. 321-322. Index. ISBN 2-10-004277-7 (Br.)
- Structures de données en C++ / John Hubbard ; trad. de l'américain Virginie Maréchal. - Paris : Dunod, 2003. - X-405 p. : ill. n. et bl. ; 27 cm. - (Schaum's). ISBN 2-10-006938-1 (Br.)
- "Structures de données en Java, C++ et Ada95" C. Carrez, Masson 1997
Liens externes
[modifier | modifier le wikicode] GFDL
|
Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans texte de dernière page de couverture. |