Micro Systèmes n°25 sep/oct 1982
Micro Systèmes n°25 sep/oct 1982
  • Prix facial : 18 F

  • Parution : n°25 de sep/oct 1982

  • Périodicité : mensuel

  • Editeur : Société Parisienne d'Edition

  • Format : (213 x 271) mm

  • Nombre de pages : 246

  • Taille du fichier PDF : 178 Mo

  • Dans ce numéro : dossier sur la peau artificielle et le laser.

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 126 - 127  |  Aller à la page   OK
Pages suivantes >
126 127
Physiquement, l'élément essentiel est le pointeur. Informatique de la pile (fig. 7). Ajouter un élément revient à le placer à l'endroit où pointe cet indicateur et à l'incrémenter ; pour enlever un élément, il suffit d'accomplir l'opération inverse. Il faut cependant s'assurer que la pile contient au moins un élément si l'on ne veut pas pointer en dehors du tableau. Une autre implantation possible utilise des listes linéaires dont nous parlons plus loin. La figure 8 représente les opérations POP, PUSH et EMPTY en Basic et en Pascal, pour une pile de nombres. 126 — MICRO-SYSTEMES File d'attente La file d'attente, par certains côtés, ressemble beaucoup à une pile, mais à une pile ouverte. En effet, une file d'attente (que l'on nomme simplement une file) se définit par un ensemble d'élément sur lequel les trois opérations PLACE, ENLEVE et VIDE sont possibles. Mais, à l'inverse d'une pile, une file enlève le premier élément qui lui a été entré. C'est pourquoi les Anglo- Saxons la nomme FIFO pour « First In First Out » qui signifie « premier entré, premier sorti ». Une file ressemble à une file d'attente devant un cinéma ou un guichet de poste. Le premier arrivé est le premier à prendre sa place ou à être servi. Ces structures sont surtout utilisées dans les programmes de simulation pour représenter l'attente de personnes ou d'événements, dans les buffers d'entrée/sortie ou, d'une façon générale, en gestion de processus dans les systèmes d'exploitation multi-tâches  : l'attente de programmes pour disposer d'une imprimante, par exemple, doit être gérée au moyen d'une file. L'implantation physique d'une file se réalise généralement au moyen d'un tableau et de deux pointeurs. L'un représente l'entrée, l'autre la sortie de la structure (fig. 9). Du fait de l'insertion et de la lecture des éléments par incrémentation des pointeurs, il y a un déplacement continuel de la Pointeur du• 111› sommet de la pile push Nu F D Fig. 7. - Une pile s'implante en mémoire sous la forme d'un tableau et d'un pointeur qui indique le sommet de la pile. L'instruction « push » l'incrémente, alors que• pop » I  : décrémente. pile vers le sommet du tableau. A cet effet lorsqu'un pointeur arrive au sommet, il est remis à zéro afin de pointer à la base du tableau et être à même de continuer sa tâche. Lorsque le pointeur d'entrée rattrape celui de la sortie, la file est pleine. Si, en revanche, c'est le pointeur de sortie qui rattrape celui d'entrée, alors la file est vide. Les procédures Basic qui permettent de gérer une file sont données figure 10. Des structures chaînées Nous allons maintenant entrer dans les structures « très dynamiques ». En effet, certains auteurs estiment que les piles et les files d'attente sont à classer dans une catégorie à part  : celle des structures semi-statiques, et réserver le terme structures dynamiques pour celles que nous allons examiner maintenant. Les structures dynamiques forment la « vie » de l'informatique, son aspect changeant et évolutif. Aucun système, aucun logiciel puissant ne serait possible à l'heure actuelle sans de telles entités. Physiquement, nous allons voir que l'élément essentiel est le pointeur. A l'inverse des tableaux dans lesquels les éléments sont sagement alignés les uns à côté des autres, les composantes des structures dynamiques sont disséminées dans l'espace mémoire disponible et reliées entre elles grâce aux pointeurs. Pointer consiste à se référer à un élément sans le nommer explicitement. Certains langages parlent de pointeurs (Pascal, C), d'autres de références (Algol, Simula), quelques-uns d'accès (Ada). Beaucoup de langages qui ne parlent pas directement de pointeurs sont pourtant bâtis autour de cette notion (Lisp, Logo, Apl) et intégrés dans des structures de données bien spécifiques. Listes linéaires Une liste linéaire se décrit logiquement comme une suite ordonnée de taille variable, constituée d'éléments de type défini, sur laquelle certaines opérations sont rendues possibles. Nous nommerons une liste par L = (el, e2, en_i, en). Les opérations sont les suivantes.• L'accès à un élément particulier de la liste n'est pas réalisé par l'intermédiaire d'un indice, mais par rapport à un autre élément de la liste grâce aux fonctions  : « premier (L) » qui ramène le premier élément de la liste, et « suivant (L) » qui ramène la liste privée de son premier élément.• L'insertion d'un élément dans la liste.• La suppression d'un élément de la liste.• Tester si la liste est vide ou non. On utilisera donc des listes linéaires chaque fois que l'on aura affaire à un ensemble d'éléments de taille variable (à l'inverse des tableaux qui sont généralement de taille fixe), dans lequel les opéra- Septembre-Octobre 1982
Introduction à la programmation structurée Informatique 10 REM gestion de pile 20 DIM PILE (100) 30 DEF FNEMPTY(X) = (PT = 0) 40 REM push (X) 50 IF PT = 100 THEN PRINT "PILE PLEINE":STOP 60 PT = PT+ 1 70 PILE(PT) = X 80 RETURN 90 100 REM pop 110 REM resultat dans X 120 IF FNEMPTY THEN PRINT "PILE VIDE"  : STOP 130 X = PILE(PT) 140 PT = PT - 1 a) 150 RETURN b) program pileroutine ; const maxpile=lOO ; var pile  : array [1..maxpile] of integer ; pt  : integer ; procedure erreur ; begin (>f a definir suivant les applications if) end ; function empty:boolean• begin if pt=0 then empty:=true else empty:=false ; end ; procedure push (x:integer) ; begin if pt=maxpile then erreur else begin pt:=pt+1 ; pile Ept]  : =x ; end ; end ; function pop:integer ; begin if empty then erreur else begin pop:=pile [pt] pt:=pt-1 ; end ; end ; procedure initpile ; begin pt:=0 ; end ; begin (ii application a inserer ici ») end, Ie, procedures de manipulation d'une pile écrites en Basic (al et en Pascal (fr). t'ig. 9. - La représentation physique d'une file utilise un vecteur et deux pointeurs  : l'un pour indiquer l'entrée et l'autre la sortie de la file, lesquels sont incrémentés lors de l'exécution des instructions - place » et « enleve•. tions d'insertions, de suppressions et d'accès doivent être accomplies n'importe où. Un texte sur lequel on voudra insérer ou supprimer des lignes de texte est un bon exemple de listes linéaires. Les éléments sont alors les lignes de texte, et la liste le texte lui-même. Les secteurs sur un disque sont aussi disposés sous forme de listes linéaires, permettant ainsi une allocation dynamique des ressources de la mémoire de masse. L'implantation d'une liste correspond à une structure chaînée, c'est-à-dire à un ensemble d'éléments reliés entre eux par des pointeurs. La figure 11 montre schématiquement les opérations d'insertion en début de liste et de suppression d'un élément. Les listes peuvent se représenter physiquement sous forme d'un double vecteur  : le premier contenant les éléments, le second les pointeurs sur les éléments, comme le montre la figure 12. Les routines de manipulation de listes pour une telle représentation physique sont données en Basic figure 13. Une autre possibilité de représentation, surtout utilisable dans Septembre-Octobre 1982 MICRO-SYSTEMES — 127



