47
Présentation Structures de Données et TDA •Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique –Création de la classe Noeud –Exemples

Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Embed Size (px)

Citation preview

Page 1: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Présentation Structures de Données et TDA

•Chaînage dynamique–Retour sur les tableaux–Allocation dynamique–Liens entre les données–Chaînage dynamique–Création de la classe Noeud–Exemples

Page 2: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Chaînage dynamique

Retour sur les tableaux [ ]–Les tableaux en java sont statiques

•On ne peut pas augmenter ou diminuer le nombre de cases d’un tableau en cours d’exécution.

•Allocation dynamique•Lorsqu’on crée un objet (new), l’espace mémoire est alloué en cours d’exécution.•Nous pouvons libérer l’espace mémoire d’un objet en cours d’exécution.•Nous pouvons conserver des données à l’aide d’un objet.•Truc : Mettre les données dans des objets plutôt que dans un tableau.

Page 3: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Chaînage dynamique

Liens entre les données–Dans un tableau statique les données sont consécutives en mémoire.–Les objets ne sont pas consécutifs en mémoire.

•Tableau

•Objets

1 5 7 9 11 15 2 17 8

175

2 15

7 1198

1

Page 4: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Chaînage dynamique

Il faut prévoir un mécanisme pour faire le liens entre les objets pour simuler un tableau.

•Chaînage dynamique–La stratégie est de créer une structure qui contient l’objet et un lien vers la donnée suivante.–On appelle un nœud, la structure qui contient l’objet et le lien vers le suivant.

1

Lien

5

Lien

7

Lien

Page 5: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

La classe Nœud :

//Une classe interne et ainsi on peut accéder directement aux//attributs à partir de la classe parent.Public class Nœud{ //attributs, l’objet + le lien private Object element; private Nœud suivant;

//constructeur public Nœud(Object element, Nœud suivant){ this.element = element; this.suivant = suivant; }

Page 6: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Chaînage dynamique

Exemple : Nœud tableau;

//insertion d’une donnée dans le tableau

tableau = new Nœud(new Integer(1),null);

//insertion d’une donnée à la suite

Noeud nœud = new Nœud(new Integer(5),null);

tableau.suivant = noeud;

tableau noeud1

noeud

5

null

Enveloppeur(wrapper)

Page 7: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Récupérer un élément dans le tableau (équivalent à tableau [n])

//Dans cet exemple, on ne lève pas d’exception si n invalide

public Object getElement(int n){

//on crée un nœud qu’on place au début du tableau

Nœud position = tableau;

int i = 1;

/On se déplace tant qu’on a pas trouvé ce qu’on cherche ou

//qu’on a pas atteint la fin du tableau (null)

while(i != n && position != null){

position = position.suivant;

i++;

}

if(position != null)

return position.element;

return null;

]

Page 8: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

Les listes

Page 9: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Liste–Structure de données permettant de conserver des données consécutivement de façon linéaire.

–Services offerts : •Insérer un élément•Enlever un élément•Chercher un élément•La liste est-elle vide ?•Nombre d’éléments•...

Page 10: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Implémentation–Dans un tableau statique –Par chaînage dynamique

Dans tous les cas on peut faire l’implémentation en conservant des informations sur la liste à l’extérieur de la liste

Page 11: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

•Représentation graphique–Dans un tableau statique

–Simplement chaînée

–Doublement chaînée

Structure de données

Page 12: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Représentation graphique avec infos sur la listeNombre d’éléments

Debut

Fin

Information supplémentaire

4

Page 13: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Implémentation du déplacement–À partir d’un indice (comme un tableau)

•On passe toujours l’indice en paramètre–Ex: liste.insere(element,2); //insère à la 2ième position

–À partir d’une position courante implicite dans la liste

•L’insertion se fait toujours à une position couranteExemple : liste.premier(); //position au premier élément

liste.suivant(); //passe au suivant

liste.insere(element); //insère à la 2ième position

Page 14: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

–Via un itérateur (une classe définie) fourni par la liste.

•L’utilisateur peut obtenir l’itérateur de la listeIterateur position = liste.iterateur();

position.suivant() //déplace l’itérateurposition.insere(element);

*Rend le déplacement vraiment indépendant de la liste.*C’est la version implémentée dans Java (java.util.LinkedList et java.util.ListIterator)

Page 15: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

•Exemple d’une classe itérateur

La liste

Structure de données

Position courante

Lien sur le précédent

Un objet de la classe Iterateur

