Structures séquentielles simples

Structures séquentielles simples

Exercice 2.3 Extraire deux listes à partir d’une liste *** Soit une liste de nombres relatifs. Écrire un algorithme permettant de séparer cette liste en deux listes : la première ne comportant que des entiers positifs ou nuls, et la seconde ne comportant que des nombres négatifs. Exercice 2.4 Permuter deux places d’une liste *** Écrire un algorithme sur une liste simplement chaînée qui échange les positions des nœuds données par deux pointeurs t et v. Exercice 2.5 Supprimer des éléments ** Soit L une liste chaînée. Écrire trois algorithmes tels que : • dans le premier on supprime toutes les occurrences d’un élément donné x ; • dans le deuxième, on ne laisse que les k premières occurrences de cet élément et on supprime les suivantes ; • dans le troisième, pour chaque élément de la liste, on ne laisse que sa première occurrence. Concevez le second algorithme en adaptant le premier, puis concevez le dernier en exploitant le second. Exercice 2.6 Inverser une liste ** Écrire un algorithme qui inverse une liste chaînée sans recopier ses éléments. Réaliser une version itérative et une autre récursive. Exercice 2.7 Construire une liste à partir d’une source de données * Concevoir un premier algorithme qui construit une liste chaînée linéaire à partir d’un tableau, et un second qui duplique une liste chaînée existante. Exercice 2.8 Refermer une liste sur elle-même * Concevoir un algorithme qui transforme une liste simplement chaînée linéaire en liste simplement chaînée circulaire. Exercice 2.9 Effectuer et retourner deux calculs sur une liste ** Concevoir un algorithme qui calcule et retourne respectivement le produit des éléments positifs et celui des éléments négatifs d’une liste simplement chaînée d’entiers. Exercice 2.10 Couper une liste en deux ** Concevoir un algorithme qui sépare une liste simplement chaînée d’entiers en deux listes : • A – à partir d’un pointeur sur le maillon qui devient tête de la seconde liste de sortie ; • B – juste devant le premier maillon contenant une valeur donnée x ; • C – à partir de la k ième position (c’est-à-dire k maillons dans la première liste de sortie et le reste dans la seconde) ; • D – juste devant le maillon contenant la valeur minimale de la liste ; • E – telles que les deux listes de sortie aient même longueur n, ou que la première soit de longueur n+1 et la seconde de longueur n. 46 Problème Exercice 2.11 Supprimer un sous-ensemble d’une liste * Concevoir un algorithme qui supprime : • A – un maillon sur deux, en commençant par la tête de liste, • B – les maillons contenant des éléments impairs, • C – les maillons contenant des éléments pairs, • D – les maillons contenant des éléments supérieurs à un seuil donné, • E – les maillons contenant des éléments inférieurs à un seuil donné, d’une liste simplement chaînée (d’entiers).

PROBLÈME

Problème 2.1 Saisir, enregistrer puis évaluer un polynôme*** Enregistrer les coefficients et les exposants d’un polynôme dans une liste chaînée. Évaluer ce polynôme pour une valeur donnée de x. Utiliser au moins deux modules dans ce programme : • l’un pour construire la liste sur la base des coefficients et des exposants, qui sont saisis au clavier ; • et le second afin d’évaluer le polynôme pour la valeur x, également saisie au clavier. Corrigés des exercices et des problèmes EN PRÉAMBULE Pour la réalisation en C de tous les algorithmes spécifiés ci-dessous, on définit la structure de liste chaînée suivante dont on précisera au cas pas cas, le type . Les structures utilisées pour les spécifications des algorithmes portent le même nom et sont construites de la même manière. typedef struct listNode { content; struct place *succ; // listes simplement chaînées struct place *prev; // listes doublement chaînées } listNode; typedef listNode* list; typedef list* plist; #define ERR -1 // code d’erreur (lisibilité des exemples) Les quelques implantations C de méthodes élémentaires de manipulation de la liste chaînée conformes au contrat du type abstrait, pourront s’avérer utiles dans l’écriture de vos programmes  d’implantation C de vos algorithmes, notamment en épurant votre code d’une trop grande quantité Dunod – La photocopie non autorisée est un délit 47 Chapitre 2 • Structures séquentielles simples de ‘->’, ‘*’ et ‘&’ qui nuisent à leur lisibilité. Vous pourrez ainsi vous rapprocher de la vision algorithmique du « qu’est-ce que ça fait ? » plutôt que de la vision programmatique du « comment ça se fait ? ». content(list l) {return (l->content);} int isempty(list l) {return (l == NULL);} list succ(list l) {return l->succ;} int islast(list l) {return isempty(succ(l));} pour les solutions algorithmiques, les fonctions sont les suivantes : FONCTION content(l : list) DEBUT RETOURNER l→content FIN FONCTION isempty(l : list) VAR vide : booléen DEBUT SI(l=NULL)ALORS vide ← vrai SINON vide ← faux FINSI RETOURNER vide FIN FONCTION succ(l : list) : list DEBUT RETOURNER l→succ FIN FONCTION islast(l : list) DEBUT RETOURNER isempty(succ(l)) FIN 48 Corrigés des exercices Enfin, le constructeur suivant pourra vous aider à simplifier vos écritures pour l’allocation d’un nouveau nœud de liste : list newSingletonList(int content) { list l = malloc(sizeof(listNode)); // allocation mémoire l->content = content; // affectation du contenu l->succ = NULL; return l; } Et son équivalent en pseudo langage : FONCTION newSingletonList(content : entier) : list VAR nouveau : list DEBUT RESERVER(nouveau) nouveau→content ← content nouveau→succ ← NULL RETOURNER nouveau FIN.