Structures de donnes linaires

I. Liste, Pile et file.

Une liste linaire est la forme la plus simple et la plus courante d'organisation des donnes. On l'utilise pour stocker des donnes qui doivent tre traites de manire squentielle. Exemple On dsire, pour les besoins de la programmation d'un jeu de cartes, reprsenter le paquet de cartes. Parmi toutes les informations que l'on possde sur les cartes, la plupart sont inutiles (couleur du dos, taille, matire, propritaire ). Seuls nous intressent, la couleur (trfle, carreau, coeur ou pique), la hauteur (valeur de la carte), et le cot visible de la carte. Pour chacune des cartes ces informations utiles seront codes et ranges dans un article. Ainsi on effectuera le codage suivant: - pour le cot visible: Face = 1 signifie que la carte est "cache" (dos visible) Face = 0 signifie que la carte est "visible" (face visible) - pour la couleur: couleur = 1 pour trfle couleur = 2 pour carreau couleur = 3 pour coeur couleur = 4 pour pique - pour la hauteur: hauteur = 1 pour l'as hauteur = 2 pour le deux | hauteur = 12 pour la dame hauteur = 13 pour le roi Un article aura alors la forme suivante :

De plus, on pourra ventuellement adjoindre cet article une zone "suivant" servant indiquer l'adresse de l'lment suivant. Ainsi on aura la reprsentation de l'article sous la forme :

page 1

Le paquet de quatre cartes suivant :

pourra alors tre reprsent par :

Dfinition Une liste linaire est une suite finie (ventuellement vide) d'articles de mme type X[1], X[2], , X[N] avec N>0, dont la proprit est qu'il est linaire (une dimension), ordonn et : si N>0 alors X[1] est le premier article si 1<k<N alors X[k] est prcd de X[k-1] et est suivi de X[k+1]. Les articles sont reprs selon leur rang dans la liste mais il ne faut pas confondre le rang et la position! Les oprations que l'on peut dsirer raliser sur une telle structure sont entre autres : - examiner le kime lment de la liste - insrer un lment avant le kime lment de la liste - supprimer le kime lment de la liste - runir deux listes - rechercher les articles dont une zone contient une certaine valeur - etc Il existe diffrents type de listes linaires. Un exemple tir de la vie courante peut tre le rangement de vtements et son organisation comportemental. Dans certains types de listes les oprations d'insertion et de suppression se droulent toujours aux extrmits de la liste. Ces types de listes se rencontrant trs frquemment, on leur a donn un nom. Dfinition Une Pile est une structure de donnes linaire dans laquelle les oprations d'insertion et de suppression se font une extrmit appele sommet. L'autre extrmit tant dsigne par le terme "fond de pile". On rencontre galement le terme LIFO (Last In First Out) pour dsigner ce type de structure. Exemples - pile d'assiettes - pile d'un microprocesseur - une pile est utilise pour le calcul des expressions postfixes
page 2

Reprsentations

Dfinition Une File est une structure de donnes linaire dans laquelle les oprations d'insertion se font une extrmit appele arrire et les oprations de suppression se font l'autre extrmit appele front. On rencontre galement le terme FIFO (Fist In Fist Out) pour dsigner ce type de structure. Exemples - file de voitures - de manire gnrale : Les files d'attentes Reprsentations

Dfinition Une queue ou double file (ou deque) est une structure de donnes linaire dans laquelle les oprations d'insertion et de suppression se font aux deux extrmits. Reprsentation

Remarque On distingue galement les Queues entre restreinte (QER) dans lesquelles on ne peut insrer qu' une extrmit, mais sortir aux deux extrmits; et les Queues sortie restreinte (QSR) dans lesquelles on ne peut supprimer qu' une extrmit, mais insrer l'une des deux extrmits.
page 3

II. Implantation en mmoire

Nous reprsenterons la mmoire comme une srie de cases numrotes de 1 M. M tant le nombre de cases mmoires disponible permettant le stockage des informations.

Ainsi, les articles X[ i ] sont rangs dans ces cases. L'emplacement, l'adresse d'un article X[ i ] est alors le numro de la case o il dbute.

1. La Mthode squentielle
C'est la faon la plus naturelle de procder. En effet les articles X[ i ] de la liste linaire sont rangs, les uns la suite des autres, dans des cases mmoires conscutives. Ainsi, si chaque article a besoin de C cases mmoires pour son stockage, on aura: Adresse de X[ j + 1 ] = Adresse de X[ j ] + C = A1 + j * C (o A1 est l'adresse de X[ 1 ]). On peut donc, sans difficult, accder un article quelconque de la liste linaire, en connaissant l'adresse de base A1.

