Structures de données et récursivité

IPA – Catherine Faron Zucke et Anne Marie Deryr

Vous avez vu les ArrayList...

suite ordonnée d'éléments de taille variableArrayList<Integer> liste;liste = new ArrayList<Integer>();

Ne peuvent contenir que des objets

premier élément : liste.get(0) dernier élément : liste.get(liste.size()-1) i ième élément : liste.get(i-1)

IPA – Catherine Faron Zucker 2

ArrayList ajout d'un élt: liste.add(new Integer(3));

modif d'un élt: liste.set(i,new Integer(4));

suppression d'un élt: liste.remove(i);

› mêmes algos que sur les tableauxavec taille variable

IPA – Catherine Faron Zucker 3

Piles et Files Ordonnancements particuliers des éléments d'une

collection - implémentation à partir d’un tableau ou d'une liste

Pile : LIFO Last In First Out› empiler/dépiler des éléments› Peut être implémentée par un tableau ou une liste

File : FIFO First In Fist Out› enfiler /défiler des éléments› implémentation par liste plus simple

IPA – Catherine Faron Zucker 4

IPA – Catherine Faron Zucker

Soit la Pile contenant les valeurs : 1, 2, 5

Dessinez moi une Pile

Ajoutons l’élément 12 Dépilons un élément

Soit la File contenant les valeurs : 1, 2, 5

Dessinez moi une File

Ajoutons l’élémént 12 Sortons un élément de la file

Exemples d’utilisation

Algorithmes d'évaluation d'expressions mathématiques

Algorithmes pour mémoriser des données en attente de traitement.

IPA – Catherine Faron Zucker 6

?

Piles avec tableaupublic class Pile{

private Object[] table;private int hauteur;public void empiler(Object o){table[hauteur]=o; hauteur++;}

public Object depiler(){hauteur--; return table[hauteur];}

public Object sommet(){}public boolean vide(){}public boolean pleine(){}

}IPA – Catherine Faron Zucker 7

Files avec ArrayListpublic class File{

private ArrayList<Object> liste;private int longueur;public void enfiler(Object o){liste.add(o); longueur++;}

public Object defiler(){longueur--; return liste.remove(0);}

public Object tete(){}public Object queue(){}public boolean vide(){}

}IPA – Catherine Faron Zucker 8

Conception d'un algorithme Stratégie de résolution d'un problème

Approche incrémentale› itérer jusqu'à obtention du résultat souhaité

Approche récursive› diviser pour régner:

diviser en sous-problèmes régner sur les sous-problèmes combiner les solutions des sous-problèmes

IPA – Catherine Faron Zucker 9

PGCD(a, b) récursif diviser: pgcd(a,b) = pgcd(b, a mod b)

semblable au problème initial de taille moindre

régner: pgcd(a,0) = a

combiner: pgcd(a,b)= pgcd(b,a mod b)=...

IPA – Catherine Faron Zucker 10

PGCD(a, b) récursifSi b=0 Alors retourner a //terminaisonSinon retourner pgcd(a, a mod b)finSi

IPA – Catherine Faron Zucker 11

PGCD(a, b) itératifn <- a; m <- b;TantQue m != 0 Faire r <- n mod m n <- m m <- rFinTantQueretourner n

IPA – Catherine Faron Zucker 12

Fac(n) Relation de récurence

fac(n) = n * fac(n-1), n>0fac(0) = 1

AlgorithmeSi n = 0 Alors retourner 1Sinon retourner n * fac(n-1)FinSi

IPA – Catherine Faron Zucker 13

Fac(n)Complexité

› opération élémentaire : *› nbre de fois où elle est effectuée

fonction de n: M(n) relation de récurence: M(n) = 1 + M(n-1) pour n>0 et M(0) = 0 en développant, on a M(n) = M(n-i) + i pour tout i pour i=n, on obtient M(n) = M(O) + n = n

cf. module Maths discrètes

IPA – Catherine Faron Zucker 14

Manipulation d’une structure recursive !

Ajout d’un élément en position i Suppresssion d’un élément en position i Recherche d’un élément de valeur z Calcul de la somme des éléments

IPA – Catherine Faron Zucker 15

?

A suivre...Structures de données

Maps et Sets listes chaînées : cf. td

› simplement, doublement arbres arbres binaires arbres binaires de recherche graphes

IPA – Catherine Faron Zucker 16