Structures de données

Implémentations avec le langage C

IDE (Integrated Development Environment)

Pr. F GMIRA

-Département : Génie informatique-

Année universitaire : 2021-2022

 Contenu du cours

Les implémentations peuvent être avec : C++, Java, Python ou C#, la spécification est la même

Partie A : Langage C : Rappel et compléments

- Chapitre 1 : Langage C : Rappel
- Chapitre 2 : Langage C : Les structures
- Chapitre 3 : Langage C : Les Pointeurs
- Chapitre 4 : Applications des pointeurs
o Gestion de la mémoire
o Passages par valeur et passage par adresse
- Chapitre 4 : Introduction aux structures de données

Partie B : Structures de données linéaires

Structure de données linéaires

- Chapitre 2 : Les tableaux
- Chapitre 3 : Les piles
- Chapitre 4 : Les files
- Chapitre 5 : Les listes chaînées

Partie C : Structures de données non linéaires

- Chapitre 1 : Les arbres

- Chapitre 2 : Les graphes

Partie D : Initiation à la POO

2
Partie : A - Chapitre 1 :
Langage C : Rappel

Sommaire
Mise en situation
I. Algorithmique
1- Conception d'un algorithme
• Analyse descendent :
• Analyse ascendante
• Mélange des deux
2- L’efficacité d’un algorithme
II. Programmation en Langage C : Rappel Voir S1
1- - Composantes d'un programme en C
• La fonction main
• Les fonctions
2- Les variables
3- Types de données
4- Les constantes
5- - Les identificateurs
6- Tableaux (variables indicées)
7- Créer un type de donnée : typedef
8- Les opérateurs
• Les opérateurs arithmétiques
• Les opérateurs logiques (booléens)
• Les opérateurs Les opérateurs de comparaison
• Les opérateurs d'incrémentation
9- L’affectation
10- les expressions – les instructions
11- Communiquer avec l'ordinateur : Entrées/Sorties afficher, lire…
12- Structures de contrôle (if, while, for, switch, ...)
a) Structures conditionnelles
b) Structures réplétives
13- procédures et fonctions
a) Les fonctions
b) Les procédures
14- Une Notion Importante: La Récursivité

3
Mise en situation

problème - Algorithme – programme

Afin de résoudre un problème donné par l'informatique on doit mettre au

point un ou plusieurs paragrammes (logiciel vs. Application).

I. Algorithmique

1- Conception
on d'un algorithme

Avant de faire un programme il est nécessaire de passer tout d’abord par écrire son
algorithme.

Un algorithme est la description des étapes à suivre pour réaliser un travail.

 Analyser un problème = faire un Zoom pour Comprendre

 Concevoir une solution = proposer une solution

 Analyse descendent :
Décomposer le problème en sous problèmes

 Analyse ascendante :
Utiliser les fonctions, primitives, outils,.. dont on dispose, les assembler pour en faire un
ensemble qui résout notre problème.

 Mélange des deux :

On fait une analyse descendante tout en ayant à l'esprit les modules bien conçus qui
existent déjà.

2- L’efficacité d’un algorithme

L'efficacité d'un algorithme est fondamentale pour résoudre effectivement des

problèmes. L'efficacité d’un algorithme est mesurée avec la complexité
complexité.

4
 L'efficacité d'un algorithme est mesurée par son coût (complexité) en temps et en
mémoire.

La complexité d'un algorithme est :

 en temps : le nombre d'opérations élémentaires effectuées pour traittraiter une
donnée de taille n ;
 en mémoire : l'espace mémoire nécessaire pour traiter une donnée de taille n.

Les opérations/instructions élémentaires sont : addition, multiplication, affectation,

instruction de contrôle.

II. Programmation en Langage C : Rappel Voir S1

Un programme est une succession logique et ordonnée d'instructions ou commandes

(langages compilés vs. interprétés).

Un programme est la description d'un algorithme dans un langage de

programmation.

Donc, pour
our écrire un programme il faut :
- Comprendre le problème : S'avoir le découper logiquement en un ensemble
d'opérations élémentaires (actions);
- Ecrire un algorithme : (sur papier);
- Implémenter : Connaître un langage de programmation.

Exemple :
Langage de programmation :Fortran – Pascal - C- C++ - Java- php – js –phyton – C# -
Matlab –

1- Composantes d'un programme en C

 La fonction main
Elle constitue le programme principal:
main()
{
déclaration des variables ;
instructions ;
}
 Les fonctions
Type_du_resultat Nom_fonction (Type_param No
Nom_param,…)
{
déclaration des variables locales ;
instructions ;
}

5
 2- Les variables

 Une variable (repérée par son nom) est le moyen pour stocker les données, qui
pourront être modifiées lors de l'exécution du program.
 Les variables en langage C sont typées, c'est-à-dire que les données contenues
