Activité : Tableaux de valeurs

Consigne

Durant les 90 prochaines minutes, votre tâche est de réaliser une série de petits programmes à partir de structogrammes. Pour réaliser ces programmes, vous devrez afficher des messages à l’écran, lire des valeurs au clavier, utiliser des affectations, des structures de choix et des structures de boucle.

Résultat attendu

  • Un projet NetBeans pour chaque programme.

Objectifs

À la fin de ce travail, vous devez être capable de :

  1. écrire un programme en utilisant des déclarations de variables simples et de tableaux, des affectations, des structures de choix et des structures de boucle à partir d’un GNS.

Ressources

Logiciel :

  • Oracle NetBeans

Documents :

Fragments de code (snippets):

Ces fragments de code vous sont fournis pour vous aider à réaliser vos programmes. Prenez la peine de taper le code plutôt que de faire du copier-coller, de façon à vous familiariser avec la syntaxe et ainsi, l’apprendre.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package ch.epaifribourg.ict.username.m403; // Remplacer username par 
                                           // votre nom d'utilisateur.

// Importe le module Scanner si une variable de type Scanner est
// nécessaire pour lire des valeurs dans l'entrée standard.
import java.util.Scanner;

public class NomDuProgramme { // Remplacer NomDuProgramme par le nom 
                              // de votre programme en UpperCamelCase.

    // Si nécessaire, insérer ici les constantes. Par exemple:
    private static final int MA_CONSTANTE = 1; // Remplacer MA_CONSTANTE par  
                                               // le nom de votre constante  
                                               // en UPPER_SNAKE_CASE, int 
                                               // par le type adéquat et
                                               // 1 par la valeur souhaitée.


