Exercice 1 : Files d'attente

Traduire les opérations du modèle de file d'attente au moyen des listes linéaires chaînées.

Exercice 2 : Parcours d'un arbre ternaire

a) Définir un modèle sur les arbres ternaires (Chaque nœud a 0, 1, 2 ou 3 fils).

b) Utiliser une file d'attente pour écrire un algorithme non récursif avec le modèle défini en a) qui visite les éléments d'un arbre ternaire dans l'ordre suivant : la racine, les nœuds du niveau 1 de la gauche vers la droite, ceux du niveau 2 dans le même sens et ainsi de suite ...

Exercice 3 : Listes linéaires chaînées en représentation contigu�

On peut représenter des listes linéaires chaînées dans un même tableau o� chaque élément renferme au moins 2 champs: l'information et le lien. Par exemple la liste suivante :

peut être représentée dans un tableau comme suit :

a) Décrire la structure de données appropriée. Traduire les opérations du modèle défini sur les listes linéaires chaînées dans cette représentation.

b) Ecrire les algorithmes (exprimés avec le modèle) de recherche , d'insertion et de suppression d'un élément donné dans une liste linéaire chaînée donnée ainsi représentée. ( Pour l'insertion, on suppose qu'elle est faite en fin de liste et que les doubles ne sont pas admises)

* * * * *