dans celles-ci possèdent un type, ainsi elles sont donc stockées dans la mémoire

3- Types de données

Les types de données

 Nombre entier (int)
 Nombre à virgule (float)
 Caractère (char)
Détails des types de données en langage C :

Type de Signification Taille (en octets) Plage de valeurs

donnée acceptée
char Caractère 1 -128 à 127
unsigned char Caractère non signé 1 0 à 255
short int Entier court 2 -32 768 à 32 767
unsigned short Entier court non 2 0 à 65 535
int signé
int Entier 2 (sur processeur 16 -32 768 à 32 767
bits) -2 147 483 648 à 2 147
4 (sur processeur 32 483 647
bits)
unsigned int Entier non signé 2 (sur processeur 16 0 à 65 535
bits) 0 à 4 294 967 295
4 (sur processeur 32
bits)
long int Entier long 4 -2 147 483 648 à 2 147
483 647
unsigned long Entier long non 4 0 à 4 294 967 295
int signé
float Flottant (réel) 4 3.4*10-38 à 3.4*1038
double Flottant double 8 1.7*10-308 à 1.7*10308
long double Flottant double 10 3.4*10-4932 à 3.4*104932
long

6
 4- Les constantes

Une constante est une variable dont la valeur est inchangeable lors de l'exécution d'un
programme.

#define _Pi 3.1415927

Il est ainsi préférable d'utiliser le mot clef const, qui permet de déclarer des constantes
typées :
const int dix = 10;

5- - Les identificateurs

Les identificateurs se sont les noms de variables/fonctions

6- Tableaux (variables indicées)

Les tableaux ou variables indicées permettent le stockage de plusieurs informations

référencées par un même label. Les tableaux seront détaillés en chapitre entier.

7- Créer un type de donnée : typedef

Il est possible en C de définir un nouveau type de données grâce au mot clé typedef.

Syntaxe :
typedef Caracteristiques_du_type Nom_du_type
où
 Caracteristiques_du_type représente un type de données existant (par exemple
float, int, ...)
 Nom_du_type définit le nom que vous donnez au nouveau type de donnée

Exemple :
L’instruction suivante crée un type de donnée Ch calqué sur le type char :
typedef char Ch

8- Les opérateurs

Les opérateurs sont des symboles qui permettent de manipuler des variables, c'est-à-
dire effectuer des opérations, les évaluer, etc.
On distingue plusieurs types d'opérateurs :

 Les opérateurs arithmétiques

+ (addition) * (multiplication) % (division entière 17%3 donne 5)

- (soustraction) / (division) ^ (exponentiation)

7
  Les opérateurs logiques (booléens)

ET :&& OU : || NON : !

 Les opérateurs Les opérateurs de comparaison

= (égal) < (inférieur) <= (inférieur ou égal)

<> (différent) > (supérieur) >= (supérieur ou égal)

 Les opérateurs d'incrémentation

- X = i++; passe d'abord la valeur de i à X, puis incrémente i (le ++ est après i, on

l'incrémente après)
- X = i--; passe d'abord la valeur de i à X, puis décrémente i
- X = ++i; incrémente d'abord i puis passe la valeur de i incrémentée à X (le ++ est
avant i, on l'incrémente avant)
- X = --i; décrémente d'abord i puis passe la valeur de i décrémentée à X

Exemple 1 :
N = 5;
X = N++; Résultat: X = 5 et N = 6

Exemple 2 :
N = 5;
X = ++N; Résultat: X = 6 et N =6

9- L’affectation

Les opérateurs d’affectation permettent d'affecter, à une variable, une nouvelle valeur.

La forme: expr1 = (expr1) Opérateur (expr2); équivalente à : expr1 Opérateur = expr2;

Remarque :
L’initialisation est une affectation.

10- les expressions – les instructions

les expressions Moyen d'obtenir une valeur en utilisant les constantes, variables,
opérateurs et fonctions.
Les instructions qui permettent d'établir un dialogue entre le programme et
l'utilisateur

8
 11- Communiquer avec l'ordinateur : Entrées/Sorties afficher, lire…

Au cours de l'exécution d'un programme, il est indispensable de pouvoir communiquer

avec l'ordinateur. Cela est rendu possible grâce à l'emploi des instructions afficher,
lire… printf/scanf.

12- Structures de contrôle (if, while, for, switch, ...)

Les structures de contrôle permettant l'écriture des foncionalités du programme

a) Structures conditionnelles

Structure de contrôle conditionnelles permettent de rendre conditionnelle l'exécution

de séquences d'instructions.

 If
 if else
 switch (Variable)
{
case Valeur1 :
Liste d'instructions;
break;
case Valeur2 :
Liste d'instructions;
break;
case Valeurs... :
Liste d'instructions;
break;
default:
Liste d'instructions;
}

