Listes

On considère une structure:

Et un grand tableau global element RAM[MAX_ELEMENT]; où MAX_ELEMENT est une constante.

On représente les listes comme des suites de element , tel que le champs suivant d'un element soit l'indice dans le tableau RAM de l'élément suivant de la liste. Le dernier élément de la liste a pour suivant la valeur -1 . Un liste est représentée en machine par l'indice de son premier élément.

On suppose qu'on possède une fonction int case_vide() qui retourne l'indice d'une case non utilisée et void libere(int i) qui marque comme inutilisée la case d'indice i .

Ecrire les fonctions qui réalisent:

• L'insertion d'un élément en tête de liste.
• L'insertion d'un élément en fin de liste.
• La recherche d'un élément dans une liste.
• L'affichage d'une liste.
• La suppression du premier élément de la liste.
• Calcule le nombre d'éléments dans la liste.

Expliquez comment on pourrait faire les fonctions int case_vide() et void libere(int i) .

Reprenez l'exercice précédent en utilisant un chaînage par pointeur. Ecrivez les algorithmes en langage C. Vous écrirez, en plus, une fonction permettant la suppression de la première occurence d'un élément d'une liste (en itératif et en récursif).

Comparez les complexités des fonctions précédentes sur les listes et sur les tableaux. Quels sont les avantages et les inconvénients des listes?