Enoncé 8 : Listes linéaires chaînées - Files d'attente  Corrigé 8

Exercice 1 : File d'attente dans un tableau circulaire

On peut définir une file d'attente dans un tableau circulaire comme suit :

TYPE Typefile = STRUCTURE

FIN

o� Tête désigne l'indice de l'élément de tête de la file d'attente et Long le nombre d'éléments présents dans la file d'attente.

Traduire les 5 opérations du modèle dans cette implémentation.

Exercice 2 : Listes linéaires chaînées circulaires(llcc)

En règle générale, pour une machine donnée, les entiers ont une longueur maximale spécifique. On peut définir un grand entier positif par une liste linéaire chaînée circulaire comme suit :

Le nombre 459763497210698463 peut être représenté à raison de 5 chiffres par maillon de la façon suivante ( les chiffres sont rangés par groupe de 5 à partir de la fin du nombre) :

Le maillon de tête contient une valeur spéciale -1.

1. Créer une llcc ainsi définie à partir d'un nombre ( chaîne de caractères représentée dans un vecteur ).Il s'agit d'écrire le module Créerlist(V,L, Liste) avec en entrée un vecteur V et une longueur L, et en sortie une llcc Liste. Le nombre est supposé correct et non signé.

2. Restaurer le nombre à partir de sa représentation interne (llcc).Il s'agit d'écrire le module Restaurer(liste, V, L) avec en entrée une llcc Liste et en sortie un vecteur V et une longueur L.

3. Ecrire le module qui a en entrée 2 llccs représentant 2 nombres et qui construit une troisième llcc représentant leur somme.

NB : on utilisera les fonctions suivantes :

Car(ch) : caractère correspondant au chiffre ch.

Nbr(c) : chiffre correspondant au caractère c.

Mod(a, b) : reste de la division de a par b.

Div (a, b) : quotient entier de a par b.