Obligement - L'Amiga au maximum

Dimanche 25 août 2019 - 18:25  

Translate

En De Nl Nl
Es Pt It Nl


Rubriques

 · Actualité (récente)
 · Actualité (archive)
 · Comparatifs
 · Dossiers
 · Entrevues
 · Matériel (tests)
 · Matériel (bidouilles)
 · Points de vue
 · En pratique
 · Programmation
 · Reportages
 · Quizz
 · Tests de jeux
 · Tests de logiciels
 · Tests de compilations
 · Trucs et astuces
 · Articles divers

 · Articles in english
 · Articles en d'autres langues


Twitter

Suivez-nous sur Twitter




Liste des jeux Amiga

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Trucs et astuces

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Glossaire

0, A, B, C, D, E, F,
G, H, I, J, K, L, M,
N, O, P, Q, R, S, T,
U, V, W, X, Y, Z


Galeries

 · Menu des galeries

 · BD d'Amiga Spécial
 · Caricatures Dudai
 · Caricatures Jet d'ail
 · Diagrammes de Jay Miner
 · Images insolites
 · Fin de jeux (de A à E)
 · Fin de Jeux (de F à O)
 · Fin de jeux (de P à Z)
 · Galerie de Mike Dafunk
 · Logos d'Obligement
 · Systèmes d'exploitation
 · Trombinoscope Alchimie 7
 · Vidéos


Téléchargement

 · Documents
 · Jeux
 · Logiciels
 · Magazines
 · Divers


Liens

 · Sites de téléchargements
 · Associations
 · Pages Personnelles
 · Matériel
 · Réparateurs
 · Revendeurs
 · Presse et médias
 · Programmation
 · Logiciels
 · Jeux
 · Scène démo
 · Divers


Partenaires

Annuaire Amiga

Amedia Computer

Relec

Hit Parade


A Propos

A propos d'Obligement

A Propos


Contact

David Brunet

Courriel

 


En pratique : Algorithmes et structures de données - Les piles
(Article écrit par Lucien Turski-Marcon et Bruno Bailluet et extrait d'Amiga News Tech - février 1992)


Définition : une pile est une structure de données dans laquelle il n'est possible d'ajouter ou de retirer un élément que par son sommet (méthode dite LIFO : Last In First Out).

Si vous avez bien compris cette petite définition, alors les piles n'auront plus aucun secret pour vous... Elles sont le plus souvent représentées par un tableau, mais comme nous maîtrisons maintenant les listes chaînées, nous allons étudier les deux cas.

Primitives pour les tableaux

Les deux premières primitives (en pseudo-code) que nous vous proposons, permettent de tester l'état de la pile, à savoir si elle est pleine ou au contraire vide.

Piles

Ces deux fonctions permettent de savoir si nous dépassons les limites du tableau. "Taille_Pile" est le plus souvent une constante qui détermine le nombre de cases du tableau. Quant à "Limite_Inférieure", il s'agit comme son nom l'indique de la borne inférieure du tableau. Ainsi, nous pouvons parfaitement n'utiliser qu'un seul grand tableau que nous partagerons en plusieurs piles.

Piles

La procédure "Empile" ajoute l'élément qu'elle a reçu en paramètre après avoir testé l'état de la pile (pleine ?) et incrémenté le sommet. Le retrait d'un élément de la pile se fait après avoir testé l'état de la pile (vide ?) et avant de décrémenter le sommet.

Nous aurions pu choisir une autre méthode pour empiler, qui consiste à mettre la valeur dans le tableau avant d'augmenter le sommet. De ce fait, il aurait fallu être cohérent avec soi-même en modifiant en conséquence les autres fonctions, ainsi que les différentes bornes (essayez pour voir, c'est un bon exercice).

Primitives pour les listes chaînées

Comme vous avez pu le constater, si l'on représente une pile sous forme de tableau, il est nécessaire d'avoir une variable (appelée sommet) indiquant l'indice du dernier élément de la pile. Par contre, si l'on utilise une liste chaînée, cette variable devient inutile. Pourquoi ?

Créons un noeud vide que nous appelons "DEBUT" et qui est le point de départ de notre liste. Puis, à chaque fois qu'un élément devra être empilé, il sera inséré entre "DEBUT" et d'éventuels autres éléments précédemment empilés. La variable indiquant le sommet de la pile devient inutile puisque nous savons toujours où se trouve le dernier élément empilé. Il en est de même pour dépiler : nous prennons le noeud qui suit "DEBUT". Une liste simplement chaînée suffit amplement, car nous ne la parcourerons pas. Nous n'avons donc pas besoin de conserver la trace du noeud précédent (intérêt de la liste double).

Piles

Pour empiler, il suffit d'insérer le nouveau noeud après "DEBUT". Nous devons donc affecter à "nouveau.suivant" l'adresse du noeud qui suit "DEBUT" (cette adresse se trouve dans "DEBUT.suivant"). Ensuite, nous affectons à "DEBUT.suivant" l'adresse du nouveau noeud (ce dernier devient donc le successeur immédiat du noeud "DEBUT"). Ces deux étapes doivent se faire dans cet ordre sous peine de perdre le contenu de "DEBUT.suivant".

Le test "Pile_Pleine" se fait au moment de l'allocation mémoire du nouveau noeud. Si celle-ci échoue, on considère la pile pleine.

Piles

Si la pile n'est pas vide, nous repérons l'adresse de l'élément à dépiler (ceci nous est très facile puisqu'il s'agit toujours du successeur de "DEBUT"). Puis nous sauvegardons sa valeur dans une variable intermédiaire (variable valeur dans notre primitive). Enfin, pour le supprimer de la liste, nous le court-circuitons en faisant pointer "DEBUT.suivant" sur le successeur du noeud à dépiler (il s'agit de "noeud_temp.suivant").

Piles

Si "DEBUT.suivant" est égal à NIL, la liste ne contient aucun élément hormis le premier noeud "DEBUT" qui ne contient pas d'information pertinente.

Pratique

Pour se familiariser avec la pile, nous vous proposons ce mois-ci un petit programme permettant l'évaluation d'une expression parenthésée. Cependant, quelques contraintes sont imposées :
  • Un membre se compose de deux opérandes séparés par un signe.
  • Tout membre doit être mis entre parenthèses.
  • Les opérandes peuvent être des membres.
Ainsi, on entrera ((a+b)*c) et non (a+b)*c.

Piles
Piles
Piles
Piles
Piles


[Retour en haut] / [Retour aux articles] [Article précédent] / [Article suivant]