[PDF] [PDF] Cours 1: Listes - IGM

[PDF] Cours 1: Eléments de Java, Listes - LIX-polytechnique

En Java, toutes les variables sont déclarées et typées String a; float z; Liste lst; Pour une liste vide: lst vaut null Pour une liste non vide: ▻ lst contenu est le 

[PDF] Listes chaînées

En considérant que la liste la plus simple est la liste vide (notée [ ]), qui ne contient aucun Il y a plusieurs façons de représenter les listes chaînées en Java

[PDF] Java : les collections

G List Java List ArrayList LinkedList Vector H H: Research and Training 6 / 50 isEmpty() : retourne true si la liste est vide, false sinon contains(object) 

[PDF] TD Listes - Formations en Informatique de Lille

et en particulier du langage JAVA, cette correction1 est découpée en Liste Vide "Une chaine" (b) Liste chainée à un élément, de type String, ayant pour

[PDF] LISTES

En Java, la valeur d'une variable de type agrégé est une référence Une référence Implantation en Java LISTES ⋆ IFT2015 H2007 tete = -1; // liste vide

[PDF] Collections en Java - Département dinformatique et de recherche

List: hérite aussi de collection, mais autorise la duplication Dans cette vérifier si la collection est vide et finalement d'effacer le contenu de la collection

[PDF] Collections : listes - CS-108

vide – int size() : retourne le nombre d'éléments contenus dans la collection – boolean Le concept de liste est représenté dans l'API Java par l'interface List 

[PDF] La classe ArrayList - myplatform

