Construire une liste à partir d’une source de données

Il s’agit de parcourir la liste et de faire le produit d’une part les entiers positifs et d’autre part celui des entiers négatifs. La présence éventuelle du 0 qui selon le statut qu’on lui donne est un positif ou non (positifs strictement ou non) peut poser un problème d’interprétation de l’énoncé. Le minimum est d’en parler. Disons, pour ce corrigé qu’il n’est ni positif ni négatif et qu’il doit donc ne pas intervenir dans aucun produit qu’il annulerait. Les cas spéciaux sont les suivants : • Liste vide ou ne contenant que des zéros : le résultat est indéterminé. • Absence de positifs ou (exclusif) absence de négatifs : le résultat est partiellement indéterminé.La difficulté de cet exercice tient également au problème du double résultat qu’il s’agit de retourner.Plusieurs solutions sont possibles, la plus simple consistant à utiliser deux entrées modifiées. On utilisera un code de statut pour rendre compte des résultats spéciaux vs. standard dont les valeurs signifient les configurationsEntrée modifiée : le produit des positifs et le produit des négatifs. Sortie : code de statut qui peut prendre l’un des 4 états TOUT (4), UNIQUEMENT_POSITIFS (2), UNIQUEMENT_NEGATIFS (1), RIEN (0). Algorithme : FONCTION produits(l: liste<entier>, pos, neg: entier): statut VAR pos_ok, neg_ok: booléen; p: place;

Couper une liste en deux Étude

Dans les cinq cas de figure, il s’agit de vérifier l’existence d’une position de coupe dans la chaîne, et le cas échéant d’effectuer celle-ci, puis de savoir retourner les deux chaînes. Le cas à évacuer en début de fonction est celui de la liste vide. Ensuite, nous devons, respectivement pour les cinq cas : • A – vérifier que le pointeur désigne bien un maillon de la liste ; • B – vérifier que la liste contient bien la donnée x ; • C – vérifier que la liste contient au moins k éléments ; • D – identifier la valeur minimale de la liste ; • E – mesurer la longueur de la liste. Les cas A, B et C sont très similaires et doivent intégrer les cas de tête et de queue de liste. Les cas D, E nécessitent un premier parcours complet de la liste.Tous les cas sauf le cas E doivent intégrer la possibilité d’une coupure devant la tête de liste. Le cas E revient quasiment au cas B après l’identification du minimum de la liste. Dans tous les cas, il est pertinent de retourner un statut d’exécution qui indique si l’opération a été effective ou bien transparente (auquel cas, il n’y a pas eu production d’une seconde liste). Il peut y avoir erreur si l’un ou l’autre des deux pointeurs sur les listes à modifier est NULL ou bien dans le cas particulier du A (B et C sont discutables) si le pointeur donné pointe sur une autre liste. Comme nous sommes scrupuleux, nous indiquons également par le statut d’exécution si la seconde liste n’était pas initialisée à NULL avant l’opération effective (mise en garde : écrasement d’une ancienne valeur).

Supprimer un sous-ensemble d’une liste

Une fois n’est pas coutume (petit mensonge d’ingénieur), nous procédons à une rétro conception du principe algorithmique général à partir des cinq cas étudiés et réalisés précédemment.Cet exercice avec ses cinq cas de figure est une extension du principe algorithmique vu dans l’exercice 2.5 (supprimer des éléments). La façon de définir le critère de sélection des noeuds à supprimer change selon les cas, mais le schéma général ne change pas. Dans tous les cas, il s’agit de traiter spécialement la chaîne préfixe (de tête) constitué d’une succession de noeuds à éliminer, puis s’il reste au moins un élément, d’éliminer tous les éléments répondant au critère et situés au-delà de la tête. Le cas A donne lieu à une version simplifiée de l’algorithme général, laquelle profite à plein de la régularité des intervalles de suppression.La méthode générale de résolution reste la même, seul le critère de choix des éléments à supprimer change. Pour illustrer ce fait, dans la partie Spécification de l’algorithme, le second paramètre de la fonction removeAll est en réalité une fonction nommée critère. Cette fonction critère a pour paramètre un entier (la valeur extraite de la liste) et pour sortie un booléen indiquant si la valeurrépond au critère de suppression. Cette fonction critère peut avoir d’autres paramètres, notamment un entier indiquant le seuil à partir duquel effectuer la suppression pour les cas D et E.Le cas de figure A, du fait de la régularité des intervalles de suppression conduit à une version simplifiée du schéma général précédent. On élimine notamment un niveau d’imbrication de boucles tantque, traduction du fait qu’il n’existe pas de chaîne de plusieurs éléments directement successifs à supprimer.