Outils pour utilisateurs
Epreuve écrite du 6 décembre 2016
File
2.4 Implémentez la primitive defiler(F) en .
Les éléments importants dans la solution sont l'impératif sur la complexité en temps . Beaucoup de solutions ont omis de libérer la mémoire occupée par la cellule contenant l'élément à supprimer (défiler).
Perles choisies
On apprend de ses erreurs … Cette question a donné lieu à des formulations souffrant d'imprécisions plus ou moins graves … Votre défi consiste à corriger les erreurs ou apportez les précisions qui manquent à ces propositions …
(Réponses reprises de copies d'étudiants)
File defiler(File F) {
F->next = (F->next)->next;
return F;
}
ou pire
file defiler(F) {
if (F->next == F)
return NULL;
else
F->next = (F->next)->next;
return F;
}
Lost in space syndrom – c'est une erreur assez commune: la cellule pointée au départ par F→next n'est pas détruite. Fuite mémoire ! Mais aussi, le cas F == NULL ? M'intéresse pas …
File defiler(File F) {
File p = F->next;
while (p->next != F) (
File x = p;
p = p->next;
}
x->next = F;
return F;
}
Hmm … une boucle while qui tourne en temps constant $O(1)$, ça bat tous le sordinateurs quantiques …
file defiler(file F) {
F = F->next;
(F-1)->next = F;
return F;
C'est une file arithmétique ?
File defiler(F) {
if (F == NULL) {
return NULL;
}
return F;
}
Travailler c'est trop dur … La fonction identité, on t'a reconnu !!!
defiler(File F) {
if (F == NULL || F->next == NULL) {
return NULL;
}
else {
return F->next;
}
Pourquoi se poser toutes ces questions (la condition du if) ??? Le champ next n'est jamais NULL dans une liste circulaire … Total: la fonction ne modifie pas la file et retourne seulement un pointeur sur la tête de file …
—
Outils de la page
