Chap4.2-Listes-def-creat-2p.pdf

(248 KB) Pobierz
Algorithmique & programmation
Chapitre 4 : Listes chaînées
Définitions d’une liste chaînée
Création d’une liste chaînée
Liste linéaire chaînée
!!
Une liste linéaire chaînée est un ensemble
de cellules chaînées entre elles
"!
On connaît l’adresse de la première cellule qui
est l’adresse de la liste (variable liste)
!!
Exemple
liste!
liste
contient l!adresse de la première cellule"
a
"
b
"
c
"
d
"
cellule sans successeur (dernière de la liste)"
Chapitre 4.2
2
Notation
!!
liste
+
"!
suite des éléments contenus dans la liste dont
l’adresse de la première cellule se trouve dans
la variable liste
!!
Exemple
liste!
a
"
b
"
c
"
d
"
"!
liste
+
=
(a, b, c, d)
Chapitre 4.2
3
Notations
!!
Si
liste
=
nil
"!
liste
+
=
<> [la liste est vide]
!!
Une liste contient autant de cellules que
d’éléments
!!
Champ
suivant
d’une cellule
=!
adresse de la cellule suivante
!!
Champ
suivant
de la dernière cellule
=!
nil
Chapitre 4.2
4
Accès aux éléments d’une liste
!!
L'adresse de la première cellule, dans la
variable
liste,
permet l'accès à tous les
éléments
"!
liste!.info
"!
liste!.suivant!
"!
liste!.suivant!.info
"!
etc.
!!
Rappel
:
liste!.info
et
liste!.suivant
ne sont
pas définis si
liste
=
nil
Chapitre 4.2
5
Notations
!!
Relations d’ordre
"!
a
<
liste
+
signifie
a
<
tous les éléments de
liste
+
"!
on a aussi toutes les autres relation d’ordre
!!
Notion de
sous-liste
"!
Si
liste
+
=
(a, b, c, d)
"!
alors
!!
(b, c) est une sous-liste de
liste
+
!!
(b, d) n’est pas une sous-liste de
liste
+
Chapitre 4.2
6
Notation
liste!
p!
a
"
b
"
c
"
d
"
!!
p
+
=
(c, d)
!!
p
-
liste
=
(a, b)
"!
si
p
-
liste
n’est pas ambiguë, on écrit
p
-
!!
liste
+
=
(a, b, c, d)
!!
liste
-
=
()
Chapitre 4.2
En particulier"
si
liste = nil
alors
liste
+
=
<>"
7
Exemple d’ambiguïté pour
p
-
liste!
liste’!
p!
a
"
a!
"
b
"
b!
"
c
"
d
"
!!
p
-
est ambiguë, car on ne sait pas si c’est
"!
p
-
liste
=
(a, b)
ou
"!
p
-
liste’
=
(a’, b’)
Chapitre 4.2
8
Création d’une liste (algo)
!!
On veut créer la liste chaînée qui représente
(a, b), à partir du dernier élément
1.
créer une liste vide d’adresse
liste
"!
liste := nil ;
liste
"
2.
créer une liste, d’adresse
liste
, contenant
b
"!
nouveau (p) ;
"!
p!.info :=
b
;
"!
p!.suivant := liste ;
"!
liste := p ;
Chapitre 4.2
9
p"
b"
liste
"
Création d’une liste (algo)
3.
créer une liste d’adresse liste contenant (a, b)
"!
nouveau (p) ;
"!
p!.info :=
a
;
p"
a"
liste"
b"
"!
p!.suivant := liste ;
p"
a"
liste"
b"
"!
liste := p ;
p"
a"
liste"
Chapitre 4.2
10
b"

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin