Cours d’Algorithmique et Utilisation des Structures de Données, niveau 1, IAI-Cameroun, année académique 2012-2013.

Chapitre 3 : STRUCTURES DE DONNÉES.

Une façon de distinguer les objets est de les classer en fonction des actions qu’on peut leur appliquer.
On obtient des types de données. On obtient deux catégories de types : les types élémentaires (ou
simples, ou scalaires), et les types structurés (ou composés).
Un type est élémentaire si les actions qui le manipulent ne peuvent accéder à l’objet que dans sa
totalité. Les types élémentaires sont généralement prédéfinis par le langage, et directement utilisables
par le programmeur.
Certains langages (tel Pascal) offrent des constructeurs de types élémentaires, qui permettent au
programmeur de définir ses propres types élémentaires, notamment pour spécifier un domaine de
valeurs particulier.
Un langage est dit typé si les variables sont associés à un type particulier lors de leur déclaration.

A. Types simples :

Ils se partagent en deux groupes : les types discrets et les réels.

Les types discrets représentent des objets dont les valeurs possibles sont énumérables, en y ajoutant la
contrainte d'un nombre fini de valeurs.

A.1) Type entier :

Il représente partiellement l’ensemble Z des entiers relatifs, généralement de -MaxInt-1 à MaxInt.

MaxInt est un entier positif qui vaut généralement 32767. Les entiers négatifs sont représentés sous
forme complémentée :
− Soit en complément à 1, où la valeur négative d’un élément est obtenue en
inversant chaque position binaire de sa représentation.
− Soit en complément à 2, qui s’obtient en ajoutant 1 au complément à 1.

• Les opérations arithmétique et de comparaison s’appliquent au type entier : addition, soustraction,

multiplication, division, modulo et comparaisons ( =, >, >=, <, <=, <> ).

• Notation algorithmique : Type : Entier.

A.2) Type booléen :

Il représente un ensemble composé de deux valeurs logiques : vrai et faux.

• Les opérations s’appliquant à ce type sont :

− Les opérations logiques : disjonction (ou), disjonction exclusive (xou),
conjonction (et), négation (non)
− Les opérations de comparaison : =, <>.

Table de vérité des opérateurs logiques :

P Q non P P et Q P ou Q P xou Q
faux faux vrai faux faux
vrai faux faux
faux vrai vrai
vrai vrai faux vrai faux

• Notation algorithmique : Type : Booléen.

Chapitre 3 : STRUCTURES DE DONNÉES STATIQUES. 1/6 (version pour étudiants, 08 avril 2013) Par A. KWONTCHIE
Cours d’Algorithmique et Utilisation des Structures de Données, niveau 1, IAI-Cameroun, année académique 2012-2013.

A.3) Type caractère :

Le jeu de caractères d'une machine est normalement l'énumération, dans un certain ordre, des lettres et
signes affichables sur un écran ou imprimables sur papier. Il existe une norme (ASCII) pour un jeu de
128 caractères comprenant des caractères imprimables et des caractères de "contrôle". Cette norme ne
comporte pas de lettres accentuées.
Sur la plupart des machines, on utilise un octet pour représenter un caractère ; il est donc possible
d'en énumérer 256 différents. Si les 128 premiers caractères sont presque toujours ceux de la norme
ASCII, chaque constructeur a ses propres conventions pour les 128 caractères restants. Quelques
normes existants : EBCDIC, ISO-8859, ISO-8859-1 (= latin 1).
Face à la nécessité de prendre en compte tous les symboles de toutes les langues du monde, l’ISO
(International Standard Organisation) a proposé une norme pour représenter les caractères sur 32 bits,
mais seul un sous-ensemble de ce jeu, codé sur 16 bits, et appelé UNICODE, commence à être
exploité par quelques SE et langages de programmation.

• Les opérations possibles sont principalement les comparaisons : =, <>, >, <, <=, >= et la fonction
de conversion entier  caractère : chr().

• Notation algorithmique : Type : Car.

A.4) Constructeurs de types simples :

A.4.1) Les types énumérés :

Une façon simple de construire un type est d’énumérer la suite ordonnée des éléments ou symboles qui
le compose.

Ex : semaine = {Dimanche, Lundi, Mardi, Mercredi, Jeudi, Vendredi, Samedi}

couleurs = {vert, bleu, gris, rouge, jaune}
nbpremiers = {1, 3, 5, 7, 11, 13}
voyelles = {‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘y’}

