[PDF] [PDF] IFT2015 1 Liste chaınée

[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

IFT2015Miklos Cs}uros 6 janvier 2011

1 Liste cha

ˆın´ee

1.1 Types

D

´efinition 1.1.Untypeest un ensemble (possiblement infini) de valeurs et d"op´erations sur celles-ci.

En Java :

?typesprimitifs ( int,double,boolean, ...) ?typesagr ´eg´es(tableaux et ceux d ´efinis par les classes)

En Java, la valeur d"une variable de type agr

´eg´e est une r´ef´erence. Uner´ef´erence(ou pointeur) est une adresse d"emplacement m ´emoire contentant de l"information (ou elle est nulle). En Java, les variables de types simples donnent l"information directement. Rappel: variable = abstraction d"un emplacement en m´emoire (von Neumann) nom + adresse (lvalue) + valeur (rvalue) + type + port

´ee

D ´efinition 1.2.Untype abstrait(TA) est un type accessibleuniquement`a travers une interface.

Exemple.Le type dedictionnaireoutable de symbolesrepr´esente un ensemble d"associations(cle;info)avec

cl

´es uniques. L"interface (minimale) contient l"op´eration essentiellesearch(k)qui retourne l"info associ´ee avec

la cl ´ek, et l"op´eration d"ajouter un nouveau paireadd(cle;info).

Notions.

?client: le programme qui utilise le TA ?implantation: le programmme qui sp´ecifie le TA ?interface: contrat entre le client et l"implantation

En Java.

?interface et impl´ementation souvent dans le mˆeme fichier ?interface d´efinie par la signature des m´ethodes et variables non-priv´ees ?"clients»avec droits diff´erents (sous-classe, package)

?interfacen"est pas exactement l"interface de notre d´efinition (en Java, elle n"inclut pas le syntaxe

des constructeurs) 1

1.2 Liste cha

ˆın´ee

Des structures sp

´ecifiques permettent l"organisation de grande quantiti´es de donn´ees.

La structure appell

´eeliste chaˆın´ee(linked list) est un ensemble d"´el´ements conserv´es chacun dans un noeud

(fr) qui contient aussi un ou deux liens sur le noeud suivant et/ou pr ´ec´edent dans la liste. Chaque´el´ement de la liste est stock ´e comme un noeud form´e par le paire(info;prochain), ou, dans le cas d"une listedoublement cha

ˆın´ee, par le triple(info;prochain;precedent). Dans uneliste circulaire, on aqueue:prochain=t^ete

et/out^ete:precedent=queue.

En Java, on peut implanter une liste cha

ˆın´ee`a l"aide d"une classe pour repr´esenter les noeuds (ListeChainee.Noeud).

La liste est sp

´ecifi´ee par la tˆete de la liste (de typeNoeud).public class ListeChainee private static class Noeud private Object info; private Noeud prochain; // prochain

´el´ement

private Noeud(Object info) // cr

´eation d"un nouveau noeud sans successeur

this.info=info; this.prochain=null; private Noeud tete; public boolean isEmpty(){ return tete==null;} // si liste vide

1.3 Insertion et suppression

AFGF1234

insérer tête(null)AFGFtêteXInsertion se fait par l"affectation de deux r

´ef´erences.

public void insertFirst(Object e) { // insertion `a la tˆete

Noeud N = new Node(e);

N.prochain=tete;

tete = N; private void insert(Noeud P, Object e) { // insertion apr `es P

Noeud N = new Node(e);

N.prochain = P.prochain;

P.prochain = N;

2 supprimer AFGFtêteXAFGFXSuppression se fait par l"affectation d"une seule r

´ef´erence.

public void deleteFirst() { // suppression de la t

ˆete

if (tete==null) throw new NoSuchElementException(); tete = tete.prochain; private void delete(Noeud P)quotesdbs_dbs3.pdfusesText_6