Grande Encyclopédie Larousse 1971-1976Éd. 1971-1976
P

programmation (suite)

La pile

La pile est une chaîne particulière dans laquelle les opérations d’accès (insertion, suppression, consultation) ne peuvent avoir lieu qu’à une seule de ses extrémités. Son nom vient de ce que, comme pour une pile de draps dans une armoire, on a seulement accès à la dernière information classée suivant le principe « dernier arrivé, premier sorti ».


La file d’attente

La file d’attente est une chaîne particulière dans laquelle l’opération d’insertion n’a lieu qu’à une extrémité de la chaîne, alors que les opérations de consultation et de suppression ne peuvent se produire qu’à l’autre extrémité. Son nom vient de ce que, comme pour une file d’attente chez un commerçant, on a seulement accès à l’information qui a séjourné le plus longtemps dans la chaîne suivant le principe « premier arrivé, premier servi ».


La table

La table est une chaîne particulière dans laquelle les éléments sont composés de deux parties : une clef et une information de nature quelconque. Les clefs des éléments de la table sont deux à deux distinctes, ce qui implique que la donnée de la clef permet d’identifier l’élément auquel elle appartient, donc, en pratique, de retrouver l’information associée à la clef. L’ensemble des clefs est supposé muni d’une « structure d’ordre » naturelle, et la numérotation des éléments de la table est une permutation de la numérotation des clefs. Si l’on considère une chaîne dont les éléments sont composés des informations « numéro de sécurité sociale, nom, prénom, adresse », le numéro de sécurité sociale est une clef.

Une même chaîne peut être munie de plusieurs structures de table, et ce en fonction des « parties » de ses éléments susceptibles de jouer le rôle de clef.


Structures de mémorisation interne

Dans un ordinateur dont la mémoire interne se présente sous forme d’un ensemble de mots ordonnés, l’implantation de chaînes de données se fait essentiellement suivant deux modes : le tableau et la liste.

Si les éléments de la chaîne contiennent respectivement des informations qui, une fois transcrites en binaire, ont des tailles équivalentes, c’est-à-dire peuvent être mises, sans perte de place abusive, dans un même nombre de mots machine, la façon la plus simple d’implanter la chaîne en machine est, à partir d’une mémoire d’adresse connue (adresse de base), de ranger en séquence les blocs de mots associés respectivement aux éléments de la chaîne :

Dans ces conditions, l’ensemble des caractéristiques suivantes : adresse de base, nombre de mots constituant le bloc d’informations associé à un élément de la chaîne, numéro d’un élément choisi, permet de retrouver immédiatement l’emplacement mémoire de ce dernier : on appelle pointeur l’ensemble des informations permettant de trouver l’adresse d’un mot particulier de la mémoire. Une telle structure d’implantation est dite structure de tableau ; si A est le nom d’un tableau, son i-ième élément est désigné par A(i) ; la dimension du tableau A est le produit du nombre des éléments de la chaîne implantée dans A par le nombre de mots associés à un élément de la chaîne. Cette méthode d’implantation est évidemment mal adaptée lorsque les éléments de la chaîne n’ont pas des tailles comparables et surtout lorsqu’il y a lieu d’insérer ou de supprimer des éléments dans la chaîne, ce qui nécessiterait alors de procéder à des « glissements d’information ». Il est préférable, dans ce cas d’implanter la chaîne sous forme de structure de liste. Pour cela, une fois choisie une adresse de base (pointeur de début de liste), pour on associe matériellement au i-ième élément de la chaîne un pointeur permettant de retrouver l’emplacement mémoire du bloc d’information associé au i + 1-ième élément de la chaîne (bloc constitué du nombre de mots composant l’information, de l’information elle-même et du pointeur sur l’adresse de l’information suivante). Les opérations d’insertion, d’extraction, d’éléments sont alors ramenés à de simples manipulations de pointeurs.


Un exemple d’algorithme de programmation (algorithme de Hibbard)


Position du problème

Dans un tableau unidimensionnel A de N éléments, on suppose que, pour le contenu de la j-ième mémoire est un nombre réel aj : [A(j)] = aj. On se propose de trier par ordre croissant la suite {a1, ..., an} et, une fois ce travail terminé, de placer dans l’ordre les nombres classés dans les mémoires du tableau A ; autrement dit, on se propose de construire et d’effectuer une permutation σ de l’ensemble {1, ..., N} telle que l’on ait


Description de la méthode

• Principe. Étant choisi un élément ai de la suite à trier, on cherche la place que cet élément occupera lorsque la suite aura été triée.

• Réalisation. Pour « ranger » aN, on opère de la façon suivante :
— on met aN dans une mémoire de travail T ;
— on compare le contenu de T successivement à a1, a2, ..., jusqu’à trouver j1 tel que l’on ait

— on place dans la mémoire numéro N ;
— on compare le contenu de T à aN–1, aN–2, ..., jusqu’à trouver i1 tel que l’on ait

— on place alors dans la mémoire numéro j1 ;
— on compare ensuite le contenu de T successivement à jusqu’à trouver j2 tel que l’on ait

— on place alors dans la mémoire numéro i1 ;
et ainsi de suite en alternant le sens des comparaisons jusqu’à ce que tous les éléments a1, ..., aN–1 de la suite initiale aient été comparés au contenu de T. À la fin de cette opération, on a déterminé un entier k tel que l’on ait

et, si l’on recopie le contenu de T en position k + 1, ce nombre occupe bien sa place définitive.

Pour continuer l’opération de tri, il n’y a plus qu’à recommencer le même processus d’une part sur le sous-tableau d’autre part sur le sous-tableau

Dans ce tableau (v. ci-dessous) :
— chaque flèche désigne le début d’une des phases de la méthode ;
— les éléments en rouge sont ceux qui, pour la phase en cours, occupent leur place définitive ;
— la case vide est celle qui se libère à la fin de la phase en cours.