Les listes accycliques/asymétriques :

  1. Généralités sur les listes :
    2.

    Une liste est un ensemble de cellules (ou éléments) chaînées
    non nécessairement contiguës.

    Chaînage : méthode d'organisation en mémoire, selon laquelle chaque enregistrement ou article contient une zone indiquant les adresses ou
    les indicatifs des enregistrements ou articles qui lui sont associés.

    Une liste est une suite d'objets de même type dont le nombre est variable.

    La liste repose sur un support adressable et il est possible de passer facilement d'un élément au suivant (s'il existe). La variable contenant l'adresse de l'élément suivant est aussi appelée "Pointeur" (elle permet de pointer sur un autre élément de la liste), et son type dépendra du support utilisé pour représenter la liste.

     

  2. Caractéristiques des listes acycliques asymétriques :
  1. Définition :

    2. Une liste acyclique est une liste dont le dernier élément ne pointe sur rien.

    Une liste asymétrique est une liste qui ne comporte qu'un chaînage. Elle ne peut donc être parcourue que dans un sens.

  2. Caractéristiques particulières :

    3. Chaque élément d'une liste acyclique asymétrique comprend 2 zones :

    1 champ contenant l'information (de longueur fixe pour toute la liste),

    1 champ contenant l'adresse de l'élément suivant..

  3. Représentation graphique :

 

Dans une cellule formée par le couple (donnée, pointeur), chaque pointeur contient l'adresse du couple suivant.

LISTE (nom de la liste) contient l'adresse de la cellule "tête de liste".

- La cellule "tête de liste" contient la première donnée.