    // La procédure principale est le point d'entrée de votre 
    // programme, la première instruction de cette procédure est
    // la première instruction du programme.
    public static void main(String[] args) {

        // Insérer ici les déclarations et les
        // instructions de votre programme.
      
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Pour chaque valeur entière de i de min à max compris.
for (int i = min; i <= max; i += 1) { // Remplacer min par la valeur min;
                                      // remplacer max par la valeur max.

    // Instructions à répéter.
    // La variable de boucle i est définie uniquement 
    // dans ce bloc (entre les deux accolades).

}

// Exemple :
// Pour chaque valeur entière de i de 0 à 10 compris.
for (int i = 0; i <= 10; i += 1) { 
    System.out.println(i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Pour chaque valeur entière de i de max à min compris par pas de -1. 
for (int i = max; i >= min; i -= 1) { // Remplacer min par la valeur min;
                                      // remplacer max par la valeur max.

    // Instructions à répéter.
    // La variable de boucle i est définie uniquement 
    // dans ce bloc (entre les deux accolades).

}

// Exemple :
// Pour chaque valeur entière de i de 10 à 0 compris par pas de -1.
for (int i = 10; i >= 0; i -= 1) { 
    System.out.println(i);
}

Tâches

Réalisez les programmes décrits ci-après en Java et documentez votre code à l’aide de commentaires.

Tableaux et références

En Java, les tableaux sont créé à l’aide de l’opérateur new avec la syntaxe suivante :

<type>[] anArray = new <type>[<numOfElements>]

Dans cette ligne <type> doit être remplacé le nom du type des éléments et <numOfElements>, par une expression de type entier (int) dont la valeur est le nombre d’éléments du tableau. Il est possible de créer un tableau de n’importe quel type.

L’opérateur new demande au système d’allouer un bloc de mémoire suffisamment grand pour stocker le nombre de valeurs spécifié. Ce bloc de mémoire est alloué dans une zone de la mémoire appelée « tas » (heap). Les variables, quant à elles, sont stockées dans une autre zone de la mémoire appelée « pile » (stack). Dans notre exemple, la valeur de la variable anArray n’est donc pas le tableau lui-même, mais une référence au tableau qui se trouve dans le tas. Dans le code de la figure 1, lorsque l’on affecte la valeur de la variable anArray à la variable anAlias, on attribue à la variable anAlias la valeur de la variable anArray, c’est-à-dire une référence au tableau. Les deux variables anArray et anAlias référencent le même tableau; on peut donc lire ou modifier les éléments du tableau à travers l’une ou l’autre de ces deux variables.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
...

int n = 10;
float f = -2.8185f;

// Crée un tableau de n élément de type float et 
// stocke sa référence dans la variable anArray
float[] anArray = new float[n];

// Déclare une variable de type tableau de float
float[] anAlias;

// Crée une chaîne de caractères et stocke sa
// référence dans la variable s.
String s = "Valeurs du tableau référencé par anArray : ";
   

// Affiche les valeurs du tableau référencé 
// par anArray.
System.out.println(s);
for (int i = 0; i < anArray.length; i += 1) {
    System.out.println(anArray[i]);
}

// Stocke une référence au tableau dans anAlias.
// Les variables anArray et anAlias référencent
// le même tableau.
anAlias = anArray;

// Stocke la valeur 22 dans le sixième élément
// du tableau référencé par anAlias.
anAlias[5] = f;

// Affiche les valeurs du tableau référencé 
// par anArray (le sixième élément contient
// maintenant la valeur -2.8185)
System.out.println(s);
for (int i = 0; i < anArray.length; i += 1) {
    System.out.println(anArray[i]);
}

...
Fig 1. – Tableau et références

Le schéma de la figure 2 illustre l’organisation de la mémoire de JVM (Java Virtual Machine) pour le programme de la figure 1. Aux positions 0 et 1 de la pile (stack), on trouve les valeurs des variables n et f, alors que les positions 2, 3 et 4 contiennent des références à des valeurs qui se trouve dans le tas (heap).

image/svg+xmlPile (stack) 0 1 2 3 4 131070 131071 32 bits Tas (heap 0x0000000A 0xc0340000 0x04572398 0x04572398 0x300AE45 0x00000000 0x00000000 float f int n int[] anArray int[] anAlias String s id:0x04572398 "Valeurs du tableau référencé par anArray : " id:0x300AE45
Fig. 2 – Organisation de la mémoire de la JVM

À retenir : Lorsqu’on affecte la valeur d’une variable de type tableau à une autre variable de type tableau, la valeur qui est copiée est la référence au tableau et non le tableau lui-même.

Copier et redimissionner un tableau

L’affectation ne permet de copier un tableau, pour cela, on doit d’abord créer un tableau puis copier chacun des éléments à l’aide d’une boucle for comme le montre la code de la figure 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
...

// Crée un tableau et stocke sa référence dans la 
// variable anArray
int[] anArray = new int[10];

// Affiche les valeurs du tableau référencé 
// par anArray.
System.out.println("Valeurs du taleau référencé par anArray : ");
for (int i = 0; i < anArray.length; i += 1) {
    System.out.println(anArray[i]);
}

// Crée un nouveau tableau avec le même nombre
// d'éléments que le tableau référencé par anArray.
int[] aNewArray = new int[anArray.length];

// Copie les éléments du tableau référencé par anArray 
// dans le nouveau tableau.
for (int i = 0; i < anArray.length; i += 1) {
    aNewArray[i] = anArray[i];
}

// Stocke la valeur 22 dans le sixième élément
// du tableau référencé par anAlias.
aNewArray[5] = 22;

// Affiche les valeurs du tableau référencé 
// par anArray (le sixième élément n'a pas 
// été modifié).
System.out.println("Valeurs du taleau référencé par anArray : ");
for (int i = 0; i < anArray.length; i += 1) {
    System.out.println(anArray[i]);
}

...
Fig 3. – Copier un tableau avec une boucle

Comme le nombre d’éléments d’un tableau doit être fixé lors de sa création, celui-ci ne peut pas changer par la suite. Pour modifier la taille d’un tableau, on doit d’abord créer un nouveau tableau avec la bonne taille, copier les éléments du tableau existant dans ce nouveau tableau puis remplacé la référence de l’ancien tableau par celle du nouveau tableau avec une affectation. Le code de la figure 4 illustre cette algorithme.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...

// Crée un tableau et stocke sa référence dans la 
// variable anArray
int[] anArray = new int[10];

// Fais quelque chose avec le tableau référencé 
// par anArray ...

// Crée un tableau temporaire avec 10 éléments de 
// plus que le tableau référencé par anArray.
int[] tmpArray = new int[anArray.length + 10]

// Copie les éléments du tableau référencé par anArray 
// dans le tableau temporaire.
for (int i = 0; i < anArray.length; i += 1) {
    tmpArray[i] = anArray[i];
}

// Affecte la référence au nouveau tableau à la 
// variable anArray
anArray = tmpArray;

...
Fig 4. – Redimensionner un tableau avec une boucle

Après l’affectation de la référence du tableau temporaire à la variable anArray, le tableau de dix éléments créé à la ligne 5 n’est plus référencé par aucune variable. Lorsque cela se produit, un dispositif appelé « ramasse-miettes » (garbage collector ou GC) se charge de libérer la mémoire occupée par le tableau devenu inutile.

Comme il est assez fréquent de devoir copier les éléments d’un tableau dans un nouveau tableau de taille différente, la bibliothèque standard de Java propose la fonction Arrays.copyOf qui nous permet de faire cela en une seule instruction. Le code de la figure 5 est équivalent à celui de la figure 4.

1
2
3
4
5
6
7
8
9
10
11
12
...

int[] anArray = new int[10];

// Fais quelque chose avec le tableau référencé 
// par anArray ...

// Crée un nouveau tableau, copie les valeurs et
// affecte la référence à la variable anArray.
anArray = Arrays.copyOf(anArray, anArray.length + 10);

...
Fig 5. – Redimensionner un tableau avec la bibliothèque standard

Pour illustrer l’usage de la fonction Array.copyOf, nous allons créer un programme ReadNumers qui demande à l’utilisateur de saisir autant de nombres entiers positifs qu’il le souhaite et terminer en saisissant une chaîne vide. Pour cela, nous allons créer un tableau initial de CHUNK éléments que l’on fera grossir de CHUNK éléments à chaque fois que cela est nécessaire. Pour la déclaration de la constante CHUNK, veuillez vous référer aux fragments de code fournis.

Créer un nouveau projet ReadNumbers et réaliser le programme conformément au structogramme de la figure 6.

Fig. 6 – Structogramme du programme ReadNumbers
Fig. 6 – Structogramme du programme ReadNumbers

La figure 7 montre un exemple d’exécution du programme.

Veuillez saisir un nombre ou une chaîne vide pour terminer : 4
Veuillez saisir un nombre ou une chaîne vide pour terminer : 7
Veuillez saisir un nombre ou une chaîne vide pour terminer : 6
Veuillez saisir un nombre ou une chaîne vide pour terminer : 2
Veuillez saisir un nombre ou une chaîne vide pour terminer : 23
Veuillez saisir un nombre ou une chaîne vide pour terminer : 1
Veuillez saisir un nombre ou une chaîne vide pour terminer :

Les valeurs saisies sont :
4, 7, 6, 2, 23, 1
Fig 7. – Exemple d'exécution

Trier un tableau de valeur

Créer un nouveau projet BubbleSort (tri à bulle) et réaliser le programme conformément au structogramme de la figure 8.

Fig. 8 – Structogramme du programme BubbleSort
Fig. 8 – Structogramme du programme BubbleSort

Documentez les différentes parties de votre programme à l’aide de commentaires, en prenant soin de bien mettre en évidence les instructions qui correspondent à l’algorithme de tri à bulle. Veillez à ce que chaque partie de votre code (saisie des nombre, affichage, tri du tableau, etc.) soit bien repérable et bien expliquée.