Auris Solutions : Cabinet de Conseil en Stratégie Numérique

Cours d’algorithmique – Programmation en Turbo Pascal – VII) Suite/File/Pile

Lis moi avec webReader

VII.1. Les suites

Une suite est un objet composé d’objets élémentaires de même type. Les tables et tableaux étaient des suites dont les éléments étaient stockés de façon contigüe en mémoire et dont l’accès était direct (par un indice ou une fonction de hachage sur une clé). Dans le cas des fonctions de hachage; il se produisait parfois des collisions gérées par un renvoi sur une autre case du tableau associé : l’accès devenait donc indirect sur un ou plusieurs niveaux.

Il existe des structures de données dont l’accès ne se fait jamais directement comme dans le cas des tableaux. Il est alors souvent interactif, information après information.

Exemple :

Fichier séquentiel sur une mémoire périphérique ou table/tableau

0i                               0i+1            …                 EOF

Objet élémentaire                                                     Fin de Fichier

(un enregistrement)

Un fichier peut avoir une table variable contrairement à une table ou un tableau.

* Une liste de cellules mémoire chaînée par un « pointeur ».

Une liste est une suite particulière

Une cellule élémentaire est composée de l’information utile (enregistrement) et du pointeur sur la cellule suivante.

Pointeur : une variable d’un type donné représente un certain nombre de cases mémoires dans la machine. Structurellement, le nom donne l’adresse de la 1ère case et le type, le nombre de cases contigües pour stocker les infos de cette variable.

Un entier est par exemple souvent représenté grace à 4 octets (cases mémoires).

Chaque fois qu’une variable est déclarée, cette opération est faite automatiquement mais il est possible à l’utilisateur de gérer directement ces opérations par le biais des pointeurs.

*Un pointeur est typé dans le sens où il ne peut pointer que sur des objets d’un type donné.

* Un pointeur qui ne pointe sans aucun objet a une valeur NULL

* Les opérations de base sur les pointeurs sont :

– allocation

– dislocation

– affectation, différence

* ADA interdit qu’un pointeur désigne un objet déclaré « normal »

Exemple :

Type vecteur B array (INTEGER range 1.3) of FWAT ;

Type pt_vect B acces vecteur ;

p1,p2 : pt_vect:= NULL ;

p1:= new pt_vect ; ..allocation mémoire de vecteur

p2:= p1 ;

free(p1) ; ..libère la mémoire

(…)

VII).2. Les opérations si la suite est un tableau

* Création -> déclaration

suite : array (1..n) of elt ;

*Ajout_en_début :  suite(1):= elt -> suite

* Ajout_en_fin :         suite(n):= elt -> suite

* Ajout_en_position : suite(x):= elt -> suite

* Retrait -> il n’existe pas vraiment d’opération de retrait de suite(1):= elt -> suite

* Suite_vide -> suite(x):= elt NULL

* Parcours : premier_elt = indice_suite = 1

elt_suivant  = indice_suite:= indice_suite+1

elt_courant = indice_suite

dernier_elt = indice_suite:= 4

VII.3. Les opérations sur les suites en général

* Création : -> suite

(pour les tables et tableaux : simple déclaration)

* Ajout : en_début , en_fin } suite x elt -> suite

position :suite x elt -> suite (portable et tableau)

On considère que l’ajout déplace en même temps le pointeur de l’elt courant d’une suite

* Retrait : en_tête ; en_fin, position

* Suite_vide : suite -> booléen

* Parcours : premier_elt : suite -> suite

elt_suivant : suite -> suite

elt_courant : suite -> suite  (pour les tables et tableaux accès : table x clé -> elt)

dernier_elt : suite -> booléen

VII.3.a. Création et initialisation d’une suite

Variable : S suite de  elt ;

E elt ;

VII.3.b. Exemple de parcours d’une suite

Variable : S,S1 Suite de elt ;

(…)

Création, initialisation de S

(..) S1 Traiter(elt_courant(S1)) ;

S1
Fin TQ

(…)

VII.4. Notion de liste

Une liste est une suite :

– dont les informations ne sont normalement pas stockées de façon contigüe en mémoire

– dont la table est variable

– dont la définition est récursive :

suite { info elt -> info

-> pointeur elt_suivant ou NULL

Une liste est une structure de base de la programmation : le langage LISP (LIST Processing) conçu en 1960 par J. Mc Carthy utilise principalement cette structure.

Le codage d’une liste dans un langage utilise les pointeurs et les enregistrement.

Par défaut, suivant vaut NULL (pas de suivant -> fin de liste).

Le chaînage d’une liste peut être unidirectionnel (suivant), bidirectionnel (suivant, précédent), ou plus complexe.

Propriétés :

*Dans une liste de type LISP, on n’ajoute qu’en début

* On ne supprime que l’elt de début

* on recherche à partir du début.

VII.4.a. Exercice 1

Modifier le Ps sur les listes simples pour que l’on puisse ajouter un elt en fin de liste. (On pointe au départ sur n’importe que elt de cette liste).

VII.4.b. Exercice 2

Créer une procédure insere_après_elt qui a pour profile : liste x -> liste et qui insère une elt dans la liste.

VII.4.c. Exercice 3

Créer une procédure supprime elt qui a pour profile : liste x … -> liste

VII.4.d. Exercice 4

Écrire les procédures et fonctions nécessaires à la gestion d’une liste doublement chaînée (suivant, précédent, elt).

Donner la structure des données.

Aucun commentaire jusqu'à présent.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *


_____________


Avant d'être uberisé,
apprenez à décoder les

17 règles de l'économie numérique


Translator

FrenchItalianChinese (Traditional)EnglishGermanSpanishJapaneseArabicRussianHebrewTurkish

Catégories