Structures lineaires [ls] - Algorithmique

Karine Zampieri, Stephane Riviere

Unisciel algoprog Version 21 mai 2018

Table des matieres

1 Listes chainees 31.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Terminologie et representation . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Formes d’une liste chainee . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Recherche dans une liste chaınee . . . . . . . . . . . . . . . . . . . . . . . 61.5 Insertion dans une liste chaınee . . . . . . . . . . . . . . . . . . . . . . . 71.6 Suppression dans une liste chaınee . . . . . . . . . . . . . . . . . . . . . . 81.7 Comparaison entre tableaux et listes chaınees . . . . . . . . . . . . . . . 9

2 Piles 102.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2 Terminologie et utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Representation d’une pile par tableau . . . . . . . . . . . . . . . . . . . . 12

3 Files 133.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Terminologie et utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3 Representation d’une file par tableau . . . . . . . . . . . . . . . . . . . . 15

4 References generales 17

1

Unisciel algoprog – ls00cours-texte, May 21, 2018 2

Structures lineaires

Mots-Cles Structures lineaires �Requis Axiomatique imperative �Difficulte • • ◦

IntroductionCe module decrit les structures lineaires : listes, piles et files.

Figure 1 – http://static.commentcamarche.net/www.commentcamarche.net/faq/images/0-Anm7iJKj-dl-ex2-s-.png

Unisciel algoprog – ls00cours-texte, May 21, 2018 3

1 Listes chainees

1.1 Definitions

Voici quelques definitions de la liste chainee (linked list en anglais).

Wikipedia, fevrier 2017En informatique, une liste chainee designe une structure de donnees representant unecollection ordonnee et de taille arbitraire d’elements de meme type. L’acces aux elementsd’une liste se fait de maniere sequentielle : chaque element permet l’acces au suivant,contrairement au cas du vecteur dans lequel l’acces se fait de maniere absolue, par adres-sage direct de chaque cellule du dit vecteur.

Hubbard – ed. Schaum’sUne liste est un conteneur sequentiel capable d’inserer et de supprimer des elements loca-lement de facon constante, c.-a-d. independamment de la taille du conteneur. (Structuresde donnees en Java – Hubbard – ed. Schaum’s)

Fontaine – InterEditionsLes listes sont des conteneurs destines aux insertions s’effectuant en temps constantquelle que soit la position dans le conteneur. (La bibliotheque standard STL du C++ –Fontaine – InterEditions)

Cormen, Leiserson, Rivest – DunodUne liste chainee est une structure de donnees dans laquelle les objets sont arrangeslineairement, l’ordre lineaire etant determine par des pointeurs (ou references) sur leselements. (Introduction a l’algorithmique – Cormen, Leiserson, Rivest – Dunod)

Liste versus Liste chaineeDans la terminologie moderne, le terme liste est utilise pour denoter toute collectionsequentielle d’elements (il existe un premier element, un deuxieme, ...). Autrement dit,chaque element a une position precise dans la collection. En ce sens, un tableau ou unfichier sont egalement des listes !

Unisciel algoprog – ls00cours-texte, May 21, 2018 4

1.2 Terminologie et representation

Valeur, Suivant, Tete, QueueChaque element d’une liste chainee est compose de deux parties : la valeur proprementdite et un acces a l’element suivant. On accede au premier element de la liste via unezone speciale, la tete (head) de la liste chainee. Le dernier element n’ayant pas de suivant,il est appele la queue (tail) de la liste et on indique Nil dans la zone reservee a l’accesau suivant. Dans la litterature et selon les langages, on trouvera les notations null, nil...ou encore ∅.

Une liste L est manipulee via l’acces vers son premier element, que l’on notera tête(L).Si tête(L) vaut Nil, la liste est vide.

Representation schematiqueLa figure presente un exemple de liste chaınee et montre les consequences des operationsd’insertion et de suppression sur une telle structure de donnees.

• (a) Initialement la liste chaınee contient les valeurs 9, 6, 4 et 1.

• (b) Etat de la liste chaınee apres l’operation insertion(5).

• (c) Etat de la liste chaınee apres l’operation suppression(4).

9 6 4 1tete[L]

9tete[L] 6 4 15

9 1tete[L] 65

(a)

(c)

(b)

