Cours d’algorithmique by Ph. RIS est mis à disposition selon les termes de la licence Creative Commons Paternité – Pas d’Utilisation Commerciale – Pas de Modification 3.0 Unported. 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.