Page 16: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Pourquoi choisir une implémentation plutôt qu’une autre ?

–Tableau statique•Nombre d’éléments maximum connu•Données de petite taille

–Simplement chaînée•Nombre d’éléments maximum inconnu, beaucoup d’insertion et peu de recherche•Données de grande taille (autre langage que Java)

Page 17: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Pourquoi choisir une implémentation plutôt qu’une autre ?

–Doublement chaînée•Nombre d’éléments maximum inconnu, peu d’insertion et beaucoup de recherche

-Itérateur-Sauve de l’espace mémoire par rapport à la liste doublement chaînée-Rendre l’itérateur indépendant de la liste-Peut avoir plusieurs itérateurs sur une même liste

Page 18: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Que faire pour implémenter une liste ?–Décider du choix de l’implémentation–Décider des services à offrir–Implémenter un service à la fois–Tester tous les scénarios possibles (début, milieu, fin, vide) pour un service avant de passer au suivant –Tester des combinaisons (insère, insère , cherche , supprime, insère,...)

Page 19: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Liste que nous implémenterons

Debut

Fin

Nombre Éléments

4

Position courante

Page 20: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

Retour sur la pile et la file

Page 21: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Implémentation d’une pile en composant avec une liste

–On peut voir la pile comme un cas particulier d’une liste.–Empile //insèreDébut–Depile //getElement + supprime–estVide //estVide–Vider //supprimeTout–DepileSansEnlever //getElement

Page 22: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Implémentons d’une file avec une liste–On peut voir la file comme un cas particulier d’une liste.

–Enfile //insère à la fin–Defile //premier + getElement() + supprime–estVide //estVide–Vider //supprimeTout–DefileSansEnlever //premier + getElement()

Page 23: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Présentation

•Structure données abstraite (TDA)–Définition–Spécification vs implémentation–File–Pile

Page 24: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Structure de données :–Conteneur de données du même type.

•Type de données abstrait–Une structure de données qui utilise l’encapsulation

•Deux aspects–Services offerts (spécification des méthodes)

–Implémentation

Page 25: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Implémentation–Tableau statique

•Le nombre d’éléments maximum est limité.•L’espace mémoire est réservé totalement à la compilation.

–Chaînage dynamique•Le nombre d’éléments est illimité.•L’espace mémoire est réservé à l’exécution sur demande.

Page 26: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

•Représentation graphique–Dans un tableau statique

–Simplement chaînée

Structure de données

Page 27: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Pile

Page 28: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Pile (LIFO; Last In First Out)–Structure de données où on insère et on enlève toujours au début (dessus)–Même principe que la pile dans la vie courante

•Pile d’assiette, pile de linge, …

–Fortement utilisé en informatique•Pile système, pile d’opérateurs arithmétiques, …

Page 29: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Service d’une Pile

–Empile //Élément sur le dessus de la pile–Depile //Enlève et retourne l’élément

//du dessus de la pile –estVide //retourne si la pile est vide–Vider //Enlève tous les éléments–DepileSansEnlever //Retourne l’élément du dessus

//sans l’enlever de la pile

Page 30: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Antécédents et conséquents

Page 31: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Les antécédents, les conséquents et la levée d’exceptions deviennent importants.

–Un antécédent non respecté lève une exception.–On doit annoncer

•Les conditions préalables (antécédent)•L’état de la structure après l’opération (conséquent)•Les messages d’exception

Page 32: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

Exemple:–Dépiler()

•Antécédent : la Pile ne doit pas être vide•Conséquent : l’élément n’est plus dans la pile•Throws PileVideException

Page 33: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

File

Page 34: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•File (FIFO; First In First Out)–Structure de données où on insère à la fin et on retire au début (dessus)–Même principe que la file d’attente dans la vie courante

•File à la banque, à l’épicerie, …

–Fortement utilisé en informatique•Imprimante, réseau, …

Page 35: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique

Structure de données

•Service d’une File

–Enfile //Insère à la fin de la file–Defile //Enlève et retourne le premier de la

//file–estVide //retourne si la file est vide–Vider //Enlève tous les éléments–DefileSansEnlever //Retourne l’élément du dessus

//sans l’enlever de la file

Page 36: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 37: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 38: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 39: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 40: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 41: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 42: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 43: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 44: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 45: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 46: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique
Page 47: Présentation Structures de Données et TDA Chaînage dynamique –Retour sur les tableaux –Allocation dynamique –Liens entre les données –Chaînage dynamique