• Les opérations possibles sont les comparaisons ( =, <>, <, >, <=, >= ).

• Notation algorithmique : Type couleurs = {vert, bleu, gris, rouge, jaune}.

A.4.2) Les types intervalles :

Un type intervalle définit un intervalle de valeurs sur un type de base.

• Toutes les opérations applicables au type de base sont applicables au type intervalle qui en est
dérivé.

L'intérêt de l'utilisation des intervalles réside dans l'amélioration de la lisibilité des programmes (on
voit plus clairement quelles sont les valeurs possibles) et l'augmentation de la sécurité de
programmation (des valeurs illégales peuvent être automatiquement détectées à l'exécution).

Ex : naturel = [0, MaxInt]

lettres = [‘a’, ‘z’]

• Notation algorithmique : Type naturel = [0, MaxInt].

Chapitre 3 : STRUCTURES DE DONNÉES STATIQUES. 2/6 (version pour étudiants, 08 avril 2013) Par A. KWONTCHIE
Cours d’Algorithmique et Utilisation des Structures de Données, niveau 1, IAI-Cameroun, année académique 2012-2013.

A.5) Type réel :

Il sert à représenter partiellement et approximativement l’ensemble des nombres réels, car cet
ensemble est infini et indénombrable. Le type réel décrit ainsi un nombre fini de représentants
d’intervalles du continuum des réels. Plusieurs techniques de représentation existent : représentation
en virgule flottante, représentation en virgule fixe, représentation BCD (Binary Coded Decimal). Dans
tous les cas, les propriétés mathématiques sur les réels ne sont pas toujours vérifiées.

A.5.1) Représentation en virgule flottante :

Ici, un nombre réel x est représenté par trois entiers s, e et m tels que :

x=−1 s mB e e = exposant
s∈ { 0,  1  } m = mantisse
−E ≺ e ≺ E B = base (généralement 2, 8 ou 16)
−M ≺ m≺ M
E et M sont imposés par la longueur du mot
{}{}{} de la machine

On obtient une forme canonique ou normalisée en ajoutant la condition :

M
≤∣m∣≺ M
B

Exemple :

Si on a B = 10, M = 1000  M/B = 100

x = 0,314  x =314. 10−3
y = 52  y =520 . 10−1

A.5.2) Représentation en virgule fixe :

Elle consiste à utiliser une représentation similaire aux nombres entiers en attribuant un nombre de
"bits" fixes à la partie fractionnaire et un autre nombre de "bits" à la partie entière.

A.5.3) Représentation BCD :

Ici, on représente les nombres comme une suite de chiffres allant de 0 à 9, l'emplacement de la virgule
étant fourni séparément.

• Les opérations arithmétiques et relationnelles sont applicables, sans garantie de résultats justes.
Eviter le test d’égalité.

• Notation algorithmique : Réel.

Chapitre 3 : STRUCTURES DE DONNÉES STATIQUES. 3/6 (version pour étudiants, 08 avril 2013) Par A. KWONTCHIE
Cours d’Algorithmique et Utilisation des Structures de Données, niveau 1, IAI-Cameroun, année académique 2012-2013.

B. Types composés :

Les types composés servent à représenter des informations complexes. Nous nous contenterons des
structures statiques (tableaux, enregistrements, chaînes de caractères, ensembles) dans ce chapitre.

B.1) Type tableau :

B.1.1) Définition et concepts :

Un tableau est un agrégat de composants, objets élémentaires ou non, de même type et dont l’accès à
ses composants se fait par un indice calculé.

• Déclaration algorithmique : Type T = tableau [T1] de T2.

T1 = type des indices (ensemble discret), T2 = type des composants (ensemble quelconque).
− Cardinalité : ∣T2∣∣T1∣ ( ∣T∣= nombre d’éléments de type T)
− Si les composants sont des tableaux, on parle de tableaux à plusieurs dimensions.
− 2 dimensions  Type t = tableau [T1, T2] de T3. t2
1 caract.
− En général Type t = tableau [T1, T2, …, Tn] de Tc.
2 caract.
Exemples : 3 caract.
4 caract.
t1
Type t1 = tableau [booléen] de entier 5 caract.
faux entier
Type t2 = tableau [1,10] de caractères 6 caract.
vrai entier
7 caract.
8 caract.
9 caract.
10 caract.
Type ligne = tableau [1,5] de réel
Type nombre_de_jours = [28,31]
Type mois = {janvier, février, mars, avril, mai, juin, juillet, août, septembre, octobre, novembre,
décembre}
Type an = tableau [mois] de nombre_de_jours

