Les tableaux :
Lorsqu'on regroupe des objets, il est fréquemment utile de pouvoir faire un accès direct à un objet particulier du groupe, sans avoir à considérer séquentiellement tous ceux qui le précédent dans le groupe.
La notion de table et ses réalisations sous forme de tableau et de fichier à accès direct répondent à ces besoins.
Un tableau est une collection finie et ordonnée d'éléments de même nature, accessibles directement, en utilisant un ou plusieurs indices.
Un tableau est un ensemble d'informations, tel qu'à chaque information soit associé un nom et un seul (clé ou indicatif).
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
8 |
13 |
6 |
14 |
29 |
17 |
3 |
9 |
Exemples de matrices à deux dimensions particulières:
Matrice carrée
Matrice dont le nombre de lignes est égal au nombre de colonnes.
Matrice diagonale
Les éléments de la matrice se trouvent sur la diagonale seulement.
|
1 |
2 |
3 |
4 |
|
|
1 |
X |
|||
|
2 |
X |
|||
|
3 |
X |
|||
|
4 |
X |
Matrice triangulaire
Les éléments de cette matrice sont placés de façon triangulaire.
|
1 |
2 |
3 |
4 |
|
|
1 |
A |
|||
|
2 |
B |
C |
||
|
3 |
D |
E |
F |
|
|
4 |
G |
H |
I |
J |
Matrice partiellement remplie ou éparse
Matrice qui contient plusieurs éléments nuls répartis un peu partout dans la matrice.
Il n'existe pas de définition précise pour identifier une matrice éparse, nous le reconnaissons de façon intuitive.
Les matrices à plus de deux dimensions sont généralement regroupées sous le terme de matrices multidimensionnelles.
Les tableaux sont des structures à accès direct, c'est-à-dire que nous pouvons accéder directement à l'information en utilisant des indices.
|
Les données individuelles sont donc repérées par un sélecteur que l'on nomme indice du tableau |
|
Le rang d’un tableau est le nombre de dimensions de ce tableau |
|
La dimension d'un tableau est donnée par la (ou les) valeur(s) maximales des indices. |
Exemple:
Un vecteur de dimension (5) est un tableau à 1 ligne et 5 colonnes
Une matrice de dimension(3,5) est un tableau ayant 3 lignes et 5 colonnes...
Notation:
Tab [ 3 , 5 ] Û tableau ayant 3 lignes et 5 colonnes.
Exemple:
Tableau = ( 1.2 4.3 3.1 )
( 2.1 2.0 -5.7 )
Nom d'élément Place information
(1,1) P1 1.2
(2.1) P2 2.1
(1,2) P3 4.3
(2,2) P4 2.0
(1,3) P5 3.1
(2,3) P6 -5.7
Contrairement aux fichiers séquentiels, il n'existe qu'une primitive d'accès aux éléments d'un vecteur: l'opération d'indiçage.
Soit T un vecteur, et [1, N] l'intervalle d'entiers repérant les éléments du vecteur.
On accède au Ième élément de T par l'opération d'indiçage que l'on note T[I].
Si I n'appartient pas à [1, N], le résultat est indéterminé
.Dans le cadre des matrices à deux dimensions, on accède à un élément par l'opération d'indiçage que l'on note T[L,C], ou L représente le numéro de ligne et C celui de colonne.
ATTENTION LE FAIT QUE LES INDICES SOIENT ENTRE CROCHETS NE VEUT ABSOLUMENT PAS DIRE QU'ILS SONT FACULTATIFS.
A un indice du vecteur correspond une valeur bien précise, alors le contenu nous donne l’indice.
exemple :
Clairmois
A un indice du vecteur correspond une valeur quelconque, alors à l’indice1 correspond la 1ère valeur.
Il existe plusieurs méthodes de recherche. Pour déterminer la meilleure méthode, il faut considérer la taille du vecteur, son utilisation et son contenu.
Recherche séquentielle
Les éléments sont dans un vecteur et l'ordre n'a pas d'importance. Lors de la recherche, on compare l'élément recherché avec tous ceux du vecteur en commençant par l'indice 1.
Exemple :
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||||||||||
|
8 |
13 |
6 |
14 |
29 |
17 |
3 |
9 |
Si on cherche 14 - on le compare avec V(1) ® 8
avec V(2) ® 13
avec V(3) ® 6
avec V(4) ® 14 trouvé
Si des éléments sont recherchés plus souvent, il est bon de les placer en tête du vecteur et d'avoir un vecteur ordonné selon la fréquence d'utilisation décroissante ; ceci réduit le temps de recherche.
Si le vecteur est trié de façon ascendante, on arrête la recherche dès que l'on trouve une valeur supérieure à celle recherchée (et bien sûr inférieure si le tri est descendant).
Recherche binaire
Les éléments du vecteur doivent être classés par ordre croissant ou décroissant.
Le principe consiste à diviser en deux l'étendue de la recherche et de comparer l'élément recherché avec l'élément milieu. Si ce dernier est plus grand que l'élément recherché, nous continuons la recherche dans la moitié inférieure du vecteur. Par contre, s'il est plus petit, nous travaillerons avec la moitié supérieure.
Exemple :
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||||||||||
|
8 |
12 |
19 |
24 |
29 |
33 |
38 |
42 |
Comparaison entre la recherche séquentielle et la recherche binaire
En principe, la recherche dichotomique est plus efficace que la recherche séquentielle mais il est important de noter que :
Si aucune position n'est libre dans le vecteur alors l'insertion est impossible.
Insérer à la fin du vecteur
Nous gardons en mémoire l'indice du dernier élément et nous ajoutons après le dernier élément.
Insérer à l'intérieur du vecteur
Si la position est libre, ajouter à cette position.
Si la position n’est pas libre :
- Insérer après le Ke élément si N position occupée (vecteur trié ou non)
- Trouver le Ke élément
Faire de la place c'est à dire transférer N dans N+1, N-1 dans N, N-2 dans N1, etc
- Insérer l'élément à K+1 ;
Si peu importe les zones inoccupées, nous remplaçons l'élément à supprimer par un élément nul.
Si toutes les positions doivent être non nulles, nous transférons les positions. Si on enlève le Ke élément. (vecteur ‘’TASSE’’)
transfert K+1 dans K, K+2 dans K+1, etc.
Soit le vecteur suivant :
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||||||||||
|
A |
B |
C |
D |
E |
F |
Si on enlève le 4e élément soit D, on doit transférer le 5e élément dans le 4e et le 6e dans le 5e.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
||||||||||
|
A |
B |
C |
E |
F |
Le vecteur résultant contiendra 5 éléments.
La copie d'un vecteur sur un autre ne présente aucune difficulté dès lors que les dimensions sont compatibles.
Plusieurs méthodes de tri sont envisageables, nous verrons en particulier celle du tri à bulle.
la matrice d'ordre deux
Afin de nous exercer au maniement des tableaux à plusieurs indices, nous allons voir le chargement d'un vecteur dans une matrice d'ordre deux.
Nous avons vu que les différents types d'objets peuvent être associés en les regroupant au sein d'un type particulier le type structure.
Les objets composés de ce type sont généralement appelés structure ou enregistrement.
Ce type étant modulable à volonté il faut le définir avec précision chaque fois que l'on veut l'employer.
Déclaration des types structure.
|
NOM TYPE STRUCTURE |
||
|
Pers |
||
|
NOM CHAMP |
TYPE |
SIGNIFICATION |
|
Insee Nom Prenom Adresse |
Entier Chaîne Chaîne Chaîne |
Numéro d'immatriculation de la personne Nom de la personne Prénom de la personne Adresse de la personne |
Dans le module de déclaration les types structure sont déclarés avant les variables puisque celles-ci peuvent avoir pour type une structure.
Lorsque l'on veut faire un traitement sur un champ précis de la structure on nommera ce champ de la manière suivante : Nom de la structure suivi d'un point et du nom du champ concerné.
NOM_STRUC.NOM_CHAMP
Déclaration des variables
|
VARIABLE |
TYPE |
SIGNIFICATION |
|
VECTEUR
Indiv |
Tab[IMAX](Pers)
Pers |
Vecteur contenant les renseignements généraux des stagiaires Renseignements concernant un individu précis |