- La cellule "queue de liste" contient la dernière donnée. Son pointeur est mis arbitrairement à une valeur indiquant qu'il ne pointe sur rien. Cette valeur peut être, suivant les méthodes de travail "00" "-1" ou encore plus communément NIL.

 

  1. Manipulation des listes acycliques asymétriques :
  1. L'allocation dynamique :

    2. Les objets que nous avons manipulés jusqu'à présent sont connus en permanence pendant tout le déroulement du programme. Les variables servant à décrire ces objets sont définies au début du programme et il n'est pas possible d'en accroître le nombre pendant son exécution

    Ces variables, appelées variables statiques, ne sont pas adaptées à la résolution de problème induits par les listes.

    En effet, le support de la liste n'est pas une structure continue. De plus cette structure n'est pas fixe pendant exécution du programme (le nombre de ces éléments peut varier). On dit que la liste a une structure dynamique.

    Une structure dynamique est une structure dont la taille

    (nombre de ses composants) peut varier au cours d'exécution.

    Certains systèmes disposent donc de mécanisme d'allocation dynamique qui gère la place mémoire disponible en fonction des demandes de l'utilisateur (Cette gestion est totalement transparente pour l'utilisateur).

    Un mécanisme d'allocation dynamique est donc un mécanisme

    qui permet la création ou la destruction

    à la demande de variables dynamiques, lors du déroulement du programme.

    Une des particularités de ces variables est qu'il est impossible de les référencer à l'aide d'un nom, puisqu'elles n'ont pas d'existence avant le début du programme.

    Pour pouvoir accéder à une telle variable, nous utiliserons une variable ( statique celle-là ) qui contiendra une information permettant de "pointer" sur la variable créée (on dit également allouée). Cette information porte le nom d'adresse ( adresse de l'élément alloué ), et la variable contenant cette adresse sera appelée un POINTEUR.

    Une variable de type pointeur est une variable dont le contenu

    (qui est une adresse) peut indiquer l'emplacement en mémoire d'une autre variable

    créée dynamiquement lors de l'exécution et ayant un type de base précis (objet pointé).

    Autrement dit, le rôle d'un pointeur est de permettre l'accès à une structure qui sera créée lors de l'exécution.

    La déclaration doit spécifier le type de base de l'objet qui pourra être accessible à l'aide du pointeur. C'est-à-dire qu'un objet de type pointeur ne peut être utilisé que pour désigner des variables de même type.

    Dans le cas d'une liste, il est donc indispensable de définir le type des cellules de la liste par l'intermédiaire d'une définition classique de structure.

    Soit la structure suivante :

     

    NOM TYPE STRUCTURE

    Elemdym

    NOM CHAMP

    TYPE

    SIGNIFICATION

    Donnée

    Sui

    Chaîne

    Pointeur

    Champ contenant l'information

    Pointeur (sur un elt type Elemdym)

     

    On utilisera ensuite des variables se référant à ce type.

    VARIABLE

    TYPE

    SIGNIFICATION

    Liste

    Cell

    Adr

    Info

    Pointeur(Elemdym)

    Pointeur(Elemdym)

    Pointeur(Elemdym)

    Chaîne

    Variable de type pointeur sur élément de structure Elemdym

    Variable de type pointeur sur élément de structure Elemdym

    Variable de type pointeur sur élément de structure Elemdym

    Variable de même structure que la zone donnée de la cellule de la liste

  2. Les primitives associées aux listes acycliques asymétriques :

    3.  

    Info ¬ Cell­ .Donnée

     

    Cette affectation permet de copier dans la variable Info le contenu de la zone donnée de la cellule pointée par Cell­

    Autre notation qu'il est possible de rencontrer :

    VALEUR ( Case )

    Cette primitive est une fonction qui restitue le contenu de la zone DONNEE de la cellule dont l'adresse est contenue par la variable Case.

    Info ¬ VALEUR ( Case )

     

  3. Accès à la zone valeur de la zone adresse d'une cellule

    4. Adr ¬ Cell­ .Sui

    Cette affectation permet de copier dans la variable Adr (de type pointeur) le contenu de la zone adresse de la cellule pointée par Cell­

    Autre notation qu'il est possible de rencontrer :

    SUIVANT( Case )

     

    Cette primitive est une fonction qui restitue l'ADRESSE contenue dans le pointeur de la cellule dont l'adresse est contenue par la variable Case (cellule courante), si Case n'est pas la dernière cellule de la liste ( TRES IMPORTANT ).

    Adresse ¬ SUIVANT( Case )

  4. Affectation d'une adresse à la zone pointeur d'une cellule
    5.

     

    Cell­ .Sui ¬ Adr

    Cette affectation permet de copier dans la zone pointeur de la cellule pointée par Cell­ , l'adresse contenue dans la variable Adr. Elle est utilisée pour chaîner une cellule à celle qui la suit.

    Autre notation qu'il est possible de rencontrer :

    AFFADRESSE( Case, Adresse )

    Cette primitive permet d'affecter au pointeur de la cellule dont l'adresse est contenue par Cell, l'adresse contenue dans la variable Adr. En d'autres termes, elle effectue le chaînage de la cellule Adr à la cellule Cell. ( après exécution de AFFADRESSE (CELL, ADR),

    on a SUIVANT( CELL ) = ADR ).

  5. Affectation d'une valeur à la zone donnée d'une cellule :

    6. Cell­ .Donnée ¬ Val

    Cette affectation permet de copier dans la zone donnée de la cellule pointée par Cell­ , la valeur contenue dans la variable Val.

    Autre notation qu'il est possible de rencontrer :

    AFFVALEUR ( Case, Val )

    Cette primitive permet d'affecter à la zone Donnée de la cellule dont l'adresse est contenue par Case, la VALEUR contenue dans la variable Val ( après exécution de AFFVALEUR (Cell, Val),

    on a VALEUR( Cell ) = Val ).

     

    REMARQUES IMPORTANTES :

    Une liste est entièrement déterminée par la connaissance de sa cellule "Tête de LISTE". Le nom de la liste peut être considéré comme un pointeur contenant l'adresse de cette cellule.

    En allocation dynamique si l'on désire qu'un pointeur n'indique l'emplacement d'aucun objet, on doit lui affecter la constante prédéfinie NIL ( Not In List ) quel que soit le type de base.

    Lorsqu'une variable de type pointeur est déclarée dans un algorithme, le contenu (adresse) est indéterminé au moment de l'activation de l'algorithme ( pas forcement NIL ). Il faut donc l'initialiser.

    En allocation dynamique il faut pouvoir allouer et libérer une variable du type Elemdym. Pour ce faire deux primitives sont utilisées.

    Soit P une variable de type pointeur sur Elemdym.

  6. Allocation d'une nouvelle cellule de type Elemdym

    7. P ¬ ALLOUER(Elemdym)

    Cette instruction se lit " Allouer un élément de type Elemdym et ranger son adresse dans la variable P ’’.

    Autre notation qu'il est possible de rencontrer :

    ALLOUER ( Cell, Elemdym )

    Cell est une variable de type Elemdym. Cette instruction se lit alors "Allouer un élément de type Elemdym et ranger son adresse dans la variable Cell".

  7. Libération d'une cellule de type Elemdym

LIBERER(Elemdym, P­ )

Cette instruction se lit " Libérer l'élément de type Elemdym dont l'adresse se trouve dans la variable P ’’.

Autre notation qu'il est possible de rencontrer :

LIBERER (Cell, Elemdym)

Cell est une variable de type Elemdym. Cette instruction se lit alors

" Libérer un élément de type Elemdym dont l'adresse se trouve dans la variable Cell".

Home