Par la suite nous supposerons, pour plus de commodit, que C = 1 et A1 = 1. Etudions, prsent les cas particuliers de la pile et de la file.

a. Cas d'une pile

Les oprations d'insertion et de suppression se font une extrmit (sommet). Il faut donc connatre en permanence l'adresse de celle-ci. Pour cela, on utilisera un pointeur T qui nous indiquera o se trouve le sommet.

Primitives Les oprations de base sur les piles sont simples : empiler(p,e) : empile l'lment e dans la pile p. dpiler(p) : dpile un lment de la pile p et renvoie cette valeur.
page 4

Les oprations d'insertion et de suppression pourrons alors se raliser avec les instructions suivantes : Insertion de Y T = T + 1; X [ T ] = Y; Mais ici se pose deux problmes: - vouloir supprimer un lment alors que la pile est vide - vouloir insrer un lment alors que la pile est pleine (les M cases mmoires rserves la pile sont occupes). Il va donc falloir grer ces exceptions et on crira alors: Insertion de Y si (T == M) alors PLEIN(); sinon { T = T + 1; X [ T ] = Y; } Suppression si (T == 0) alors VIDE(); sinon { Y = X [ T ]; T = T - 1; } Suppression Y = X [ T ]; T = T - 1;

O VIDE() et PLEIN() simulent les exceptions (appel une procdure d'erreur, sortie du traitement, etc).

b. Cas d'une file

Les oprations d'insertion se font une extrmit (arrire) et les oprations de suppression se font l'autre extrmit (front). Il faut donc connatre en permanence l'adresse de celles-ci. Pour cela, on utilisera un pointeur F qui nous indiquera o se trouve le front et un pointeur A qui nous indiquera o se trouve l'arrire.

Les oprations d'insertion et de suppression pourrons alors se raliser avec les instructions suivantes : Insertion de Y A = A + 1; X [ A ] = Y; A nouveau ici se pose deux problmes: - vouloir supprimer un lment alors que la file est vide - vouloir insrer un lment alors que la file est pleine (les M cases mmoires rserves la file sont occupes).
page 5

Suppression Y = X [ F ]; F = F + 1;

De plus, le fait que les deux pointeurs soient incrments lors de chaque opration signifie que l'on risque de se retrouver dans le cas o le dbut de mmoire est inoccup, le pointeur A tant en fin de mmoire (A = M) et interdire ainsi les oprations d'insertions. Pour ne pas interrompre le traitement, dans un tel cas de figure, on va supposer la mmoire comme tant circulaire.

La file X pourra alors prendre la forme suivante:

Il reste encore un problme rsoudre. En effet, dans une telle configuration, les tests de file vide et de file pleine sont identiques (A = F - 1). Pour pouvoir diffrencier les deux cas, on va supposer que la case pointe par F est "interdite" pour le stockage d'un lment de la file.

Les oprations d'insertion et de suppression pourront alors se raliser avec les instructions suivantes: Insertion de Y si ((A == F-1) ou (A == M et F == 1)) PLEIN(); sinon { si (A == M) alors A = 1; sinon A = A + 1; X [A] = Y; } Suppression si (A == F) alors VIDE(); sinon { si (F == M) alors F = 1; sinon F = F + 1; Y = X [F]; }

Le problme de la diffrentiation entre une liste pleine et une liste vide aurait pu aussi se rsoudre en ajoutant une variable boolenne qui passerai de vrai faux ds la premire insertion dun lment.
page 6

Remarquons aussi que lon peut tout moment connatre le nombre dlments de la file : - Si A > F, il sagit de A - F. - Si A <= F, il sagit de M - F + A.

2. Les listes chanes

Une autre approche traditionnelle pour implanter une liste est lutilisation de pointeurs. De cette faon, la mmoire est alloue dynamiquement : la rservation de lespace se fait en fonction des donnes insres ou supprimes.

a. Listes simplement chanes

On ajoute chaque article un information complmentaire qui pointe vers larticle suivant. Lensemble sera appel un maillon ou un noeud. On peut reprsenter ce type de liste de la faon suivante :
Noeud

Tte de liste

Fin de liste

La tte de liste est une variable qui va pointer le premier lment de la liste. Chaque article (noeud) est composer de son information et dun pointeur vers le noeud suivant. Le dernier article nayant pas de suivant pointe vers vide, nil ou null reprsent dans lexemple suivant par /. La linarit de cette reprsentation est purement virtuelle. En effet, les lments n'ont aucune raison d'tre ordonns ou contigus en mmoire.

Chaque lment est li son successeur. Il n'est donc pas possible d'accder directement un lment quelconque de la liste. On peut simuler ce type de liste dans un tableau : rang 0 1 2 3 valeur 4 7 12 25 suivant 1 / 3 0

Fin de chanage

Dbut de liste

Mais en utilisant un tableau, on perd videmment le ct dynamique de lallocation de la mmoire.

page 7

Primitives teteDeListe(lst) : permet daccder au pointeur dsignant la tte de liste de la liste lst. valeur(p,lst) ou plus simplement valeur(p): permet daccder la valeur du noeud point par p de la liste lst. suivant(p,lst)ou plus simplement suivant(p): permet daccder au suivant du noeud point par p de la liste lst. Si on sintresse un peu plus lallocation mmoire, on peut aussi considrer des fonctions qui initialise une liste, cre un noeud point par p ou libre lespace mmoire dun noeud point par p. Insertion dun lment dans une liste chane Il y a trois cas diffrents que nous devons traiter : linsertion en dbut de liste, au sein de la liste et en fin de liste. Insertion en dbut de liste : p = creerNoeud(); // Ces deux lignes sont inutiles valeur(p) = information; // si le noeud existe dj. suivant(p) = teteDeListe(lst); teteDeListe(lst) = p; Remarquons que cette suite dinstructions convient pour une insertion dans une liste vide. Insertion aprs un noeud point par q : p = creerNoeud(); valeur(p) = information; suivant(p) = suivant(q); suivant(q)= p; Insertion en fin de liste : Il faut en premier lieu parcourir toute la liste et ensuite insrer aprs le dernier lment de celle-ci. p = creerNoeud(); valeur(p) = information; si (teteDeListe(lst) == NIL) { suivant(p) = NIL; teteDeListe(lst) = p; } sinon { q = teteDeListe(lst); tant que (suivant(q) != NIL) { q = suivant(q); } suivant(p) = NIL; suivant(q)= p; } Suppression dun lment dans une liste chane Nous nous intressons la suppression du noeud point par p dans une liste lst. Le problme consiste retrouver le prdcesseur de p.
page 8

si (teteDeListe(lst) == p) teteDeListe(lst) = suivant(p); sinon { tant que (suivant(q) != p) q = suivant(q); suivant(q) = suivant(p); } Exercice Trouver un algorithme qui donne le nombre dlments dune liste chane lst. Correction si (teteDeListe(lst) == NIL) nbr = 0; sinon { q = teteDeListe(lst); nbr = 1; tant que (suivant(q) != NIL) { nbr = nbr + 1; q = suivant(q); } } Exercice Trouver un algorithme donnant le maximum des valeurs dune liste chane non vide dentiers lst. Correction q = teteDeListe(lst); max = valeur(q); tant que (suivant(q) != NIL) { q = suivant(q); si (valeur(q) > max) max = valeur(q); } Exercices supplmentaires a. b. c. d. e. f. Ecrire une fonction qui indique si une valeur fait partie dune liste. Ecrire une fonction qui renvoie la n-ime valeur d'une liste (traiter les cas o il ny a pas de n-ime lment. Ecrire une fonction qui concatne deux listes lst1 et lst2. Ecrire une fonction qui renverse une liste lst pour obtenir une liste lstInverse. Ecrire une fonction qui insre un lment p dans une liste lst (non vide) trie par ordre croissant. Ecrire une fonction qui fusionne deux listes non vides lst1 et lst2 tries pour obtenir de nouveau une liste trie lst.

page 9

b. Listes doublement chanes

Le parcours dune liste chane se fait en sens unique. Cela complique bien des problmes. Une solution apporte ce parcours et de faire appel une liste doublement chane. Ce type de liste est similaire une liste chane ceci prs que lon adjoint chaque noeud une information qui est ladresse de son prdcesseur. Exemple

De nouveau, cette linarit est purement virtuelle. Tout comme pour la liste chane, les noeuds ne sont pas ncessairement adjacents et/ou ordonns en mmoire.

Primitives En plus des primitives des listes simplement chanes, cest--dire : teteDeListe(lst), valeur(p)et suivant(p), nous avons : finDeListe(lst)qui permet daccder au pointeur dsignant la fin de liste de la liste lst. precedent(p)qui permet daccder au prcdent du noeud point par p. Insertion dun lment dans une liste doublement chane De mme que pour les listes simplement chanes, il y a trois cas diffrents que nous devons traiter : linsertion en dbut de liste, au sein de la liste et en fin de liste. On grera en mme temps les exceptions. Insertion en dbut de liste : p = creerNoeud(); // Ces deux lignes sont inutiles valeur(p) = information; // si le noeud existe dj. si teteDeListe(lst) == NIL) { finDeListe(lst) = p; suivant(p) = NIL; /* idem a */ precedent(p) = NIL; /* idem b */ teteDeListe(lst) = p; /* idem c */ } sinon { precedent(teteDeListe(lst)) = p; suivant(p) = teteDeListe(lst); /* idem a */ precedent(p) = NIL; /* idem b */ teteDeListe(lst) = p; /* idem c */ }
page 10

Remarquons que les lignes /* idem a */, /* idem b */ et /* idem c */ des deux cas effectuent les mme oprations et peuvent donc tre exclues du test et places en fin dinstructions. Insertion en fin de liste : p = creerNoeud(); valeur(p) = information; si (finDeliste(lst) == NIL) debutDeListe = p; sinon suivant(finDeListe(lst)) = p; precedent(p) = finDeListe(lst); suivant(p) = NIL; finDeListe(lst) = p; Insertion aprs un noeud point par q : si (q == finDeListe(lst)) { insrer en fin de liste } sinon { p = creerNoeud(); valeur(p) = information; suivant(p) = suivant(q); precedent(p) = q; precedent(suivant(q)) = p; suivant(q)= p; } Suppression dun lment dans une liste doublement chane si (teteDeListe(lst) == p) { si (finDeListe(lst) == p) { teteDeListe(lst) = NIL; finDeListe(lst) = NIL; } sinon { teteDeListe(lst) = suivant(p); precedent(suivant(p)) = NIL; } } sinon si (finDeListe(lst) == p) { finDeListe(lst) = precedent(p); suivant(precedent(p)) = NIL; } sinon { suivant(precedent(p)) = suivant(p); precedent(suivant(p)) = precedent(p); } Exercice Ecrire une fonction qui insre un noeud p dans une liste lst (non vide) trie par ordre croissant.

page 11

Correction si (valeur(p) < valeur(teteDeListe(lst)) insrer p en dbut de liste; sinon { q = teteDeListe(lst); tant que (valeur(p) < valeur(q)) q = suivant(q); si (q != NIL) insrer p aprs le precedent de q; sinon insrer p la fin de la liste; } Exercice Ecrire une fonction qui fusionne deux listes non vides lst1 et lst2 tries pour obtenir de nouveau une liste trie lst. Remarque 1: on n'utilisera pas la fonction de lexercice prcdent. Remarque 2 : cest videment beaucoup plus simple en rcursif en considrant quune liste est un premier lment et une liste. Correction p = teteDeListe(lst1); q = teteDeListe(lst2); teteDeListe(lst) = NIL; tant que ((p!=NIL) && (q!=NIL)) { si ((p!=NIL) && (q!=NIL)) si (valeur(p) < valeur(q)) { insrer le noeud p = suivant(p); } sinon { insrer le noeud q = suivant(q); sinon } si (p==NIL) { insrer le noeud q = suivant(q); } sinon { insrer le noeud p = suivant(p); } }

p la fin de la liste lst

q la fin de la liste lst

q la fin de la liste lst

p la fin de la liste lst

c. Listes circulaires
Une liste circulaire peut tre simplement chane ou doublement chane. Elle sobtient en remplaant le ou les pointeurs NIL par le pointeur de tte de liste et, dans le cas dune liste doublement chane par le pointeur de dbut de liste. On obtient une liste qui na ni premier ni dernier lment. Tous les noeuds sont accessibles partir de nimporte quel autre.
page 12

III. Un exemple d'utilisation de pile : expressions arithmtiques

Les piles ont de nombreuses applications : les navigateurs web (prcdent), les annulateurs dactions dans un traitement de texte ou autres logiciels, les algorithmes de recherches en profondeur dun arbre ou implicitement les algorithmes rcursifs de certains langages. Une des applications des piles ncessite de sy attarder un peu. Il sagit des expressions arithmtiques et de la mthode postfixe de calcul qui est utilise par exemple dans certaines calculatrices HP. Les expressions arithmtiques sont habituellement crites de manire infixe, c'est dire quun oprateur binaire est plac entre ses deux oprandes. Mais une autre faon dvaluer les expressions mathmatiques consiste placer l'oprateur aprs ses oprandes. Cest ce quon appelle la notation postfixe, appele aussi notation polonaise inverse car introduite en 1920 par le polonais Jan Lukasiewicz : Cela permet dviter les parenthses et pas consquent doptimiser le compilateur. Exemple 3 + 4 s'crit en postfix : 3 4 + 3 + 5 - 9 s'crit en postfix : 3 5 + 9 Un intrt de cette notation est qu'il n'y a plus besoin de connatre les priorits des oprateurs, et donc plus besoin de parenthses (qui servent contrer les priorits). 3 + 2 * (3 + 2) 4 + 7 * 4 7 + 8 5 cest--dire 3 + (2 * 5) s'crit en postfix : 3 2 5 * + * 5 s'crit en postfix : 3 2 + 5 * (8 + 2) s'crit en postfix : 4 7 8 2 + * + 2 * + donne en infix : 4 + 7 + 8 * 2

Pour effectuer un calcul en postfix, on utilise une pile. On lit de gauche droite et les rgles sont les suivantes : Si on rencontre : - un nombre : on l'empile - un oprateur binaire: on dpile le sommet et le sous sommet on effectue le calcul sous-sommet "opration" sommet on empile le rsultat - un oprateur unaire (une fonction ou le moins unaire) : on dpile le sommet on calcule la fonction pour la valeur du sommet on empile le rsultat Remarque : Il faut bien diffrencier le moins unaire de loprande de soustraction. Pour cela, on utilisera plutt NEG ou +/- pour loprateur unaire. Un autre avantage du calcul en postfix dans une calculatrice est quil ny a pas dtat cach. Lutilisateur na pas besoin de se demander sil a bien frapp la touche + - * ou / dune calculatrice. En effet, une frappe entrane immdiatement un calcul. Dun autre ct, il ne faut pas malencontreusement frapper deux fois une touche dopration.
page 13

Exercice Avec l'expression ci-dessous donnez les modifications de la pile en respectant les rgles (en supposant la pile vide au dpart) 2 5 + 4 5 3 + 2 ^ * * Quelle est lcriture courant (infixe) de cette expression? Correction

Il sagit de (2 + 5 ) % 4 % (5 + 3 ) .
2

Traducteur Linconvnient le plus important du calcul en postfix consiste en la gymnastique intellectuelle de traduction dinfix en postfix qui crot en complexit avec la taille de lexpression traduire. Un question naturel devient donc : y-a-t-il un algorithme pour passer d'une infixe une postfixe ? La rponse est oui : la mthode consiste empiler les oprateurs. On lit l'expression infixe caractre par caractre. Si c'est un oprande, on l'crit. Sinon (c'est un oprateur), si la pile est vide ou bien si l'oprateur est (strictement) plus prioritaire que l'oprateur en sommet de pile, alors on l'empile. Sinon, on dpile jusqu' pouvoir l'empiler. Lorsquil ny a plus doprandes, on dpile. Remarque xy est un oprateur binaire. Il sagit de x ^ y. Exemples 2 + 3 * 4 - 5 + 6 devient 2 3 4 * + 5 - 6 + 3 + 2 - 5 * 6 / 2 + 3 devient 3 2 + 5 6 * 2 / - 3 + Pour les parenthses : on doit empiler les ouvrantes. Quant aux fermantes, elles imposent de tout dpiler jusqu' l'ouvrante associe. Exemple 2 * 3 + 5 * (1 + 6 * 4) + 7 devient 2 3 * 5 1 6 4 * + * + 7 + 2 * ( 5 + 4 * (3 + 2 ) ^ 2 ) devient 2 5 4 3 2 + 2 ^ * + * Remarque Ne pas oublier quil y a parfois des parenthses sous-entendues.
page 14

Exemple
2 2 3 + 5 % 4 + (1 + 2 ) = (3 + 5 % 4) + ((1 + 2 ) ) et devient donc 3 5 4 * +

1 2 + 2 ^ +

Exercice Traduire en postfix lexpression 3 & 4 + 5 2 + 2 + 1/6 & 7. Correction 3 4 5 2 ^ 2 + + * 1 6 / 7 * +

page 15