Cours Algo Tableaux

Institut National des sciences Appliques et des Technologies

Algorithmique et Structure de Donnes 1Niveau MPI

Les TableauxLes Tableaux

F. Chaieb [email protected]

IntroductionIntroduction

Problme

Ecrire un algorithme qui permet de lire les notes de 100 tudiantset dafficher les notes des 10 premiers dentre eux.

2

IntroductionALGORITHME tudiant

Introduction

Dbut

Var n1, n2, .., n100 : rel;

Lire (n1);Lire (n2) ; Lire (n100);

Ecrire (Voici les notes des dix premiers tudiants) ;

Ecrire (n1);Ecrire (n2);

.. Ecrire (n10);

Fi t di t

3

Fin tudiant

Introduction

Ncessit dutiliser 100 variables de mme type pour saisir les notes

Introduction

Ncessit d utiliser 100 variables de mme type pour saisir les notesde tous les tudiants,

ce qui augmente la taille de lalgorithmeq g g

Une nouvelle structure permettant de ranger les notes d ddes tudiants.

4

Tableau mono dimensionnel ou vecteurTableau mono-dimensionnel ou vecteur

Lorsque les donnes sont nombreuses et de mme type, afind'viter de multiplier le nombre des variables, on les regroupe dansun tableau

Dfi i i

un tableau

Un tableau mono-dimensionnel ou vecteur est une manire ded l d l d l

Dfinition

ranger des lments ou des valeurs de mme type, il regroupe ceslments dans une structure fixe et permet daccder chaquelment par lintermdiaire de son rang ou indice.lment par l intermdiaire de son rang ou indice.

5

Tableau mono dimensionnel ou vecteurLe type d'un tableau prcise le type (commun) de tous les lments

Tableau mono-dimensionnel ou vecteur

12 10 15 7.5 20 3.5 17 8 4 6

lments.

0 1 2 3 4 5 6 7 8 9

N bl T blI di blNom tableau

Ex. Notes

Type tableau

Ex. rel

Indice tableau

Ex. 0..9

Syntaxe :

tableau [borne_inf .. borne_sup] de type_des_lments

Syntaxe :

6

Tableau mono-dimensionnel ou vecteur` Exemple :


` Chacun des dix nombres du tableau est repr par son rang, 45 54 1 -56 22 134 49 12 90 -26

p p g,appel indice

` Dclaration : Tab : tableau [0..9] de entier ` Dclaration : Tab : tableau [0..9] de entier ` Pour accder un lment du tableau, il suffit de prciser entre

crochets l'indice de la case contenant cet lment.

` Exemple : Pour accder au 5me lment (22), on crit : Tab[4]( ), [4]

7


z Les instructions de lecture, criture et affectation s'appliquent aux


, pp qtableaux comme aux variables.

x Tab[0][ ]

L bl d l l d l d bl ' d La variable x prend la valeur du premier lment du tableau, c'est dire : 45

Tab[6] 43

Cette instruction a modifie le contenu du tableau

8

Alg rithm tr it nt un T bl u m n dim n i nn l

Problme de parcours dun tableau mono-dimensionnel

Algorithmes traitant un Tableau mono-dimensionnel

T un tableau n lments.

Algorithme Parcours Algorithme ParcoursAlgorithme ParcoursVari : entier,T bl [0 1] d l

Algorithme ParcoursVari : entier,T bl [0 1] d l T : tableau [0..n-1] de type_lment,

Dbut i 0;

T : tableau [0..n-1] de type_lment,

Dbut tantque i

Alg rithm tr it nt un T bl u m n dim n i nn lAlgorithmes traitant un Tableau mono-dimensionnel

Dans l'exemple suivant, le programme initialise un un tous les lments d'un tableau de n lments :

Algorithme InitTableau

VVari : entier,tab : tableau [0..n-1] dentier

Dbutpour i 0 n-1 faire

tab[i] 0finpour

Fin

10

Alg rithm tr it nt un T bl u m n dim n i nn lAlgorithmes traitant un Tableau mono-dimensionnel

Algorithmes daccs un lment dun tableau

Soit un tableau T[0..n-1], laccs T est dfini par T[i].[ ], p [ ]Soit val une variable contenant une valeur de mme type que cellescontenues dans T,

on veut dterminer un indice i [0..n-1] sil existe T[i] = val.

CasT non ordonn

CasT ordonn

11




Algorithmes d accs un lment d un tableau

Recherche squentielle dans un Tableau non ordonn