Representation des liensAu contraire du vecteur, il n’y a pas d’acces direct a un element (en donnant son indice) :il est necessaire de partir du premier element et de suivre les liens chaines. Mais commentrepresenter ce lien ? Cela depend du type de langage :

• En programmation procedurale (PP), on utilise la notion de pointeur (module@[Pointeurs et References]).

• En oriente-objet (OO), un element est represente par un objet dont un attribut estune reference (ou pointeur) vers l’objet representant l’element suivant.

Liste triee ou nonUne liste est triee ou non suivant que l’ordre lineaire des elements dans la liste corres-pond ou non a l’ordre lineaire des cles de ces elements.

Unisciel algoprog – ls00cours-texte, May 21, 2018 5

1.3 Formes d’une liste chainee

Liste bidirectionnelleDans une liste bidirectionnelle, dite aussi doublement chaınee, chaque element pos-sede, en plus, une reference a l’element precedent.

Representation schematiqueLa figure presente un exemple de liste bidirectionnelle et montre les consequences desoperations d’insertion et de suppression sur une telle structure de donnees.

• (a) Initialement la liste contient les valeurs 9, 6, 4 et 1.

• (b) Etat de la liste apres l’operation insertion(5).

• (c) etat de la liste apres l’operation suppression(4).

5 9(b) 6 14

5 9(c) 6 1

9 6 14(a)

tete[L]

tete[L]

tete[L]

Un des avantages est de faciliter grandement la suppression car il n’est plus necessaire deconnaıtre l’element precedent pour pouvoir le faire puisqu’on peut le retrouver a partirde l’element a supprimer.

Liste CirculaireSi le champ predecesseur de la tete de la liste pointe sur la queue et si le champ successeurde la queue pointe sur la tete, la liste est dite circulaire : elle est alors vue comme unanneau.

Unisciel algoprog – ls00cours-texte, May 21, 2018 6

1.4 Recherche dans une liste chaınee

L’algorithme rechercheListe(L,k) trouve le premier element de cle k dans la liste L par unesimple recherche lineaire et renvoie un iterateur sur cet element. Si la liste ne contientaucun element de cle k, il renvoie Nil.

Algorithme rechercheListe

Fonction rechercheListe ( L : Liste ; k : Elément ) : ItérateurDébut| x <- tête ( L )| TantQue ( x <> Nil Et clé ( x ) <> k ) Faire| | x <- successeur ( x )| FinTantQue| Retourner ( x )

Fin

RemarqueCet algorithme manipule aussi bien des listes simplement que doublement chaınees.

Unisciel algoprog – ls00cours-texte, May 21, 2018 7

1.5 Insertion dans une liste chaınee

Etant donne un element x| et une liste \lstinlineL@, l’algorithme insererListe inserex| en tête de la liste~\lstinlineL@.

Algorithme insererListe

Action insererListe ( DR L : Liste ; x : Elément )Début| successeur ( x ) <- tête ( L )| Si tête ( L ) <> nil Alors| | prédécesseur ( tête ( L ) ) <- x| FinSi| tête ( L ) <- x| prédécesseur ( x ) <- nil

Fin

RemarqueCet algorithme est ecrit pour les listes doublement chaınees. Il suffit d’ignorer les deuxinstructions concernant le champ predecesseur pour obtenir l’algorithme equivalent pourles listes simplement chaınees.

Unisciel algoprog – ls00cours-texte, May 21, 2018 8

1.6 Suppression dans une liste chaınee

L’algorithme supprimerListe elimine un element x d’une liste chaınee L. Cet algorithmea besoin d’un iterateur sur l’element x a supprimer. Si on ne possede que la cle de cetelement, il faut prealablement utiliser l’algorithme rechercheListe pour obtenir l’iterateurnecessaire.

Algorithme supprimerListe

Action supprimerListe ( DR L : Liste ; k : Itérateur )Début| Si prédécesseur ( x ) <> Nil Alors| | successeur ( prédécesseur ( x ) ) <- successeur ( x )| Sinon| | tête ( L ) <- successeur ( x )| FinSi| Si successeur ( x ) <> Nil Alors| | prédécesseur ( successeur ( x ) ) <- prédécesseur ( x )| FinSi

Fin

