CHAPITRE 2
auteur: Philippe Moreau (U.P.J.V.)
 
Si vous avez déjà lu le chapitre vous pouvez accéder à la série d'EXERCICES concernant les structures de données linéaires.
Ces exercices sont également accessibles à la fin du chapitre.

STRUCTURES DE DONNEES LINEAIRES

Ce sont les structures les plus simples.
 
Exemple:
On désire, pour les besoins de la programmation d'un jeu de cartes, représenter le paquet de cartes. Parmi toutes les informations que l'on possède sur les cartes, la plupart sont inutiles (couleur du dos, matière, propriétaire ). Seuls nous intéressent, la couleur (trèfle, carreau, coeur ou pique), la hauteur (valeur de la carte), et la coté visible de la carte. Pour chacune des cartes ces informations utiles seront codées et rangées dans un article.
 
Ainsi on effectuera le codage suivant:
- pour le coté visible:
Face = 1 signifie que la carte est "cachée" (dos visible)
Face = 0 signifie que la carte est "visible" (face visible)
- pour la couleur:
couleur = 1 pour trèfle
couleur = 2 pour carreau
couleur = 3 pour coeur
couleur = 4 pour pique
- pour la hauteur:
hauteur = 1 pour l'as
hauteur = 2 pour le deux
|
|
hauteur = 12 pour la dame
hauteur = 13 pour le roi
 
Un article aura alors la forme suivante:
 

De plus on pourra, éventuellement, adjoindre à cet article une zone "suivant" servant à indiquer l'adresse de l'élément suivant. Ainsi on aura la représentation de l'article sous la forme:
 

 
Le paquet de quatre cartes suivant
 

pourra alors être représenté par:

 

 
 
Définition:
Une liste linéaire est un ensemble d'articles X[ 1 ] , X[ 2 ] , , X[ N ] avec N>0, dont la propriété est qu'il est linéaire (une dimension), ordonné et:
si N>0 alors X[ 1 ] est le premier article
si 1>k>N alors X[ k ] est précédé de X[ k-1 ] et est suivi de X[ k+1 ].
 
 
Les opérations que l'on peut désirer réaliser sur une telle structure sont entre autres types:
- examiner le kième élément de la liste
- insère un élément avant le kième élément de la liste
- supprimer le kième élément de la liste
- réunir deux listes
- rechercher les articles dont une zone contient une certaine valeur
- etc
 
Dans certains types de listes les opérations d'insertion et de suppression se déroulent toujours aux extrémités de la liste. Ces types de listes se rencontrant très fréquemment, on leur a donné un nom.
 
 
Définition:
Une Pile est une structure de données linéaire dans laquelle les opérations d'insertion et de suppression se font à une extrémité appelée sommet. L'autre extrémité étant désignée par le terme "fond de pile". On rencontre également le terme LIFO (Last In Fist Out) pour désigner ce type de structure.
 
Exemples:
- pile d'assiettes
- pile d'un microprocesseur
-Une pile est utilisée pour le calcul des expressions postfixées
 
Représentations:

 
 
Définition:
Une File est une structure de données linéaire dans laquelle les opérations d'insertion se font à une extrémité appelée arrière et les opérations de suppression se font à l'autre extrémité appelée front. On rencontre également le terme FIFO (Fist In Fist Out) pour désigner ce type de structure.
 
Exemples:
- file de voitures
- de manière générale: Les files d'attentes
 
Représentations:

 
Définition:
Une queue ou double file (ou deque) est une structure de données linéaire dans laquelle les opérations d'insertion et de suppression se font aux deux extrémités.
 
Représentation:

 
 
Remarque:
On distingue également les Queues à entrée restreinte (QER) dans lesquelles on ne peut insérer qu'à une extrémité, mais sortir aux deux extrémités; et les Queues à sortie restreinte (QSR) dans lesquelles on ne peut supprimer qu'à une extrémité, mais insérer à l'une des deux extrémités.
 
 
IMPLANTATION EN MEMOIRE
 
Nous représenterons la mémoire comme une série de cases numérotées de 1 à M. M étant le nombre de cases mémoires disponible permettant le stockage des informations.

 
Ainsi, les articles X[ i ] sont rangés dans ces cases. L'emplacement, l'adresse d'un article X[ i ] est alors le numéro de la case où il débute.
 
 
La Méthode séquentielle: (Nous n'étudierons ici que cette méthode)
 
C'est la façon la plus naturelle de procéder. En effet les articles X[ i ] de la liste linéaire sont rangés, les uns à la suite des autres, dans des cases mémoires consécutives.
Ainsi, si chaque article a besoin de C cases mémoires pour son stockage, on aura:
Adresse de X[ j + 1 ] = Adresse de X[ j ] + C = A1 + j * C (où A1 est l'adresse de X[ 1 ]).
On peut donc, sans difficulté, accéder à un article quelconque de la liste linéaire, en connaissant l'adresse de base A1.
 

 
Par la suite nous supposerons, pour plus de commodité, que C = 1 et A1 = 1.
 
Etudions, à présent les cas particuliers de la pile et de la file.
 
 
a) cas d'une pile
 
Les opérations d'insertion et de suppression se font à une extrémité (sommet). Il faut donc connaître en permanence l'adresse de celle-ci. Pour cela, on utilisera un pointeur T qui nous indiquera où se trouve le sommet.

 
Les opérations d'insertion et de suppression pourrons alors se réaliser avec les instructions suivantes:

 

Mais ici se pose deux problèmes:
- vouloir supprimer un élément alors que la pile est vide
- vouloir insérer un élément alors que la pile est pleine (les M cases mémoires réservées à la pile sont occupées).
Il va donc falloir gérer ces exceptions et on écrira alors:
Où VIDE( ) et PLEIN( ) simulent les exceptions (appel à une procédure d'erreur, sortie du traitement, etc).
 
 
 
b) cas d'une file
 
Les opérations d'insertion se font à une extrémité (arrière) et les opérations de suppression se font à l'autre extrémité (front). Il faut donc connaître en permanence l'adresse de celles-ci. Pour cela, on utilisera un pointeur F qui nous indiquera où se trouve le front et un pointeur A qui nous indiquera où se trouve l'arrière.
 

 
Les opérations d'insertion et de suppression pourrons alors se réaliser avec les instructions suivantes:
 
A nouveau ici se pose deux problèmes:
- vouloir supprimer un élément alors que la file est vide
- vouloir insérer un élément alors que la file est pleine (les M cases mémoires réservées à la file sont occupées).
De plus, le fait que les deux pointeurs soient incrémentés lors de chaque opération signifie que l'on risque de se retrouver dans le cas où le début de mémoire est inoccupé, le pointeur A étant en fin de mémoire (A = M) et interdire ainsi les opérations d'insertions. Pour ne pas interrompre le traitement, dans un tel cas de figure, on va supposer la mémoire comme étant circulaire.
 

 
La file X pourra alors prendre la forme suivante:

 
Il reste encore un problème à résoudre:
- En effet, dans une telle configuration, les tests de file vide et de file pleine sont identiques (A = F).
Pour pouvoir différencier les deux cas, on va supposer que la case pointée par F est "interdite" pour le stockage d'un élément de la file.
 

Les opérations d'insertion et de suppression pourrons alors se réaliser avec les instructions suivantes:
 
 
EXERCICES sur les Structures de Données Linéaires

 

Auteur: Philippe Moreau (U.P.J.V.)