close

Se connecter

Se connecter avec OpenID

Algorithme et structure de données

IntégréTéléchargement
Algorithme et structure de
données
CPGE
plan


Définition et rôle des structures de données en
programmation
Les enregistrements
–

L’allocation dynamique de la mémoire
Les pointeurs
Les listes
– Pile
– File
–

Allocation statique
Objectifs

Connaître les structures de données
élémentaires, tableaux, piles, files, listes
chaînées, arbres

Être sensibilisé aux problèmes
algorithmiques et leur complexité

Modélisation et résolution d’un problème
Définition et rôle des structures
de données en programmation
CPGE
Structures de données



Une S.D indépendante de tout langage de
programmation
Une S.D modéliser au mieux les informations
à traiter
Programme = algorithme + données
Une S.D.A. est un ensemble organisé d’informations (ou données) reliées
logiquement et pouvant être manipulées non seulement individuellement
mais aussi comme un tout
Exemple

Un vecteur est un formalisme mathématique
d’espace vectoriel sur un corps K qui
contient n coordonnées (éléments de K )
(structure abstraite)

En programmation un vecteur peut être
modélisé par un tableau de n éléments
(structure concrète )
Les enregistrements




Les éléments d’un tableau sont de même
type
Dans la réalité les modèles sont plus
complexe
Un enregistrement est un extension de la
notion de type simple (type primitive)
Un enregistrement = variable
Déclaration de la structure d’un
enregistrement
Non standardisé
Mot clé : structure ou enregistrement
Type
Structure NomStruct

var1: type
var2: type
var3: type
……
FinStruct
Exemple

La définition
Type
structure date
j:entier
m:entier
a:entier
finStruct
Type
structure personne
Nom: chaine
Prenom:chaine
DN:date
finStruct
{DN: date de naissance}
Variable
…….
Debut
……
Fin
Exemple
Instanciation et manipulation

Variables
D :date
P :personne
TP
Début
D.j <- 30 {manipulation par champs}
D.m<- 1
D.a<- 1999
lire(P.nom)
P.prenom<- ’’ali’’
P.DN<-D {manipulation globale de la structure date }
Fin
P
nom
prenom
j
m
a
DN
Tableaux d’nregistrements

Déclaration
–
Tableaux
TP(3):personne
Manipulation:
TP(0).nom<- ’’alaoui’’
ecrire(TP( 1).nom, TP( 1).prenom)
lire(TP)
lire(TP(0)) ou evrire(TP(0))
Manipulation des enregistrement



le nom d'un champ est TOUJOURS précédé
du nom de l'enregistrement auquel
ilappartient
Les champs d'un enregistrement, tout
comme les éléments d'un tableau, sont des
variables à qui on peut faire subir les mêmes
opérations (affectation, saisie, affichage,… ).
il est possible d'affecter un enregistrement à
un autre de même type(affectation par
champs)
les enregistrements en langage C

Exemple
struct personne{
char nom[20];
char prenom[20];
struct date dn;
};//le point virgule est obligatoire
struct date { int j,m,a;};
–
les enregistrements en langage C
Void main(){
struct personne p;date p
printf(‘’nom=? ’’);scanf(‘’%s’’,&p.nom);
p.prenom=’’ali’’;
d.j=1;d.m=1;d.a=1999;
p.dn=p;
p.dn.j=10;
printf(’’%s , %s ’’,p.nom,p.prenom);
}
Instruction typedef

Pour créer des types synomime
–
typedef int Entier;
Entier a;
typedef PI 3.14;
typedef if Si;

int a;
Masqué le mot clé struct
typedef struct personne{
……
} personne ;
personne P;
Manipulation en langages C

void affiche(personne p){
–
printf(’’ % s %s ,
%d//%d//%d ’’,p.nom,p.prenom,p.dn.j, p.dn.m,
p.dn.a);
}
personne tp[5];
Void main(){personne p;
scanf(’’%s’’,&p.nom);gets(p.prenom);
……
affiche(p);affiche(tp(2));}
Auteur
Документ
Catégorie
Без категории
Affichages
4
Taille du fichier
256 Кб
Étiquettes
1/--Pages
signaler