1

Algorithmique
&
structures des données II
1ère Business Computing (BC)
Responsable : Dr. Fadoua Bouafif

Dr. Fadoua.BOUAFIF
 2
Objectifs du cours

Ce cours a pour objectif de prolonger les acquis du premier semestre dans

l’élément algorithmique et programmation1, en introduisant de nouvelles
structures de données linéaires et arborescentes avec différentes
implémentations (contiguë et chainée).
 Nous commençons tout d’abord par introduire la notion des types
d’éléments abstraits, ainsi que le principe de la récursivité.
 Ensuite, nous couvrons les structures de données linéaires : les listes, les
files et les piles et leur application à travers l’évaluation des expressions
arithmétiques.
 Enfin, les structures de données arborescentes sont étudiées (arbres,
graphes).
 3
Plan du cours

Chapitre 1: Les enregistrement

Chapitre 2: La récursivité
Chapitre 3: Les variables dynamiques
Chapitre 4: Les listes chainées
Chapitre 5: Les piles et les files
Chapitre 6: Les arbres
Chapitre 7: Les arbres de recherche
 4

Chapitre 1

Les enregistrements

Dr. Fadoua.BOUAFIF
 5
Objectifs du chapitre

A la fin du chapitre, les étudiants seront en mesure de:

- Définir le type enregistrement en algorithmique et en langage C

- Nommer les opérations de manipulation des enregistrements

- Déterminer le tableau d’enregistrement

- Arranger les pointeurs et les enregistrements

Dr. Fadoua.BOUAFIF
 6
Plan du chapitre

1) Introduction
2) Définition
3) Déclaration
4) Accès aux champs d'une variable structurée
5) Opérations sur les enregistrements
6) Tableaux et enregistrements
7) Pointeurs et enregistrements
8) Conclusion
Dr. Fadoua.BOUAFIF
 7
Introduction

Les types utilisés, jusqu'à présent, sont :

 des types simples, tels que:
 réel,
 entier,
 caractère,
 et le type structuré tableau qui permet de stocker plusieurs données de même type.
Il est parfois nécessaire de définir un objet qui décrit plusieurs informations de types différents. Cet
objet est alors définit à travers un type structuré appelé enregistrement ou structure.

Dr. Fadoua.BOUAFIF
 8
Définition

 Le type enregistrement (structure) est une structure de données qui rassemble un ensemble
d'informations de types différents - simple, complexe ou même de type enregistrement- dans une
même variable.
 L'information qui compose cette structure est appelée champ ou attribut.
 Une structure est un ensemble d'attributs.
Exemple: Structure Etudiant
nom : chaine [20]
prénom : chaine [20]
Carte_etudiant : entier

Dr. Fadoua.BOUAFIF
 9
Déclaration : Syntaxes
En Algorithme En C
Structure NomStructure Typedef Struct Typedef Struct Struct NomStructure
champ1 : type1 NomStructure { {
Déclaration champ2 : type2 { type1 champ1 ; type1 champ1 ;
structure champ3 : type3 type1 champ1 ; type2 type2 champ2 ;
..... type2 champ2 ; champ2 ; type3 champ3 ;
champn : type3 type3 champ3 ; type3 .....
..... champ3 ; typen champn ;
typen champn ; .....
};
}; typen
champn ;
} NomStructure ;

Struct NomStructure
Déclaration Var: nom_variable: NomStructure nom_variable ;
variables NomStructure nom_variable ;

Dr. Fadoua.BOUAFIF
 10
Déclaration: Exemples

En Algorithme En C

Structure Personne Typedef Struct Typedef Struct Struct Personne

Déclaration nom : chaine[20] Personne { {
structure prenom : chaine[20] { char nom[20] ; char nom[20] ;
CIN : entier char nom[20] ; char prenom[20] ; char prenom[20] ;
char prenom[20] ; int CIN ; int CIN ;
int CIN ; } Personne ; };
};

Déclaration Var: P1, P2: Personne Personne P1, P2 ; Struct Personne P1,
variables P2 ;

Dr. Fadoua.BOUAFIF
 11
Remarques
En C
 Il est possible de déclarer et d’initialiser une variable structure dans un seul et même temps :
Struct NomStructure
{ Exemple
type1 champ1 ; Struct Personne
{
type2 champ2 ;
char nom[20];
type3 champ3 ; char prenom[20];
..... int CIN;
}P1= {"med", " selmi", 12345678};
typen champn ;
} Nom_variable = {val_champ1, val_champ2,… };

