Les types de référence : utilisation des tableaux
Concept des tableaux :
Une variable ordinaire ne peut stocker qu'une seule donnée. Si vous avez besoin d'une variable pour stocker plusieurs données, vous pouvez déclarer la varible comme un tableau.
Déclaration de tableaux :
Syntaxe 1 : type_de_données nom_variable[] ; int i[] ;
Syntaxe 2 : type_de_données[] nom_variable ; int[] i ;
Après avoir déclaré un tableau, vous devez spécifier l'espace du tableau.
Spécification de l'espace : nom_variable = new type_de_données[longueur] ; i = new int[10] ;
Écriture combinée :
Écriture 1 : déclarer un tableau de longueur 5 appelé tab
int[] tab = new int[5] ; déclarer un tableau
Attribution de valeurs aux éléments du tableau via les indices de tableau. Chaque tableau a un indice commençant à 0 et se terminant à longueur-1. Si la longueur est 5, les indices sont de 0 à 4.
tab[0] = 1; tab[1] = 2; tab[2] = 3; ......
Écriture 2 :
int[] tab1 = new int[]{10,20,30,40,50};
Écriture 3 :
int[] tab2 = {10,20,30,40,50};
package com.jour4.tableau;
/*
Déclaration et utilisation de tableaux
*/
public class ExempleTableau01 {
public static void main(String[] args) {
// Déclaration d'un tableau
int[] tab = new int[5];
// Si aucune valeur n'est attribuée aux indices, que contient le tableau ?
// Après sa création, si aucun élément n'est initialisé, chaque élément a la valeur par défaut 0
System.out.println(tab[0]);
System.out.println(tab[1]);
// Attribution de valeurs aux indices
tab[3] = 50;
System.out.println(tab[3]);
// tab[4] = "bonjour"; // Les types doivent correspondre
// Écriture 2
int[] tab2 = new int[]{10,20,30};
System.out.println(tab2[1]);
// La longueur du tableau est déterminée lors de sa déclaration
// On ne peut pas accéder à un indice supérieur à la longueur, car on ne peut pas attribuer de valeur à un indice hors limites
// System.out.println(tab2[3]); // Erreur d'indice de tableau hors limites
// tab2[3] = 40;
// System.out.println(tab2[3]);
// Écriture 3
int[] tab3 = {10,20,30,40,50};
System.out.println(tab3[0]);
System.out.println(tab3[1]);
System.out.println(tab3[2]);
System.out.println(tab3[3]);
System.out.println(tab3[4]);
// Parcours du tableau avec une boucle
// On peut obtenir dynamiquement la longueur du tableau avec l'attribut length
for (int indice = 0; indice < tab3.length ; indice++) {
System.out.println(tab3[indice]);
}
// Raccourci clavier itar + Entrée + Entrée
for (int indice = 0; indice < tab3.length; indice++) {
int element = tab3[indice];
System.out.println(element);
}
// Boucle for-each améliorée
for (int element : tab3) {
System.out.println(element);
}
// Raccourci clavier iter + Entrée + Entrée
for (int element : tab3) {
System.out.println(element);
}
// Créer une méthode qui prend un tableau en paramètre, le parcourt
// puis concatène les valeurs du tableau en une chaîne de caractères et affiche le résultat
afficherTableau(tab3);
afficherTableau(tab);
}
public static void afficherTableau(int[] tab){
for (int indice = 0; indice < tab.length; indice++) {
int element = tab[indice];
System.out.print(element + " ");
}
}
}
package com.jour4.tableau;
import java.util.Scanner;
public class ExempleTableau03 {
public static void main(String[] args) {
// Exercice : utiliser un tableau pour enregistrer les notes de 5 étudiants,
// puis afficher chaque note et la note maximale
// Création d'un tableau de longueur 5
int[] notes = new int[5];
Scanner scanner = new Scanner(System.in);
int max = 0;
// Enregistrement des notes via une boucle
for (int i = 0; i < notes.length; i++) {
// Attribution des valeurs via l'indice (enregistrement des notes)
System.out.println("Veuillez entrer la note du "+(i+1)+"ème étudiant :");
notes[i] = scanner.nextInt();
// Pendant l'enregistrement, comparer chaque note avec max
if (notes[i] > max){
max = notes[i];
}
}
// Affichage des notes
for (int i = 0; i < notes.length; i++) {
System.out.println("La note du "+(i+1)+"ème étudiant est : "+notes[i]);
}
System.out.println("La note maximale est : "+max);
}
}
Caractéristiques des tableaux :
- La longueur d'un tableau est fixe, elle ne peut pas être modifiée après sa déclaration
- Les éléments du tableau sont stockés de manière ordonnée selon leurs indices, on peut accéder à un élément via son indice
- Un tableau ne peut stocker que des données du type spécifié
package com.jour4.tableau;
import java.util.Scanner;
public class ExempleTableau02 {
public static void main(String[] args) {
// Déclaration d'un tableau
int[] tab = new int[10];
tab[0] = 10;
tab[1] = 20;
tab[2] = 30;
tab[3] = 40;
tab[4] = 50;
System.out.println(tab);
afficherTableau(tab);
}
public static void afficherTableau(int[] tab){
for (int i = 0; i < tab.length; i++) {
System.out.print(tab[i] + " ");
}
}
}
Tableaux à deux dimensions
Un tableau qui contient un ou plusieurs autres tableaux
Syntaxe : type_de_données[][] nom_tableau = new type_tableau[m][n];
Syntaxe : type_de_données[][] nom_tableau = new type_tableau[][]{{...},{...},{...}};
Syntaxe : type_de_données[][] nom_tableau = {{...},{...},{...}};
package com.jour4.tableau;
import java.util.Scanner;
public class ExempleTableau04 {
public static void main(String[] args) {
/*
// Création d'un tableau à deux dimensions
int[][] tab = new int[3][4];
System.out.println(tab[0]);
//{{0,0,0,0},{0,0,0,0},{0,0,0,0}}
System.out.println(tab[0]);
System.out.println(tab[1]);
System.out.println(tab[2]);
System.out.println(tab[0][0]);
System.out.println(tab[0][1]);
System.out.println(tab[0][2]);
System.out.println(tab[0][3]);
for (int i = 0; i < tab.length; i++) {
for (int j = 0; j < tab.length; j++) {
System.out.println(tab[i][j]);
}
}
*/
// Trois classes, chacune avec 5 étudiants
// Enregistrer les notes de chaque étudiant des trois classes
// Afficher le total de points pour chaque classe
// 1. Créer un tableau à deux dimensions pour les classes et les étudiants
int[][] notesClasses = new int[3][5];
// 2. Créer un objet d'entrée
Scanner sc = new Scanner(System.in);
// 3. Boucle d'enregistrement
for (int i = 0; i < notesClasses.length; i++) {
for (int j = 0; j < notesClasses[i].length; j++) {
System.out.println("Veuillez entrer la note du "+ (i+1)+"ème classe, "+
"le "+ (j+1) + "ème étudiant :");
notesClasses[i][j] = sc.nextInt();
}
}
// Calcul du total
int totalPoints = 0;
for (int i = 0; i < notesClasses.length; i++) {
for (int j = 0; j < notesClasses[i].length; j++) {
totalPoints += notesClasses[i][j];
}
System.out.println("Le total de points du "+(i+1)+"ème classe est : "+ totalPoints);
// Réinitialiser le total pour le prochain calcul
totalPoints = 0;
}
}
}
Triage des tableaux
Utilisation d'algorithmes différents pour trier les données d'un tableau dans un ordre spécifique
Algorithmes de tri courants : à bulles, par sélection, rapide, par insertion, de tas, de Shell...
Triage à bulles
Principe : Comparer les éléments adjacents, si le premier est plus grand que le second, les échanger. Après la première passe, le plus grand élément est à la fin. Répéter l'opération pour trouver le plus grand élément restant à chaque passe.
package com.jour4.triage;
import java.util.Scanner;
public class ExempleTriageBulle {
public static void main(String[] args) {
// Déclarer un tableau
int[] donnees = {86, 57, 68, 25, 34, 2};
System.out.println("Avant le tri :");
afficherTableau(donnees);
triBulle(donnees);
System.out.println("Après le tri :");
afficherTableau(donnees);
}
// Méthode de tri à bulles
public static void triBulle(int[] tab){
for (int i = 0; i < tab.length - 1; i++) {
for (int j = 0; j < tab.length-1-i; j++) {
if (tab[j] > tab[j+1]){
int temp = tab[j];
tab[j] = tab[j+1];
tab[j+1] = temp;
}
}
}
}
public static void afficherTableau(int[] tab){
for (int i = 0; i < tab.length; i++) {
System.out.print(tab[i] + " ");
}
System.out.println();
}
}
Triage par sélection
Principe : Diviser le tableau en zone non triée et zone triée. Initialement, la zone non triée est de 1 à n, la zone triée est vide. À chaque passe, trouver le plus petit élément de la zone non triée et l'échanger avec le premier élément de la zone non triée. Répéter jusqu'à ce que tout soit trié.
package com.jour4.triage;
public class ExempleTriageSelection {
public static void main(String[] args) {
int[] donnees = {86, 57, 68, 25, 34, 2};
System.out.println("Avant le tri :");
afficherTableau(donnees);
triSelection(donnees);
System.out.println("Après le tri :");
afficherTableau(donnees);
}
// Méthode de tri par sélection
public static void triSelection(int[] tab){
for (int i = 0; i < tab.length-1; i++) {
// Déclarer l'index du plus petit élément
int indexMin = i;
for (int j = i+1; j < tab.length; j++) {
// Si un élément suivant est plus petit, mettre à jour l'index du plus petit élément
if (tab[j] < tab[indexMin]){
indexMin = j;
}
}
// Après la boucle, échanger le premier élément avec le plus petit trouvé
if (i != indexMin){
int temp = tab[i];
tab[i] = tab[indexMin];
tab[indexMin] = temp;
}
}
}
public static void afficherTableau(int[] tab){
for (int i = 0; i < tab.length; i++) {
System.out.print(tab[i] + " ");
}
System.out.println();
}
}
Triage rapide
Une amélioration du tri à bulles. Principe : Spécifier une valeur pivot (généralement le premier élément). Diviser les données en deux parties : éléments plus petits que le pivot à gauche, éléments plus grands à droite. Répéter récursivement pour chaque partie.
package com.jour4.triage;
public class ExempleTriageRapide {
public static void main(String[] args) {
int[] donnees = {86, 57, 68, 25, 34, 2,12,4,2,56,3};
System.out.println("Avant le tri :");
afficherTableau(donnees);
triRapide(donnees,0,donnees.length-1);
System.out.println("Après le tri :");
afficherTableau(donnees);
}
// Méthode de tri rapide
public static void triRapide(int[] tab,int gauche,int droite){
// Déclarer les variables utilisées
int i,j,temp,t;
// Condition de sortie récursive
if (gauche > droite){
return;
}
// Logique du tri
i = gauche;
j = droite;
temp = tab[gauche]; // Pivot
while(i < j){
// Si l'élément à j est plus grand que le pivot, décrémenter j
while (temp <= tab[j] && i < j){
j--;
}
// Si l'élément à i est plus petit que le pivot, incrémenter i
while ((temp >= tab[i]) && i < j){
i++;
}
// Si i trouve un élément plus grand que le pivot et j trouve un élément plus petit, les échanger
if (i < j){
t = tab[j];
tab[j] = tab[i];
tab[i] = t;
}
}
// Échanger le pivot avec l'élément à la position où i et j se rencontrent
tab[gauche] = tab[i];
tab[i] = temp;
// Appels récursifs
triRapide(tab,gauche,i-1);
triRapide(tab,i+1,droite);
}
public static void afficherTableau(int[] tab){
for (int i = 0; i < tab.length; i++) {
System.out.print(tab[i] + " ");
}
System.out.println();
}
}
Triage par insertion
Principe : Diviser le tableau en zone non triée et zone triée. Par défaut, le premier élément est considéré comme trié. À partir du deuxième élément de la zone non triée, le comparer avec les éléments triés et l'insérer à la position appropriée.
package com.jour4.triage;
public class ExempleTriageInsertion {
public static void main(String[] args) {
// Déclarer un tableau
int[] donnees = {86, 57, 68, 25, 34, 2,12,4,2,56,3};
System.out.println("Avant le tri :");
afficherTableau(donnees);
triInsertion(donnees);
System.out.println("Après le tri :");
afficherTableau(donnees);
}
public static void triInsertion(int[] tab){
for (int i = 1; i < tab.length; i++) {
// Valeur à insérer
int valeurInseree = tab[i];
// Éléments déjà triés
int j = i - 1;
while (j >= 0 && tab[j] > valeurInseree){
// Déplacer les plus grandes valeurs d'une position vers la droite
tab[j+1] = tab[j];
j--;
}
// Insérer la valeur à la position correcte
tab[j+1] = valeurInseree;
}
}
public static void afficherTableau(int[] tab){
for (int i = 0; i < tab.length; i++) {
System.out.print(tab[i] + " ");
}
System.out.println();
}
}
Exercice
package com.jour4.triage;
public class ExerciceTriage02 {
public static void main(String[] args) {
// Trier une chaîne de caractères "gdeafcthmkl" et retourner le résultat trié
// chaire.toCharArray(); // Convertir une chaîne en tableau de caractères
// String.valueOf(); // Convertir un tableau de caractères en chaîne
// 1. Déclarer la chaîne
String texte = "gdeafcbthmkl";
// 2. Convertir la chaîne en tableau de caractères
char[] caracteres = texte.toCharArray();
// 3. Écrire une méthode de tri pour le tableau de caractères
triBulle(caracteres);
// 4. Convertir le tableau de caractères trié en chaîne
String texteTrie = String.valueOf(caracteres);
System.out.println(texteTrie);
}
public static void triBulle(char[] tab){
for (int i = 0; i < tab.length - 1; i++) {
for (int j = 0; j < tab.length-1-i; j++) {
if (tab[j] > tab[j+1]){
char temp = tab[j];
tab[j] = tab[j+1];
tab[j+1] = temp;
}
}
}
}
public static void afficherTableau(char[] tab){
for (int i = 0; i < tab.length; i++) {
System.out.print(tab[i] + " ");
}
System.out.println();
}
}
Efficacité des algorithmes de tri
package com.jour4.triage;
import java.util.Random;
public class TestEfficaciteTri {
public static void main(String[] args) {
// Comparer l'efficacité des algorithmes de tri
// 1. Stocker 100 000 données aléatoires dans un tableau
// Objet de nombres aléatoires
Random aleatoire = new Random();
// Appeler une méthode pour obtenir des valeurs aléatoires
int[] donnees = new int[100000];
// Boucle pour stocker les données
for (int j = 0; j < 100000; j++) {
donnees[j] = aleatoire.nextInt(100000000);
}
// Appeler les méthodes de tri et mesurer le temps
long debut = System.currentTimeMillis(); // Retourne la valeur actuelle en millisecondes
// ExempleTriageBulle.triBulle(donnees); // Tri à bulles
// ExempleTriageRapide.triRapide(donnees,0, donnees.length-1); // Tri rapide
// ExempleTriageSelection.triSelection(donnees); // Tri par sélection
ExempleTriageInsertion.triInsertion(donnees); // Tri par insertion
long fin = System.currentTimeMillis(); // Retourne la valeur en millisecondes à la fin
System.out.println("Temps d'exécution : " + (fin-debut) + " ms");
}
}
Recherche dans les tableaux
Recherche linéaire
Pour les tableaux non triés, parcourir tous les éléments pour trouver la valeur cible.
Recherche binaire
Pour les tableaux triés, comparer avec l'élément central et diviser l'espace de recherche par à chaque étape, améliorant ainsi l'efficacité.
package com.jour4.recherche;
public class ExempleRecherche {
public static void main(String[] args) {
/*
Recherche linéaire, trouver l'indice d'un élément spécifique dans un tableau
*/
int[] tableau = {86, 57, 68, 25, 34, 2,12,4,2,56,3};
// Trouver la position de 12
/* // Recherche linéaire
int indice = -1;
int cible = 12;
for (int i = 0; i < tableau.length; i++) {
if (tableau[i] == cible){
indice = i;
}
}
System.out.println(indice);
}
*/
int[] tableauTrie = {11,22,33,44,55,66,77,88,99};
int position = rechercherBinaire(tableauTrie, 77);
System.out.println(position);
}
// Méthode de recherche binaire
public static int rechercherBinaire(int[] tab, int valeur){
// Calculer l'indice central
int max = tab.length-1;
int min = 0;
int milieu = (max+min)/2;
// Comparer la valeur à l'indice central
while (tab[milieu] != valeur){
if (tab[milieu] > valeur){
max = milieu-1;
} else if (tab[milieu] < valeur){
min = milieu+1;
}
// Cas où la valeur n'est pas trouvée
if (min > max){
return -1;
}
milieu = (max+min)/2;
}
return milieu;
}
}
Classe utilitaire Array
La classe utilitaire Array de JDK fournit des méthodes pratiques pour manipuler les tableaux.
package com.jour4.triage;
import java.util.Arrays;
/*
Test de la classe utilitaire Array
*/
public class TestClasseArray {
public static void main(String[] args) {
int[] tab1 = {11,22,33,44,55,66,77,88,99};
int position = Arrays.binarySearch(tab1, 55);
System.out.println(position);
int[] tab2 = {10,20,30};
int[] tab3 = {10,20,30};
System.out.println(tab2 == tab3); // false
// Comparer si deux tableaux sont égaux
System.out.println(Arrays.equals(tab2,tab3)); // true
int[] tab4 = {111,22,323,344,255,166,577,188,99};
Arrays.sort(tab4); // Méthode de tri fournie
System.out.println(Arrays.toString(tab4)); // Méthode de conversion en chaîne de caractères
}
}