[PDF]

[PDF] Listes chaînées

Il y a plusieurs façons de représenter les listes chaînées en Java L'idée de base est d'utiliser un enchaînement de cellules : – chaque cellule contient un élément  

[PDF] TD Listes - Formations en Informatique de Lille

et en particulier du langage JAVA, cette correction1 est découpée en plusieurs parties : 1 la premi`ere propose une façon d'implémenter les listes chainées, 

[PDF] LISTES

En Java, la valeur d'une variable de type agrégé est une référence Une liste chaınée est un ensemble d'éléments conservés chacun dans un nœud

[PDF] IFT2015 1 Liste chaınée

6 jan 2011 · En Java, on peut implanter une liste chaınée `a l'aide d'une classe pour représenter les nœuds (ListeChainee Noeud) La liste est spécifiée par 

[PDF] TD n 9 - Correction

JAVA MASS L2 Année 2007-2008 TD n◦9 - Correction Listes Une liste est une Une liste est donc une chaine d'élément (d'o`u le terme liste chainée)

[PDF] Collections : listes - CS-108

côte, ou au moyen de nœuds chaînés entre eux via des références Le concept de liste est représenté dans l'API Java par l'interface List du paquetage 

[PDF] 1 Les listes chaînées : représentation sous forme de maillons 2 Les

Vous utiliserez la syntaxe Java 1 1 Qu'est-ce qu'une liste chaînée ? Une liste chaînée correspond à un assemblage d'éléments (ou maillons) reliés entre eux 

[PDF] PILES, FILES ET LISTES CHAÎNÉES

Piles, files et listes chaînées Une interface de pile en Java • Même si la structure de donnée pile est déjà incluse comme classe Java dans le “package” java util 

[PDF] les loisirs fiche pédagogique

[PDF] les loisirs vocabulaire

[PDF] les mille et une nuits

[PDF] les mille et une nuits pdf

[PDF] les montagnes de la france

[PDF] les mots d'un ' langage soutenu en français

[PDF] les multiplexeurs exercices corrigés

[PDF] les musées de paris

[PDF] les nombres complexes cours 2 bac

[PDF] les nombres complexes cours bac

[PDF] les nombres complexes cours bac pc

[PDF] les nombres complexes cours cm2

[PDF] les nombres complexes cours et exercices corrigés pdf

[PDF] les nombres complexes. cours maths sup

[PDF] les nombres premiers 5ème

Amphi 21

Plan •Listes chaînées •Piles

Amphi 22

Listes chaînées

Une liste chaînée est une suite de couples formés d'un élément et de l'adresse (référence) vers l'élément suivant. C'est un jeu de piste (ou un lien dans une page).

Opérations usuelles sur les listes

-Créer une liste vide et tester si une liste est vide. -Afficher une liste -Ajouter un élément en tête de liste. -Rechercher un élément. -Supprimer un élément. -Afficher, retourner, concaténer, dupliquer . . .

Amphi 23

Listes chaînées en Java

class Liste { int contenu;

Liste suivant;

Liste(int x,Liste a) {

contenu = x; suivant = a; contenu contenu contenu suivant suivant suivant

Amphi 24

Les opérations primitives sur les listes

static int tete(Liste a) return a.contenu; static Liste queue(Liste a) return a.suivant; static Liste ajouter(int x, Liste a) return new Liste(x, a); non destructives !

Amphi 25

Identités sur les opérations de liste

• tete(ajouter(x, a)) = x • queue(ajouter(x, a)) = a • ajouter(tete(a), queue(a)) = a (a ≠ null)

Amphi 26

Recherche dans une liste (itérative)

static boolean estDansI(int x, Liste a) while (a != null) if (a.contenu == x) return true; a = a.suivant; return false;

Amphi 27

Recherche itérative (variante)

static boolean estDansI(int x, Liste a) for ( ; a != null; a = a.suivant) if (a.contenu == x) return true; return false;

Amphi 28

Recherche dans une liste (récursive)

static boolean estDans(int x, Liste a) if (a == null) return false; if (a.contenu == x) return true; return estDans(x, a.suivant);

Amphi 29

Recherche dans une liste (récursive abrégée) static boolean estDans(int x, Liste a) return (a != null) && (tete(a) == x || estDans(x, queue(a)));

Amphi 210

Suppression de la première occurrence de x

static Liste supprimerI(int x, Liste a){ if (a == null) return a; if (a.contenu == x) return a.suivant;

Liste b = a, c = b.suivant;

for (; c != null; b = c, c = c.suivant) if (c.contenu == x){ b.suivant = c.suivant; break; return a;

Amphi 211

Suppression (itératif)

(1) c.contenu ≠ x 2 3 4 5 b c // invariant b.suivant == c (2) c.contenu = x 2 3 4 5 b c 2 3 4 5 b c

Amphi 212

Suppression dans une liste (récursive)

static Liste supprimer(int x, Liste a) if (a == null) return a; if (a.contenu == x) return a.suivant; a.suivant = supprimer(x, a.suivant); return a; // variante dans le poly x

Amphi 213

Suppression récursive en conservant la liste

static Liste supprimer(int x, Liste a) { // variante dans le poly if (a == null) return a; if (a.contenu == x) return a.suivant; return new Liste(a.contenu, supprimer(x, a.suivant)); x

Amphi 214

Concaténation de listes (avec copie de a)

static Liste concat(Liste a, Liste b) { // variante dans le poly if (a == null) return b; return ajouter(a.contenu, concat(a.suivant, b); b a

Amphi 215

Fusion de deux listes (itératif)

static Liste fusionI(Liste a, Liste b) {// Suppose a et b distinctes if (a == null) return b;

Liste c = a;

while (c.suivant != null) c = c.suivant; c.suivant = b; return a; b a c

Amphi 216

Fusion de deux listes

static Liste fusion(Liste a, Liste b) if (a == null) return b; a.suivant = fusion(a.suivant, b); return a; ba

Amphi 217

Inverser une liste (itératif, détruit la liste) static Liste inverserID(Liste a)

Liste b = null;

while (a != null)

Liste c = a.suivant;

a.suivant = b; b = a; a = c; return b;

Amphi 218

Inverser une liste (itératif)

12 3 4 5 (2) b = a (3) a = c (1) a.suivant = b

On raccroche le

wagon bleu au train mauve ... b a 12 3 4 5 b cquotesdbs_dbs3.pdfusesText_6