ED n°9 --- Algorithmique et Programmation


Objectifs

Exercice

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

Question 2 Question 3

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

Question 5 Question 6

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

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.