Algorithmique et structure des
données
Elaboré par Mme Elkamel Hager
[Link]@[Link]
FSM de Monastir 2020-2021
1ière année Licence en Sciences d’Informatique
Semestre 1
H. Jamoussi Elkamel , FSM 1
ASD1 – 2020 – S1
Plan du cours
• Chapitre 1 : Introduction à l’algorithmique
• Chapitre 2 : Types de données, constantes, Variables
• Chapitre 3 : Structures conditionnelles
• Chapitre 4 : Structures itératives
• Chapitre 5 : Procédures et fonctions
• Chapitre 6 : Les tableaux
• Chapitre 7 : La Récursivité
• Chapitre 8 : Les algorithmes de recherche
• Chapitre 9 : Les algorithmes de Tri
• Chapitre 10 : Les enregistrements
• Chapitre 11 : Les pointeurs
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 2
1
Chapitre 6 : Les tableaux
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM
sommaire
1. Structure des données
2. Définition algorithmique d’un tableau
3. Tableau à une dimension
3.1 Déclaration d’un tableau
3.2 Le type tableau
3.3 Désignation d’un élément du tableau
3.4 opérations globales sur les tableaux
a. affectation
b. comparaison
3.5 opérations sur les éléments d’un tableau
3.6 les principaux traitements sur les tableaux
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 4
2
Structure des données
• Jusqu’ici, nous avons eu affaire à des données élémentaires comme
les nombres ou les caractères.
• Pour leur rangement en mémoire, nous avons utilisé des cases
mémoires.
• Pour ranger des données plus complexes comme par exemple un
relevé de températures journalières au mois du janvier 2021 à
Monastir.
• Si on modélise ce relevé de températures par une suite de 31 réels
indicée de 1 à 31.
• Pour les ranger en mémoire, nous allons utiliser non plus une seule
case, mais plusieurs cases et reliées d’une certaine façon.
H. Jamoussi Elkamel , FSM 5
ASD1 – 2020 – S1
Structure des données
• Une structure des données est un ensemble des cellules de
mémoire qui sont reliées d’une certaine façon et qui
peuvent contenir chacune une valeur. Toutes ces valeurs
étant de même type.
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 6
3
Définition algorithmique d’un tableau
• Un tableau est une structure de données de cellules contigües et
d’accès direct regroupant un ensemble d’éléments de même type.
– C’est une collection ordonnée de variables de même type.
– C’est un ensemble d’éléments en nombre fixé, mémorisés dans
une zone contiguë et accessibles par un, ou plusieurs, indices.
• Lorsque l’indice est unique, le tableau est dit à une dimension.
• Lorsque N indices sont nécessaires pour repérer une valeur, le tableau
est dit à N dimensions.
• Cet indice permet d’accéder directement à chacun des éléments du
tableau.
• L’accès direct signifie que l’on peut obtenir le contenu d’une cellule
sans qu’il soit nécessaire de connaitre le contenu des cellules
précédentes du tableau.
H. Jamoussi Elkamel , FSM 7
ASD1 – 2020 – S1
Tableau à une dimension
• Un tableau à une dimension est appelé aussi vecteur.
• Déclaration d’un tableau
Var
nomT : tableau[borne_inf .. borne_s] de type_éléments
Exemples
constante Nmax = 20
var t : tableau[1..100] d’entiers
temp :tableau[1.. 31] de réel
note :tableau[1.. Nmax] de réel
Remarque : Le nombre d’éléments du tableau doit être connue à
l’avance.
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 8
4
Tableau à une dimension
D’une façon générale
• Nmax est l’identificateur d’une constante qui désigne le nombre de
cellules du tableau, qu’on appelle longueur ou taille du tableau
• Et n et le nombre d’éléments de la suite à implanter dans le tableau
1 ≤ n ≤ Nmax
• Le numéro d’une cellule sera appelé position dans le tableau
Exemple :
Constante Nmax = 7
Var T : tableau[1.. Nmax] d’entiers
n : entier
T 18 19 14 15 17 ? ? n= 5
1 2 3 4 5 6 7
H. Jamoussi Elkamel , FSM 9
ASD1 – 2020 – S1
Tableau à une dimension
• Type tableau
Type
TypeTab = tableau[borne_inf .. borne_sup] de type_éléments
Var
T_tab : TypeTab
Exemples
constante Nmax = 100
type eleves = tableau[1..Nmax ] de chaines
notes = tableau[1.. Nmax] de réel
Tab = tableau[1.. Nmax] de réel
Var T_eleves : eleves
T_notes: notes
T: Tab 10
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM
5
Désignation d’un élément du tableau
• Pour désigner l’élément d’indice i d’un tableau, on utilise le nom du
tableau suivi de l’indice de l’élément entre crochets :
nomT[i]
• Le contenu a un sens si 1 ≤ i ≤ n ≤ Nmax
• Pour désigner un élément du tableau on peut utiliser une expression
arithmétique (dont la valeur est comprise dans l’intervalle de définition
du tableau)
nomT[k*2+1]
H. Jamoussi Elkamel , FSM 11
ASD1 – 2020 – S1
Opérations globales sur les tableaux
• Affectation
Lorsque deux tableaux T1 et T2 de même type, on peut effectuer une
affectation globale entre T1 et T2
T1 T2
• Comparaison (égalité, inégalité)
Lorsque T1 et T2 sont de même type on peut comparer T1 et T2
• T1 = T2 : vrai si et seulement si pour tout i, 1 ≤ i ≤ n ≤ Nmax,
T1[i]= T2[i] et faux sinon
• T1T2 : vrai si et seulement si il existe i tel que T1[i] T2[i]
et faux sinon
Remarque : T1< T2 n’a pas de sens
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 12
6
Opérations sur les éléments
D’une façon générale on peut effectuer, sur les éléments d’un tableau,
toutes les opérations définies sur le type des éléments, comme l’addition,
multiplication, ect ..
Exemples
Type
tab= tableau[1..31] de réel
Var T1, T2 : Tab
…
T1[i] 18
T2[i] 25
T1[i] ( T1[i]+ T2[i] ) /2
H. Jamoussi Elkamel , FSM 13
ASD1 – 2020 – S1
Les principaux traitements sur les tableaux
• chargement ou initialisation
• L’écriture
• recherche : Minimum, Maximum, Un élément
• Tris : Tri sélection, tri à bulles , tri insertion
• Fusion
• Le décalage à droite ou à gauche des éléments
ASD1 – 2020 – S1 H. Jamoussi Elkamel , FSM 14