Autres parutions de ce magazine  voir tous les numéros


Liens vers cette page
Couverture seule :


Couverture avec texte parution au-dessus :


Couverture avec texte parution en dessous :


Micro Systèmes numéro 25 sep/oct 1982 Page 1Micro Systèmes numéro 25 sep/oct 1982 Page 2-3Micro Systèmes numéro 25 sep/oct 1982 Page 4-5Micro Systèmes numéro 25 sep/oct 1982 Page 6-7Micro Systèmes numéro 25 sep/oct 1982 Page 8-9Micro Systèmes numéro 25 sep/oct 1982 Page 10-11Micro Systèmes numéro 25 sep/oct 1982 Page 12-13Micro Systèmes numéro 25 sep/oct 1982 Page 14-15Micro Systèmes numéro 25 sep/oct 1982 Page 16-17Micro Systèmes numéro 25 sep/oct 1982 Page 18-19Micro Systèmes numéro 25 sep/oct 1982 Page 20-21Micro Systèmes numéro 25 sep/oct 1982 Page 22-23Micro Systèmes numéro 25 sep/oct 1982 Page 24-25Micro Systèmes numéro 25 sep/oct 1982 Page 26-27Micro Systèmes numéro 25 sep/oct 1982 Page 28-29Micro Systèmes numéro 25 sep/oct 1982 Page 30-31Micro Systèmes numéro 25 sep/oct 1982 Page 32-33Micro Systèmes numéro 25 sep/oct 1982 Page 34-35Micro Systèmes numéro 25 sep/oct 1982 Page 36-37Micro Systèmes numéro 25 sep/oct 1982 Page 38-39Micro Systèmes numéro 25 sep/oct 1982 Page 40-41Micro Systèmes numéro 25 sep/oct 1982 Page 42-43Micro Systèmes numéro 25 sep/oct 1982 Page 44-45Micro Systèmes numéro 25 sep/oct 1982 Page 46-47Micro Systèmes numéro 25 sep/oct 1982 Page 48-49Micro Systèmes numéro 25 sep/oct 1982 Page 50-51Micro Systèmes numéro 25 sep/oct 1982 Page 52-53Micro Systèmes numéro 25 sep/oct 1982 Page 54-55Micro Systèmes numéro 25 sep/oct 1982 Page 56-57Micro Systèmes numéro 25 sep/oct 1982 Page 58-59Micro Systèmes numéro 25 sep/oct 1982 Page 60-61Micro Systèmes numéro 25 sep/oct 1982 Page 62-63Micro Systèmes numéro 25 sep/oct 1982 Page 64-65Micro Systèmes numéro 25 sep/oct 1982 Page 66-67Micro Systèmes numéro 25 sep/oct 1982 Page 68-69Micro Systèmes numéro 25 sep/oct 1982 Page 70-71Micro Systèmes numéro 25 sep/oct 1982 Page 72-73Micro Systèmes numéro 25 sep/oct 1982 Page 74-75Micro Systèmes numéro 25 sep/oct 1982 Page 76-77Micro Systèmes numéro 25 sep/oct 1982 Page 78-79Micro Systèmes numéro 25 sep/oct 1982 Page 80-81Micro Systèmes numéro 25 sep/oct 1982 Page 82-83Micro Systèmes numéro 25 sep/oct 1982 Page 84-85Micro Systèmes numéro 25 sep/oct 1982 Page 86-87Micro Systèmes numéro 25 sep/oct 1982 Page 88-89Micro Systèmes numéro 25 sep/oct 1982 Page 90-91Micro Systèmes numéro 25 sep/oct 1982 Page 92-93Micro Systèmes numéro 25 sep/oct 1982 Page 94-95Micro Systèmes numéro 25 sep/oct 1982 Page 96-97Micro Systèmes numéro 25 sep/oct 1982 Page 98-99Micro Systèmes numéro 25 sep/oct 1982 Page 100-101Micro Systèmes numéro 25 sep/oct 1982 Page 102-103Micro Systèmes numéro 25 sep/oct 1982 Page 104-105Micro Systèmes numéro 25 sep/oct 1982 Page 106-107Micro Systèmes numéro 25 sep/oct 1982 Page 108-109Micro Systèmes numéro 25 sep/oct 1982 Page 110-111Micro Systèmes numéro 25 sep/oct 1982 Page 112-113Micro Systèmes numéro 25 sep/oct 1982 Page 114-115Micro Systèmes numéro 25 sep/oct 1982 Page 116-117Micro Systèmes numéro 25 sep/oct 1982 Page 118-119Micro Systèmes numéro 25 sep/oct 1982 Page 120-121Micro Systèmes numéro 25 sep/oct 1982 Page 122-123Micro Systèmes numéro 25 sep/oct 1982 Page 124-125Micro Systèmes numéro 25 sep/oct 1982 Page 126-127Micro Systèmes numéro 25 sep/oct 1982 Page 128-129Micro Systèmes numéro 25 sep/oct 1982 Page 130-131Micro Systèmes numéro 25 sep/oct 1982 Page 132-133Micro Systèmes numéro 25 sep/oct 1982 Page 134-135Micro Systèmes numéro 25 sep/oct 1982 Page 136-137Micro Systèmes numéro 25 sep/oct 1982 Page 138-139Micro Systèmes numéro 25 sep/oct 1982 Page 140-141Micro Systèmes numéro 25 sep/oct 1982 Page 142-143Micro Systèmes numéro 25 sep/oct 1982 Page 144-145Micro Systèmes numéro 25 sep/oct 1982 Page 146-147Micro Systèmes numéro 25 sep/oct 1982 Page 148-149Micro Systèmes numéro 25 sep/oct 1982 Page 150-151Micro Systèmes numéro 25 sep/oct 1982 Page 152-153Micro Systèmes numéro 25 sep/oct 1982 Page 154-155Micro Systèmes numéro 25 sep/oct 1982 Page 156-157Micro Systèmes numéro 25 sep/oct 1982 Page 158-159Micro Systèmes numéro 25 sep/oct 1982 Page 160-161Micro Systèmes numéro 25 sep/oct 1982 Page 162-163Micro Systèmes numéro 25 sep/oct 1982 Page 164-165Micro Systèmes numéro 25 sep/oct 1982 Page 166-167Micro Systèmes numéro 25 sep/oct 1982 Page 168-169Micro Systèmes numéro 25 sep/oct 1982 Page 170-171Micro Systèmes numéro 25 sep/oct 1982 Page 172-173Micro Systèmes numéro 25 sep/oct 1982 Page 174-175Micro Systèmes numéro 25 sep/oct 1982 Page 176-177Micro Systèmes numéro 25 sep/oct 1982 Page 178-179Micro Systèmes numéro 25 sep/oct 1982 Page 180-181Micro Systèmes numéro 25 sep/oct 1982 Page 182-183Micro Systèmes numéro 25 sep/oct 1982 Page 184-185Micro Systèmes numéro 25 sep/oct 1982 Page 186-187Micro Systèmes numéro 25 sep/oct 1982 Page 188-189Micro Systèmes numéro 25 sep/oct 1982 Page 190-191Micro Systèmes numéro 25 sep/oct 1982 Page 192-193Micro Systèmes numéro 25 sep/oct 1982 Page 194-195Micro Systèmes numéro 25 sep/oct 1982 Page 196-197Micro Systèmes numéro 25 sep/oct 1982 Page 198-199Micro Systèmes numéro 25 sep/oct 1982 Page 200-201Micro Systèmes numéro 25 sep/oct 1982 Page 202-203Micro Systèmes numéro 25 sep/oct 1982 Page 204-205Micro Systèmes numéro 25 sep/oct 1982 Page 206-207Micro Systèmes numéro 25 sep/oct 1982 Page 208-209Micro Systèmes numéro 25 sep/oct 1982 Page 210-211Micro Systèmes numéro 25 sep/oct 1982 Page 212-213Micro Systèmes numéro 25 sep/oct 1982 Page 214-215Micro Systèmes numéro 25 sep/oct 1982 Page 216-217Micro Systèmes numéro 25 sep/oct 1982 Page 218-219Micro Systèmes numéro 25 sep/oct 1982 Page 220-221Micro Systèmes numéro 25 sep/oct 1982 Page 222-223Micro Systèmes numéro 25 sep/oct 1982 Page 224-225Micro Systèmes numéro 25 sep/oct 1982 Page 226-227Micro Systèmes numéro 25 sep/oct 1982 Page 228-229Micro Systèmes numéro 25 sep/oct 1982 Page 230-231Micro Systèmes numéro 25 sep/oct 1982 Page 232-233Micro Systèmes numéro 25 sep/oct 1982 Page 234-235Micro Systèmes numéro 25 sep/oct 1982 Page 236-237Micro Systèmes numéro 25 sep/oct 1982 Page 238-239Micro Systèmes numéro 25 sep/oct 1982 Page 240-241Micro Systèmes numéro 25 sep/oct 1982 Page 242-243Micro Systèmes numéro 25 sep/oct 1982 Page 244-245Micro Systèmes numéro 25 sep/oct 1982 Page 246