Cours 7 Pointeurs, allocation dynamique et listes chaînées

Cours 7

Pointeurs, allocation dynamique

et listes chaînées

Les types vus jusqu'à présent (entier, flottant,…) permettaient d'utiliser des variables qui contenaient directement des valeurs.

1 – Les pointeurs

5a:entier

5a:entier p: pointeur sur entier

Une variable du type pointeur sur T contient, non pas une valeur, mais une adresse, adresse à laquelle on trouve une variable du type T.

Soit T un type quelconque (entier, flottant,…).

On note T* le type "pointeur sur T ". On pourra alors déclarer:p : T*

p est un pointeur sur T p va pouvoir contenir l'adresse mémoire d'une variable de type T

1 – Les pointeurs

*p signifie "valeur se trouvant à l'adresse p ".

Soit a de type T: a:T&a signifie "l'adresse de a".

Les pointeurs sont en fait des adresses mémoire.

1 – Les pointeurs

Exempleaux p1, p2 : entier*;aux a : entier;

a = 2;p1 = &a;p2 = p1;

*p1 = 5;écrire(*p2);écrire(*p2 == *p1);écrire(p2 == p1);

Que fait l'exemple suivant?

aux p : entier*;

*p = 2;

2 – L'allocation dynamique

Que fait l'exemple suivant?

aux p : entier*;

*p = 2;

2 – L'allocation dynamique

Comme les variables de type classique, les pointeurs ne sont

pas initialisés automatiquement!

p contient donc une adresse quelconque, c'est un pointeur qui pointe n'importe où.

Solution: il faut allouer dynamiquement des ressources, c'est-à-dire demander à réserver une zone mémoire durant l'exécution du programme,

ce que nous ne pouvions faire auparavant.

On utilisera pour cela le mot-clé nouveau().

nouveau(p) réserve la mémoire nécessaire au type pointé par p et fait pointer p vers cette zone mémoire.

Que fait l'exemple suivant?

aux p : entier*;

nouveau(p);

*p = 2;

2 – L'allocation dynamique

1 – IntroductionUne liste est une suite finie ordonnée d'éléments de même type. Les éléments sont repérés par leur rang dans la liste.

Nous avons déjà utilisé des listes, sous forme de tableau:

3 – Les listes chaînées

Nous allons maintenant définir une nouvelle représentation pour les listes:

les listes chaînées.

début

2 – Exemple de liste chaînéeUne liste chaînée est un ensemble d'éléments où chaque élément (sauf le dernier) est chaîné avec son successeur.

Pour accéder à une liste, il suffit de connaître l'adresse de son premier élément.

Pour rechercher un élément, on suit le chaînage jusqu'à ce qu'on atteigne l'élément voulu, ou la fin de la liste.

3 – Les listes chaînées

début

fin

3 – Construction d'une liste chaînéeConsidérons un article Fiche contenant un nom et un pointeur:

Fiche : type articlenom : texte;suiv : Fiche*;

fin Fiche

Écrivons maintenant la fonction construction() qui crée une liste chaînée d'une ou plusieurs Fiches, dans l'ordre inverse de leur saisie:

fonction construction() retourne Fiche*{S:renvoie la tête de la liste construite}aux début,cellule:Fiche*, nom:texte;début

début=NIL;écrire("Tapez un nom ou STOP pour arrêter");lire(nom);tant que nom!="STOP" faire

nouveau(cellule);(*cellule).nom =nom;(*cellule).suiv=début;début=cellule;lire(nom);

fait;retourne(début);

fin

3bis – Construction d'une liste chaînéeÉcrivons maintenant la fonction construction() qui crée une liste chaînée d'une ou plusieurs Fiches, dans l'ordre de leur saisie.Principe:

• on doit ajouter chaque nouvelle fiche en fin de liste• pour cela, on maintient un pointeur sur le dernier élément de la liste

4 – Affichage de la listeOn souhaite afficher la liste dans son ordre normal.Principe: on parcourt simplement la liste en affichant chaque cellule.Écrivons la procédure affiche(début: Fiche*) :

