Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Faculté des Sciences Département d’Informatique Pr. Khalid HOUSNI Pr. Khalid HO

Faculté des Sciences Département d’Informatique Pr. Khalid HOUSNI Pr. Khalid HOUSNI Structures de Données Structures de Données SMI/SMA (S4) SMI/SMA (S4) https://khalidhousni.shost.ca/ 2015/2014 Structures de données - SMA/ SMI (S4) 2 Objectifs de cours Ce cours a pour objectifs : ●Introduire la problématique de la structuration des données et les types abstraits . ●Étudier les structures les plus classiques rencontrées en informatique pour organiser des données (files, piles, arbres, …). permettant la mise au point de programmes nécessitant la représentation de données complexes. Le cours est structuré en 4 parties ●Structures de données et types abstraits. ●Structures linéaires: listes, files et piles. ●Structures arborescentes: arbres binaires, arbres binaire de recherche, tas, hachage, arbre équilibré. ●Graphes: terminologie, représentation, algorithmes de parcours. 2015/2014 Structures de données - SMA/ SMI (S4) 3 Introduction : algorithme Qu'est-ce qu’un algorithme ? ●Enchaînement d’opérations destiné à résoudre un problème ●Spécification d’un schéma de calcul sous forme d’une suite finie d’opérations élémentaires obéissant à un enchaînement déterminé L’élaboration d’un algorithme exige : ●Description des données ●Description des méthodes ●Preuve de bon fonctionnement La complexité d’un algorithme : ●Temps de calcul, ●Espace nécessaire. 2015/2014 Structures de données - SMA/ SMI (S4) 4 Définitions et Terminologie ... Type Un type de données, ou simplement type, définit le genre de contenu d'une donnée et les opérations pouvant être effectuées sur la variable correspondante. => Le typage est l’association à un objet : – un ensemble de valeurs possibles, – et un ensemble d’opérations admissibles sur ces valeurs Structure de données Une structure de données est une manière particulière de stocker et d’organiser des données dans un ordinateur de façon à pouvoir être utilisées efficacement. On distingue : – Structures de données du langage (types primitifs : Tableaux,…) – Structures de données abstraites (piles, listes…) 2015/2014 Structures de données - SMA/ SMI (S4) 5 … Définitions et Terminologie Structure de données abstraite Un type abstrait ou une structure de données abstraite est une spécification mathématique d'un ensemble de données et de l'ensemble des opérations qu'elles peuvent effectuer. On qualifie d'abstrait ce type de données car il correspond à un cahier des charges qu’une structure de données doit ensuite implémenter. Structure dynamique Une structure dynamique est une structure dont la taille peut varier en fonction des besoins. Ce cours exige la maîtrise des notions de pointeurs et de gestion dynamique de la mémoire. Ce cours exige la maîtrise des notions de pointeurs et de gestion dynamique de la mémoire. 2015/2014 Structures de données - SMA/ SMI (S4) 6 Classification des structures de données On peut classer les structures de données en deux grandes catégories ● Les structures de données linéaires, qui permettent de relier des données en séquence (on peut numéroter les éléments) √ Tableaux √ Piles √ Simplement chaînées √ Listes √ Files √ Doublement chaînées ● Les structures de données non linéaires, qui permettent de relier un élément à plusieurs autres éléments √Binaire (arbre binaire, arbre binaire de recherche, arbre équilibré, tas) √ Arbres √ n-aire √ Graphes Tete 6 suiv 2 suiv 4 suiv 8 suiv 2015/2014 Structures de données - SMA/ SMI (S4) 7 Chapitre 1 : Rappel 7 ●Tableaux ●Enregistrement (structure) ●Pointeurs ●Allocation dynamique ●Fonctions & procédures 2015/2014 Structures de données - SMA/ SMI (S4) 8 Définition : ●Un tableau est une structure de données composée d'un nombre fixe d'éléments d'un même type. Les éléments d’un tableau sont indicés (numérotés). ●Un tableau occupe dans la mémoire des zones contiguës ayant même longueur 1.1) Tableaux 2015/2014 Structures de données - SMA/ SMI (S4) 9 ●Le nombre d’indices correspond à la dimension du tableau : – Pour un tableau simple on utilisera un seul indice – Pour un tableau de dimension 2 on utilisera deux indices. VAR nomTableau1D : Tableau[1..1000] de Type VAR nomTableau2D : Tableau[1..50] [1..10] de Type VAR nomTableau1D : Tableau[1..1000] de Type VAR nomTableau2D : Tableau[1..50] [1..10] de Type 1.1) Tableaux – Déclaration VAR Notes : Tableau[1..253] de Réel 2015/2014 Structures de données - SMA/ SMI (S4) 10 1.1) Tableaux - Accès aux éléments ● L’accès aux éléments d’un tableau simple se fait à l’aide des indices ●Un élément est référencé par la donné du nom du tableau suivie par une expression, renvoyant la valeur de l’indice, entre crochés : NomDuTableau[expression] Exemple : A[8]←25; M←Note[5*2+3] Pour i depuis 0 JSQ 5 faire Note[i]←0 FinPour 2015/2014 Structures de données - SMA/ SMI (S4) 11 1.2) Enregistrement Problématique Besoin d'un mécanisme permettant de grouper des variables de types différents au sein d'une même entité. Exemple : on veut regrouper une variable de type chaîne de caractères pour le nom, une variable de type entier pour le numéro d'employé, etc. 2015/2014 Structures de données - SMA/ SMI (S4) 12 Solutions possibles ? → → On peut penser à créer une variable pour chaque champ. Problème : ces variables ne permettent de contenir que des informations d’une seule personne. → → On peut penser à créer un tableau pour chaque champ. Problème : les informations concernant une personne sont éparpillées sur plusieurs tableaux on ne peut pas donc parler de l’entité personne. 1.2) Enregistrement 2015/2014 Structures de données - SMA/ SMI (S4) 13 ●La réponse à ce besoin est le concept d'enregistrement (en anglais record) : ●Un enregistrement (appelé aussi structure dans certains langages) est un type, ou encore un méta-type, complexe construit à partir de types plus simples. ●Un enregistrement est un ensemble d'éléments de types différents repérés par un nom. Les éléments d'un enregistrement sont appelés des champs. 1.2) Enregistrement 2015/2014 Structures de données - SMA/ SMI (S4) 14 Syntaxe de déclaration d’un enregistrement Exemple Type identifiant_du_type = structure champ1 : type1 champ2 : type2 ... Fin identifiant_du_type Type Etudiant = structure nom, prenom : Chaîne de caractères sexe : Caractère moyenne : Réel CNE : Entier long Fin Etudiant 1.2) Enregistrement – Déclaration 2015/2014 Structures de données - SMA/ SMI (S4) 15 1.2) Enregistrement - Manipulation ● Déclaration d’une variable de type enregistrement Exemple ● La manipulation d'un enregistrement se fait au travers de ses champs. Et1.nom ← "Hanine" Et1.prénom ← "Azedine" Et1.sexe ← "M" Et1.moyenne ← 13.25 Et1.CNE ← 9997070890 nom_enregistrement . nom_champ VAR Et1 : Etudiant VAR identificateur : NomEnregistrement 2015/2014 Structures de données - SMA/ SMI (S4) 16 Gestion dynamique de la mémoire  Pointeurs  Variables dynamiques  Tableaux dynamiques : dimension 1 2015/2014 Structures de données - SMA/ SMI (S4) 17 I.3) Pointeurs a. Adressage des variables Il existe deux modes d'adressage de zone en mémoire : Adressage direct: Accès au contenu d'une variable par le nom de la variable. Adressage indirect: Accès au contenu d'une variable, en passant par un pointeur qui contient l'adresse de la variable. 2015/2014 Structures de données - SMA/ SMI (S4) 18 I. Pointeurs b. Définition Un pointeur est une variable spéciale qui peut contenir l'adresse d'une autre variable ou zone mémoire. Si un pointeur P contient l'adresse d'une variable A, on dit que : P pointe sur A Les pointeurs et les noms de variables ont le même rôle: Ils donnent accès à un emplacement dans la mémoire. Il faut faire la différence: Un pointeur est une variable qui peut 'pointer' vers différentes adresses durant son existence. Le nom d'une variable reste toujours lié à la même adresse. 2015/2014 Structures de données - SMA/ SMI (S4) 19 I. Pointeurs c. Déclaration La syntaxe de déclaration d’un pointeur : VAR identificateur : type; Exemple : VAR np : Entier ; VAR xp : Réel; Un pointeur peut être initialisé à 0, à NULL, ou à une adresse mémoire. Un pointeur de valeur 0 ou NULL ne pointe vers rien. Exemple : np← 0 ; xp ←NULL; On peut pointer sur n’importe quel type : prédéfini, structure, tableau, chaîne, pointeur, fonction, … On peut pointer sur n’importe quel type : prédéfini, structure, tableau, chaîne, pointeur, fonction, … 2015/2014 Structures de données - SMA/ SMI (S4) 20 I. Pointeurs c. Opérateurs Opérateur 'adresse de‘ : & pour obtenir l'adresse d'une variable. Exemple : np←&A L'opérateur & ne peut pas être appliqué à des constantes ou des expressions. Opérateur 'contenu de‘ : (* en langage c) pour accéder au contenu d'une adresse. Exemple : np←345; les pointeurs sont aussi des variables et peuvent être utilisés comme telles: p1 ← p2; p1 pointe vers la même zone que p2 i←p1p2; nombre d’éléments entre les deux adresses 2015/2014 Structures de données - SMA/ SMI (S4) 21 I. Pointeurs d. Exemple ●Soit A une variable contenant la valeur 10, B une variable contenant la valeur 50 et np un pointeur non initialisé: ● Après les instructions : P← &A ; B ← P ; P ← 20 ; np pointe sur A , le contenu de A (référencé par P) est affecté à B, le contenu de A (référencé par P) est mis à 20. 2015/2014 Structures de données - SMA/ SMI (S4) 22 I. Pointeurs e. pointeurs et structures Un pointeur peut être utilisé sur des structures: type complexe=structure reel : Réel img : Réel Fin complexe VAR pc:complexe uploads/Ingenierie_Lourd/ cours-structures-des-donnees-3.pdf