Tableaux à une dimension

Parent Category: Informatique et réseaux Category: Algorithme

Généralités

Les objets manipulés jusqu'ici sont de types simples, c'est-à-dire qu'ils ne peuvent contenir qu'une valeur à la fois. Cependant il peut arriver qu'on ait envie d'utiliser plusieurs valeurs à la fois et de pouvoir les récupérer dans la suite du traitement. Dans ce cas, il est conseillé d'utiliser les objets de type composé comme:

  • Les vecteurs
  • Les fichiers
  • Les enregistrements
  • Les listes chaînées
  • Les piles
  • Les files
  • Les arbres
  • Les graphes

Un tableau à une dimension encore appelé vecteur est une suite de données contiguëes logées en mémoire centrale et référencé par un indexe (suite contiguë; c'est lorsque ses éléments se suivent).


Caractéristiques et déclaration d'un vecteur

Un vecteur est caractérisé par:

  • Le nom
  • Le type de ses éléments
  • la borne inférieure et la borne supérieure
  • la taille (taille d'un vecteur: c'est le nombre d'élément que contient un vecteur). taille=Sup-inf+1

Déclaration d'un vecteur

Premier cas:

type vecteur=tableau[inf..sup] de type d'élément
var v : vecteur

Deuxième cas:

var v: tableau[inf..sup] de type d'élément

Exemple 1:

const max = 100
type vecteur = tableau[1..max] d'entier
var v: vecteur

Exemple 2:

var v : tableau[1..100] d'entier

 

Référence d'un élément de vecteur

Chaque élément du vecteur est repéré par son rang dans ce vecteur. Si "inf" est le rang du premier élément du vecteur alors le rang du ‘’ième’’ élément est donné par la formule inf+(i-1)
Soit un vecteur

 

-5

2

1

10

0


V[1]=-5
V[2]=2
V[3]=1
V[4]=10
V[5]=0
V[i] = ieme élément du vecteur V


Opération sur les vecteurs: Opération de base

 

La lecture

 

pour i=1 à n faire
lire(V[i])
fin pour

 

Ecriture

 

pour i=1 à n faire
écrire(V[i])
fin pour

 

Exemple 1

 

Ecrivons une procédure qui permet de lire un vecteur de 10 entiers et qui ensuite met tous les éléments de ce vecteur à zéro.

Correction:

type vecteur = tableau[1..10] d'entier
procédure lecture_zero(T: vecteur)
var i: entier
debut
pour i=1 à 10 faire
lire(T[i])
fin pour
pour i =1 à 10 faire
T[i] ←0
fin pour
fin

 

Exemple 2

 

Ecrire une fonction qui prend en paramètre un vecteur d'entier et qui renvoie la somme des éléments de ce vecteurs.

Correction

fonction somme(V: vecteur) entier
var S, i: entier
debut
S←0
pour i=1 à 10 faire
S←V[i]+S
fin pour
somme←S
fin

Exercice 1:

Ecrire une procédure qui prend en paramètre deux vecteurs de réel "A" et "B" et qui transfert les éléments du vecteur "A" dans le vecteur "B".

Exercice 2:

Ecrire une procédure qui prend en paramètre un vecteur de caractère V et n le nombre d'élément de ce vecteur, et qui permet de lire n caractères dans le vecteur V. Ensuite cette procédure doit pouvoir compter le nombre de fois que le caractère "A" apparaît dans le vecteur.

Selon que le vecteur est trié ou pas les opérations suivantes peuvent être effectuées:

  • La consultation.
  • La mise à jour.

La consultation d'un vecteur

 

Consulter un vecteur consiste à parcourir tous les éléments de ce vecteur sans toutefois les modifier. Exemple: le transfert, la copie etc.

 

La mise à jour d'un vecteur

 

Mettre à jour un vecteur consiste à le modifier:

  • Soit en ajoutant d'autres éléments dans ce vecteur.
  • Soit en supprimant certaines valeurs du vecteur.
  • Soit en modifiant la valeur d'un élément du vecteur.

Le vecteur est trié lorsque les éléments sont classés dans un ordre précis (croissant, décroissant, etc.)

 

Ajout d'un élément dans un vecteur

 

Premier cas: Le vecteur est non trié (les éléments sont en désordre)
Pour insérer un nouvel élément dans un vecteur non trié, on ajoute une case à la suite du vecteur. On insère le nouvel élément dans cette case.

 

V :

4

5

2

-5

 

V :

4

5

2

-5

1

 

 

procédure: ajout_non_trié(V: entier, n, val: entier)
debut
n←n+1
V[n]←val
fin


Deuxième cas: Vecteur trié.

 

val = 6

V :

3

4

8

12

14

 

V :

3

4

6

8

12

14

 

 


Pour insérer un nouvel élément dans un vecteur trié:

  • On ajoute une case à la fin du vecteur.
  • On recherche la position d'insertion de la nouvelle valeur en effectuant un décalage à droite de tous les éléments qui sont supérieur à droite de tous les éléments qui sont supérieurs ou égaux à lui.
  • Lorsque la position d'insertion est trouvée on ajoute cette nouvelle valeur dans la case correspondante.

procédure: ajout_trié(V: vecteur, n, val: entier)
var i: entier
debut
n←n+1
i←n
tant que val<=V[i-1] et i>1 faire
V[i] ←V[i-1]
i←i-1
fin tant que
V[i] ←val
fin

 

Suppression

 

Val = 2

 

V :

4

7

1

2

5

8

 

 

Pour supprimer un élément dans un vecteur:

  • On recherche si cet élément existe dans le vecteur.
  • Si l'élément à supprimer existe on le supprime alors en effectuant un décalage à gauche de tous les éléments situés à sa droite.
  • On diminue la taille du vecteur.

La procédure correspondante est:

procédure: supprime(V: vecteur, n, val: entier)
var i: entier
debut
i←1
tant que i<=n et val≠V[i] faire
i←i+1
fin tant que
si val=V[i] alors
tant que i<n faire
V[i] ←V[i+1]
i←i+1
fin tant que
n←b-1
fin si
fin

 

Modification d'un élément du vecteur

 

Premier cas: vecteur non trié
val=7 par Nval=6

 

V :

4

7

1

5

8

 

 

Pour modifier une valeur dans un vecteur non trié:

  • On recherche si cette valeur existe dans le vecteur.
  • Dans le cas où elle existe on la remplace par la nouvelle valeur

Ecrivons la procédure correspondante

Procédure: modifier_nom_trié(V: vecteur, n, val, Nval: entier)
var i: entier
debut
i←-1
tant que i<=n et val#V[i] faire
i←i+1
fin tant que
si val=V[i] alors
V[i] ←Nval
fin si
fin


Deuxième cas: Vecteur trié
val=7 par Nval=9

 

V :

4

5

7

8

10

14

 

 

Principe 1:

Pour modifier une valeur dans un vecteur trié:

  • On recherche si cette valeur existe dans le vecteur.
  • Dans le cas où elle existe on la supprime en effectuant un décalage vers la gauche de tous les éléments situés à droite.
  • On recherche la position d'insertion de la nouvelle valeur en effectuant un décalage à droite.
  • Lorsque la position d'insertion est retrouvée, on insère la nouvelle valeur dans la case correspondante.

Principe 2:

Pour modifier une valeur dans un vecteur trié:

  • On recherche si cette valeur existe dans le vecteur.
  • Dans le cas où cette valeur existe. On vérifie si cette valeur est plus petite que la nouvelle valeur. Si c'est le cas on effectue un décalage à gauche de toute les éléments situés à sa droite à la recherche de la position d'insertion de "Nval". Dans le cas contraire on effectue un décalage à droite de tous les éléments situés à sa  gauche à la recherche de la position d'insertion de "Nval".
  • Lorsque cette position est retrouvée, on insère la nouvelle valeur dans la case correspondante.

procédure: ajout_trié_1(V: vecteur, n, Nval, val: entier)
var i: entier
debut
i←1
tant que i<=n et val≠V[i] faire
i←i+1
fin tant que
si val=V[i] alors
tant que i<n faire V[1] ←V[i+1]
i←i+1
fin tant que
fin si
tant que Nval<=V[i-1] et i>1 faire
V[1] ←V[i-1]
i←i-1
fin tant que
V[i] ←Nval
fin

Procédure: ajout_trié_2(V: vecteur, n, val, Nval: entier)
var i: entier
debut
i←1
tant que i<=n et val≠V[i] faire
i←i+1
fin tant que
si val=V[i] alors
si val<V[i] alors
tant que i<n et Nval>=V[i+1] faire
V[i] ←V[i+1]
i←i+1
fin tant que
sinon
tant que i>1 et Nval<=V[i-1] faire
V[i] ←V[i-1]
i←i-1
fn tant que
fin si
V[i] ←Nval
fin si
fin

 

 


Les chaînes de caractères

 

Une chaîne de caractères est un ensemble de caractères portant le même nom de variable. Chaque caractère est repéré par son rang dans la chaîne.
Une chaîne de caractères correspond alors à un vecteur donc les éléments sont les caractères.

 

Déclaration

 

const max=20
type chaîne = tableau[1..max] de caractères
var ch: chaîne

ou alors

var ch: chaîne.

Remarque:

  • Le premier élément d'une chaîne de caractère commence toujours au rang "1".
    Exemple:
    ch'ESSO'
    ch[1]='E'
  • Généralement la longueur d'une chaîne de caractère ne dépasse pas 255 caractères.
  • Une chaîne de caractère se manipule exactement comme un vecteur de caractère à l'exception de la lecture, l'écriture et de l'affectation

Exemple

 

var c: tableau[1..20] de caractère
ch1, ch: chaîne

  • Lecture des caractères:
    pour i=1 à 20 faire
    lire(C[i])
    fin pour
  • Lecture de chaîne:
    lire(ch)
  • Ecriture des caractères:
    pour i=1 à 20 faire
    écrire(C[i])
    fin pour
  • Ecriture des chaînes
    écrire(ch)
  • Affectation des caractères:
    pour i=1 à 20 faire
    A[i]C[i]
    fin pour
  • Affectation des chaînes:
    ch1ch

Avec les objets de types chaîne de caractère on peut effectuer les opérations suivantes:

  • Calculer la longueur de la chaîne de caractères on utilise la fonction lon(ch)
  • On peut effectuer la concaténation de deux chaînes de caractères.
    Exemple:
    ch1'je suis'
    long(ch1)=7
    ch2'je pense, donc je suis.'
    long(ch2)=23


Exercice

 

Gestion des congressistes
Les congressistes et les sessions sont stockés dans le vecteur. Les informations sur un hôtel sont:

  • Le nom de l'hôtel
  • Localité
  • Numéro de téléphone
  • Prix de l'hôtel

Les informations sur une session sont:

  • Numéro de la session
  • Désignation
  • Le nombre de place max
  • Le nombre d'inscrit
  • La durée de la session (jour, mois, année)
  • Heure de debut de session.

Les informations sur un congressiste sont:

  • Le nom
  • L'adresse: le numéro de téléphone
  • L'accompagnateur
  • L'hébergement: la liste des sessions auquel il est inscrit.

Le champ accompagnateur est un entier qui vaut "1" si le congressiste est accompagné "0" sinon.
Le champ hébergement est de type hôtel
Le champ liste des sessions est un tableau de session sachant que chaque congressiste ne peut participer qu'à 10 sessions au maximum.
Le nombre de congressiste est de 100 avec un total de 20 sessions.

Questions:

    • Définit la structure de données correspondant à la liste des sessions.
    • Définir la structure de donnée correspondante à un hôtel
    • Définir la structure de donnée correspondante à un hôtel.
    • Définir la structure de données correspondante à la liste des congressistes.
  1. Ecrire une procédure qui permet de créer la liste des sessions.
  2. Ecrire une fonction qui prend en paramètre la liste des congressistes et qui compte le nombre de congressiste accompagné sachant qu'on a enregistré que 80 congressistes.
  3. Ecrire une procédure qui affiche la liste des sessions qui se sont déroulée le 11/06/2009
  4. Ecrire une procédure qui affichage la liste des congressistes inscrits dans la session "base de données repartie"
  5. Ecrire une fonction qui compte le nombre de congressistes affectés à " Prestige hôtel".
  6. Ecrire une procédure qui recherche et affiche la session qui a le plus grand nombre d'inscrit et celle qui a le plus petit nombre d'inscrit