4bis – Affichage de la liste version récursiveOn souhaite afficher la liste dans son ordre normal.Principe:

• si la cellule courante est NIL, on quitte la fonction• sinon on affiche le contenu de la cellule courante, et on appelle

récursivement l'affichage de la cellule suivanteÉcrivons la procédure affiche(début: Fiche*) :

5 – Calcul de la longueur d'une listeUne liste de deux éléments a une longueur 2.Écrivons la fonction longueur(début: Fiche*)retourne entier :

fonction longueur(début: Fiche*)retourne entieraux lon: entier, courant: Fiche*;début

lon = 0;courant = début;

tant que courant != NIL fairelon = lon+1;courant = (*courant).suiv;

fait

retourne lon;fin

5bis – Calcul de la longueur d'une liste version récursiveUne liste de deux éléments a une longueur 2.Écrivons la fonction longueur(début: Fiche*)retourne entier :

6 – Recherche d'un élémentÉcrivons la fonction cherche(début: Fiche*, nom:texte) retourne booléen :

fonction cherche(début: Fiche*, nom:texte)retourne booléen

{renvoie VRAI si nom est dans la liste, FAUX sinon}aux courant: Fiche*;début

courant = début;

tant que courant!=NIL ET (*courant).nom!=nom fairecourant = (*courant).suiv;

fait

si courant==NIL alorsretourne FAUX;

sinonretourne VRAI;

fsifin

6bis – Recherche d'un élément version récursiveUne liste de deux éléments a une longueur 2.Principe:

• si la cellule courante est NIL, on renvoie FAUX• si la cellule courante est la cellule recherchée, on renvoie VRAI• sinon, on renvoie le résultat de l'appel récursif sur la cellule suivante

Écrivons la fonction cherche(début: Fiche*, nom:texte) retourne entier :

7 – Affichage de la liste inverséeOn souhaite afficher la liste dans l'ordre inverse.Écrivons la procédure afficheInverse(début: Fiche*) :

Pour afficher en ordre inverse, il nous faut mémoriser les éléments au fur et à mesure qu'on parcourt la liste.

SOLUTIONS:1. Utiliser un tableau (quelle taille?)2. Construire une autre liste chaînée en ordre inverse!

CONCLUSION: c'est compliqué!

7bis – Affichage de la liste inversée, version récursiveOn souhaite afficher la liste dans l'ordre inverse.Principe:

• si la cellule courante est NIL, on quitte la fonction• on appelle récursivement l'affichage de la cellule suivante,

PUIS, AU RETOUR DE CET APPEL RECURSIF,on affiche le contenu de la cellule courante.

Écrivons la procédure afficheInverse(début: Fiche*) :

7bis – Affichage de la liste inversée, version récursive

A B Cdébut NIL

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

7bis – Affichage de la liste inversée, version récursive

A B Cdébut NIL

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

7bis – Affichage de la liste inversée, version récursive

A B Cdébut NIL

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

7bis – Affichage de la liste inversée, version récursive

A B Cdébut NIL

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

7bis – Affichage de la liste inversée, version récursive

A B Cdébut NIL

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

7bis – Affichage de la liste inversée, version récursive

A B Cdébut NIL

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

7bis – Affichage de la liste inversée, version récursive

A B Cdébut NIL

procédure afficheInv(début: Fiche*)début

si début!=NIL alors

afficheInv((*début).suiv);

écrire((*début).nom);fsi

fin

8 – Insertion à la kième position d'une listeOn souhaite insérer une nouvelle cellule à la kième position d'une liste.Principe:

• si on veut insérer à la première position, la tête de la liste change• sinon, on doit se positionner sur la k-1ième cellule SI ELLE EXISTE

et réaliser l'insertion en modifiant les chaînages correctement.

Écrivons la procédureinsère(R début: Fiche*, V k:entier, V nom:texte,R erreur:booléen) :