Dr. Fadoua.BOUAFIF
 12
Remarques
En C
 La déclaration de la structure sera effectuée avant le programme principal.

 Exemple: #include <studio.h>

Struct Personne
{
char nom[20];
char prenom[20];
int CIN;
}; /*N’oubliez pas ce point virgule*/
void main ( )
{
………
}
Dr. Fadoua.BOUAFIF
 13
Activité 1

 Déclarer une variable enregistrement représentant un nombre Complexe en algorithmique et en

langage C .

Typedef Struct
 Solution: {
Structure Complexe float P_reel;
P_reel: reel float P_complexe;
P_complexe: reel } Complexe;

var: N:Complexe Complexe N;

Dr. Fadoua.BOUAFIF
 14
Accès aux champs d'une variable structurée

Syntaxe:
.
nom_variable nom_champ
Exemple:
En algorithme EN C
Structure Personne #include <stdio.h>
nom :chaine [20] Typedef Struct Personne
CIN : entier {
char nom[20];
Algorithme Affiche_P int CIN;
var : P : Personne };
debut Void main()
Ecrire ("taper nom et CIN") { Personne P;
lire(P.nom, P. CIN) printf ("taper nom et CIN")
Fin scanf("%s %d", P.nom, &P.CIN)
Dr. Fadoua.BOUAFIF }
 15
Opérations sur les enregistrements

 Egalité ou différence (== ou !=):

 On ne peut pas tester l'égalité ou la différence de deux enregistrements de même type
d'une façon globale.
 La comparaison doit se faire champ par champ : le 1er champ du premier
enregistrement est comparé au premier champ du second enregistrement et ainsi de suite.
 Exemple:
P1=P2  écriture fausse
Structure Personne
nom :chaine [20] En algorithme
CIN : entier P1.nom =P2.nom
P1.CIN =P2.CIN  écriture correcte
var: P1,P2: Personne En C
Strcmp(P1.nom, P2.nom)  écriture correcte
Dr. Fadoua.BOUAFIF P1.CIN =P2.CIN
 16
Opérations sur les enregistrements

 Affectation (← en algo = en c):

Il est possible d'affecter une variable enregistrement dans une autre, à condition qu'ils soient

de même structure.
=> Tous les champs de la première variable enregistrement à affecter seront recopiés dans
les champs de l'autre variable enregistrement.
Exemple:
Struct Personne
}
P1= P2;
char nom [20]; Printf ("%s %d", P1.nom, p1.CIN);
int CIN;  ali 12345678
};
Struct Personne P1, P2={"ali",12345678};
Dr. Fadoua.BOUAFIF
 17
Opérations sur les enregistrements

 Comparaison (≥, ≤, >, < ):

Les opérateurs de comparaisons ne peuvent pas être utilisés sur une variable de type structure.

 lire(objet .champ)/écrire (objet . champ)

Les opérations de lecture/écriture n'acceptent que des types simples, alors on ne peut pas lire/écrire
directement une variable de type structure.
=> On doit lire/écrire les attributs de la variable de type structure un à un.

Dr. Fadoua.BOUAFIF
 18
Attention!

 En C
Pour la manipulation des attributs de type chaîne de caractères, les fonctions prédéfinies de
manipulation des chaînes sont utilisées.
Exemple:
Personne P2;
Typedef Struct Personne
} Strcpy(P2.nom, "alia"); // affectation du nom « alia » à P2.nom
char nom [20];
P2.CIN =12345679; // affectation CIN à P2.CIN
int CIN;
}; Strcmp(P1.nom, P2.nom); // Comparaison de deux chaines

Personne P1= {"ali",12345678};

Dr. Fadoua.BOUAFIF
 19
Activité 2

 Ecrire un programme qui permet de saisir le nom, le prénom et l'âge de deux étudiants et
d’afficher la différence d'âge entre eux.

 Solution

Dr. Fadoua.BOUAFIF
 20
Tableau & enregistrement
Syntaxe

En Algorithme En C
Structure NomStructure Typedef Struct NomStructure
At1 : type1 {
At2 : type2 type1 At1;
At3 : type3 type2 At2;
type3 At3;
Type Tab : tableau [1…10] de NomStructure };

Var : T : Tab NomStructure T[10];

Dr. Fadoua.BOUAFIF
 21
Tableau & enregistrement
Exemple
En algorithme En C

Structure Etudiants Typedef Struct Etudiants