RemarqueCet algorithme est ecrit pour les listes doublement chaınees. L’algorithme equivalentpour les listes simplement chaınees est plus complique puisqu’avec les listes simplementchaınees nous n’avons pas de moyen simple de recuperer l’iterateur sur l’element quiprecede celui a supprimer.

Algorithme supprimerListe(Cas listes simplement chaınees)

Action supprimerListe ( DR L : Liste ; k : Itérateur )Début| Si x <> tête ( L ) Alors| | tête ( L ) <- successeur ( x )| Sinon| | y <- tête ( L )| | TantQue successeur ( y ) <> x Faire| | | y <- successeur ( y )| | FinTantQue| | successeur ( y ) <- successeur ( x )| FinSi

Fin

Unisciel algoprog – ls00cours-texte, May 21, 2018 9

1.7 Comparaison entre tableaux et listes chaınees

Aucune structure de donnees n’est parfaite, chacune a ses avantages et ses inconvenients.Le tableau presente un comparatif des listes simplement chaınees, doublement chaıneeset des tableaux, tries ou non, sur des operations elementaires. Les complexites indiqueessont celles du pire cas. Suivant les operations que nous aurons a effectuer, et suivant leursfrequences relatives, nous choisirons l’une ou l’autre de ces structures de donnees.

Efficacites respectives des listes chaınees et des tableaux

Liste chaınee simple Liste chaınee double Tableaunon triee triee non triee triee non trie trie

recherche(L,k) Θ(n)(a) a Θ(n)a Θ(n)a Θ(n)a Θ(1) b Θ(1)bΘ(n) c Θ(n) d

Insertion(L,x) Θ(1) Θ(n) e Θ(1) Θ(n)e ou Θ(n)c ouerreur f erreurf

suppression(L,x) Θ(n) Θ(n) Θ(1) Θ(1) Θ(n) g Θ(n)gsuccesseur(L,x) h Θ(n) i Θ(1) Θ(n)i Θ(1) Θ(n)i Θ(1)

Predecesseur(L,x) h Θ(n)i Θ(n) j Θ(n)i Θ(1) Θ(n)i Θ(1)Minimum(L) Θ(n)i Θ(1) Θ(n)i Θ(1) Θ(n)i Θ(1)Maximum(L) Θ(n)i Θ(n) k Θ(n)i Θ(n)k Θ(n)i Θ(1)

a. Dans le pire cas il faut parcourir tous les elements pour se rendre compte que la cle n’etait pasdans l’ensemble.

b. La cle etant l’indice de l’element dans le tableau.c. Dans le pire cas, il faut allouer un nouveau tableau et recopier tous les elements de l’ancien tableau

dans le nouveau.d. Dans le pire cas, l’insertion a lieu dans la premiere cas du tableau, et il faut decaler tous les

elements deja presents.e. Au pire, l’insertion a lieu en fin de liste.f. Au cas ou l’on veut effectuer une insertion dans un tableau deja plein et qu’il n’est pas possible

d’effectuer une allocation dynamique de tableau, comme en Fortran 77 ou en Pascal.g. Dans le pire cas on supprime le premier element du tableau et il faut decaler tous les autres

elements.h. Au sens de l’ordre sur la valeur des cles.i. Complexite de la recherche du maximum (ou du minimum) dans un ensemble a n elements.j. Complexite de la recherche du maximum dans un ensemble a n elements... car il faut entreprendre

la recherche du predecesseur depuis le debut de la liste.k. Il faut parcourir la liste en entier pour trouver son dernier element.

Unisciel algoprog – ls00cours-texte, May 21, 2018 10

2 Piles

2.1 Definition

PileStructure de donnees definie par un seul point d’acces (appele « sommet ») et les quatreoperations elementaires suivantes :

• « empiler » : Ajouter un element au sommet de la pile.

• « depiler » : Supprimer le dernier element ajoute a la pile.

• « sommet » : Acceder a la valeur du dernier element ajoute a la pile.

• « pilevide » : Tester si la pile est vide.

Elle met en oeuvre le principe « dernier entre, premier sorti » (Last-In, First-Out)

ExempleLa figure presente un exemple de pile et montre les consequences des operations empiler

et dépiler :

• (a) Initialement la pile contient les valeurs 3, 5 et 2

• (b) Etat apres l’operation empiler(6)

