Remerciez-le!

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

Les types abstraits de données (TAD) Les types abstraits de données Un TAD est

Les types abstraits de données (TAD) Les types abstraits de données Un TAD est une description d’un ensemble de données qui fait abstraction de la structure de données structure interne inconnue de l’extérieur Un TAD spécifie: Le type de données contenues Une description détaillée des opérations qui peuvent être effectuées sur les données Un TAD ne spécifie pas: La façon dont les données sont stockées Comment les méthodes sont implémentées Les types abstraits de données Exemple Modéliser un sac de billes avec un TAD: Le TAD contient des billes Le TAD fournit la possibilité de remettre ou de retirer une bille dans le sac Algorithme : Le joueur prend une bille du sac de billes et la lance vers la bille cible. Le joueur avec la bille la plus proche du but gagne toutes les billes et remet les billes dans son sac L’algorithme fait référence au sac des billes uniquement et non pas au tissu en coton Exemple d’implémentation du TAD : sac à billes Un tissu en coton avec ruban Les types abstraits de données Abstraction: Séparation entre les propriétés du type de données et son implémentation => Modularité : Changer l’implémentation d’un module sans affecter l’implémentation de l’autre Exemple d’implémentation du TAD : sac à billes Un tissu en coton noué avec un ruban Exemple d’implémentation du TAD : sac à billes Un sac en cuir Exemple d’implémentation du TAD : sac à billes Un sac plastique avec une fermeture L’implémentation de l’algorithme « jeu de billes » est indépendante de l’implémentation du TAD «Sac de billes » Exemple 2 : un réseau routier peut être modélisé par un graphe. Les nœuds correspondent aux intersections et les arcs représentent les routes. Opérations : recherche d’un itinéraire (entre deux lieux, avec ou sans étape); recherche de l’itinéraire le plus court. Les types abstraits de données Les types abstraits de données Les types de données déjà rencontrés sont en fait des TAD Exemple du type entier Notation : suite de chiffres décimaux, éventuellement précédée d’un signe – ou + Opérations : op. arithm. (+, *, /, -, mod, div) On ne se soucie pas de la représentation d’un entier : binaire par complément à 2, … Exemple du type booléen Notation : Vrai, Faux Opérations : opérateurs OU, ET, NON, etc… Représentation : 1 octet en Pascal et C++, rien de prévu en C Les types abstraits de données Pourquoi avoir recours à cette notion nouvelle de type abstrait ? elle permet de définir des types de données non « primitifs », c'est-à dire non disponibles (non déjà implémentés) dans les langages de programmation courants. En résumé : L’implantation d’un TAD comporte deux parties : la structure de données (la mise en œuvre du modèle); les primitives d’accès à la structure de données (les fonctions de bases). Rappel : Notion de pointeur et enregistrement Rappel : Notion de pointeur Structure dynamique  Une variable est dite statique si elle est déclarée dans un algorithme et associée à un identificateur  Elle est créée pendant la phase de compilation et l’espace occupé en mémoire reste constant  Son domaine de valeurs admises et les instructions qui peuvent être appliqués sont bien déterminés à l’avance exemple : Les types statiques : de base – entier, réel, caractères, booléen enregistrements Rappel : Notion de pointeur  Une variable est dite dynamique si elle est créée en cours d’exécution  Elles ne sont donc pas déclarées et ne sont donc pas repérées par des identificateurs mais par des entités mémoires (ou variables) de type pointeur qui ne sont rien d’autres que l’adresse mémoire de la variable générée. Rappel : Notion de pointeur Définition Un pointeur est une variable qui contient l’adresse d’une autre variable dans la mémoire. Les pointeurs sont typés : si T dénote un type, alors ^T dénote le type "adresse d'un objet de type T". Déclaration La déclaration d’une variable de type pointeur se fait de la manière suivant En algorithmique : Nom_variable : ^Type Exemple p,p1 :^entier Rappel : Notion de pointeur  Nom_variable^ est la variable pointée par Nom_variable  La déclaration d’une variable de type pointeur ne réserve pas un espace mémoire pour la variable pointée. Rappel : Notion de pointeur Opérations sur les pointeurs L’affectation d’un pointeur p à un pointeur p1 de même type que p. p,p1 : ^Type p1 ← p l'addition d'un entier à un pointeur. Le résultat est un pointeur de même type que le pointeur de départ. p,p1 : ^Type n : entier p1 ← p+n Rappel : Notion de pointeur la soustraction d'un entier à un pointeur. Le résultat est un pointeur de même type que le pointeur de départ. p,p1 : ^Type n : entier p1 ← p-n la différence de deux pointeurs pointant tous deux vers des objets de même type. Le résultat est un entier. p,p1 : ^Type n : entier n ← p1-p Notons que la somme de deux pointeurs n'est pas autorisée. Rappel : Notion de pointeur Allocation La fonction nouveau (^T), permet de réserver une zone mémoire de taille égale à la taille d’une variable de type T. La fonction renvoie l’adresse de cette zone mémoire qui sera sauvegardée dans une variable de type pointeur sur T. Exemple p ← nouveau (^entier) Destruction La fonction liberer (p), permet de libérer la zone mémoire dont l’adresse se trouve dans p. Exemple liberer(p) Rappel : Les pointeurs en C Déclaration type * nom de var Exemple : déclaration d'un pointeur sur int int *p; Initialisation avec NULL Un pointeur avec la valeur NULL est un pointeur qui n'a pas de cible. p = NULL; Affectation avec une adresse de variable int a; ... p = &a; Rappel : Les pointeurs en C int *px; px=&x; Rappel : Les pointeurs en C Exemple int * p; Rappel : Les pointeurs en C Exemple int * p; int a=4; Rappel : Les pointeurs en C Exemple int * p; int a=4; p = &a; p « pointe » sur a &a : adresse de a Rappel : Les pointeurs en C Exemple int * p; int a=4; p = &a; int b; Rappel : Les pointeurs en C Exemple int * p; int a=4; p = &a; int b; b = *p; *p contenu de la variable pointée par p ou « déréférencement » de p Rappel : Les pointeurs en C Type d'un pointeur float a=4.0; int * p = &a;  Erreur de compilation: un pointeur est un pointeur sur des variables d'un type donné. float a=4.0; float * p = &a; Une variable de type truc * pointe sur un truc Les erreurs Un pointeur non initialisé sur une adresse de variable ne peut être déréférencé. int * p; int b; b = *p;  Erreur d'exécution int * p = NULL; int b; b = *p;  Erreur d'exécution Rappel : Les pointeurs en C Utilisation de NULL On affecte NULL quand un pointeur ne sert plus ou pas encore Le pointeur est mis à NULL  Après utilisation: p = &a; ... b = *p; ... p = NULL; A la déclaration : int * p = NULL; ... p = &a; Avant d'utiliser un pointeur on teste sa valeur: if (p!=NULL) { ... b = *p; ...} else { ... } Rappel : Les pointeurs en C Allocation dynamique L'allocation dynamique de mémoire en langage C peut être réalisée via la fonction malloc() de la bibliothèque <stdlib.h> void * malloc ( size_t t ) Exemple : int * p; p = malloc (sizeof(int)); Libération de mémoire free(void *ptr): libère le bloc mémoire d’adresse ptr précédemment alloué par un malloc Rappel : Les pointeurs en C Allocation dynamique 3étapes : 1. Appeler malloc pour demander de la mémoire : int* memoireAllouee = NULL; memoireAllouee = malloc(sizeof(int)); 2. Vérifier la valeur retournée par malloc pour savoir si l'OS a bien réussi à allouer la mémoire ; if (memoireAllouee == NULL) // Si l'allocation a échoué { exit(0); // On arrête immédiatement le programme } 3. Une fois qu'on a fini d'utiliser la mémoire, on doit la libérer avec free Free(memoireAllouee) Rappel : Les pointeurs en C Exemple 1 : int a = 1; int * p = &a; int b = *p; a = 2; b = 3; p = &b; a = 4; b = 5; Quelle est la valeur des différentes variables après chaque instruction. Rappel : Les pointeurs en C Exemple 1 int a = 1; int * p = &a; int b = *p; a = 1, b = 1, *p = 1. Rappel : Les pointeurs en C Exemple 1 int a = 1; int * p = &a; int b = *p; a = 2; a = 2, b = 1, *p = 2. Rappel : Les pointeurs en C Exemple 1 int a = 1; int * p = &a; int b = *p; a = 2; b = 3; a = 2, b = 3, *p uploads/s3/ asdc-20-21-part3.pdf