• Les paquetages

Une file de priorité (FP) est une séquence d'élements  munis d'une priorité. L'insertion d'un nouvel élément dans une FP ne tient pas compte de l'ordre de priorité. En revanche, lors d'une extraction, c'est toujours l'élément de plus haute priorité qui est retiré. Si plusieurs éléments possèdent la même plus haute priorité, seul un élément est extrait.

On définit un Type Abstrait de Données (TAD) pour les FPs :

Domaine de valeurs : N (ensemble des entiers naturels)
Opérations :

taille : FP -> N
inserer : Element*FP -> FP
extraire : FP -> Element
vide : -> FP
racine : FP -> Element

Sémantique :

inserer : on insère un élément en queue de la séquence
extraire : (soit X, l'entier extrait, quel que soit Y appartenant à FP, X>=Y)

Les élements que l'on veut insérer et extraire d'une FP sont des articles caractérisés par deux champs :
le sigle d'un aéroport  (chaine de 3 caractères) et sa priorité (un entier naturel). Les opérations réalisables sur ces éléments sont :

Domaine de valeurs : ensemble des Element
Utilise : Chaine (de 3 caractères)
Opérations :

get : Chaine *Naturel -> Element
put : Element -> vide
itemPriorite : Element -> Naturel
itemChaine : Element -> Chaine

Question 1

• Déclaration du type d'un Element

• Spécification du paquetage itemfp qui implante l'interface du TAD précédent

• Spécification du corps du paquetage itemfp qui implante le TAD précédent

Implantation du type FP sous la forme d'un tableau

Chaque élément, quelle que soit sa priorité est rangé dans le tableau à la première place libre, repérée par un indice. Lors de l'extraction, une place du tableau est libérée et les éléments suivants sont décalés vers la gauche afin de combler la place vacante. On suppose le tableau suffisamment grand pour satisfaire toute insertion .

Question 4

• Définir le type FP. Ne pas oublier que l'indice d'insertion ainsi que le nombre d'éléments font partie des données caractérisant une FP. On suppose aussi que MAX est la constante représentant la dimension du tableau.

• Spécification du paquetage FPTab qui implante l'interface du TAD précédent

• Spécification du corps du paquetage FPTab qui implante le TAD précédent

Implantation du type FP sous la forme d'une liste chainée

• Mêmes questions que précédemment.

Autre implantation possible

--PAQUETAGE FPTab(spécification)
--implantation des FPs avec des tableaux dimensionnés dynamiquement
 

Implantation d'un client du type FP

On souhaite trier un tableau d'Element. Pour cela, on insèrera chaque èlèment du tableau dans une FP, puis on les extraira pour les ranger dans le tableau d'origine. Ecrire le programme client.

Solution