Cours programmation tableaux monodimensionnels et dichotomiq
Télécharger PDFIntroduction aux Tableaux en Algorithmique et en Langage C
Ce guide explore les concepts fondamentaux des tableaux, qu'ils soient monodimensionnels ou bidimensionnels, en mettant l'accent sur leur implémentation en algorithmique et en langage C. Nous aborderons leur déclaration, les opérations de lecture et d'affichage, la recherche d'éléments, l'insertion, et enfin l'allocation dynamique.
Partie 1 : Introduction aux Tableaux
Les tableaux sont des structures de données essentielles en programmation, permettant de stocker une collection d'éléments du même type sous un nom unique. Chaque élément est accessible via un indice ou une combinaison d'indices.
Partie 2 : Les Tableaux Monodimensionnels
Déclaration d'un tableau monodimensionnel
En algorithmique, la déclaration d'un tableau monodimensionnel suit une syntaxe spécifique :
Nom_Tableau : tableau [1..N] de Type
Où Type est le type des éléments du tableau (par exemple, entier, réel, caractère), et N représente la taille maximale du tableau.
Exemples :
Tab : Tableau [1..100] de réel(un tableau de 100 nombres réels)Tab : tableau [1..10] d'entiers(un tableau de 10 entiers)
Dans de nombreux langages de programmation comme le C, l'indexation des tableaux commence à 0. Un tableau de taille N aura des indices allant de 0 à N-1.
Exemple d'accès : Tab[0]
Lecture et affichage d'un tableau monodimensionnel
Pour interagir avec un tableau, des procédures de lecture et d'affichage sont nécessaires. Voici un exemple en pseudo-code :
Procédure de Lecture
Procédure Lecture(Tab: tableau [1..N] d'Entiers)
Var
i : Entier
Début
Pour i de 1 à N faire
Écrire("Entrez la valeur ", i, " du tableau : ")
Lire(Tab[i])
FinPour
FinProcédureProcédure d'Affichage
Procédure Affichage(Tab: tableau [1..N] d'Entiers)
Var
i : Entier
Début
Pour i de 1 à N faire
Écrire("Tab[", i , "] = ", Tab[i])
FinPour
FinProcédureRecherche d'un élément dans un tableau monodimensionnel
La recherche permet de vérifier la présence d'une valeur spécifique dans un tableau et, si elle existe, de trouver sa position.
Recherche séquentielle (Tableau non ordonné)
On souhaite déterminer s'il existe un indice i allant de 1 à N tel que T[i] = val.
Algorithme Recherche_Sequentielle
Var
T : tableau [1..N] d'Entiers
val : Entier // La valeur à rechercher
i : Entier
Trouve : Booléen
Début
Trouve ← Faux
Pour i de 1 à N faire
Si T[i] = val Alors
Trouve ← Vrai
// On peut ajouter une instruction pour sortir de la boucle ici si on ne cherche que la première occurrence
FinSi
FinPour
// Le résultat (Trouve) indique si l'élément a été trouvé ou non.
FinAlgorithmeRecherche dichotomique (Tableau ordonné)
Cette méthode est beaucoup plus efficace pour les tableaux triés. Elle consiste à diviser le tableau en deux à chaque étape de la recherche.
Algorithme Recherche_Dichotomique
Var
T : tableau [1..N] d'Entiers // Le tableau doit être trié
elem : Entier // L'élément à rechercher
binf : Entier // Borne inférieure
bsup : Entier // Borne supérieure
mil : Entier // Milieu
Trouve : Booléen
Début
binf ← 1
bsup ← N
Trouve ← Faux
Répéter
mil ← (binf + bsup) div 2
Si elem = T[mil] Alors
Trouve ← Vrai
Sinon Si elem < T[mil] Alors
bsup ← mil - 1
Sinon // elem > T[mil]
binf ← mil + 1
FinSi
Jusqu'à ((Trouve = Vrai) Ou (binf > bsup))
// Le résultat (Trouve) indique si l'élément a été trouvé ou non.
FinAlgorithmeInsertion d'un élément dans un tableau monodimensionnel
Insérer une valeur dans un tableau, surtout s'il est trié, demande de décaler des éléments.
Voici les étapes générales pour insérer une valeur (VAL) dans un tableau trié :
- Lire les éléments du tableau dans un ordre croissant.
- Lire la valeur à insérer (
VAL). - Déplacer les éléments du tableau qui sont plus grands que
VALd'une position vers la droite pour faire de la place. - Copier
VALà la position libérée. - Afficher le nouveau tableau.
Algorithme d'Insertion
Algorithme Insertion
Var
T : tableau [1..N+1] d'Entiers // Le tableau avec une taille augmentée pour l'insertion
val : Entier // La valeur à insérer
i : Entier
Début
// Lecture des N premiers éléments du tableau
Pour i de 1 à N faire
Écrire("Entrez la valeur ", i, " du tableau : ")
Lire(T[i])
FinPour
Écrire("Entrez la valeur à insérer : ")
Lire(val)
// Trouver la position d'insertion et décaler les éléments
i ← N
Tantque (i > 0 ET T[i] > val) faire
T[i+1] ← T[i]
i ← i - 1
FinTantQue
// Insérer la valeur
T[i+1] ← val
// Le tableau T contient maintenant N+1 éléments, triés.
FinAlgorithmePartie 3 : Les Tableaux à Deux Dimensions (Matrices)
Les tableaux à deux dimensions, souvent appelés matrices, sont utilisés pour stocker des données structurées en lignes et en colonnes. Ils sont idéaux pour représenter des grilles, des tables ou des données nécessitant deux indices.
Problème : Comment sauvegarder et manipuler les notes de classe dans 6 matières ?
Un tableau à deux dimensions est la solution idéale, avec par exemple une dimension pour les élèves (lignes) et une autre pour les matières (colonnes).
Déclaration d'un tableau à deux dimensions
La syntaxe algorithmique pour la déclaration est :
Nom_Tableau : tableau [1..N, 1..M] de Type
Où N est le nombre de lignes et M est le nombre de colonnes.
Accès aux éléments
Pour accéder à un élément spécifique, on utilise deux indices : un pour la ligne et un pour la colonne.
Appel : Tab[ligne, colonne]
Exemple : X ← Tab[2,3] permet d'accéder à l'élément de la matrice qui se trouve à la ligne 2 et de la colonne 3.
Exemples d'algorithmes pour les tableaux à deux dimensions
Voici des exemples d'algorithmes pour l'initialisation et l'affichage d'un tableau à deux dimensions.
Algorithme InitTableau
Algorithme InitTableau
Var
i, j : Entier
Tab : tableau [1..100, 1..50] d'Entiers
Début
Pour i de 1 à 100 faire
Pour j de 1 à 50 faire
Tab[i,j] ← 0 // Initialise chaque élément à 0
FinPour
FinPour
FinAlgorithmeAlgorithme AfficheTableau
Algorithme AfficheTableau
Var
i, j : Entier
Tab : tableau [1..100, 1..50] d'Entiers
Début
Pour i de 1 à 100 faire
Pour j de 1 à 50 faire
Écrire(Tab[i,j]) // Affiche chaque élément
FinPour
FinPour
FinAlgorithmePartie 4 : De l’Algorithmique au Langage C
Cette section détaille comment les concepts de tableaux sont implémentés en langage C, avec des exemples concrets pour les tableaux monodimensionnels et bidimensionnels.
Les tableaux monodimensionnels en C
En C, un tableau est un ensemble fini d’éléments de même type, stockés en mémoire à des adresses contiguës. L'indice du premier élément est toujours 0.
Déclaration
La déclaration d'un tableau en C se fait comme suit :
type nom_tableau[nombre_elements];
nombre_elements est une constante entière qui détermine la taille du tableau. L'indice du dernier élément est alors nombre_elements - 1.
Exemple : float Moy[20]; (un tableau de 20 flottants, indexés de 0 à 19).
Accès aux éléments
Pour accéder à un élément, on utilise la syntaxe : nom_tableau[indice].
Exemples :
Moy[1] = 17.0;// Affecter la moyenne 17 au 2ème élément (indice 1)scanf("%f", &Moy[4]);// Saisie de la moyenne du 5ème élément (indice 4)printf("%f", Moy[4]);// Affichage de la moyenne du 5ème élément (indice 4)
Particularités des tableaux en C
- Le nom du tableau (sans indice) est une adresse mémoire, plus précisément l'adresse du premier élément. Ainsi,
Tab == &Tab[0]est vrai. - Un tableau ne peut pas figurer directement à gauche de l'opérateur d'affectation pour copier tout son contenu (par exemple,
Tab1 = Tab2;est invalide). Pour copier un tableau dans un autre, il faut parcourir les éléments un par un.
Exemple de copie de tableau :
#include <stdio.h>
void main() {
const int N = 10;
int tab1[N], tab2[N];
int i;
// Supposons que tab2 est déjà rempli avec des valeurs
// for (i = 0; i < N; i++) { tab2[i] = i + 1; }
for (i = 0; i < N; i++) {
tab1[i] = tab2[i]; // Copie élément par élément
}
// ...
}Initialisation d'un tableau en C
On peut initialiser un tableau lors de sa déclaration avec une liste de constantes :
type nom_tableau[N] = {constante_1, constante_2, ..., constante_N};
Exemple :
#include <stdio.h>
void main() {
const int N = 4;
int tab[N] = {1, 2, 3, 4}; // tab aura les valeurs 1, 2, 3, 4
// ...
}Exercice : Manipulation d'un tableau en C
Écrire un programme C qui permet de :
- Lire et d'afficher un tableau
Tde 10 entiers. - Calculer la somme des éléments de
T. - Chercher le maximum et le minimum de
T.
#include <stdio.h>
void main() {
int T[10];
int i, Som, Max, Min;
// Saisie de T
for (i = 0; i < 10; i++) {
printf("Donner l'élément d'indice %d : ", i);
scanf("%d", &T[i]);
}
// Affichage de T
printf("\nAffichage du tableau T :\n");
for (i = 0; i < 10; i++) {
printf("T[%d]=%d\n", i, T[i]);
}
// Somme de T
Som = 0;
for (i = 0; i < 10; i++) {
Som = Som + T[i];
}
printf("\nLa somme de T = %d\n", Som);
// Max et Min de T
Max = T[0];
Min = T[0];
for (i = 1; i < 10; i++) {
if (T[i] > Max) {
Max = T[i];
} else if (T[i] < Min) {
Min = T[i];
}
}
printf("Le max de T = %d et le min de T = %d\n", Max, Min);
}Les tableaux à deux dimensions en C
En C, les tableaux à deux dimensions sont des "tableaux de tableaux".
Déclaration
La syntaxe de déclaration est :
Type Nom[Dim1][Dim2];
Avec :
Type: Type des éléments du tableau.Nom: Nom du tableau.Dim1: Nombre de lignes.Dim2: Nombre de colonnes.
Exemple : float M[3][4]; (une matrice de 3 lignes et 4 colonnes de flottants).
Accès aux éléments
Pour accéder à un élément, on utilise la syntaxe : Nom[Ind_Ligne][Ind_Colonne].
Exemples :
M[1][2] = 22.0;// Affecter 22 à l'élément de la 2ème ligne (indice 1) et de la 3ème colonne (indice 2)scanf("%f", &M[2][0]);// Saisie de l'élément de la 3ème ligne (indice 2) et de la 1ère colonne (indice 0)printf("%f", M[2][0]);// Affichage de l'élément de la 3ème ligne (indice 2) et de la 1ère colonne (indice 0)
Exercice : Manipulation d'une matrice en C
Écrire un programme C qui permet de :
- Lire et d'afficher une matrice
Mde 7 lignes et 5 colonnes. - Calculer la somme des éléments de
M. - Chercher le maximum et le minimum de
M.
#include <stdio.h>
void main() {
int M[7][5];
int i, j, Som, Max, Min;
// Saisie de M
for (i = 0; i < 7; i++) {
for (j = 0; j < 5; j++) {
printf("Donner un élément pour M[%d][%d] : ", i, j);
scanf("%d", &M[i][j]);
}
}
// Affichage de M
printf("\nAffichage de la matrice M :\n");
for (i = 0; i < 7; i++) {
for (j = 0; j < 5; j++) {
printf("%d\t", M[i][j]); // Utilisation de tabulation pour un meilleur formatage
}
printf("\n"); // Nouvelle ligne après chaque ligne de la matrice
}
// Somme de M
Som = 0;
for (i = 0; i < 7; i++) {
for (j = 0; j < 5; j++) {
Som = Som + M[i][j];
}
}
printf("\nLa somme de M = %d\n", Som);
// Max et Min de M
Max = M[0][0];
Min = M[0][0];
for (i = 0; i < 7; i++) {
for (j = 0; j < 5; j++) {
if (M[i][j] > Max) {
Max = M[i][j];
} else if (M[i][j] < Min) {
Min = M[i][j];
}
}
}
printf("Le max de M = %d et le min de M = %d\n", Max, Min);
}Allocation dynamique de tableaux en C
L'allocation dynamique permet de créer des tableaux dont la taille n'est pas connue à la compilation, mais déterminée à l'exécution.
Allocation dynamique d'un tableau monodimensionnel
Pour allouer dynamiquement un tableau monodimensionnel, on utilise la fonction malloc. La syntaxe de malloc est la suivante :
(type *) malloc (taille_en_octets)
Nous voulons allouer un tableau d'entiers de 10 éléments :
#include <stdlib.h> // Pour malloc et free
// ...
int* t = (int*) malloc (10 * sizeof(int));
// Vérifier si l'allocation a réussi : if (t == NULL) { /* gérer l'erreur */ }
// N'oubliez pas de libérer la mémoire : free(t);
// ...Allocation dynamique d'un tableau à deux dimensions
Un tableau à deux dimensions alloué dynamiquement est conceptuellement un "tableau de pointeurs vers des tableaux". Chaque case du premier tableau contient un pointeur sur un tableau (une ligne).
Voici comment allouer, remplir et afficher un tableau n x m dynamiquement :
#include <stdlib.h> // Pour malloc, free, exit
#include <stdio.h> // Pour printf, scanf, perror
// Fonction pour remplir un tableau monodimensionnel
void remplirTab(int* t, int n) {
int i;
for (i = 0; i < n; i++) {
printf("Donner l'élément %d : ", i + 1);
scanf("%d", t + i); // t + i est équivalent à &t[i]
}
}
// Fonction pour afficher un tableau monodimensionnel
void showTab(int* t, int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d ", t[i]);
}
printf("\n");
}
// Fonction pour remplir un tableau bidimensionnel (matrice)
int** remplirTab2D(int n_lignes, int m_colonnes) {
int i;
int** t_2D;
// Allocation du tableau de pointeurs (pour les lignes)
t_2D = (int**) malloc(n_lignes * sizeof(int*));
if (t_2D == NULL) {
perror("Échec de l'allocation des lignes");
exit(EXIT_FAILURE);
}
// Allocation de chaque ligne (chaque tableau monodimensionnel)
for (i = 0; i < n_lignes; i++) {
t_2D[i] = (int*) malloc(m_colonnes * sizeof(int));
if (t_2D[i] == NULL) {
perror("Échec de l'allocation d'une ligne");
// Libérer la mémoire déjà allouée pour les lignes précédentes
for (int k = 0; k < i; k++) {
free(t_2D[k]);
}
free(t_2D);
exit(EXIT_FAILURE);
}
printf("Donner la ligne %d :\n", i + 1);
remplirTab(t_2D[i], m_colonnes); // Utilise la fonction de remplissage 1D
}
return t_2D;
}
// Fonction pour afficher un tableau bidimensionnel (matrice)
void showTab2D(int** t_2D, int n_lignes, int m_colonnes) {
int i, j;
for (i = 0; i < n_lignes; i++) {
for (j = 0; j < m_colonnes; j++) {
printf("%d\t", t_2D[i][j]);
}
printf("\n");
}
}
int main() {
int n_lignes, m_colonnes;
int** t_matrice;
printf("Donner le nombre de lignes : ");
scanf("%d", &n_lignes);
printf("Donner le nombre de colonnes : ");
scanf("%d", &m_colonnes);
t_matrice = remplirTab2D(n_lignes, m_colonnes);
printf("\nAffichage du tableau 2D dynamique :\n");
showTab2D(t_matrice, n_lignes, m_colonnes);
// N'oubliez pas de libérer la mémoire allouée !
for (int i = 0; i < n_lignes; i++) {
free(t_matrice[i]);
}
free(t_matrice);
return 0;
}Foire Aux Questions (FAQ)
Qu'est-ce qu'un tableau en programmation ?
Un tableau est une structure de données qui permet de stocker une collection d'éléments de même type dans une séquence contiguë en mémoire. Chaque élément est identifié par un indice ou une combinaison d'indices.
Quelle est la différence entre un tableau monodimensionnel et bidimensionnel ?
Un tableau monodimensionnel (ou vecteur) est une séquence linéaire d'éléments, accessible avec un seul indice (par exemple, T[i]). Un tableau bidimensionnel (ou matrice) est une grille d'éléments organisée en lignes et en colonnes, accessible avec deux indices (par exemple, M[ligne][colonne]).
Quand utiliser l'allocation dynamique pour les tableaux ?
L'allocation dynamique est utilisée lorsque la taille d'un tableau n'est pas connue au moment de la compilation du programme, mais doit être déterminée pendant l'exécution. Cela permet une gestion plus flexible de la mémoire et d'éviter les gaspillages ou les débordements de mémoire.