Type U = tableau [booléen] de tableau [semaine] de [1,7]

Type V = tableau [[0,4], [‘a’,’f’]] de réel

B.1.2) Opérations sur les tableaux :

Outre la déclaration d’un tableau, les autres opérations possibles (affectation et comparaison) se
limitent à la manipulation des composants individuels et impliquent que les tableaux mis en jeu aient
le même type de composants et le même type d’indice.

− Accès et modification sélective :

Pour type T = tableau [T1] de T2, si i est une expression d’indice compatible avec le type T1, alors
T[i] donne accès à un composant de T.

La modification sélective s’obtient en modifiant la variable indicée.

Pas de constante de type tableau.

Chapitre 3 : STRUCTURES DE DONNÉES STATIQUES. 4/6 (version pour étudiants, 08 avril 2013) Par A. KWONTCHIE
Cours d’Algorithmique et Utilisation des Structures de Données, niveau 1, IAI-Cameroun, année académique 2012-2013.

B.2) Type enregistrement (ou structure, ou article) :

C’est un type composite, qui regroupe des composants de type quelconque, simple ou composé. Le
nombre de composants est fixe et défini à la déclaration, et chaque composant est accessible
directement.

• Notation algorithmique :
type nomType = article
champ1 : type1,
champ2 : type2,
…
champn : typen
finarticle.
Exemples :

type datation = article jour : [1,31], mois : [1,12], annee : [1900,2100] finarticle.
type designation article patronyme, prénom : chaine finarticle.
type commande = article
date : datation,
client : designation,
numero : entier,
nom_de_produit : tableau [1,max] de chaine,
numero_de_produit : tableau [1,max] de entier,
montant : réel
finarticle.

• Opérations :
− Affectation (d’un article à une variable de même type article)
− Sélection d’un composant : le champ c d’un article x se dénote x.c.
− Comparaisons : =, <>.
− Pas de constante de type article.

B.3) Type chaîne de caractères :

Il sert à représenter des « mots », et peut être vu comme un tableau de caractères.

• Notation algorithmique : chaîne.

• Opérations usuelles : concaténation, calcul de longueur, recherche de caractères ou de sous
chaînes. Et aussi : comparaison (=, <>), affectation.

B.4) Type ensemble :

C’est un type propre au langage Pascal, rarement utilisé et basé sur la notion mathématique
d’ensemble et sur le type énuméré.

• Notation algorithmique : variable identif : ensemble de type_de_lensemble.

Exemples : variable hasard : ensemble de entier, variable binaire : ensemble de [0,1].

type prenom = {Axel, Boris, Aurore}
variable club : ensemble de prenom.

• Opérations : comparaisons [=, <>, <= (inclus), >= (contenant), + (union), - (complément), *
(intersection)],

Chapitre 3 : STRUCTURES DE DONNÉES STATIQUES. 5/6 (version pour étudiants, 08 avril 2013) Par A. KWONTCHIE
Cours d’Algorithmique et Utilisation des Structures de Données, niveau 1, IAI-Cameroun, année académique 2012-2013.

C. Les variables :

C.1) Définitions :

Une variable est un objet matérialisant une information écrite en mémoire centrale. Il s’agit d’un
emplacement mémoire destiné à accueillir une structure de donnée.
Une variable est caractérisée par :
− Son nom
− Son type
− Sa valeur.

Son nom, qui doit être une chaîne significative, dépend du programmeur. Son type dépend du
problème à résoudre. La valeur est définie par les différents traitements qui agissent sur la variable.
La valeur de la variable peut être fixe et in-changeable, on parle alors de constante.

C.2) Opérations sur les variables :

C.2.1) Déclaration :

• Variable :
− Variable nomsymbolique : Type
− Variables nom1, nom2, …, nomn : type.

• Constante :
− Constante nomsymbolique [: Type] = valeur
− Exemple : constante Pi : réel = 3,14.

C.2.2) Affectation :

Elle consiste à attribuer la valeur d’une expression ou d’une constante à une variable.

nomvariable  expression.

Chapitre 3 : STRUCTURES DE DONNÉES STATIQUES. 6/6 (version pour étudiants, 08 avril 2013) Par A. KWONTCHIE