Cours d’informatique

Partie 4 : Structures de données. Définition, tableaux

multidimensionnels, parcours de tableaux.…
 Plan
1. Introduction : pourquoi des tableaux ?
2. Définition des tableaux
3. En pratique : utilisation des tableaux
4. Pour aller plus loin :
• Les tableaux dynamiques
• Les tableaux à deux dimensions
• Les tableaux associatifs
• Algorithmes avancés sur les tableaux
Introduction I
Introduction I
 Introduction I
Un «tableau», dans la vie, on parlera dans la suite
de tableau «abstrait», est un «outil» qui permet de
structurer des informations que l’on souhaite
garder en tête...

Il permet de travailler sur ces informations...

Ils sont tellement omniprésents qu’on a inventé

des outils pour les manipuler: les «tableurs»
 Introduction I
Un «tableau», dans la vie, on parlera dans la suite
de tableau «abstrait», est un «outil» qui permet de
structurer des informations que l’on souhaite
garder en tête...

Il permet de travailler sur ces informations...

Ils sont tellement omniprésents qu’on a inventé

des outils pour les manipuler: les «tableurs»
 Introduction II

• En informatique, un tableau est un outil permettant

de stocker une information complexe, qu’elle soit
structurée sous forme d’un tableau «abstrait» ou
non.

• Concrètement, un tableau en informatique consiste

en une réservation de plusieurs cases successives
en mémoire pour stocker de l’information.
 Illustration bis

Algorithme Premier tableau

Variables:
a, b : entiers
T : Tableau de 7 cases d’entiers
Début
a ← 5;
b ← 10;
Remplir les 3 premières cases de T avec les valeurs 12, 3 et 7
Fin
 a
b
T Illustration bis
10 5 12 3 7

Algorithme Premier tableau

Variables:
a, b : entiers
T : Tableau de 7 cases d’entiers
Début
a ← 5;
b ← 10;
Remplir les 3 premières cases de T avec les valeurs 12, 3 et 7
Fin
 Définition
• Un tableau, en informatique, est une structure de
donnée linéaire permettant de stocker un ensemble
d’éléments.

• Sa particularité est que ces éléments sont stockés

dans des cases contiguës en mémoire.

• On accède à un élément du tableau en donnant son

indice, un entier (rq: l’élément situé dans la première
case du tableau porte l’indice 0).
 Définition
• En langage algorithmique, ceci se traduit par un
nouveau type de données qui pourra être attribué à
une variable : le type «Tableau de...»

Algorithme Moyenne
Variables:
T : Tableau de 6 cases de réels
Début
.......
Fin
Lire ou modifier une case du
tableau
• Chaque case du tableau T correspond à une
variable individuelle dont le nom est T[indice].

• On peut lire ou modifier ces cases tout comme on

le fait pour une variable.
Algorithme Moyenne
Variables:
T : Tableau de 6 cases de réels
Début
T[0] ← 5;
T[1] ← 2;
Ecrire( (T[0]+ T[1])/2 );
Fin
Quelques fonctions utiles

• Combien de cases mémoires sont utilisées pour

stocker le tableau ?

• Taille : Tableau ⟶ Entier

• Ex : Taille(T)

• D’autres fonctions ?
Remplir un tableau
Algorithme Remplissage
Variables
Tab : Tableau de 10 cases
d’entiers;
i : entier;
Début
pour i allant de 0 à Taille(Tab)-1 faire
Tab[i] ← Saisie();
fin pour
Fin
 Traiter un tableau
Algorithme Case du maximum
Variables
Tab: Tableau de 10 cases d’entiers;
i, imax : entier;
Début
imax ← 0;
pour i allant de 0 à Taille(Tab)-1 faire
si (Tab[i]>Tab[imax])
alors imax ← i;
fin si
fin pour
Fin
 Traiter un tableau
accu ← 0;
pour i allant de 0 à 99 faire
accu ← accu +Tab[i] ;
fin pour
 Traiter un tableau
