Manipulation de listes d'entiers

Le problème

Il s'agit d'écrire un certain nombre de procédures ou fonctions permettant de manipuler des listes d'entiers.

Programmation

Ecrire les procédures ou fonctions suivantes :

Traitement d'une liste d'entiers

• initialisation d'une liste de n entiers (n est entré au clavier par l'utilisateur),
• initialisation AU HASARD d'une liste de n entiers entre 0 et 100 (n est entré au clavier par l'utilisateur),
• afficher une liste d'entiers,
• inversion en place du sens de la liste,
• inversion en copie du sens de la liste,
• insertion en place d'un élément à une position donnée,
• insertion en copie d'un élément à une position donnée,
• suppression en place d'un élément à une position donnée,
• suppression en copiee d'un élément à une position donnée,
• suppression en copie de tous les entiers pairs de la liste,
• suppression en place de tous les entiers pairs de la liste,
• écrire une procédure ou fonction de recherche simple d'un élément dans une liste. Il s'agit de donner une liste et un entier est de savoir si cet entier fait partie de la liste et si oui en quelle position. Votre procédure ou fonction devra donc rendre la position de l'entier dans la liste si l'entier est bien dedans et -1 s'il n'est pas dans la liste.

Traitement de deux listes d'entiers

• calculer l'union de deux listes,
• calculer l'intersection de deux listes,
• calculer la différence (éléments propres à chaque liste) de deux listes.

Recherche dichotomique dans une liste d'entiers

Ecrire une procédure ou fonction de recherche dichotomique d'un élément x dans une liste. Le principe de recherche dichotomique ne peut s'appliquer que sur une liste triée (dans l'ordre croissant par exemple). Le mécanisme est le suivant

• considérer l'élément médian med de la liste (le milieu de la liste à un prés),
• comparer cet élément médian med à l'élément x à rechercher.
• si x>med alors recommencer la recherche dans la partie de la liste située après med,
• si x<med alors recommencer la recherche dans la partie de la liste située avant med.
• la recherche s'arrête lorsque l'élément médian est égal à x (on a alors trouvé x dans la liste) ou lorsque l'on est arrivé en début ou en fin de liste (on sait alors que x n'est pas dans la liste).

Choix des opérations

Vous écrirez une procédure menu permettant à l'utilisateur de choisir l'opération qu'il désire effectuer parmi toutes celles programmées.