La liste des références des Comme ce type de probl`eme est récurrent en informatique, java, comme la plupart des permet de savoir si une liste est vide

[PDF] • Listes chaînées • Piles - IRIF

Listes chaînées Une liste chaînée est une suite de couples formés Créer une liste vide et tester si une liste est vide – Afficher une Listes chaînées en Java

[PDF] Cours 1: Listes - IGM

Java) pour présenter les exemples ou les signatures de fonctions Néanmoins Une liste de T est, soit la liste vide, soit composée d'une tête de liste de type T 

[PDF] cours php pdf complet

[PDF] parcours 3éme année du cycle secondaire collégial

[PDF] référentiel parcours avenir

[PDF] contraintes du parcours avenir

[PDF] parcours avenir folios

[PDF] les grandes phases de la seconde guerre mondiale

[PDF] guerre des tranchées 14-18

[PDF] epi parcours avenir stage

[PDF] l'immigration irlandaise aux etats unis

[PDF] immigration aux etats unis au 20eme siecle

[PDF] intégration irlandaise aux etats unis

[PDF] immigration aux etats unis d'amérique

[PDF] célébrité immigré aux usa

[PDF] les héros de l'iliade résumé

[PDF] iliade personnages

Cours 1: Listes

Marie-Pierre Beal

Universite Paris-Est Marne-la-Vallee

Plan

1Denition2Operations sur les listes3Choix d'une implementationImplementation par tables

Implementation par pointeurs

Implementation par curseurs

4Piles5Files d'attente

Preambule

Nous utiliserons une syntaxe semblable a celle de C (ou parfois Java) pour presenter les exemples ou les signatures de fonctions.

Neanmoins, le contenu de ce cours n'est pas propre a C.Les types generiques seront beaucoup utilises.

Denitions

Denition 1 : (Structure)

La liste est unestructure de donneepermettant de stocker des collections d'objets (en general de m^eme type).SoitTun type quelconque.Denition 2 (Recursive) Une liste deTest, soit laliste vide, soit composee d'unet^ete de liste de typeTavec unequeue de liste, de type liste deT.Denition 3 (sequentielle) Une liste deTest une suite d'elements de typeT, ainsi qu'un pointeur vers un element distingue, l'element courant. Cet element courant a un successeur.

Denitions

Denition 1 : (Structure)

La liste est unestructure de donneepermettant de stocker des collections d'objets (en general de m^eme type).SoitTun type quelconque.Denition 2 (Recursive) Une liste deTest, soit laliste vide, soit composee d'unet^ete de liste de typeTavec unequeue de liste, de type liste deT.Denition 3 (sequentielle) Une liste deTest une suite d'elements de typeT, ainsi qu'un pointeur vers un element distingue, l'element courant. Cet element courant a un successeur.

Denitions

Denition 1 : (Structure)

La liste est unestructure de donneepermettant de stocker des collections d'objets (en general de m^eme type).SoitTun type quelconque.Denition 2 (Recursive) Une liste deTest, soit laliste vide, soit composee d'unet^ete de liste de typeTavec unequeue de liste, de type liste deT.Denition 3 (sequentielle) Une liste deTest une suite d'elements de typeT, ainsi qu'un pointeur vers un element distingue, l'element courant. Cet element courant a un successeur.

Denitions suite

Denition 4 (Type abstrait)

Ensemble de suite nies d'elementsEd'un m^eme type

E =f(e1;e2;:::;en)jei2Eg longueur((e1;e2;:::;en) =n liste vide = () =" position(ei) dans (e1;e2;:::;en) =i

acces sequentielp: place ou adresse deeiSucc(p) = adresse deei+1si elle existeTete(L) = adresse dee1si elle existeFin(L) = adresse du dernier element si il existe

Operations de base

Listevide:!ListeTete: Liste!AdresseFin: Liste!AdresseCons: ElementListe!ListePremier: Liste!ElementElem: Adresse!ElementSucc: Adresse!Adresse

Implementation par tableaux, pointeurs, curseurs.

Operations

Concatenation :Produit: ListeListe!Liste

(e1;;en)(f1;;fm) = (e1;;en;f1;;fm).Modications :

Ajouter: ElementAdresseListe!Liste

ajoutereapres l'element d'adressepSupprimer: AdresseListe!ListeElement: ElementListe!Booleen

Exemple

SuppimeDoublons(ListeL) : Liste

1 // Supprime deLles copies d'elements

2p Tete(L)

3while(pest deni)

4doq p

5while(Succ(q;L) est deni)

6do

7ifElem(p) =Elem(Succ(q;L))

8thenEnlever(Succ(q;L))

9elseq Succ(q;L)

10p Succ(p;L)

11returnL//ici en tempsO(L2)

Choix d'une implementation

1Probleme faisant intervenir une ou des listes : modelisation2Operations elementaires sur les listes : critere de realisation

(simplicite, rapidite, etc)3Implementation des listes

Implementation par tables

L= (e1;e2;:::;en)0e

11e 22e
3i1e in1e nn

Implementation par tables

L= (e1;e2;:::;en)

Positions explicitesAdresse(ei) =i1.Succ(p) =p+ 1 pour 1pn1Longueur(L) =n

Avantage : simplicite

Inconvenients : operations de modication lentes, concatenation lente

Implementation par tables

typedef struct { int longueur;

Element table[MAX];

} Liste;

Ajouter(ListeL, Adressep, Elemente) : Liste

1ifL:longueur=MAX

2thenerreur("operation impossible")

3ifp<1 oupL:longueur

4thenerreur("operation impossible")

5forq L:longueur1top+ 1

6doL:table[q+ 1] L:table[q]

7L:table[p+ 1] e

8L:longueur L:longueur+ 1

9returnL

Implementation par pointeurs

Les adresses sont les adresses en memoire

Successeur explicite

Lest parfois identie aTete(L)

Avantage : nombreuses operations rapides, acces a l'espace memoire, souplesse Inconvenients : pas d'acces direct, gourmand en memoire, temps ralenti

Implementation par pointeurs

typedef int

Element;

typedef struct cellule{

Element elem;

struct cellule* succ; } Cellule; typedef Cellule* Liste;

Liste cons(Liste lst, Element elem){

Liste p = (Liste) malloc(sizeof(Cellule));

if (p == NULL) return NULL; p->elem = elem; p->succ = lst; return p;

Implementation par pointeurs

int ajouter(Liste lst, Liste p, Element elem) {

Liste temp= cons(lst, elem);

if (temp == NULL) return 0; if (p == NULL) return 0; temp -> succ = p -> succ; p -> succ = temp; temp -> elem = elem; return 1;

Implementation par pointeurs

Transfert d'une cellule d'une liste lst2 a une autre lst1inttransfert(Liste lst1, Liste lst2, Liste p, Liste q) {

if ((p == NULL) || (q == NULL)) return 0;

Liste temp = q -> succ;

temp-> succ = p -> succ; p -> succ = temp; q -> succ = temp -> succ; return 1; temps constant avec implementation par pointeurs

Implementation par curseurs

L= (e1;e2;:::;en)elemsucc

0e 22
1 2e 312
3 4

Fin!5e

n16 7 L!8e 10 MAX

Avantage : gestion directe des adresses

Inconvenient : choix de MAX

Implementation par curseurs

typedef struct cellule{

Element elem;

int succ; } Cellule; typedef int

Liste;

Cellule table[MAX];

Ajouter(ListeL, Adressep, Elemente) : Liste

1temp indice d'une case libre de la table

2table[temp]:elem e

3table[temp]:succ table[p]:succ

4table[p]:succ temp

5returnL(temps constant)

Question : Comment trouver ecacement une case libre?

Implementation par curseurs

Liste : L

Liste des cellules disponibles : Libre

Ajouter(ListeL, Adressep, Elemente) : Liste

quotesdbs_dbs3.pdfusesText_6