Exercice langage C: Insertion dans un tableau
Dans cet exercice vous allez apprendre à insérer une nouvelle valeur au bon endroit dans un tableau trié.
Le programme ci-dessous crée un tableau d'entier triés par ordre croissant. Seuls nb_element-1 éléments sont insérés dans le tableau (la derniière case vaut ), de telle manière qu'il reste une place de libre pour un nouvel élement.
Copiez le programme dans Emacs et remplacez les points de suspension par du code demandant à l'utilisateur d'entrer un nombre à insérer dans le tableau. Le programme devra ensuite insérer le nombre dans le tableau, de manière à ce qu'il soit toujours correctement trié par ordre croissant.
Finalement, votre programme devra afficher à l'écran le tableau avec le nouvel élément.
Indice: commencez par identifier la place du nouvel élément dans le tableau, puis déplacez les éléments à sa droite d'une case vers la droite, afin de libérer une position.
#include
#include
using namespace std;
int main(int argc, char **argv) {
const int nb_elements = 15;
int tableau[nb_elements];
srand(time(0));
tableau[0] = rand() % 50;
for (int i=1; i<nb_elements-1; i++)
tableau[i] = tableau[i-1] + (rand() % 20);
tableau[nb_elements-1] = 0;
cout << "Tableau initial:" << endl;
for (int i=0; i<nb_elements; i++)
cout << tableau[i] << " ";
cout << endl;
...
return 0;
}
#include
#include
using namespace std;
int main(int argc, char **argv) {
const int nb_elements = 15;
int tableau[nb_elements];
int n, pos;
srand(time(0));
tableau[0] = rand() % 50;
for (int i=1; i<nb_elements-1; i++)
tableau[i] = tableau[i-1] + (rand() % 20);
tableau[nb_elements-1] = 0;
cout << "Tableau initial:" << endl;
for (int i=0; i<nb_elements; i++)
cout << tableau[i] << " ";
cout << endl;
cout << "Entrez un entier a inserer dans le tableau: ";
cin >> n;
/* calcul de la position a laquelle on va
* inserer le nouvel element */
pos = 0;
while (tableau[pos] < n)
pos++;
// decalage des elements vers la droite
for (int i=nb_elements-1; i>pos; i--)
tableau[i] = tableau[i-1];
// insertion du nouvel element
tableau[pos] = n;
cout << endl << "Tableau avec le nouvel element:" << endl;
for (int i=0; i<nb_elements; i++)
cout << tableau[i] << " ";
cout << endl;
return 0;
}