b) Structures réplétives

On utilise les Structures de contrôle réplétives quand une suite d'instructions se répète
plusieurs fois dans un programme de façon consécutive.

 while
 do - while
 for

Discussion :
Choix de la structure répétitive

9
 13- procédures et fonctions

Les procédures/fonctionss permettent :

 structurer
urer un programme
 diviser les difficultés
 accroître la lisibilité d'un programme
 éviter les répétitions (optimisation du code)
 -constituer
constituer des bibliothèques

Bonne pratique :
Dès
ès qu'une tâche est cernée et définie il est utile et souvent indispensable de faire
une procédure reflétant cette tâche.

a) Les fonctions

Portion de programme destinée à produire un résultat utilisable par la partie de

programme appelante.
- la communication entre le programme (ou portion de programme) appelant et la
fonction se fait
ait grâce aux paramètres et au "résultat".

b) Les procédures

Portion de programme destinée à réaliser un traitement utilisable par la partie de

programme appelante.

14- Une Notion Importante: La Récursivité

La récursivité : c’est quand une procédure (ou ffonction)

onction) fait appel à elle-même.
elle

Ainsi, pour un problème donné; la façon de concevoir sa résolution peut passer par :
- une solution itérative
- ou bien par une solution récursive.

Pour aboutir à une solution récursive il faut pouvoir énoncer la résoluti

résolution d'un
problème P en évoquant, dans l'algorithme mis en œuvre, la résolution du même
problème P (mais avec des données différentes).

10
Partie : A - Chapitre 2 :
Langage C : Les structures

Sommaire
Mise en situation :
I. Les structures
1- Déclarer une structure
2- Accéder à un champ d’une structure
II. Structures comportant d'autres structures
1- Déclaration
2- Typedef
3- Accès aux données
III. Tableaux de structures
1- Déclaration d’un tableau de structures
2- Remplissage d’un tableau de structures

Mise en situation :
Lorsque l'on cherche à faire des programmes plus complexes, On a
besoin de traiter un groupe de variables comme une seule variable
(un seul bloc).
Exemples :
- Etudiants (Nom, Prénom, Code…)
- Salles (N°, Capacité , …)
- Filières
- Pays …
peut-on
on créer nos propres types de variables composés de plusieurs
variables primitives ?

I. Les structures

Objectif :
Créer et gérer nos propres types de variables

1- Déclarer une structure

Une structure est un type composé variable (défini par nous même)
qui permet de regrouper plusieurs variables de types différents et de
leur donner un nom.

11
Syntaxe :

struct <nom de la structure> Typedef struct

{ {
type-1 champ-1 ; type-1 champ-1 ;
type-2 champ-2 ; type-2 champ-2 ;
… …
type-n champ-n ; type-n champ-n ;
}; } <nom de la structure>;
struct <nom de la structure> <nom de la structure>
Ma_variable ; Ma_variable ;

2- typedef
typedef permet d’associer un nouveau nom à un type de donnée.
Syntaxe :
typedef TypeExistant TypeEquivalent;
L’utilisation de typedef simplifie l'écriture du programme et en accroît la lisibilité.

Attention :
la définition d’une structure n’engendre pas de réservation
mémoire (ne définit que définit le modèle.).

Exemple :

12
Remarque :
- Dans une structure, tous les noms de champs doivent être distincts.
- rien n'empêche d'avoir 2 structures avec des noms de champs en commun.
- L'affectation globale est possible avec les structures, on peut écrire: S2 = S1;
- Par contre on ne peut pas comparer deux structures (il faut comparer champ
par champ)

3- Accéder à un champ d’une structure

Syntaxe :

Nom_de_la_structure.nom_du_champ

Exemple:

II. Structures comportant d'autres structures

1- Déclaration

Une structure peut comporter d’autres structures, la déclaration se fait selon le même
modèle que la déclaration d'une structure dont les éléments sont de type simple.
(voir exemple)

2- Accès aux données

Ce fait également de la même manière

13
Exemple :

III. Tableaux de structures

1- Déclaration d’un tableau de structures

Une déclaration de tableau de structures se fait selon le même modèle que la déclaration
d'un tableau dont les éléments sont de type simple.

Exemple : Déclaration d’un tableau de 100 structures de type Etudiant

14
Pour référencer le nom de la personne qui a l'index i dans Etudiant on écrira :

Syntaxe :

etudiant_ESTF[i].nom

2- Remplissage d’un tableau de structures

Exercice :
Ecrire une procédure Remplir_Etudiant qui rempli les informations d’un étudiant.

Conclusion :
Les structures permettent de traiter un groupe de variables comme une seule variable
(un seul bloc). Il est fréquent de manipuler un tableau de structures ou une structure
qui contient des tableaux.

15