On considère ici une liste L comme un tableau dont la taille
peut varier, et pour laquelle on dispose des actions élémentaires associées à
un accès séquentiel aux données, en pointant sur un unique élément de la liste
(un élément L[i] dont l'indice i n'est pas connu).
Nous choisirons les actions élémentaires suivantes : estvide(L) : teste si une liste est vide. Audébut(L) : se place sur le premier élément d'une
liste non vide (ce qui correspondrait à L[1]). Ausuivant(L) : se place sur l'élément suivant d'une liste
d'au moins deux éléments (pointe sur L[i+1] si on pointait sur L[i]).
Lire(L) : donne la valeur de la position courante (valeur
L[i]). Estalafin(L) : teste si on pointe sur le dernier élément
d'une liste non vide. Ajouter(L,x) : insère x à la position courante, et donc en
début de liste pour une liste vide (L[i] prend la valeur x et les éventuels éléments suivants sont décalés : l'ancien L[i] devient L[i+1], etc.). Supprimer(L) : supprime la valeur de la position courante
(supprime L[i], l'ancien L[i+1], s'il existait, devient L[i], etc.).
Exercice 5.1.
Ecrire un algorithme pour chacun des problèmes
suivants. En faire la preuve et déterminer la complexité. a) Vérifier si une valeur donnée appartient à une liste. b) Calculer le nombre d'occurrence d'une valeur dans une liste. c) Calculer la taille d'une liste. d) Calculer la valeur moyenne d'une liste de nombres. e) Ne conserver qu'une seule occurrence d'une valeur donnée dans
une liste. f) Purger une liste : supprimer toutes les occurrences multiples
d'une liste (càd ne garder qu'un exemplaire de chaque valeur de la liste).
Exercice 5.2.
Si on utilise des listes purgées pour représenter des
ensembles, quelles pourront être les complexités des problèmes suivants ?
La complexité change-t-elle si la liste est triée par ordre croissant de
valeurs ? a) Test d'appartenance x∈L ? b) Intersection L1∩L2. c) Union L1∪L2. d) Test d'inclusion : L1⊆L2 ?
Exercice 5.3.
Ecrire un algorithme pour chacun des problèmes suivant.
a) Extraire sous forme de liste, tous les éléments divisibles par n
d'une liste d'entiers. b) Extraire d'une liste L une liste formée d'au plus B valeurs
inférieures à F. c) construire l'inverse une liste (le début devient la fin). d) Position du minimum dans une liste (0 si la liste est vide, 1 s'il
est au début, etc.). e) Découper une liste en deux listes de taille identique (à une unité
près). f) Décomposer une liste d'entiers en une liste de nombres négatifs et
une liste de nombres strictement positifs. g) Trier une liste par ordre croissant.
Exercice 5.4.
Ecrire un algorithme pour chacun des problèmes suivant.
a) Deux listes ont-elles la même longueur ? b) Plus longue suite constituant un début (liste préfixe) commun
à deux suites. c) Plus longue suite constituant une fin (liste suffixe) commune
à deux suites. d) Longueur de la plus longue sous-suite contigüe (liste infixe) commune
à deux suites. e) Longueur de la plus longue sous-suite dont les éléments sont présents
dans le même ordre dans deux listes (liste incluse).
Exerice 5.5. a) Ecrire un algorithme qui donner le nombre de pièces de monnaie de
chaque sorte (1ct à 2€) présents dans une liste de pièces. b) Soit une somme m à payer, une somme n≤m réellement payée par un
client et un tableau donnant le nombre de chaque sorte de pièces détenues par
le vendeur. Ecrire un algorithme qui donne la liste de pièce rendue au client
par le vendeur pour faire l'appoint. La liste sera la plus courte possible.
Exercice 5.6.
Dans une liste doublement chainée, on dispose en plus des
actions élémentaires : Alafin(L) : se place sur le dernnier élément d'une
liste non vide. Auprecedent(L) : se place sur l'élément précédent d'une
liste d'au moins deux éléments (pointe sur L[i−1] si on pointait sur
L[i]). Estaudebut(L) : teste si on pointe sur le premier élément
d'une liste non vide. Modifier chacun des algorithmes ci-dessus utilisant une liste pour
prendre en compte ces actions supplémentaires et diminuer quand c'est possible
la complexité.