Algorithmique - pile, file et listes chaînées

Résumé du document

Une structure de données se définit tout simplement comme étant la manière de représenter des données. Une pile est une structure de données qui suit le principe dernier entré - premier sorti. En anglais cela ce dit last in - first out (LIFO). L'opération consistant à insérer un élément dans une pile s'appelle empiler. L'opération consistant à supprimer un élément d'une pile s'appelle dépiler. Ces deux opérations s'accomplissent du même côté de la pile.

La manière la plus courante servant à implémenter une pile est celle consistant à utiliser un tableau. La pile possède deux attributs essentiels nommés respectivement sommet et longueur. Ainsi pour une pile nommée P, sommet [P] indexe l'élément au sommet de celle-ci et longueur [P] le nombre n maximum d'éléments du tableau. Lorsqu'on atteint ce maximum (longueur [P]), la pile est dite pleine.

Tenter d'empiler dans ce cas précis conduit à un débordement. La pile est vide lorsque sommet[P] = 0 ; dans ce cas précis, tenter de dépiler conduit à un débordement négatif. Par ailleurs, il convient de noter que pour l'implémentation d'une pile à n éléments il faut un tableau à n éléments.

Extraits

[...] Les listes simplement chaînées. Les listes chaînées circulaire. Dans tous ce qui suit , il sera uniquement question des listes doublement chaînées en raison de leur utilisation récurrente . II - LISTES DOUBLEMENT CHAINEES Illustration d'une liste doublement chaînée Tête[L] III - ATTRIBUTS RELATIFS A UNE LISTE DOUBLEMENT CHAINEE Au sein d'une liste doublement chaînée, chaque élément x (objet) a trois champs qui sont : Pred[x] : qui pointe sur l'élément précédent. Succ[x] : qui pointe sur l'élément suivant. Clé[x] : qui est l'information contenue en x. [...]

[...] La manière la plus courante servant à implémenter une pile est celle consistant à utiliser un tableau. Illustration Après ENFILER , on obtient : Après DEFILER on obtient : II - ATTRIBUTS D'UNE FILE Une file F possède principalement trois attributs qui sont : Tête[F] qui indexe le premier élément de la file. Queue[F] qui indexe le prochain emplacement non occupé de la file. Longueur[F] la longueur du tableau servant à implémenter la file. Par ailleurs notons que avec tableau F à n élément on peut représenter une file d'au plus éléments. [...]

[...] Par ailleurs, on a l'attribut tête[L] qui pointe sur le premier élément de la liste doublement chaînée. Si pred[x] = NIL alors x est l'élément en tête de la liste. Si succ[x] = NIL alors x est l'élément en dernière position dans la liste. IV - PSEUDO CODES RELATIFS AUX LISTES DOUBLEMENT CHAINEES IV - a Recherche d'un élément de clé k dans une liste doublement chainée. La procédure qui suit retourne un pointeur sur le premier élément de clé k. [...]

[...] RECHERCHER_LISTE( L , k ) Début x tête[L] tant que (clé[x] et NIL) faire x Succ[x] fin tant que retourner x fin IV - b Insertion d'un élément x en tête d'une liste doublement chainée LISTE_INSERER , Début Succ[x] tête[L] si ( x NIL ) alors pred[ tête[L] ] x fin si tête[L] x pred[x] NIL Fin IV - c Suppression d'un élément pointé par x LISTE_SUPPRIMER ( L , x ) Début Si pred[x] NIL alors Succ [ pred ] succ[x] Sinon Tête[ L ] succ[ x ] Fin si Si ( succ[ x ] NIL ) alors Pred [ succ[x] ] pred[x] Fin si Fin V Listes doublement chaînées avec sentinelle Une sentinelle est un objet vide. Cependant, il possède les mêmes champs que tout objet de la liste chaînée. Elle permet de simplifier les conditions aux limites. Illustration : L'objet vide grisé en tête de liste est la sentinelle. Vous remarquez par ailleurs que la liste de vient circulaire. On parle de NIL[L] au lieu de NIL. [...]

[...] Algorithmique - pile, file et listes chaînées BLE DROH DIOMANDE (béni humble) SOMMAIRE LES PILES I DEFINITIONS I - a Définition d'une structure de données I - b Définition d'une pile II - LES ATTRIBUTS DE LA PILE III - PSEUDO CODES RELATIFS AUX PILES III - a Tester si oui ou non une pile est vide III - b Tester si oui ou non une pile est pleine III - c Insérer un élément x dans une pile P III - d supprimer un élément d'une pile P LES FILES I - DEFINITION DE LA FILE II - ATTRIBUTS D'UNE FILE III - PSEUDO CODES RELATIFS AU FILES III - a Tester si oui ou non une file F est vide III - b Tester si oui ou non une file est pleine III - c Ajout d'un élément dans une file III - d Suppression d'un élément contenu dans une file F LES LISTES CHAINEES I - DEFINITION II - LISTES DOUBLEMENT CHAINEES III - ATTRIBUTS RELATIFS A UNE LISTE DOUBLEMENT CHAINEE IV - PSEUDO CODES RELATIFS AUX LISTES DOUBLEMENT CHAINEES IV - a Recherche d'un élément de clé k dans une liste doublement chainée IV - b Insertion d'un élément x en tête d'une liste doublement chainée IV - c Suppression d'un élément pointé par x V Listes doublement chaînées avec sentinelle V 1 pseudo codes relatifs aux listes doublement chainées avec sentinelle V 1 a Recherche d'un élément de clé k V 1 b Suppression d'un élément x V 1 c Insertion en tête de liste d'un élément x LES PILES I - DEFINITIONS I - a Définition d'une structure de données. Une structure de données se définit tout simplement comme étant la manière de représenter des données. I - b Définition d'une pile Une pile est une structure de données qui suit le principe dernier entré - premier sortie. En anglais cela ce dit last in - first out (LIFO). L'opération consistant à insérer un élément dans une pile s'appelle empiler. L'opération consistant à supprimer un élément d'une pile s'appelle dépiler. [...]