nom: chaine [20] {
prenom: chaine [20] char nom[20];
carte_etu: entier char prenom[20];
int carte_etu;
Type Tab : tableau [1…10] de Etudiants };

Var : E : Tab Etudiants E;

E [0] E[1] ………

Etudiants E[10]; med sassi 222 afef Ben ali 111 …

Dr. Fadoua.BOUAFIF
E [0].nom E [1].carte_etu
 22

Activité 3

 Soit un étudiant est définie par son nom, son prénom et 4 notes.
 Définir la structure étudiant
 Ecrire un algorithme qui permet de saisir une liste de 30 étudiants

Dr. Fadoua.BOUAFIF
 23
Activité 4

 Soit un ouvrier est définie par son nom, son prénom et sa date de naissance.
 Définir la structure date
 Définir la structure Ouvrier
 Ecrire un sous-programme « Vérifier » qui permet de tester et vérifier si deux ouvriers sont
identiques ou non. Le sous-programme envoie 1 si identique 0 sinon.
 Ecrire le programme principal qui permet de saisir deux ouvriers et de les vérifier s’ils sont
identique ou non

Dr. Fadoua.BOUAFIF
 Pointeurs & enregistrements 24

Syntaxes

En Algorithme En C

Structure Nom_Structure typedef Struct

Atr1 : type1 {
Atr2 : type2 type1 Atr1;
……. type1 Atr1;
….
Var: pt_structure: ↑ Nom_Structure }Nom_Structure;

Nom_Structure *pt_structure;

ASD II
 Pointeurs & enregistrements 25

Syntaxes (suite)
Pour accéder à un champ de la structure avec une variable pointeur, nous utilisons:
 En algorithme l’opérateur (.)
 En C l’operateur  ou l’opérateur (.)
En Algorithme En C
Structure Nom_Structure typedef Struct
Déclaration structure Atr1 : type1 {
Atr2 : type2 type1 Atr1;
……. type1 Atr1;
….
}Nom_Structure;

Déclaration variable Var: pt_structure: Nom_Structure Nom_Structure *pt_structure;

Accès aux champs pt_structure.Atr1 (*pt_structure). Atr1; ou pt_structureAtr1;

ASD II
 Pointeurs & enregistrements 26

Exemple
En algorithme En C
Algorithme test #include<stdio.h>

structure article Typedef struct Article

{ char nom[20];
nom : chaine[20]
int reference ;
reference : entier float prix;
prix : réel };
var : A : article void main ()
pA : article {
ref : entier Article A; // déclaration variable enregistrement
Article *pA ; // déclaration d’un pointeur de type enregistrement
Début int ref; // déclaration variable entier
pA  A pA=&A; // pA pointe sur l’adresse de A
(*pA).prix 20 (*pA).prix=20; // ou A.prix =20
lire ( (*pA).reference) scanf("%d",&(pAreference) ); //ou scanf("%d", &((*pA).reference));
écrire ((*pA).prix) //ou scanf("%d", &(A.reference));
ref=(*pA).reference; // ou ref = pA -> reference ;
ref (*pA). reference
// ou ref = A . reference ;
Fin } ASD II
 27
Structure contenant des pointeurs
Exemple (suite)
 Un pointeur peut être membre (attribut) d'une structure.
En Algorithme En C
Algorithme test Typedef struct IntPointeurs
structure IntPointeurs { int *p1; // pointeur p1 de type entier
p1 : entier int *p2; // pointeur p2 de type entier
p2 : entier };
var : point : IntPointeurs
i1: entier void main ()
i2 : entier {
IntPointeurs point; // declaration variable de type enregistrement
Début int i1, i2; // declaration de i1 et i2 de type entier
i1100 i1=100;
point.pl  i1 point.p1=&i1; // point.p1 pointe sur i1
point.p2  i2 point.p2=&i2; // point.p1 pointe sur i2
*(point.p2) 5 *(point.p2)=5; // 5 est affecté à i2 (i2=5)
écrire (* point.pl ) printf("i1=%d\n", *(point.p1)); // affiche i1=100
écrire (* poiut.p2 ) printf("i2=%d\n", *(point.p2)); // affiche i2=5 ASD II
Fin }
 28
Conclusion

 Dans ce cours nous avons :

 Définir le type enregistrement (structure)
 Détailler les opérations qui sont effectués sur les enregistrements
 Présenter le tableau d’enregistrement
 Présenter l’utilisation des pointeurs sur les enregistrements

Dr. Fadoua.BOUAFIF