Utiliser l'insertion dichotomique
Utiliser l'insertion dichotomique
Notions utilisées
- Utilisation de fonctions, passage de paramètres, prototypage
- Manipulation de tableaux statiques
Cahier des charges
Le programme saisit successivement des entiers à partir du clavier pour les insérer dans un tableau en faisant en sorte que les entiers soient toujours classés par ordre croissant ; le nombre maximum d'entiers saisis est de 10 ; le programme commence par demander le nombre d'entiers à saisir. Le tableau obtenu est affiché après la fin de la saisie.
Les entiers seront insérés en utilisant la dichotomie. Si l'utilisateur indique un entier à insérer qui existe déjà, cet entier n'est pas insérer, un message l'indique à l'utilisateur.
Spécifications
Le nombre maximum de données fournies par l'utilisateur (que nous avons choisi égal à 10) sera une constante du programme notée MAX. Le programme n'aura pas de variable globale. On pourra reprendre partiellement le programme précédent. On modifiera la fonction saisit et on ajoutera deux fonctions :
- Une fonction de prototype :
- int chercheIndice(int * tableau, int taille, int cle);
qui suppose que le tableau passé en paramètre est trié par ordre croissant et qui
- si la "cle" ne figure pas dans le tableau, retourne l'indice auquel il faut la mettre pour respecter l'ordre croissant ;
- si la "cle" figure déjà retourne -1.
Le paramètre taille donne le nombre d'entiers contenus par le tableau.
- Une fonction de prototype :
- void insere(int * tableau, int taille, int cle, int place)
qui insère la "cle" dans le tableau contenant déjà "taille" entiers, à la place indiquée.
Corrigé
Voir le corrigé
Irène Charon
Last modified: Fri Sep 10 09:16:56 MET DST 1999