• (c) Etat apres l’operation empiler(1)

• (d) Etat apres l’operation dépiler qui renvoie la valeur 1

sommet

sommetsommet

3

5

2 sommet

(a)

3

5

2

(b)

3

5

2

3

5

2

6

1 1

6

(c) (d)

6

Unisciel algoprog – ls00cours-texte, May 21, 2018 11

2.2 Terminologie et utilisations

TerminologieLa pile (en anglais stack) est donc une collection de donnees de type dernier entre,premier sorti (en anglais LIFO, last in first out). L’analogie avec la pile de dossiers surun bureau est claire : les dossiers sont deposes et retires du sommet et on ne peut jamaisajouter, retirer ou consulter un dossier qui se trouve ailleurs dans la pile.

ConsequencesOn ne peut donc pas parcourir une pile, ou consulter directement le n-eme element. Lesoperations permises avec les piles sont donc peu nombreuses, mais c’est precisement laleur specificite : elles ne sont utilisees en informatique que dans des situations particulieresou seules ces operations sont requises et utilisees. Paradoxalement, on implementera unepile en restreignant des structures plus riches aux seules operations autorisees par lespiles.

UtilisationsDes exemples d’utilisations sont la gestion de la memoire par les micro-processeurs,l’evaluation des expressions mathematiques en notation polonaise inverse, la fonction« ctrl-Z » dans un traitement de texte qui permet d’annuler les frappes precedentes, lamemorisation des pages web visitees par un navigateur, etc. Nous les utiliserons aussipour parcourir les arbres et les graphes.

Unisciel algoprog – ls00cours-texte, May 21, 2018 12

2.3 Representation d’une pile par tableau

Il est facile d’implementer une pile au moyen d’un tableau. La seule difficulte dans cetteimplementation est la gestion des debordements de pile qui interviennent quand on tented’effecteur l’operation dépiler sur une pile vide et l’operation empiler sur un tableau co-dant la pile qui est deja plein. Ce dernier probleme n’apparaıt pas lorsque l’on implementeles piles au moyen d’une liste chaınee.

ExempleLa figure montre la representation d’une pile par un tableau :

• (a) Etat initial de la pile

• (b) Nouvel etat apres les actions empiler(7) et empiler(3)

• (c) Nouvel etat apres l’operation dépiler qui renvoie la valeur 3

5 6 2 9 7 3

1 2 3 4 5 6 8 97

P 5 6 2 9 7 3

1 2 3 4 5 6 8 97

P5 6 2 9

1 2 3 4 5 6 8 97

P

sommet[P] = 5sommet[P] = 6sommet[P] = 4

(a) (c)(b)

Algorithme pilevide

Fonction pileVide ( P : Pile ) : BooléenDébut| Retourner ( sommet ( P ) = 0 )

Fin

Algorithme empiler

Action empiler ( DR P : Pile ; x : Element )Début| Si sommet ( P ) = capacité ( P ) Alors| | Erreur "Débordement positif"| Sinon| | sommet ( P ) <- sommet ( P ) + 1| | P [ sommet ( P ) ] <- x| FinSi

Fin

Algorithme depiler

Action dépiler ( DR P : Pile )Début| Si pileVide ( P ) ) Alors| | Erreur "Débordement négatif"| Sinon| | sommet ( P ) <- sommet ( P ) - 1| | Retourner P [ sommet ( P ) + 1 ]| FinSi

Fin

Unisciel algoprog – ls00cours-texte, May 21, 2018 13

3 Files

3.1 Definition

FileStructure de donnees admettant les fonctionnalites suivantes :

• « enfiler » : Ajouter un element en queue de la file.

• « defiler » : Supprimer le premier element ajoute a la file.

• « tete » : Acceder a la valeur du premier element ajoute a la file.

• « queue » : Acceder a la valeur du dernier element ajoute a la file.

• « filevide » : Tester si la file est vide.

ExempleLa figure presente un exemple de file et montre les consequences des operations enfileret defiler :

• (a) Initialement la file contient les valeurs 7, 4, 8, 9, 6 et 1 (de la plus anciennementa la plus recemment inseree)

• (b) Etat apres l’operation enfiler(3)

• (c) Etat apres l’operation defiler qui a renvoye la valeur 7

48961 7

48961 73

89613 4

Unisciel algoprog – ls00cours-texte, May 21, 2018 14

3.2 Terminologie et utilisations

TerminologieLa file (en anglais queue) est donc une collection de donnees de type premier entre,premier sorti (en anglais FIFO, first in first out). L’analogie avec une file de clients aun guichet (poste, caisse du supermarche...) est evidente : c’est le premier arrive qui estle premier servi, et il est tres malvenu d’essayer de doubler une personne dans une file.Notez qu’une fois entre dans une file – au sens informatique du terme – on ne peut pasen sortir par l’arriere : le seul scenario pour en sortir est d’attendre patiemment son touret d’arriver en tete de la file.

ConsequencesOn ne peut ni parcourir une file, ni consulter directement le n-eme element.

UtilisationsLes files sont tres utiles en informatique. Citons la creation de memoire tampon (buffer)dans de nombreuses applications, les processeurs multitaches qui doivent accorder dutemps-machine a chaque tache, la file d’attente des impressions pour une imprimante...

Unisciel algoprog – ls00cours-texte, May 21, 2018 15

3.3 Representation d’une file par tableau

On peut implementer les files a n − 1 elements au moyen d’un tableau a n elements etde deux attributs :

• tête(F) qui indexe (ou pointe) vers la tete de la file ;

• queue(F) qui indexe le prochain emplacement ou sera insere un element nouveau.

Les elements de la file se trouvent donc aux emplacements tête(F)|, \lstinlinetete(F)+1|,..., queue(F)-1 (modulo n). Quand tête(F)=queue(F), la file est vide.La seule difficulte dans cette representation est la gestion des debordements de file quiinterviennent quand on tente d’effectuer l’operation défiler sur une file vide et l’operationenfiler sur un tableau codant la file qui est deja plein. Ce dernier probleme n’apparaıtpas lorsque l’on implemente les files au moyen d’une liste doublement chaınee.

ExempleLa figure montre la representation d’une file par un tableau :

• (a) Etat initial de la file

• (b) Nouvel etat apres l’action enfiler(7)

• (c) Nouvel etat apres l’action enfiler(5)

• (d) Nouvel etat apres l’operation défiler qui a renvoye la valeur 1

48961

321 4 5 6 7 8 9 10 1211

tete[F] = 7queue[F] = 1

7

4896

9 10 1211

7

8

queue[F] = 2

1

321 4 5 6 7

5

tete[F] = 8

48961

321 4 5 6 7 8 9 10 1211

tete[F] = 7queue[F] = 2

75

48961

321 4 5 6 7 8 9 10 1211

tete[F] = 7 queue[F] = 12

(d)

(c)

(b)

(a)

Algorithme filevide

Fonction fileVide ( F : File ) : BooléenDébut| Retourner ( tête ( F ) = queue ( F ) )

Fin

Unisciel algoprog – ls00cours-texte, May 21, 2018 16

Algorithme enfiler

Action enfiler ( DR F : File ; x : Elément )Début| Si ( Modulo ( queue ( F ) + 1 , n ) = tête ( F ) ) Alors| | Erreur "Débordement positif"| Sinon| | F [ queue ( F ) ] <- x| | queue ( F ) <- queue ( F ) + 1| FinSi

Fin

Algorithme defiler

Action défiler ( DR F : File )Variable x : ElémentDébut| Si ( fileVide ( F ) ) Alors| | Erreur "Débordement négatif"| Sinon| | x <- F [ tête ( F ) ]| | tête ( F ) <- tête ( F ) + 1| | Retourner x| FinSi

Fin

Unisciel algoprog – ls00cours-texte, May 21, 2018 17

4 References generales

Aho-AL2 @BookAho-AL2, author = Aho, A.V. AND Ullmann, J.D., title = Conceptsfondamentaux de l’informatique, publisher = Dunod, ISBN = 2-10-001683-0, year= 1993, note = Best-seller mondial. Fortement recommande pour toutes les ma-tieres du centre informatique.

Baynat-AL1 @BookBaynat-AL1, author = Baynat B., title = Exercices et problemesd’algorithmique, publisher = Dunod, ISBN = 978-2-10-054991-7, year = 2010 (3eedition), note = 155 enonces avec solutions detaillees – Tres bon complement de[L’algorithmique, Cormen-A1]