accu ← 0;
pour i allant de 0 à 99 faire
accu ← accu +Tab[i] ;
fin pour
pour i allant de 0 à 98 faire
Tab[i] ← Tab[i+1] ;
fin pour
 Traiter un tableau
accu ← 0;
pour i allant de 0 à 99 faire
pour i allant de 1 à 99 faire
accu ← accu +Tab[i] ;
Tab[i] ← Tab[i-1]
fin pour
fin pour
pour i allant de 0 à 98 faire
Tab[i] ← Tab[i+1] ;
fin pour
 Traiter un tableau
accu ← 0;
pour i allant de 0 à 99 faire
pour i allant de 1 à 99 faire
accu ← accu +Tab[i] ;
Tab[i] ← Tab[i-1]
fin pour
fin pour
pour i allant de 0 à 98 faire
Tab[i] ← Tab[i+1] ;
fin pour
pour i allant de 0 à 48 faire
aux ← Tab[i] ;
Tab[i] ← Tab[99-i] ;
Tab[99-i] ← aux ;
fin pour
et Python dans tout ça…
Dans les langages de programmation haut niveau,
comme Python, il existe différentes structures de
données permettant de stocker des informations :

- sous une forme linéaire comme les tableaux

([Link]), les listes (list), les n-uplets (tuples), les
ensembles (set)

- ou sous une forme plus structurée comme les

dictionnaires (dict)
 Les [Link]
C’est la structure de données la plus proche des
tableaux “algorithmiques”

taille fixée, type des cases fixé et même type pour

toutes les cases

Ces contraintes rendent cette structure très

compacte et très efficace.

Elle est privilégiée pour les traitements “intensifs”

 Les [Link]
import numpy
T=[Link]([4,3,2,1]) # Création du tableau
print(T[3]) affiche 1 # lecture d’une case du tableau
T[2]=5 # modification d’une
case du tableau
len(T) vaut 4 # longueur du tableau
T[1:3] # extraction d’un sous-
tableau

for i in range(len(T)):
….T[i]..... # accès en lecture/écriture
à T[i]

for v in T:
…. v …. # accès en lecture à T[i], via v
 Les listes
La structure la plus flexible, privilégiées dans de
nombreuses applications pour sa facilité d’utilisation.

Taille variable (on peut lui ajouter ou retirer des

éléments), type des cases non fixé, compréhension
de liste,....
 Les listes
L=[4,3,2,1] # Création de la liste
print(L[3]) affiche 1 # lecture d’une valeur dans la liste
L[2]=5 # modification
d’une case de la liste
len(L) vaut 4 # longueur de la liste
L[1:3] # extraction d’une sous-
liste

for i in range(len(L)):
….L[i]..... # accès en lecture/
écriture à L[i]

for v in L:
…. v …. # accès en lecture à L[i], via v
 Les listes, c’est aussi
L=[0]*5 # Création d’une
liste de 5 zéros
[1,2,3]+[2,3,4] # concaténation de listes
[Link](5) # ajout d’un élément
en bout de liste
[Link]() # retire le dernier
élément de la liste

[i**2 for i in range(5)] # compréhension de liste

[i for i in range(10) if i%3==0]

L=[1,"bonjour",3.5] # des types différents

 Les n-uplets
Le tuple implémente la notion de n-uplet en
mathématiques.

T=(3,2,1) # Création d’un tuple.

Structure très proche de la liste a ceci près que les

éléments du tuple ne sont pas modifiables.
Conséquence : un tuple ne se trie pas !
 Les ensembles
Le set implémente la notion de n-uplet en
mathématiques.

S={3,2,1} # Création de l’ensemble

{1,2,3}
{3,2,1} == {2,1,3} est vrai

Dispose d’opérations propres aux ensembles (union,

intersections,...)
{3,2,1}.union({2,3,4}) vaut {1,2,3,4}
 Les dictionnaires
Implémente les tables d’associations clé=>valeur, où
clé est une chaîne de caractères. le type de valeur peut
différer d’une clé à l’autre.

D=dict()
D[“nom”] = “Bourdon”
D[“prenom”] = “Jérémie”
D[“dpt”] = 44

ou encore
D={"nom":"Bourdon", "prenom":"Jérémie", "dpt":44}
 Les dictionnaires
si D={"nom":"Bourdon", "prenom":"Jérémie", "dpt":44}
len(D) vaut 3, le nombre de clés

for cle in D:
….cle…
….D[cle]....
 Et si on combinait…
Mis à part les [Link], les valeurs stockées dans
ces structures de données peuvent être de n’importe
quel type, y compris des types complexes.

On peut donc avoir des listes dans un dictionnaire,

des dictionnaires dans des listes,.... Tout est
imaginable.
 Et si on combinait…
On peut imaginer des listings d’enseignants avec
leurs spécialités.

D=[ {"nom":"Bourdon", "prenom":"Jérémie", "dpt":44,

“matieres”: [“Algo-Prog”,”Biologie des systèmes”]},
{"nom":"De la Higuera", "prenom":"Colin", "dpt":44,
“matieres”: [“Algo-Prog”,”Intelligence artificielle”]}]
 Pour aller plus loin
Les tableaux à deux dimensions

• Les tableaux à plusieurs dimensions ne sont que

des représentations «graphiques» de données.

• En informatique, ces données peuvent très bien être

stockées dans une mémoire «linéaire» (ex: les
images peuvent être stockées et heureusement
qu’elles peuvent l’être).
 Pour 1 D
aller plus loin
a u
l e
Les tableaux
Ta b à deux dimensions

• Les tableaux à plusieurs dimensions ne sont que

des représentations «graphiques» de données.

• En informatique, ces données peuvent très bien être

stockées dans une mémoire «linéaire» (ex: les
images peuvent être stockées et heureusement
qu’elles peuvent l’être).
 Pour 1 D
aller plus loin
a u
l e
Les tableaux
Ta b à deux dimensions

• Les tableaux à plusieurs dimensions ne sont que

des représentations «graphiques» de données.

• En informatique, ces données peuvent très bien être

stockées dans une mémoire «linéaire» 2 D (ex: les
images peuvent être stockées a
etuheureusement
l e
qu’elles peuvent l’être). Tab
Les tableaux à deux dimensions
Revoir la numérotation...
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8

1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8

2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8

3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8

4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8

5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

Les tableaux à deux dimensions
Revoir la numérotation...
0,0
0 0,1
1 0,2
2 0,3
3 0,4
4 0,5
5 0,6
6 0,7
7 0,8
8

1,0
9 1,1
10 1,2
11 1,3
12 1,4
13 1,5
14 1,6
15 1,7
16 1,8
17

2,0
18 2,1
19 2,2
20 2,3
21 2,4
22 2,5
23 2,6
24 2,7
25 2,8
26

3,0
27 3,1
28 3,2
29 3,3
30 3,4
31 3,5
32 3,6
33 3,7
34 3,8
35

4,0
36 4,1
37 4,2
38 4,3
39 4,4
40 4,5
41 4,6
42 4,7
43 4,8

5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

Les tableaux à deux dimensions
Revoir la numérotation...
0,0
0 0,1
1 0,2
2 0,3
3 0,4
4 0,5
5 0,6
6 0,7
7 0,8
8

1,0
9 1,1
10 1,2
11 1,3
12 1,4
13 1,5
14 1,6
15 1,7
16 1,8
17

2,0
18 2,1
19 2,2
20 2,3
21 2,4
22 2,5
23 4*9+8=44
2,6
24 2,7
25 2,8
26

3,0
27 3,1
28 3,2
29 3,3
30 3,4
31 3,5
32 3,6
33 3,7
34 3,8
35

4,0
36 4,1
37 4,2
38 4,3
39 4,4
40 4,5
41 4,6
42 4,7
43 4,8

5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

Les tableaux à deux dimensions
Revoir la numérotation...
0,0
0 0,1
1 0,2
2 0,3
3 0,4
4 0,5
5 0,6
6 0,7
7 0,8
8

1,0
9 1,1
10 1,2
11 1,3
12 1,4
13 1,5
14 1,6
15 1,7
16 1,8
17

2,0
18 2,1
19 2,2
20 2,3
21 2,4
22 2,5
23 4*9+8=44
2,6
24 2,7
25 2,8
26

3,0
27
Pour pouvoir renuméroter, il suffit
3,1
28 3,2
29 3,3
30 3,4
31 3,5
32 3,6
33 3,7
34 3,8
35

4,0
36
de fixer la largeur l du tableau. La
4,1
37 4,2
38 4,3
39 4,4
40 4,5
41 4,6
42 4,7
43 4,8

valeur de la case (x,y) est stockée

à l’indice x*l+y !!!
5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

Les tableaux à deux dimensions
Revoir la définition...
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8

1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8

2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8

3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8

4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8

5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

 Les tableaux à deux dimensions
0
Revoir la définition...
0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8

1
1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8

2
2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8

3 3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 3,8

4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8

4

5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

5

6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

6
7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

7
 Les tableaux à deux dimensions
0 0,0
Revoir la définition...
0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8

0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8

1 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8

1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8

2 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8

2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8

3 3,0
3,0
3,1
3,1
3,2
3,2
3,3
3,3
3,4
3,4
3,5
3,5
3,6
3,6
3,7
3,7
3,8
3,8

4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8

4 4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8

5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

5 5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

6 6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

7 7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

 Les tableaux à deux dimensions
0 0,0
0
Revoir la définition...
0,1
1 0,2
2 0,3
3 0,4
4 0,5
5 0,6
6 0,7
7 0,8
8

0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8

1 1,0
0 1,1
1 1,2
2 1,3
3 1,4
4 1,5
5 1,6
6 1,7
7 1,8
8

1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8

2 2,0
0 2,1
1 2,2
2 2,3
3 2,4
4 2,5
5 2,6
6 2,7
7 2,8
8
2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8

3 3,0
0
3,0
3,1
1
3,1
3,2
2
3,2
3,3
3
3,3
3,4
4
3,4
3,5
5
3,5
3,6
6
3,6
3,7
7
3,7
3,8
8
3,8

4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8

4 4,0
0 4,1
1 4,2
2 4,3
3 4,4
4 4,5
5 4,6
6 4,7
7 4,8
8

5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

5 5,0
0 5,1
1 5,2
2 5,3
3 5,4
4 5,5
5 5,6
6 5,7
7 5,8
8

6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 6,8

6 6,0
0 6,1
1 6,2
2 6,3
3 6,4
4 6,5
5 6,6
6 6,7
7 6,8
8

7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

7 7,0
0 7,1
1 7,2
2 7,3
3 7,4
4 7,5
5 7,6
6 7,7
7 7,8
8
 Les tableaux à deux dimensions
0 0,0
0
Revoir
0,1
1
la
0,2
2
définition...
Un tableau à deux dimensions peut être défini
0,3
3 0,4
4 0,5
5 0,6
6 0,7
7 0,8
8

comme un tableau de lignes, chaque ligne étant un

0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8

1 1,0
0

1,0
1,1
1

1,1
tableau.
1,2
2

1,2
1,3
3

1,3
1,4
4

1,4
1,5
5

1,5
1,6
6

1,6
1,7
7

1,7
1,8
8

1,8
La2 valeur stockée en position (x,y) correspond donc à
2,0
0 2,1
1 2,2
2 2,3
3 2,4
4 2,5
5 2,6
6 2,7
7 2,8
8

la valeur d’indice y dans le tableau T[x], ce qui s’écrit

2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8

3 3,0
0
3,0
3,1
1
3,1
2T[x][y] !!!
3,2
3,2
3,3
3
3,3
3,4
4
3,4
3,5
5
3,5
3,6
6
3,6
3,7
7
3,7
3,8
8
3,8

Un exemple de tableau à deux dimensions:

4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 4,8
4 4,0
0 4,1
1 4,2
2 4,3
3 4,4
4 4,5
5 4,6
6 4,7
7 4,8
8

5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 5,8

5 5,0
0 5,1
1 5,2
2 5,3
3 5,4
4 5,5
5 5,6
6 5,7
7 1 5
5,8
8

6,0 6,1
T=[ [1,5], [7,9], [3,4] ];
6,2 6,3 6,4 6,5 6,6 6,7 6,8

6 6,0
0 6,1
1 6,2
2 6,3
3 6,4
4 6,5
5 6,6
6 6,7
7 7 9
6,8
8

7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8

3 4
7 7,0
0 7,1
1 7,2
2 7,3
3 7,4
4 7,5
5 7,6
6 7,7
7 7,8
8
 Pour aller plus loin
Les tableaux à deux dimensions
• Définition en algorithmique
• Variable T: Tableau de mxn cases d’entiers
• T[i,j] ← 8;

• En Python
• T = [[1,2],[3,4],[5,6]]
• T[2][1] = 8
• print(T[1][0]) # Affiche 3

• ou en utilisant un [Link]
• T =[Link](shape=(nb_l,nb_c))
 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

7 3 5 15 11 14 6 12 19 1 9 10

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

12 cases lues, 13 n’est pas dans le tableau!!!

7 3 5 15 11 14 6 12 19 1 9 10

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

10 cases lues, 13 n’est pas dans le tableau !!!

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Aller plus loin
Quelques exemples de plus
Recherche d’un élément dans un tableau

Recherche d’un élément dans un tableau trié

On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

4 cases lues, 13 n’est pas dans le tableau !!!

1 3 5 6 7 9 10 11 12 14 15 19

Je recherche le nombre 13....

 Recherche d’un élément
v1.0
Algorithme Recherche_1
Variables:
x,i :entier;
montab : Tableau;
trouvé :booléen;
Début
// montab est supposé rempli
x ← Saisie();
trouvé ← faux;
i ←0;
tant que (non trouvé et i < Taille(montab)) faire
si (montab[i]=x)
alors trouvé ←vrai;
fin si ;
i ←i+1;
fin tant que
Ecrire(trouvé);
Fin
 Recherche d’un élément # Algorithme Recherche_1
montab=[5, 11, 9, 10, 8, 13] # par exemple

v1.0
x = int(input("Valeur recherchée : "))
trouve = False
i=0
Algorithme Recherche_1 while (not trouve and i<len(montab)) :
Variables: if (montab[i] == x):
x,i :entier; trouve = True
montab : Tableau; i = i+1
trouvé :booléen;
Début
print(trouve)
// montab est supposé rempli
x ← Saisie();
trouvé ← faux;
i ←0;
tant que (non trouvé et i < Taille(montab)) faire
si (montab[i]=x)
alors trouvé ←vrai;
fin si ;
i ←i+1;
fin tant que
Ecrire(trouvé);
Fin
 Recherche d’un élément
dans un tableau trié
Algorithme Recherche_2
Variables:
x,i :entier;
montab : Tableau;
Début
// montab est supposé rempli
x ← Saisie();
i ←0;
tant que (montab[i] ≤ x et i < Taille(montab)) faire
i ←i+1;
fin tant que
Ecrire (montab[i]=x);
Fin
 Recherche d’un élément
dans un tableau trié # Algorithme Recherche_2
montab=[5, 8, 9, 10, 11, 13] # par exemple
Algorithme Recherche_2 x = int(input("Valeur recherchée : "))
Variables: i=0
x,i :entier; while (i<len(montab) and montab[i] < x) :
i=i+1
montab : Tableau;
Début if i<len(montab):
// montab est supposé rempli print(montab[i] == x)
x ← Saisie(); else:
print(False)
i ←0;
tant que (montab[i] ≤ x et i < Taille(montab)) faire
i ←i+1;
fin tant que
Ecrire (montab[i]=x);
Fin
 Recherche d’un élément
dans un tableau trié (rapide)
Algorithme Recherche_3
Variables:
x :entier;
début, fin, milieu:entier;
montab : Tableau;
Début
// montab est supposé rempli
x ← Saisie();
début ←0;
fin ← Taille(montab)-1;
Tant que ((fin - début) > 0) faire
milieu ← (début+fin) div 2;
si (montab[milieu]<x)
alors fin ← milieu;
sinon début ← milieu;
fin si
fin tant que
Ecrire (montab[début]=x);
Fin
 Recherche d’un élément
dans un tableau trié (rapide) # Algorithme Recherche_3
montab=[5, 8, 9, 10, 11, 13] # par exemple
Algorithme Recherche_3 x = int(input("Valeur recherchée : "))
Variables: debut=0
x :entier; fin=len(montab)
début, fin, milieu:entier; while (fin-debut>1) :
montab : Tableau; milieu = (debut+fin)//2
Début
print(debut,milieu,fin)
// montab est supposé rempli
if x<montab[milieu]:
x ← Saisie();
début ←0;
fin = milieu
fin ← Taille(montab)-1; else:
Tant que ((fin - début) > 0) faire debut = milieu
milieu ← (début+fin) div 2;
si (montab[milieu]<x) print(debut,fin)
alors fin ← milieu; if (montab[debut] == x or montab[fin] == x):
sinon début ← milieu; print("trouvé")
fin si else:
fin tant que print("non trouvé")
Ecrire (montab[début]=x);
Fin
 Trions un peu…

• On suppose que les données sont dans un tableau

montab de n cases et que l’on cherche un élément x

• Supposons que n=1000000

 Comment faire ?
Supposons que j’ai une solution pour trouver le
maximum et le déplacer à la fin du tableau…
Avant
7 3 5 15 11 14 6 12 19 1 9 10

Après
7 3 5 15 11 14 6 12 10 1 9 19
 On pourrait itérer

• La première fois : traiter le tableau entre 0 et 10

• La deuxième fois : traiter le tableau entre 0 et 9

• La troisième fois : traiter le tableau entre 0 et 8

• La ième fois : traiter le tableau entre 0 et 11-i

• Génial ! On sait donc résoudre le problème.

• Sauf qu’il faut être capable de le faire une fois

Recherche d’un maximum dans
un tableau

// Dans quelle case se trouve le maximum ?

imax ← 0;
pour i allant de 0 à Taille(Tab)-1 faire
si (Tab[i]>Tab[imax])
alors imax ← i;
fin si
fin pour
 Recherche d’un maximum dans
un tableau
pour j allant de 1 à Taille(Tab) faire
// Dans quelle case se trouve le maximum ?
imax ← 0;
pour i allant de 0 à Taille(Tab)-1 faire
si (Tab[i]>Tab[imax])
alors imax ← i;
fin si
fin pour
Placer le max à la fin ?????
fin pour
 Recherche d’un maximum dans
un tableau
pour j allant de 1 à Taille(Tab) faire
// Dans quelle case se trouve le maximum ?
imax ← 0;
pour i allant de 0 à Taille(Tab)-1j faire
si (Tab[i]>Tab[imax])
alors imax ← i;
fin si
fin pour
Placer le max à la fin ?????
fin pour
 Placer le maximum à la fin ?

b)-j
Ta
le(
ax

il
Avant

im

Ta
7 3 5 15 11 14 6 12 19 1 9 10

Après Échange !

7 3 5 15 11 14 6 12 10 1 9 19
 Tri maximum
Algorithme Tri maximum
Variables
Tab : Tableau d’entiers;
i,j,tmp : entiers;
Début
// On suppose que Tab est déjà rempli
pour j allant de 1 à Taille(Tab) faire
imax ← 0;
pour i allant de 0 à Taille(Tab)-j faire
si (Tab[i] >Tab[imax])
alors imax ← i;
fin si
fin pour
tmp ← Tab[i];
Tab[i] ← Tab[imax];
Tab[imax] ← tmp;
fin pour
// Le tableau Tab est trié
Fin
 Caractéristiques des
tableaux
❑ Structure de données statique

❑ On doit connaître la taille à la déclaration

❑ Mais il en existe des versions dynamiques

❑ Accès direct à chaque cellule !!!

❑ Aussi facile et rapide d’atteindre montab[5477]

que montab[1]