Listes chaînées
Une liste est une structure de données constituée de cellules
chaînées les unes aux autres par pointeurs.
Une liste simplement chaînée : une cellule est un
enregistrement qui peut être déclarée comme suit:
struct
structNode
Node{{
int
int data;
data; /*/*les
lesinformations
informations*/*/
struct
structNode
Node *next;
*next; /*/*lelelien
lien*/*/
};};
Une liste doublement chaînée
struct
structNode
Node{{
int
int data;
data; /*/*les
lesinformations
informations*/*/
struct
structNode
Node *next;
*next; /*/*lien
lienvers
verslelesuivant
suivant*/*/
struct
structNode
Node *prev;
*prev; /*/*lien
lienvers
versleleprécédent
précédent*/*/
};};
1
Structures de données dynamiques
typedef : mot réservé, typedef struct
typedef structNode
Node{{
int
int data;
data;
crée de nouveaux noms struct
structNode
Node *next;
*next;
de types de données }cellule;
}cellule;
Ex :
typedef char * cellule
cellule**new_node(int
new_node(intvalue)
value)
STRING; {{
fait de STRING un synonyme cellule
cellule**p;
p;
de "char * «
Portée : comme les variables. pp==(cellule
p=new struct Node; (cellule*)malloc(sizeof(cellule));
*)malloc(sizeof(cellule));
p->data
p->data==value;
value;
p->next
p->next==NULL;
NULL;
return
returnp;
p;
}}
2
Nouvelle cellule dans une liste chaînée vide
cellule
cellule*debut;
*debut; Denis\0
debut
debut==(cellule
(cellule*)
*)malloc
malloc(sizeof(cellule));
(sizeof(cellule)); NULL
strcpy
strcpy((debut->name,
debut->name,“Denis”);
“Denis”); debut
debut->next
debut->next==NULL;NULL;
Le début de la liste est indiqué par un pointeur indépendant (debut) et la fin par NULL
Nouvelle cellule en début de liste chaînée
cellule
cellule*prec;
*prec;
prec
prec==(cellule
(cellule*)
*)malloc
malloc(sizeof(cellule));
(sizeof(cellule));
strcpy
strcpy((prec->name,
prec->name,“Claire”);
“Claire”);
prec->next
prec->next==debut;
debut; Denis
Claire
debut = prec;
debut = prec; NULL
debut
prec 3
Nouvelle cellule après la
cellule prec
cellule
cellule*p;
*p;
pp==(cellule
(cellule*)
*)malloc
malloc(sizeof(cellule));
(sizeof(cellule));
strcpy
strcpy((p->name,
p->name,“Alfred”);
“Alfred”);
p->next
p->next==prec->next;
OK?
prec->next;
prec->next
prec->next==p; p;
Alfred
p Denis
Claire
Claire Denis
NULL
debut NULL
prec
debut
4
Parcourir une liste
void
voidparcours
parcours(struct
(structNode
Node*debut)
*debut) debut est un pointeur sur
{{ la cellule qui contient le
struct
structNode
Node*p;*p; premier élément de la
pp==debut;
debut;
while liste
while((pp!=
!=NULL)
NULL){{
printf
printf(“%s\n”,
(“%s\n”,p->name);
p->name); Liste identifier par l'adresse
pp==p->next;
p->next; de sa première cellule
}}
}}
Alfred Denis
Claire
NULL
debut
5
Structures et allocation
dynamique de mémoire :
listes, files, piles, etc..
Pas plus de variables que de pointeurs déclarés
Lorsque on veut créer dynamiquement des variables, on :
déclare un pointeur sur structure
dans la structure on définit un membre qui est lui-
même un pointeur (à l'aide duquel on pourra créer
dynamiquement une autre structure qui elle-même
contient un pointeur, etc …)
Exemple
struct ent {
int valeur;
struct ent * suivant;
};
struct ent * p1;
p1=NULL;
p1 = (struct ent *) malloc(sizeof(struct ent));
p1->valeur=1;
p1->suivant= (struct ent *) malloc(sizeof(struct ent));
p1->suivant->valeur=2;
p1->suivant->suivant= (struct ent *) malloc(sizeof(struct ent));
…..
p1=NULL; /*1*/
p1 = (struct ent *) malloc(sizeof(struct ent)); /*2*/
p1->valeur=1; /*3*/
p1->suivant= (struct ent *) malloc(sizeof(struct ent)); /*4*/
p1->suivant->valeur=2; /*5*/
p1->suivant->suivant= (struct ent *) malloc(sizeof(struct ent)); /*6*/
…..
valeur suivant
p1
p1 p1 1
p1 1 p1 1 p1 1
2 2
p1 1
Les valeurs sont accessibles par :
p1->valeur
p1->suivant->valeur
p1->suivant->suivant->valeur
Pb1 : on doit connaitre le nombre de (->suivant) au moment de l'écriture du pgm !!
Pb2 : quand doit on s'arrêter ?
rep : le dernier membre suivant doit être NULL.
struct ent {
int valeur;
struct ent * suivant;
};
struct ent * p1;
p1 = (struct ent *) malloc(sizeof(struct ent));
Syntaxe équivalente plus commode
typedef struct ent element , *pt ; //element et pt sont
des types
struct ent {
int valeur;
pt suivant;
};
pt p1;
p1 = (pt) malloc(sizeof(element);
Listes
Création d'une liste contenant les n premiers entiers
pt deb=NULL; pt paux;
for(i=1;i<=n;i++) {
paux= (pt) malloc (sizeof(element));
paux->valeur = i;
paux->suiv=deb;
deb=paux;
}
Parcours des éléments de la liste
paux=deb;
// on prend un pointeur auxiliaire pour ne pas perdre l'adresse de début de la
liste
While (paux!=NULL) {
printf("%d",paux->valeur);
paux=paux->suiv;
}
Attention: ne jamais perdre l'adresse du début de la liste
Listes : exemples de fonction
Fonction ajoutant une donnée en début de liste
void ajoutdeb (pt * d , int data) {
// doit être appelée avec le pointeur de début de la liste ex
: ajout(&deb,56)
pt paux;
paux =(pt) malloc(sizeof(element));
paux->valeur=data;
paux->suiv=*d;
*d=paux;
}
Listes : exemples de fonction
Fonction ajoutant une donnée en fin de liste
void ajoutfin (pt * d; int data) {
// appelée avec le pointeur de début de la liste Ex :
ajoutfin(&L,42);
pt paux,paux2;
paux=(pt) malloc(sizeof(element));
paux->valeur=data; `//attention priorité des opérateurs
paux->suiv=NULL;
if(*d==NULL) *d=paux; // cas d'une liste initialement
vide
else { // autres cas
paux2=*d;
while(paux2->suiv!=NULL) paux2=paux2->suiv;
paux2->suiv=paux;
}
}
Listes : exemples de fonction
Fonction retournant l'adresse d'une donnée présente dans
la liste
pt adresse1(pt d; int data) {
// doit être appelée avec le pointeur de début de la liste
p=adresse2 (L,42);
while(d->valeur!=data) d=d->suiv;
return(d);
}
Fonction retournant l'adresse d'une donnée dont on ne
sait si elle est présente ou pas dans la liste (dans ce
cas, la fonction renvoie NULL)
pt adresse2(pt d; int data) {
// doit être appelée avec le pointeur de début de la liste ex:
p=adresse2 (L,42);
while(d!=NULL)
if(d->valeur==data) return(d);
else d=d->suiv;
return(NULL);
}
Listes : exemples de fonction
Fonction supprimant la liste
pt detruit (pt * d) {
// doit être appelée avec le pointeur de début de la liste
while (*d!=NULL) {
paux=*d;
*d=(*d)->suiv;
free(paux);
}
}
Listes : exemples de
Fonction supprimant une donnée dans la liste
fonction
void detruit (pt * d, int data) {
// doit être appelée avec le pointeur de début de la liste ex: detruit (&L,42);
pt p,prec;
prec=NULL
p=*d;
while (p!=NULL) { *d
if (p->valeur!=data) { //on avance dans la liste
prec=p;
p=p->suiv;
}
else { //on a trouvé l'élément à supprimer
if(prec!=NULL) prec->suiv=p->suiv;
else *d =(*d)->suiv;
free(p); prec
return;
} p data
}}
