Remerciez-le!

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

Structures de Données Pr. A. MARZAK 2018-2019 Université Hassan II - Casablanca

Structures de Données Pr. A. MARZAK 2018-2019 Université Hassan II - Casablanca Faculté des Sciences Ben M’sik Département mathématique et informatique Stuctures de données ? Définition : une structure de donnée est un moyen de coder et de structurer les données manipulées.. Exemple : type suite = tableau [1..N] d’entiers etudiant = structure nom, prénom : chaîne de caractères âge : entier positif sexe : caractère ... fin structure Données Algorithme Résultats Structures de données Programme = Algorithme + Structures de données Structures linéaires. Pile • Piles, Files, Listes font partie des structures dynamiques linéaires. • Les opérations sur un ensemble dynamique peuvent être regroupées en deux catégories : • les requêtes (consultation); • les opérations de modification. Les opérations classiques : rechercher(S,clé), Insertion(S,elt), Supression(S,elt), Min(S),Max(S), Successeur(S,elt), Prédécesseur(S,elt), etc. Les piles Piles • Une pile contient des objets insérés et retirés selon le principe du dernier arrivé, premier sorti (last-in-first-out LIFO) • Les objets peuvent être insérés à tout moment, mais seulement le dernier (le plus récemment inséré) peut être retiré • Insérer un objet dans la pile correspond à l’empiler (pushing). Dépiler la pile (popping) correspond au retrait d’un objet . • Analogie: distributeur de bonbons PEZ® Pile • Pile est un ensemble dynamique dans lequel l’élément supprimé est celui le plus récemment inséré : dernier entré-premier sorti LIFO • Opérations : • Insérer = Empliler • Supprimer = Dépiler • Valeur= Recherche • (toujours l’élément pointé par le sommet) • Illustration graphique dans le cas d’implémentation par un tableau TDA Pile • Type Pile • utilise Booléen, Elément • Opérations Pile-vide : ->Pile {création d’une pile vide PV(P)} Empiler : Pile x Element ->Pile {EP(P,a)} Dépiler : Pile ->Pile {supprimer le dernier DP(P)} Valeur : Pile->Elément {renvoie l’élément au sommet sans modifier la pile VP(P)} Est-vide : Pile->Booléen {test si la pile est vide EV(P)} Les opérations Dépiler et Valeur ne sont définies que si la pile n’est pas vide Dépiler(P) est-défini-ssi est-vide(P)=faux Valeur(P) est-défini-ssi est –vide(P)=faux • Axiomes Dépiler(Emplier(P,e))=P Valeur(empiler(P,e))=e Est-vide(Pile-vide)=vrai Est-vide(Empiler(P,e))=faux Evaluation d’une expression • A l’aide des opérations et des axiomes du TDA Pile évaluer l’expression suivante : • EV(DP(DP(EP(EP(PV,a)),b)))? Pile. Implémentation à l’aide d’un tableau(1) • Type Pile = enregistrement sommet : entier; elts : tabelau [1..lmax] d’Element FinEnregistrement • Procédure Pile-vide(réf P: Pile) • Début P.sommet:=0; Fin Pile-vide; Procédure Empiler(réf P: Pile, val X : Elément); Procédure Dépiler(réf P: Pile); Fonction Valeur(val P: Pile) : Elément; Fonction Est-vide(val P: Pile) : Booléen; Pile. Implémentation à l’aide d’un tableau(2) Procédure Empiler(réf P: Pile, val X : Elément) Début Si P.sommet=lmax Alors Erreur « débordement » Sinon P.sommet:=P.sommet+1; P.elts[P.sommet]:=X; FinSiFinEmpiler Remarque : chacune des opérations (Empiler, Dépiler) consomme le temps en O(1) Problème: Expliquer comment implémenter deux piles dans un tableau A[1..n] de telle manière qu’aucune ne déborde à moins que le nombre total d’éléments des deux piles vaille n. Les opérations Empiler et Dépiler devront s’exécuter dans un temps en O(1) Pile Dynamique Une pile dynamique est une liste à la quel on attache un pointeur sommet. C’est un enregistrement à une seule case : pointeur qui pointe la dernière valeur traitée dans la liste (sommet). De même que pour les piles statiques nous présentons la déclaration et les sous algorithmes de bases détaillés pour le type statique. Et dans un souci d’uniformisation nous utilisons les mêmes noms mais en ajoutant un D (pour rappeler Dynamique) à la fin de chaque nom pour faire la différence. Note : Il n’y a pas de pile pleine pour les piles dynamique. La seule possibilité de ne pas pouvoir ajouter un élément c’est d’avoir une mémoire pleine, cas que l’on ne prend pas en considération ici. Pile Dynamique Note : Les données enregistrées dans la pile peuvent être des entiers, des réels, des caractères, des chaînes de caractères, des booléens, des tableaux, des pointeurs de listes ou encore des piles ou files. Pile Dynamique Pile Dynamique Les fichiers Les fichiers Motivation Toutes les structures de données que nous avons vues ont un point commun: • Résident dans la mémoire principale de l'ordinateur. (existence limitée à la durée d’exécution du programme) Besoin de conserver des données (pour une utilisation future) après l’exécution du programme (exemple : carnet d ’adresses) la notion de fichier. Les fichiers Qu'est-ce qu'un fichier? Un fichier est une collection de fiches; Exemple : un fichier dans une bibliothèque, une administration etc. Trouver une fiche ? • parcourir le fichier fiche après fiche • utiliser une clé d'accès, si le fichier est trié selon cette clé (ordre alphabétique, ordre de cotation des livres...). Les fichiers En informatique : Un fichier est une séquence de données du même type enregistrées sur un support informatique (de manière permanente). • Un fichier est : • conservés en mémoire secondaire (disques et bandes magnétiques, disquettes,...) • désigné par un nom et possède des attributs tels que date de création, taille,... Fichiers : organisation et accès Définition L’organisation d'un fichier est la manière dont sont rangés physiquement les enregistrements du fichier. • Le but est d'arranger les enregistrement de manière à y accéder le plus rapidement possible. • L'organisation est choisie à la création du fichier. • Le choix d'une organisation correspond à un compromis entre rapidité d'accès et espace de stockage disponible. Fichiers : organisation séquentielle • Elle ne permet qu'un seul accès : le séquentiel. Toutes les informations sont enregistrées de façon séquentielle (linéaire) les unes à la suite des autres. Pour accéder à une information particulière, il faut nécessairement parcourir le fichier à partir du début, et ce jusqu'au moment où cette information est retrouvée. Fichiers : organisation relative (accès direct) • Chaque enregistrement possède un numéro. • On accède à la fiche recherchée en spécifiant ce numéro d'enregistrement. • L'indication d'un numéro permet donc un accès direct à l'information ainsi référencée. Fichiers : organisation indexée Notion d ’index : • Soit un fichier F dont les enregistrements E possèdent une clé C (e.g. nom). Un index permet d ’associer à chaque clé C le rang R de l ’enregistrement E de clé C dans F. • L’index est alors une « table des matières » du fichiers • On crée des fichiers supplémentaire d'index • On parcourt un index pour rechercher une clef. On obtient ainsi l'adresse exacte de l'information recherchée. Les types de fichiers • On distingue deux catégories: • Les fichiers binaires contenant du code binaire représentant chaque élément (enregistrement). Ces fichiers ne doivent être manipulés que par des programmes! • Les fichiers textes (appelés aussi imprimables) contenant des caractères et susceptibles d'être lus, éditées, imprimés... TDA File(1) • Dans le cas d’une file on fait les adjonctions à une extrémité, les accès et les suppressions à l’autre extrémité. • Les files sont aussi appelées FIFO ( first –in –first out) : premier-entré- premier-sorti • Une file comporte une tête et une queue. Les éléments sont donc retirés et consultés dans la tête et rajoutés dans la queue TDA File(2) • Type File • utilise Booléen, Elément • Opérations File-vide : ->File {création d’une file vide FV(F)} Enfiler : File x Elément ->File {EF(F,a)} Défiler : File ->File {supprimer le dernier DF(F)} Valeur : File->Elément {renvoie l’élément au sommet sans modifier la file VF(F)} Est-vide : File->Booléen {test si la file est vide EV(F)} Les opérations Défiler et Valeur ne sont définies que si la file n’est pas vide Défiler(F) est-défini-ssi est-vide(F)=faux Valeur(F) est-défini-ssi est –vide(F)=faux • Axiomes Est-vide(F)=vrai => Valeur(Enfiler(F,e))=e Est-vide(F)=faux => Valeur(Enfiler(F,e))=Valeur(F) Est-vide(F)=vrai => Défiler(Enfiler(F,e))= File-vide Est-vide(F)=faux => Défiler(Enfiler(F,e))=Enfiler(Défiler(F),e) Est-vide(File-vide)=vrai Est-vide(Enfiler(F,e))=faux Représentation contiguë des files Moyens de représentation : tableau On fait progresser les indices modulo taille Lmax du tableau Représentation contiguë des files(2) • Gérer les débordements (1) Enfiler • j:=j+1 mod lmax • Si j=i alors File-pleine • sinon • Si File-vide(F) alors i:=j; FSi • Tab[j]:=e; • FSI (2) Défiler Si !File-vide(F) • i:=i+1 mod lmax e:=Tab[i]; Si i:=j alors j:=-1; i:=-1; FSi (3) File vide i=-1et j=-1 File Dynamique Une File dynamique est une liste à la quel on attache deux (2) pointeurs Debut et Queue. C’est un enregistrement à deux cases : pointeur qui pointe le premier élément de la liste (Debut) et un autre qui pointe la dernière valeur ajoutée dans la liste (Queue). • Exemples : 1- Une file vide Debut = Queue = Nil 2- Une file a un seul élément Debut = Queue ≠ Nil 3- Une file a plus d’un élément Debut ≠ Queue De même que pour les files statiques nous présentons la déclaration et les sous algorithmes de bases détaillés pour le type statique. Et dans un souci d’uniformisation nous utilisons les mêmes noms mais en ajoutant un D (pour rappeler Dynamique) à la fin de chaque nom pour faire la différence Note : Il n’y a pas de file pleine pour les files dynamique. La seule possibilité de ne pas pouvoir ajouter un élément c’est d’avoir une mémoire pleine, cas que l’on ne prend pas en considération ici. File Dynamique File Dynamique File Dynamique File Dynamique Listes chaînées Listes uploads/Ingenierie_Lourd/ cour-struct-1-pdf.pdf