Les pointeurs & les listes chaînées
Introduction
Toute variable déclarée dans un algorithme est localisée dans la mémoire RAM à une adresse définie , allouée au moment de la déclaration .
Il existe deux méthodes d'allocation de la mémoire :
Allocation statique :
Le système à la déclaration de variables alloue des adresses qui resterons fixes pendant toute la durée d'exécution .
Allocation dynamique :
Dans ce cas le système à la déclaration d'une variable de type pointeur, n'alloue aucune adresse c'ad ne fait aucune réservation de mémoire , la réservation se fera à la demande pendant l'exécution du programme (grâce à l'instruction Allouer).
Il existe deux méthodes d'allocation de la mémoire :
Allocation statique :
Le système à la déclaration de variables alloue des adresses qui resterons fixes pendant toute la durée d'exécution .
Allocation dynamique :
Dans ce cas le système à la déclaration d'une variable de type pointeur, n'alloue aucune adresse c'ad ne fait aucune réservation de mémoire , la réservation se fera à la demande pendant l'exécution du programme (grâce à l'instruction Allouer).
I. Les pointeurs
I.1 Définition d'un pointeur :
Un pointeur c'est une adresse référençant (pointe vers) une structure de données de type associé .
I.2 Déclration d'un pointeur ;
Var <nom_pointeur> : ^type_associé
exp : Var P:^entier
(P est un pointeur qui contient une adresse qui pointe vers un entier)
exp : Var P:^entier
(P est un pointeur qui contient une adresse qui pointe vers un entier)
I.3 Opérations sur les pointeurs :
1.3.1 L'instruction Allouer :
Language Algorithmique :
Allouer (<nom_pointeur>) : permet d'allouer un espace mémoire pour le pointeur .
exp : Allouer(P)
exp : Allouer(P)
Language C :
<nom_pointeur>=malloc (sizeof (<type_élément>) )
exp : P=malloc(sizeof(int))
exp : P=malloc(sizeof(int))
1.3.2 L'instruction Libérer :
Language Algorithmique :
Libérer(<nom_pointeur>) : permet de libérer l'espace mémoire associé au pointeur .
exp : Libérer(P)
exp : Libérer(P)
Language C :
free (<nom_pointeur>)
exp : free(P)
exp : free(P)
II. Les listes simplement chaînées
II.1 Définition :
Une liste chaînée est une suite d'éléments liées entre eux par des liens de chaînage déclarés comment pointeurs , où chaque pointeur contient l'adresse du prochain élément et ainsi de suite jusqu'au dernier élément dont le pointeur est à NILL (ne pointe vers aucun autre élément )
La liste chaînée est accessible à partir du pointeur appelé tête (ou bien sommet) qui pointe toujours vers le premier élément de la liste chaînée .
La liste chaînée est accessible à partir du pointeur appelé tête (ou bien sommet) qui pointe toujours vers le premier élément de la liste chaînée .
II.2 Déclaration :
Le type liste c'est un enregistrement qui contient les information de chaque élément de la liste et un pointeur vers le prochain élément .
Language Algorithmique :Type Liste = ^Elément
Elément = Enregistrement info : <type_élément> suivant : Liste (pointeur vers le prochain élément) Fin Enreg ; exp :
Type Liste = ^Elément Elément = Enregistrement Nom_erudiant : chaine[20] Matricule : entier suivant : Liste Fin Enreg ; |
Language C :typedef struct Liste
{ <type_élément> info ; struct Liste *suivant ; }Liste; typedef struct Liste { char etudiant[20] ; int matricule ; struct Liste *suivant ; }Liste; |
II.3 Création d'une liste simplement chaînée :
Il existe deux méthodes de création d'une liste :
Méthode FIFO (First in first out) :
Le principe appliqué est celui d'une file d'attente , on crée d'abord le premier élément qui est la tête (sommet) de la liste , ensuite à la création du 2ème élément (qu'on met son pointeur suivant à NILL ) on doit mettre à jour le lien de chaînage , le premier élément va recevoir l'adresse du deuxième élément nouvellement créé , et ainsi de suite jusqu'au n ème élément de la liste .
Language Algorithmique : |
Déroulement : |
Procédure CréaList FIFO (E/ n:entier S/ tête:Liste)
Var tête,P,Q : Liste Début //Création du premier élément tête et mettre l'adresse suivant à NILL (1) Allouer (tête) Lire (tête^.info) tête^.suivant=NILL (2) P←tête //Création des autres éléments et mise à jour des liens de chainage Pour i:=2 à n Faire (3) Allouer (Q) Lire (Q^.info) P^.suivant←Q (4) P←P^.svt Fait P←NILL Q←NILL Fin Language C :struct liste* CreatListFIFO(int n)
{ liste *p,*q,*tete; int i; tete=malloc(sizeof(struct liste)); printf("saisir la premiere valeur \n"); scanf("%d",&tete->info); tete->suivant=NULL; p=tete; for(i=1;i<n;i++) { p=malloc(sizeof(struct liste)); printf("Saisir une autre val \n"); scanf("%d",&p->info); p->suivant=NULL; tete->suivant=p; tete=p; }; P=NULL; Q=NULL; return tete; }; |
|
Méthode LIFO (First in last out) :
Le principe appliqué est celui d'une pile , où le premier élément créé sera le dernier . Donc à chaque fois on doit déplacer le pointeur tête au dernier .
Language Algorithmique :Prcédure CréaList LIFO (E/ n:entier S/ tête:Liste)
Var tête,P : Liste Début Allouer (tête) Lire (tête^.info) tête^.suivant=NILL P←tête Pour i:=1 à n Faire Allouer (P) Lire (P^.info) P^.suivant←P tête←tête^.svt Fait Fin |
Language C :struct liste* CreatListLIFO(int n)
{ struct liste *p,*tete; int i; tete=malloc(sizeof(struct liste)); printf("saisir la premiere valeur \n"); scanf("%d",&tete->info); tete->suivant=NULL; p=tete; for(i=1;i<n;i++) { p=malloc(sizeof(struct liste)); printf("Saisir une autre val \n"); scanf("%d",&p->info); p->suivant=tete; tete=p; }; return (tete); }; |
II.4 Affichage des éléments d'une liste :
Language Algorithmique :Procédure Affichage (E/tete : Liste)
Var P:Liste Début P←tête Tantque (P!=NILL) Faire Ecrire (P^.info) P←P^.suivant Fait Fin |
Language C :void Affichage(struct liste *tete)
{ struct liste *p; p=tete; while(p!=NULL) { printf("%d ",p->info); p=p->suivant; } } |
Dans ce qui suit on prendra comme exemple une liste qui contient des valeurs entières :
Type Liste =^Elément
Elément=Enregistrement
val : entier
svt : Liste
Fin Enreg
Type Liste =^Elément
Elément=Enregistrement
val : entier
svt : Liste
Fin Enreg
II.5 Insertion d'un élément dans une liste :
Insertion avant un élément donnée :
Procédure Insérer_Avant(E/S tête:Liste E/info:entier)
Var P, P_Prec,P_new : Liste
Début
//On avance jusqu'à ce qu'on trouve l'élément recherché
Tantque (P!=NILL) ET (P^.val != info) Faire
P_Prec←P
P←P^.svt
Fait
Si (P^.val != info) Alors Ecrire("Elément non éxistant")
Sinon //L'élément existe , on alloue le nouvel élément à insérer avant l'élément trouvé
Allouer (P_new)
Lire (P_new^.val)
P_new^.svt←NILL
Si (P=tête) Alors //Cas ou l'insertion se fera au début
P_new^.svt←P_Prec
tete←P_new
Sinon //Cas ou l'insertion se fera au milieu ou à la fin
P_Prec^.svt←P_new
P_new^.svt←P
Fsi
Fsi
Fin
Var P, P_Prec,P_new : Liste
Début
//On avance jusqu'à ce qu'on trouve l'élément recherché
Tantque (P!=NILL) ET (P^.val != info) Faire
P_Prec←P
P←P^.svt
Fait
Si (P^.val != info) Alors Ecrire("Elément non éxistant")
Sinon //L'élément existe , on alloue le nouvel élément à insérer avant l'élément trouvé
Allouer (P_new)
Lire (P_new^.val)
P_new^.svt←NILL
Si (P=tête) Alors //Cas ou l'insertion se fera au début
P_new^.svt←P_Prec
tete←P_new
Sinon //Cas ou l'insertion se fera au milieu ou à la fin
P_Prec^.svt←P_new
P_new^.svt←P
Fsi
Fsi
Fin
Insertion après un élément donnée :
Procédure Insérer_Après(E/S tête:Liste E/val:entier)
Var P, P_new : Liste
Début
//On avance jusqu'à ce qu'on trouve l'élément recherché
Tantque (P!=NILL) ET (P^.val != info) Faire
P←P^.svt
Fait
Si (P^.val != info) Alors Ecrire ("Elément non éxistant")
Sinon //L'élément existe , on alloue le nouvel élément à insérer après l'élément trouvé
Allouer (P_new)
Lire (P_new^.val)
P_new^.svt←NILL
Si (P=tête) Alors //Cas ou l'insertion se fera au début
tete^.svt←P_new
P_new^.svt←tête^.svt
Sinon //Cas ou l'insertion se fera au milieu ou à la fin
P^.svt←P_new
P_new^.svt←P^.svt
Fsi
Fsi
Fin
Var P, P_new : Liste
Début
//On avance jusqu'à ce qu'on trouve l'élément recherché
Tantque (P!=NILL) ET (P^.val != info) Faire
P←P^.svt
Fait
Si (P^.val != info) Alors Ecrire ("Elément non éxistant")
Sinon //L'élément existe , on alloue le nouvel élément à insérer après l'élément trouvé
Allouer (P_new)
Lire (P_new^.val)
P_new^.svt←NILL
Si (P=tête) Alors //Cas ou l'insertion se fera au début
tete^.svt←P_new
P_new^.svt←tête^.svt
Sinon //Cas ou l'insertion se fera au milieu ou à la fin
P^.svt←P_new
P_new^.svt←P^.svt
Fsi
Fsi
Fin
II.6 Suppression d'un élément dans une liste :
Procédure Supprimer(E/S tête:Liste E/val:entier)
Var P, P_Prec : Liste
Début
//On avance jusqu'à ce qu'on trouve l'élément recherché
Tantque (P!=NILL) ET (P^.val != info) Faire
P_Prec←P
P←P^.svt
Fait
Si (P^.val != info) Alors Ecrire("Elément non éxistant")
Sinon
Si (P=tête) Alors //Cas ou la suppression se fera au début
Libérer (P)
tete←NILL
Sinon //Cas ou la suppression se fera au milieu ou à la fin
P_Prec^.svt←P^.svt
Libérer (P)
Fsi
Fsi
Fin
Var P, P_Prec : Liste
Début
//On avance jusqu'à ce qu'on trouve l'élément recherché
Tantque (P!=NILL) ET (P^.val != info) Faire
P_Prec←P
P←P^.svt
Fait
Si (P^.val != info) Alors Ecrire("Elément non éxistant")
Sinon
Si (P=tête) Alors //Cas ou la suppression se fera au début
Libérer (P)
tete←NILL
Sinon //Cas ou la suppression se fera au milieu ou à la fin
P_Prec^.svt←P^.svt
Libérer (P)
Fsi
Fsi
Fin
III. Autres types de listes chainées :
Liste doublement chaînée :
Ce type de Liste contient deux pointeurs , un pointeur 'suivant' qui pointe vers le prochain élément , et un pointeur 'précédent' qui pointe vers l'élément précédant .
Déclaration d'une liste doublement chainée (bidirectionnellle) :
Type ListeBD=^Elément
Elément=Enregistrement
info :<type_elm>
prec : ListeBD
svt : ListeBD
Fin Enreg
Elément=Enregistrement
info :<type_elm>
prec : ListeBD
svt : ListeBD
Fin Enreg
Liste circulaire :
La liste circulaire c'est une liste simplement chainée dont le dernier élément pointe toujours vers le premier élément (tête) .
IV. Exercices d'application :
Exercice 1 : **
Soit deux listes chainées d'entiers positifs , écrire les AP qui permettent de vérifier si elles sont égales , similaires ou comparables .
- Deux listes sont égales si elles contiennent les mêmes éléments aux mêmes positions .
- Deux listes sont similaires si elles contiennent les mêmes éléments mais pas forcément aux mêmes positions .
- Deux listes sont comparables si l'ensemble des valeurs qu'elles contiennent est le même .
VOIR LA CORRECTION
1. Fonction Egale (E/ tête1,tête2 :Liste): Booléen Var P1,P2 Liste Début P1←tête1 P2←tête12 Tantque (P1!=NILL) ET (P2!=NILL) ET (P1^.info=P2^.info) Faire P1←P1^.svt P2←P2^.svt Fait Si (P1=NILL) ET (P2=NILL) Alors Retourner (Vrai) Sinon Retourner (Faux) FSi Fin //Langage C : int Egale(struct liste *l1,struct liste *l2) { struct liste *p1,*p2; p1=l1; p2=l2; while((p1!=NULL)&&(p2!=NULL)&&(p1->info=p2->info)) { p1=p1->svt; p2=p2->svt; } if((p1=NULL)&&(p2=NULL)) { return 1; }; else {return 0;}; } 2. Fonction Simmilaire (E/ tête1,tête2 :Liste): Booléen Var P1,P2 Liste nb1,nb2,nb : entier Début //On calcule le nombre d'éléments de chaque liste Tantque (P1!=NILL) Faire nb1←nb1+1 P1←P1^.svt Fait Tantque (P2!=NILL) Faire nb2←nb2+1 P2←P2^.svt Fait Si (nb1!=nb2) Alors Retourner (Faux) //On peut faire 'Simmilaire←faux' Sinon //On calcule le nombres d'éléments commun entre les deux listes et on le compare au nombre d'éléments de chaque liste Tantque (P1!=NILL) Faire Tantque (P2!=NILL) Faire Si (P1^.info=P2^.info) Alors nb←nb+1 FSi Fait Fait Si(nb=nb1) Alors Retourner(Vrai) FSi FSi Fin 3. FonctionComparable (E/ tête1,tête2 :Liste): Booléen Var P1,P2 Liste nb1,nb2,nb : entier Début //On calcule le nombre d'éléments de chaque liste Tantque (P1!=NILL) Faire nb1←nb1+1 P1←P1^.svt Fait Tantque (P2!=NILL) Faire nb2←nb2+1 P2←P2^.svt Fait //On calcule le nombres d'éléments commun entre les deux listes et on le compare au nombre d'éléments de chaque liste Tantque (P1!=NILL) Faire Tantque (P2!=NILL) Faire Si (P1^.info=P2^.info) Alors nb←nb+1 FSi Fait Fait Si (nb=nb1) ou (nb=nb2) Alors Retourner(Vrai) Sinon Retourner(Faux) FSi Fin |
Exercice 2 : **
1. Ecrire une action paramétrée qui lit n chaines de caractères d'un fichier de chaines et les stocke dans une liste chainée .
2. Ecrire une action paramétrée qui permet d'insérer une valeur entière dans une liste d'entiers triée d'ordre croissant , de sorte à garder l'ordre du tri (on suppose que la liste est triée d'ordre croissant ) .
3. Ecrire une action paramétrée qui permet d'éclater une liste de réels non triée en deux listes triées de point d'entrée T1 , T2 contenant respectivement les valeurs < X (donnée) et les valeurs >=X .
2. Ecrire une action paramétrée qui permet d'insérer une valeur entière dans une liste d'entiers triée d'ordre croissant , de sorte à garder l'ordre du tri (on suppose que la liste est triée d'ordre croissant ) .
3. Ecrire une action paramétrée qui permet d'éclater une liste de réels non triée en deux listes triées de point d'entrée T1 , T2 contenant respectivement les valeurs < X (donnée) et les valeurs >=X .
VOIR LA CORRECTION
1. Type Liste = ^Elément Elément = Enregistrement Mot : chaine[30] suivant : Liste (pointeur vers le prochain élément) Fin Enreg ; Procédure CréaListChaines (E /F: fichier de chaines S/ tête:Liste) Var tête,P,Q : Liste ch :chaine[30] Début Relire(F) Allouer (tête) Lire(F,ch) tête^.Mot←ch tête^.suivant=NILL P←tête Tantque (NonFDF(F)) Faire Allouer (Q) Lire(F,ch) P^.Mot←ch P^.suivant←Q P←P^.svt Fait P←NILL Q←NILL Fin 2. Procédure Insérer_suivant_ordre(E/S tête:Liste E/info:entier) Var P, P_Prec,P_new : Liste Début //On avance jusqu'à ce qu'on trouve la position de l'insertion Tantque (P!=NILL) ET (P^.val < info) Faire P_Prec←P P←P^.svt Fait Si P!=NILL) //On alloue le nouvel élément à insérer Allouer (P_new) P_new^.val←info P_new^.svt←NILL Si (P=tête) Alors //Cas ou l'insertion se fera au début P_new^.svt←P_Prec tete←P_new Sinon //Cas ou l'insertion se fera au milieu ou à la fin P_Prec^.svt←P_new P_new^.svt←P Fsi Fsi Fin |
Exercice 3 : *** ( Rattrapage USTHB 2016 )
Écrire une action paramétrée qui fusionne 3 listes chaînées triées d'ordre croissant sans allocation (sans utiliser l'instruction Allouer , c'ad mise à jour de liens de chainage uniquement ) .
Indice : Écrire une action paramétrée qui fusionne 2 listes chaînées sans allocation et faire l'appel 2 fois .
Indice : Écrire une action paramétrée qui fusionne 2 listes chaînées sans allocation et faire l'appel 2 fois .
VOIR LA CORRECTION
Fonction Fusion2Listes (E/ tête1 , tête2 : Liste ) :Liste Var P1,P2,P3:Liste Début //On retrouve la tête de la nouvelle liste Si (tête1^.info<tête2^.info) Alors tête3←tête1 tête1←tête1^.svt Sinon tête3←tête2 tête2←tête2^.svt FSi P3←tête3 Tantque (P1!=NILL) ET (P2!=NILL) Faire Si (P1^.info<P2^.info) Alors P3^.svt←P1 P1←P1^.svt P3←P3^.svt Sinon P3^.svt←P2 P2←P2^.svt P3←P3^.svt FSi Fait //Cas où on arrive à la fin de la liste 2 mais la liste 1 contient encore des éléments Tantque (P1!=NILL) Faire P3←P1 P1←P1^.svt P3←P3^.svt Fait //Cas où on arrive à la fin de la liste 1 mais la liste 2 contient encore des éléments Tantque (P2!=NILL) Faire P3^.svt←P2 P2←P2^.svt P3←P3^.svt Fait Retourner (tête3) Fin Fonction Fusion3Listes (E/ tête1 , tête2 ,tête3 : Liste ) :Liste Var P,tête:Liste Début P←Fusion2Listes (tête1 ,tête2) tête←Fusion2Listes (P ,tête3) Retourner (tête) Fin |
Exercice 4 : ***
On veut trier une liste d'entiers sans allocation en ordre croissant .
1. Ecrire une procédure Chercher_Min (E/tête:Liste S/PMin,PMin_Prec :Liste) qui cherche le minimum et son précédant .
2. En utilisant la procédure Chercher_Min écrire un algorithme qui permet de trier la liste de point d'entrée tête en ordre croissant .
1. Ecrire une procédure Chercher_Min (E/tête:Liste S/PMin,PMin_Prec :Liste) qui cherche le minimum et son précédant .
2. En utilisant la procédure Chercher_Min écrire un algorithme qui permet de trier la liste de point d'entrée tête en ordre croissant .
VOIR LA CORRECTION
1. Procedure Chercher_Min (E/tête : Liste S/P_Min,P_Min_Prec : Liste) Var PMin,PMin_Prec : Liste Début P_Min←P Min←tête^.info P←tête //On cherche le minimum Tantque (P!=NILL) Faire Si (P^.info<Min) Alors Min←P^.info PMin←P FSi Fait P←tête //On cherche le précédant Tantque (P!=Min) Faire PMin_Prec←P P←P^.svt Fait Fin 2. //Pour comprendre l'algorithme il suffit de le dérouler Algorithme Tri_Liste Var tête,L :Liste //On suppose que la liste est déjà triée Début Chercher_Min(tête,PMin,PMin_Prec) //On commence par fixer la tête (le minimum) ensuite trouver le minimum à enchainer avec le précédant ... Si (PMin!=tête) Alors PMin_Prec^.svt←PMin PMin^.svt←tête tête←P FSi L← tête Tantque (L^.svt!=NILL) Faire PMin←L Chercher_Min(l^.svt,PMin_Prec,PMin) PMin_Prec^.svt←PMin^.svt PMin^.svt←L^.svt L^.svt←P L←P Fin |
Exercice 5 : *** ( Examen USTHB 2016 )
Soit la structure suivante qui représente une liste de listes chaînées d'entiers positifs .
1. Faites la déclaration de la structure .
2. Écrire une action paramétrée qui décompose un nombre entier en binaire .
3. Écrire une action paramétrée "linéaire " qui permet de transformer la structure en liste linéaire .
4. A partir de la liste linéaire , écrire une action paramétrée qui crée une nouvelle liste qui contient les représentations binaires de chaque élément de la liste linéaire .
2. Écrire une action paramétrée qui décompose un nombre entier en binaire .
3. Écrire une action paramétrée "linéaire " qui permet de transformer la structure en liste linéaire .
4. A partir de la liste linéaire , écrire une action paramétrée qui crée une nouvelle liste qui contient les représentations binaires de chaque élément de la liste linéaire .
VOIR LA CORRECTION
11. Déclaration de la structure : La structure est une liste verticale (Liste 1) où chaque élément de cette liste pointe vers une liste chaînée horizontale (Liste 2), tout d'abord nous déclarons la liste horizontale (Liste 2) de chaque ligne puis nous déclarons la liste verticale (Liste 1) qui contient deux pointeurs : un pour le suivant de la liste 1 et l'autre pour le début de la liste horizontale (Liste 2) Type Liste2 =^Elément2 //Liste verticale Elément2=Enregistrement val : entier svt2 : Liste2 Fin Enreg Type Liste1 =^Elément1 Elément1=Enregistrement svt1 : Liste1 (pointeur vers le prochain élément de la liste 1 "la liste veticale" ) svt2 : Liste2 (pointeur vers le prochain élément de la liste 2 "la liste horizontale" ) Fin Enreg 2. Fonction Binaire (E/x: entier) Var T:Tableau[1..1000] x ,y ,nb ,k ,i :entier; Début //On utilise la méthode des divisions successives par 2 Tantque (X>0) Faire T[k]=X mod2 x←x div2 k←k+1 Fait i←nb //Les chiffres doivent être lues de droite à guauche Tantque (i>0) Faire y←y*10+T[i] i←i-1 Fait Retourner (y) Fin 3. Procedure Linéaire (E/S tête : Liste1) Var P1,Temp: Liste1 P2: Liste2 Début P1←tête tête←P1^.svt2 Tantque (P1!=NILL) Faire Temp←P1 P2←P1^.svt2 Tantque (P2!=NILL) Faire P2←P2^.svt2 Fait P1←P1^.svt1 P2^.svt2←P1^.svt2 Libérer(Temp) P2←P1^.svt2 Fait 4. Fonction CréaListBinaire (E/tête : Liste2 ) : Liste Var P,Q,L : Liste2 Début P←tête Allouer (tête2) tête2^.info←Binaire (tête^.info) tête2^.suivant=NILL L←tête2 //Création des autres éléments et mise à jour des liens de chainage Tantque (P!=NILL) Faire Allouer (Q) Q^.info←Binaire (P^.info) L^.suivant←Q L←L^.suivant P←P^.svt Fait L←NILL Q←NILL Fait Retourner(tête2) Fin |
Notez sur 5 :
Auteur :
Afrit Hani
Ce cours est mis à jour le 25/04/2018
Encore des points flous sur les listes chainées ?
Posez-nous toutes vos questions, et nous vous répondrons par mail.