l (i 1) i l d bl T i l les (i 1) premiers lments du tableau T traits et val T[0..i-1]

i






ALGORITHME RechercheSeq Var T : tableau [0..n-1] dentiers val, i : entiers Trouve : boolen Dbut

i 0 ; f trouve faux ;

tantque (i






ALGORITHME RechercheSeqVar T : tableau [0..n-1] dentiers

Cas dun tableau non vide

T : tableau [0..n 1] d entiers elem, i: entier Trouve: boolen Dbut

i 0;tantque (T[i] elem) ET (i < n-1) faireOn peut prvoir la fin du

tableau grce la variable ii i + 1 ;

fintantqueTrouv (T[i] = elem) ;

14

Fin

Alg rithm tr it nt un T bl u m n dim n i nn lAlgorithmes daccs un lment dun tableauRecherche squentielle dans un Tableau ordonn


les (i 1) premiers lments du tableau T traits et

Recherche squentielle dans un Tableau ordonn

T[0..i-1] < elem

i = elem, T[i] < elem, T[0..i] < elem

t li di i t l lalgorithme est termin

et T[0..n-1] < elem, elem T.

on a trouv lindice i tel que T[0..i-1] < elem




ALGORITHME RechercheSeqTrie

Algorithmes d accs un lment d un tableauRecherche squentielle dans un Tableau ordonn

Var T : tableau [0..n-1] de entier i, elem : entiers T b l Trouve : boolen Dbut

si elem > T[n-1] alorsT f Trouve faux

sinoni 0 tantque T[i] < elem fairetantque T[i] < elem faire

i i + 1 fintantqueTrouv (T[i] = elem)

16

Trouv (T[i] elem)finsi

Fin


Insrer une valeur dans un tableau tri



Un tableau T de dimension N+1 contient N valeurs entires tries Un tableau T de dimension N+1 contient N valeurs entires tries par ordre croissant; La (N+1)ime valeur est indfinie.

I l VAL d l i d l bl T d i Insrer une valeur VAL donne au clavier dans le tableau T de manire obtenir un tableau de N+1 valeurs tries.

17





1. Lecture des lments du tableau dans un ordre croissant

2. Lecture de la valeur rechercher (VAL)

3 Dplacer les lments plus grands que VAL d'une position vers l'arrire 3. Dplacer les lments plus grands que VAL d une position vers l arrire.

4. VAL est copi la position du dernier lment dplac

5. Afficher le nouveau tableau

18

T bl u d u dim n i n m triTableau deux dimensions : matrice

Nbre de lignes

Nbre de colonnes

Var

T b bl [0 NMAX 0 MMAX] d d l

Dclaration dun tableau deux dimensions

19

Tab : tableau [0 .. NMAX, 0 .. MMAX] de type_des_lments

Rcapitulons .

V

Dclaration dun tableau mono-dimensionnel

Var

Tab : tableau [0 .. NMAX] de type_des_lments OU

Type

Tab : tableau [0 .. NMAX] de type_des_lmentsVar

T : Tab

Var

Dclaration dun tableau deux dimensions

Tab : tableau [0 .. NMAX, 0 .. MMAX] de type_des_lments

20

Rcapitulons .

Remarques

1. Allocation statique de la mmoire : espace mmoire rserve au dbut du prog une fois pour toute

2 Taille fixe du tableau NMAX 1 limiter le nombre dlments que 2. Taille fixe du tableau : NMAX-1 : limiter le nombre d lments que le prog peut traiter

Les tableaux sont souvent surdimensionns par rapport leur usage courant

3. Il faut valuer la taille du tableau pour viter un pbm de saturation de la machine de la machine

Exemple

un tableau de dimensions 1000x 500 dentiers possde une taille da peu prs : 2Mo (1000x500x4 octets),

La dclaration de cette variable rserve 2Mo dans la mmoire centrale .

21

centrale .

Rcapitulons .

Initialisation dun tableau

Gestion dun tableau

Initialisation d un tableau

Algorithme InitTableauConst

Algorithme InitTableauConst Const

(N 100): entierVar

i : entier

Const (N ,M 100): entierVar

i j : entieri : entier,Tab : tableau [0..N-1] dentier

DbutPour i 0 N-1 faire

i,j : entier,Tab : tableau [0..N-1, 0..M-1] dentier

DbutPour i 0 N-1 fairePour i 0 N 1 faire

Tab[i] 0FinPour

Fin

Pour i 0 N 1 fairePour j 0 M-1 faire

Tab[i,j] 0FinPour

FinPourFin

22

Rcapitulons .Gestion dun tableau

Saisie des lments dun tableau : Nombre de donnes (nb) est connu lavance : boucle Pour

Gestion d un tableau

Nombre de donnes (nb) est connu l avance : boucle Pour Nombre de donnes (nb) inconnu : Tant que

VarVari ,nb : entier,Tab : tableau [0..N-1] dentier

DbutExemple : charger les notes des Dbutnb 0i 0 Ecrire("Entrer la liste des notes (-1 pour terminer ) : ")

Exemple : charger les notes des tudiants, user saisit une srie de notes termine par -1 (quil ne faut pas ranger)

TantQue (nb -1) FaireLire(nb)Si nb -1 alors

Tab[i] nb

pas ranger)

Tab[i] nbFin Si

FinTantQuenbnotes i

23

Fin

Rcapitulons .Gestion dun tableau

Exemple (suite) :

- Le surdimensionnement du tableau : une seule partie contiendra des donnes

Gestion d un tableau

Le surdimensionnement du tableau : une seule partie contiendra des donnes

- Contenu des autres cases doit tre ignor

- Solution : utiliser une variable qui indique le nombre dlments contenus dans le tableau

Varnbnotes ,nb : entier,Tab : tableau [0..N-1] dentier

On peut retirer le test :

- on range la valeur -1 - on diminue le nombre

Dbutnb 0nbnotes 0 E i ("E t l li t d t ( 1 t i ) ")

- on diminue le nombre de donnes de 1

Ecrire("Entrer la liste des notes (-1 pour terminer ) : ")TantQue (nb -1) Faire

Lire(nb)Si nb -1 alors

TantQue (nb -1) et nbnotes < N Faire

Tab[nbnotes ] nbnbnotes nbnotes +1

Fin SiFi T tQ

Eviter dpassement de la taille

24

FinTantQueFin

Rcapitulons .

Affichage des lments dun tableau :

Gestion dun tableau

Affichage des lments d un tableau :

Algorithme AfficheTableauConst

Algorithme AfficheTableauConst Const

(N 100): entierVar

i nb : entier

Const (N ,M 100): entierVar

i j nbc nbl : entieri,nb : entier,Tab : tableau [0..N-1] dentier

DbutPour i 0 nb faire

i,j, nbc, nbl : entier,Tab : tableau [0..N-1, 0..M-1] dentier

DbutPour i 0 nbc fairePour i 0 nb faire

Ecrire(Tab[i]) FinPourFin

Pour i 0 nbc fairePour j 0 nbl faire

Ecrire(Tab[i,j])FinPour

FinPourFin

25

Rcapitulons .Recherche dune valeur dans un tableau


ALGORITHME RechercheSeqVar T t bl u [0 N 1] d ti T : tableau [0..N-1] d entiers elem, i,nb: entier Trouve: boolen Dbut Dbut

i 0;tantque (T[i] elem) ET (i < nb-1) faire

i i + 1 ;fintantqueTrouv (T[i] = elem) ;( [ ] ) ;

Fin

26


Recherche squentielle dans un Tableau Tri

ALGORITHME RechercheSeqTrie Var T : tableau [0..N-1] de entier i, nb, elem : entier Trouve : boolen Db Dbut

si elem > T[nb-1] alorsTrouve faux

in nsinoni 0 Tantque T[i] < elem faire

i i + 1 i i + 1 FinTantque Trouv (T[i] = elem)

FinSi

27

FinSiFin


Recherche dichotomique dans un Tableau TriALGORITHME RechercheDichoALGORITHME RechercheDichoVar T : tableau [0..N-1] de entier elem ,Binf, bsup : entierelem ,Binf, bsup : entierTrouve : boolen Dbut

binf0; bsup nb-1; Trouve faux; p ;Rpeter

mil(binf+bsup) div 2si elem=T[mil] alors

trouvevraisinon Si elembsup)Fin

Rcapitulons .Insertion dun nouvel lment

Cas Tableau non tri Cas Tableau non tri

1. Ajout la fin du tableau

2. Dduire le Num de la case de rangement partir du nombre dlments de T

Cas Tableau Tri

g p

1. Lecture des lments du tableau dans un ordre croissant

2. Lecture de la valeur rechercher (val)

3. Dplacer les lments plus grands que VAL d'une position vers l'arrire.

4. VAL est copi la position du dernier lment dplac

5. Afficher le nouveau tableau

29

Documents

Cours Algo Tableaux