Algorithmes et
structures de données
10ème cours
Patrick Reuter
http://www.labri.fr/~preuter
Aujourd’hui
-Types de données dynamiques
- Pointeurs
- New et Dispose
- Type de données dynamiques
- Listes
Type : tableaux (angl. ARRAY)
- structure de données la plus connue
- structure homogène, chaque élément est du
même type de base
- occupe de la place successive dans la
mémoire
- « random access » = l’accès aux différents
éléments se fait à coût égal
• Tableau statique
• Tableau dynamique
• Tableau statique
Organisation de la mémoire
var points : array[1..10] of byte; {10 octets}
#536.870.911
#536.870.910
...
points[10] #2009 90
... Occupe de la place
successive
points[3] #2002 31 dans la mémoire
points[2] #2001 25
points[1] #2000 130
...
#0
points[index] #(2000+index-1)
• Tableau dynamique
var points : array of byte; {pointeur 4 octets}
var i : byte;
SetLength(points, 10);
points[0] := 130;
points[1] := 25;
… points[9] #129
...
points[2] #122
points[1] #121 25
points[0] #120 130
i #104 10
points #103 0
points #102 0
points #101 0
points #100 120
...
#0
jours[index] #(120+index)
Adresse d’une variable
Organisation de la mémoire
var a : byte; ( 1 octet (byte) )
#536.870.911
#536.870.910
...
#1.000
...
#5
#4
#3
#2
#1
#0
Organisation de la mémoire
var a : byte;
#536.870.911
#536.870.910
...
#1.000
...
#5
a #4
#3
#2
#1
#0
Organisation de la mémoire
var a : byte;
a := 97;
#536.870.911
#536.870.910
...
#1.000
...
#5
a #4 97
#3
#2
#1
#0
Organisation de la mémoire
var a : byte;
a := 97;
#536.870.911
#536.870.910
...
#1.000
...
#5
a #4 97
#3
#2
#1
#0
Comment connaître l’adresse de a ?
Addr(a)
Organisation de la mémoire
var a : byte;
a := 97;
p_a := Addr(a); { Sauvegarder l’adresse }
#536.870.911
#536.870.910
...
#1.000
...
#5
a #4 97
#3
#2
#1
#0
Comment connaître l’adresse de a ?
Addr(a)
var a : byte;
var p_a : ^byte; {4 octets, lire : pointeur vers a}
a := 97;
p_a := Addr(a); { Sauvegarder l’adresse }
#536.870.911
#536.870.910
« p_a pointe vers a »
p_a #1.003 0
p_a #1.002 0
p_a #1.001 0
p_a #1.000 4
...
#5
a #4 97
#3
#2
#1
#0
Comment connaître l’adresse de a ?
Addr(a)
var a : byte;
var p_a : ^byte; {4 octets, lire : pointeur vers a}
a := 97;
p_a := Addr(a); { Sauvegarder l’adresse }
p_a^ := 10; { Déréférencement }
#536.870.911
#536.870.910
p_a #1.003 0
p_a #1.002 0
p_a #1.001 0
p_a #1.000 4
...
#5
a #4 10
#3
#2
#1
#0
Comment connaître l’adresse de a ?
Addr(a)
var a : byte;
var p_a : ^byte; {4 octets, lire : pointeur vers a}
a := 97;
p_a := Addr(a); { Sauvegarder l’adresse }
p_a^ := 10; { affectation par déréférencement
}
a := 10; { affectation }
var a : byte;
var p_a : ^byte; {4 octets, lire : pointeur vers a}
a := 97;
p_a := Addr(a); { Sauvegarder l’adresse }
p_a^ := 10; { affectation par déréférencement
}
a := 10; { affectation }
C’est équivalent !!
Définitions
• Déclaration d’un pointeur vers un byte
var p_a : ^byte;
• Déréférencement d’un pointeur :
p_a^
• Connaître l’adresse d’une variable a
Addr(a); {ou bien }
@a;
Solution
var p_a : ^byte; {4 octets, lire :...
New(p_a);
p_a^ := 10; { affectation par déréférencement
}
#536.870.911
#536.870.910
« p_a pointe vers p_a^ »
p_a #1.003 0
p_a #1.002 0
p_a #1.001 0
p_a #1.000 0
...
...
#5
#4
#3
#2
#1
p_a^ #0 10
Solution
var p_a : ^byte; {4 octets, lire : pointeur vers a}
...
New(p_a);
p_a^ := 10; { affectation par déréférencement
}
...
Dispose(p_a); #536.870.911
{ Libérer la mémoire }
#536.870.910
p_a #1.003 0
p_a #1.002 0
p_a #1.001 0
p_a #1.000 0
...
...
#5
#4
#3
#2
#1
#0
Ebauche da la mémoire plus
compacte
var a : byte;
var p_a : ^byte; {4 octets, lire : pointeur vers a}
p_a := Addr(a); { Sauvegarder l’adresse }
p_a^ := 10; { Déréférencement }
#536.870.911
#536.870.910
« p_a pointe vers a »
p_a #1.003 0
p_a #1.002 0
p_a #1.001 0
p_a #1.000 4
...
#5
a #4 10
#3
#2
#1
#0
Comment connaître l’adresse de a ?
Addr(a)
var a : byte;
var p_a : ^byte; {4 octets, lire : pointeur vers a}
p_a := Addr(a); { Sauvegarder l’adresse }
p_a^ := 10; { Déréférencement }
p_a a 10
…..
type p_t_musicien = ^t_musicien; bassiste.cle #42
t_musicien = record bassiste.cle #41
cle : integer; bassiste.cle #40
nom : string; ...
annee : integer; guitariste.suivant #35
suivant : p_t_musicien; guitariste.suivant #34
end;
guitariste.suivant #33
var guitariste : t_musicien;
guitariste.suivant #32
var bassiste : t_musicien; guitariste.annee #31
var chanteur : t_musicien; guitariste.annee #30
var musicien : t_musicien; guitariste.annee #29
guitariste.annee #28
guitariste.nom #27
guitariste.nom #26
guitariste.nom #25
guitariste.nom #24
guitariste.cle #23
guitariste.cle #22
guitariste.cle #21
guitariste.cle #20
...
#0
…..
type p_t_musicien = ^t_musicien; bassiste.cle #42
t_musicien = record bassiste.cle #41
cle : integer; bassiste.cle #40
nom : string; ...
annee : integer; guitariste.suivant #35 0
suivant : p_t_musicien; guitariste.suivant #34 0
end;
guitariste.suivant #33 0
guitariste.suivant #32 40
var guitariste : t_musicien;
var bassiste : t_musicien; guitariste.annee #31
var chanteur : t_musicien; guitariste.annee #30
var musicien : t_musicien; guitariste.annee #29
guitariste.annee #28
guitariste.cle := 1; guitariste.nom #27
... guitariste.nom #26
guitariste.suivant := Addr(bassiste);
guitariste.nom #25
guitariste.nom #24
guitariste.cle #23 0
guitariste.cle #22 0
guitariste.cle #21 0
guitariste.cle #20 1
...
#0
Ebauche da la mémoire plus
compacte
‘R’ ‘o’ ‘b’ ‘e’ ‘r’ ‘t’
guitariste cle 1 bassiste cle
nom nom
annee 1982 annee
suivant suivant
Type liste simplement chaînée
type
p_t_liste_simple = ^t_liste_simple;
t_liste_simple = record
cle : integer;
nom : string;
annee : integer;
...
suivant : p_t_liste_simple;
end;
element1
element1^ cle 1
var element1 : p_t_liste_simple;
New(element1); nom
element1^.cle := 1; annee
suivant
Type liste simplement chaînée
var element1 : p_t_liste_simple;
var element2 : p_t_liste_simple;
New(element1);
New(element2);
element1^.suivant := element2;
element2^.suivant := NIL;
element1 element2
element1^ cle element2^ cle
nom nom
annee annee
suivant suivant
Type liste simplement chaînée
var element3 : p_t_liste_simple;
New(element3);
element2^.suivant := element3;
element3^.suivant := NIL;
element1 element2 element3
element1^ cle element2^ cle element3^ cle
nom nom nom
annee annee annee
suivant suivant suivant
Type liste simplement chaînée
- structure de données trés connue
- N’occupe pas de la place successive dans la
mémoire
Type liste simplement chaînée
{ Création de n éléments dans une
New(element);
boucle : }
element^.suivant := NIL;
temp := element;
var element : p_t_liste_simple;
premier := element;
var temp : p_t_liste_simple;
Pour i de 1 à n-1 faire
var premier : p_t_liste_simple;
New(element);
var i : integer;
element^.suivant := NIL;
temp^.suivant := element;
temp := element;
Fin pour
element
temp
premier
cle
nom
annee
suivant
Type liste simplement chaînée
{ Création de n éléments dans une
New(element);
boucle : }
element^.suivant := NIL;
temp := element;
var element : p_t_liste_simple;
premier := element;
var temp : p_t_liste_simple;
Pour i de 1 à n faire
var premier : p_t_liste_simple;
New(element);
var i : integer;
element^.suivant := NIL;
temp^.suivant := element;
temp := element;
Fin pour
element
temp
premier
cle cle
nom nom
annee annee
suivant suivant
Type liste simplement chaînée
{ Création de n éléments dans une
New(element);
boucle : }
element^.suivant := NIL;
temp := element;
var element : p_t_liste_simple;
premier := element;
var temp : p_t_liste_simple;
Pour i de 1 à n faire
var premier : p_t_liste_simple;
New(element);
var i : integer;
element^.suivant := NIL;
temp^.suivant := element;
temp := element;
Fin pour
element
temp
premier
cle cle
nom nom
annee annee
suivant suivant
Type liste simplement chaînée
{ Création de n éléments dans une
New(element);
boucle : }
element^.suivant := NIL;
temp := element;
var element : p_t_liste_simple;
premier := element;
var temp : p_t_liste_simple;
Pour i de 1 à n faire
var premier : p_t_liste_simple;
New(element);
var i : integer;
element^.suivant := NIL;
temp^.suivant := element;
temp := element;
Fin pour
element
temp
premier
cle cle
nom nom
annee annee
suivant suivant
Type liste simplement chaînée
{ Création de n éléments dans une
New(element);
boucle : }
element^.suivant := NIL;
temp := element;
var element : p_t_liste_simple;
premier := element;
var temp : p_t_liste_simple;
Pour i de 1 à n faire
var premier : p_t_liste_simple;
New(element);
var i : integer;
element^.suivant := NIL;
temp^.suivant := element;
temp := element;
Fin pour
premier
cle cle cle cle
nom nom nom
annee annee … annee
nom
annee
suivant suivant suivant suivant
