06/11/2021
LE TYPE TABLEAU
Université de Sousse
Institut Supérieur des Sciences Appliquées et de Technologie de Sousse
• Plan du chapitre :
I. Définition
Algorithmique et structures II. Les tableaux à une dimension (Vecteur)
III. Techniques utilisées avec les tableaux
de données IV. Les tableaux a deux dimensions (Matrice)
V. Méthodes de tri
CHAPITRE 5 : LE TYPE TABLEAU
Année universitaire 2020 – 2021
I. Introduction : I. Introduction :
• Un tableau est une structure de données qui permet de regrouper un nombre fini Remarques :
d’éléments de même type.
• Un tableau est caractérisé par :
• Il y a deux types de tableaux :
son nom.
• Les tableaux à une dimension appelés également Vecteurs.
sa taille (borne inférieure et borne supérieure connues à l’avance).
ses éléments : chaque élément est défini par son type et son contenu.
• Les tableaux à deux dimensions appelés également Matrices.
• Un tableau est formé par un nombre fini de cases contigües (situé en mémoire
centrale).
• L’accès à un élément du tableau se fait à l’aide d’un indice.
1
06/11/2021
II. Les tableaux à une dimension : II. Les tableaux à une dimension :
1. Définition : 2. Représentation algorithmique :
• Un tableau unidimensionnel (ou vecteur) permet de ranger des éléments ou des Type:
Nomtableau = Tableau [borne_inf .. borne_sup] de type_élément
valeurs de même type. Var:
Nomvar : Nomtableau
• Il regroupe ces éléments dans une structure fixe et permet d’accéder à chaque Indice : entier
élément par l’intermédiaire de son rang ou indice. Exemple :
• On veut déclarer un tableau T de moyennes
Tableau A : 1 30 80 41 91 27 43 19 Type:
Tab_Moy = Tableau [1..20] de réel
Var:
T : Tab_Moy
i : entier (* indice du tableau T *)
II. Les tableaux à une dimension : II. Les tableaux à une dimension :
• En mémoire, on va avoir une variable T comportant 10 cases. Remarques :
• Dans chaque case on place une valeur de type réel (la moyenne). • L’indice du tableau est de type entier.
01 02 03 04 05 06 07 08 09 10 • Il est préférable que cet indice soit initialisé à la valeur 1.
T 11.5 09.2 09.7 11.0 10.5 18.6
• La taille du tableau doit être connu à l’avance.
• Le premier élément de T contient la valeur 11.5 ; on note T[1] ←11.5 • Un tableau, s’il est rempli, ne doit pas faire l’objet d’une lecture supplémentaire sauf s’il
s’agit d’une opération de mise à jour où on doit modifier le contenu des éléments du
• Le deuxième élément de T contient la valeur 09.2 ; on note T[2] ← 09.2
tableau.
• D’une manière générale, le iè élément de T est noté T[i] et contient une valeur de type réel.
• T[i] désigne également le contenu de la iè case du tableau T.
2
06/11/2021
II. Les tableaux à une dimension : II. Les tableaux à une dimension :
b. Remplir un Tableau :
3 Opérations de base sur un tableau :
• Afin de représenter les différentes opérations sur le tableau, on prend l’exemple d’un tableau
d’entiers. Algorithme Remplir_Tableau
Const:
a. Initialisation d’un Tableau : N=30
Type:
Algorithme Initialisation_Tableau TableauEtudiant = Tableau [1..N] de entier
Const: Var:
N=30 Tetud : TableauEtudiant
Type: i: entier
TableauEtudiant = Tableau [1..N] de entier Début
Var: Pour i de 1 à N faire
Tetud : TableauEtudiant Lire (T[i])
i: entier Finpour
Début Fin
Pour i de 1 à N faire
T[i] ← 0
Finpour Attention:
Fin Lire(T[i]) consiste à entrer une valeur à partir du clavier et la mémoriser dans la ième case du tableau.
II. Les tableaux à une dimension : II. Les tableaux à une dimension :
c. Affichage des éléments d’un tableau : d. Addition des éléments de deux tableaux :
• Pour afficher les éléments d’un tableau, on utilise l’algorithme suivant: • Etant donnée de deux tableaux Tab1 et Tab2 et on veut calculer la somme élément par élément.
• Ça consiste à additionner les éléments de même indice et les mémoriser dans un tableau Tab3.
Algorithme Affichage_Tableau
• Condition nécessaire : Tab1 et Tab2 de même taille.
Const:
N=30
Type: Algorithme Addition_Tableaux
TableauEtudiant = Tableau [1..N] de entier Const:
Var: N=60
Tetud : TableauEtudiant Type:
i: entier TableauEnt = Tableau [1..N] de entier
Début Var:
Pour i de 1 à N faire Tab1, Tab2, Tab3 : TableauEnt
Écrire (T[i]) i: entier
Finpour Début
Fin Pour i de 1 à N faire
Tab3[i] ← Tab1[i]+Tab2[i]
Finpour
Fin
3
06/11/2021
II. Les tableaux à une dimension : III. Techniques utilisées avec les tableaux :
e. Multiplication des éléments de deux tableaux : 1. Recherche dans un tableau :
a. Introduction :
Algorithme Multiplication_Tableaux • Pour rechercher un élément dans un tableau, on présente deux différentes méthodes:
Const:
N=60
La recherche séquentielle.
Type:
TableauEnt = Tableau [1..N] de entier
La recherche dichotomique : C’est une recherche plus optimisée que la recherche
Var:
Tab1, Tab2, Tab3 : TableauEnt séquentielle mais il y a des précautions et des actions préalables à faire.
i: entier
Début
Pour i de 1 à N faire
Tab3[i] ← Tab1[i]*Tab2[i]
Finpour
Fin
III. Techniques utilisées avec les tableaux : III. Techniques utilisées avec les tableaux :
Algorithme Recherche_Séquentielle
1. Recherche dans un tableau : Const: 1. Recherche dans un tableau :
N=40
b. Recherche Séquentielle : Type: c. Recherche Dichotomique :
TableauEnt = Tableau [1..N] de entier
Var: Pour appliquer la recherche dichotomique, il faut que :
Tab : TableauEnt
i, X: entier le tableau T soit Rempli
B : Booléen
Début le tableau T soit Trié.
Lire (X)
i←1 Cette recherche réduit le temps de recherche d’un élément dans un tableau trié.
B ← Faux
Tant que (i<= N) et (B = Faux) faire On commence par comparer l’élément X à chercher avec le contenu de l’élément du milieu :
Si (T([i] <> X) alors
i←i+1 si X est inférieur à cette valeur alors on doit continuer la recherche dans la partie gauche du
Sinon
B ← vrai
tableau avec la modification du borne supérieure,
Finsi
Fin tant que
sinon on continue la recherche dans la partie droite du tableau avec modification de la valeur de
Si (B = vrai) alors la borne inférieure.
Écrire (X, "appartient à T")
Sinon On s’arrête lorsque X est égale à la valeur du milieu ou quand on dépasse les bornes du tableau.
Ecrire (X, "ne se trouve pas dans T")
Finsi
Fin
4
06/11/2021
III. Techniques utilisées avec les tableaux : III. Techniques utilisées avec les tableaux :
1. Recherche dans un tableau : 2. Comparaison de deux Tableaux :
c. Recherche Dichotomique : • On doit s’assurer que les deux tableaux ont le même type et de même taille.
Algorithme Comparaison
Algorithme Recherche_Dichotomique • La comparaison se fait élément par élément. Const:
Const:
N=10
N=40 Type:
Type: TableauEnt = Tableau [1..N] de entier
TableauEnt = Tableau [1..N] de entier
Var:
Var: Tab1, Tab2 : TableauEnt
Tab : TableauEnt
i : entier
i,inf, sup, milieu, X: entier B: Booléen
Début Début
Lire (X) i←1
inf ← 1 B ← vrai
sup ← N Tant que ( i <= N ) et ( B = vrai ) faire
Répéter Si (Tab1[i] <> Tab2(i)) alors
mil ← (inf + sup) div 2 B ← faux
Si (X < T(mil) alors Sinon
sup ← mil - 1 i←i+1
Sinon Finsi
inf ← mil + 1 Fin Tant que
Finsi Si (B= vrai) alors
Jusqu’à (X = T[mil] ou (inf > sup) Ecrire ("Tab1 et tab2 sont similaires")
Fin Finsi
Fin
IV. Les Tableaux à deux dimensions : Les Matrices IV. Les Tableaux à deux dimensions : Les Matrices
1. Définition:
• Le tableau à deux dimensions ou matrice est une structure de données permettant d’organiser Remarques :
des informations ayant le même type en lignes et en colonnes.
• Le Type_Elément de la matrice peut être simple ou structuré.
• Cette structure est caractérisé par son nombre de lignes et son nombre de colonnes.
2. Représentation Algorithmique : • L’accès à un élément de la matrice se fait avec deux indices.
Const: • Un élément est identifié par son numéro de ligne et son numéro de colonne.
Nbre_ligne = 30
Nbre_colonne=20 • Si Mat est la matrice, Mat[i,j] désigne l’élément de Mat situé à la iè Ligne et à la jè Colonne.
Type:
Matrice = Tableau [1..Nbre_ligne, 1..Nbre_colonne] de type_élément
Var:
Mat: Matrice
i,j:entier
5
06/11/2021
IV. Les Tableaux à deux dimensions : Les Matrices IV. Les Tableaux à deux dimensions : Les Matrices
3. Opérations de base sur une Matrice : c. Parcourir une matrice :
• Afficher tous les éléments de la matrice Mat:
• On suppose que le Type_Elément de la matrice est Entier.
a. Initialiser une matrice : Pour i de 1 à nbre_ligne faire
Pour i de 1 à nbre_ligne faire Pour j de 1 à nbre_colonne faire
Pour j de 1 à nbre_colonne faire Ecrire (Mat[i,j])
Mat[i,j] ← 0 Finpour
Finpour Finpour
Finpour
d. Additionner deux matrices :
b. Remplir une matrice : Condition nécessaire: les deux matrices Mat1 et Mat2 doivent avoir le même type et la même
Pour i de 1 à nbre_ligne faire taille.
Pour j de 1 à nbre_colonne faire Pour i de 1 à nbre_ligne faire
Lire (Mat[i,j]) Pour j de 1 à nbre_colonne faire
Finpour Mat3[i,j] ← Mat1[i,j]+Mat2[i,j]
Finpour Finpour
Finpour
