2 Listes

JAVA for Beginners

Java programming There are a number of IDEs present, all of them are fine but perhaps some are easier to work with than others It depends on the users level of programming and tastes The following is a list of some of the IDEs available: BlueJ – www bluej (freeware) NetBeans – www netbeans (freeware/open-source)

Introduction to Programming Using Java

Introduction to Programming Using Java Version 5 0, December 2006 (Version 5 0 2, with minor corrections, November 2007) David J Eck Hobart and William Smith Colleges

Java Cheat Sheet - Programming with Mosh

• Java Micro Edition (ME): a subset of Java SE, designed for mobile devices It also has libraries specific to mobile devices • Java Card: used in smart cards How Java Code Gets Executed The Java compiler takes Java code and compiles it down to Java Bytecode which is a cross-platform format When we run Java applications, Java Virtual Machine

OnBot Java Guide - FIRST

The FTC OnBot Java Programming Tool is a text-based programming tool that lets programmers use a web browser to create, edit and save their Java op modes This tool is recommended for programmers who have basic to advanced Java skills and who would like to write text-based op modes

2 Listes - IFT2015

IFT2015 Mikl os Csur } os 14 septembre 2016 2 Listes 2 1 Types Deﬁnition 2 1 ´ Un type est un ensemble (possiblement inﬁni) de valeurs et d’operations sur celles-ci ´ En Java :

STRUCTURES RECURSIVES ´ : LISTES ET ARBRES

Speciﬁcation de l’API Java d´ eﬁnit l’interface pour´ java util LinkedList, supportee par une liste doublement cha´ ˆınee :´ package java util; public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java io Serializable; openjdk :LinkedList java

LISTE CHAÎNÉE - WordPresscom

Spéciﬁcation de l’API Java déﬁnit l’interface pour java util LinkedList, supportée par une liste doublement chaînée : package java util; public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java io Serializable; source java util LinkedList : classe imbriquée pour les nœuds

Programmer’s Guide

Design and UML Class Diagrams - University of Washington

Design phase • design: specifying the structure of how a software system will be written and function, without actually writing the complete implementation • a transition from "what" the system must do, to

[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

IFT2015Miklos Cs}uros 14 septembre 2016

2.1 Types

´efinition 2.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. D ´efinition 2.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

´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

2.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;next), ou, dans le cas d"une listedoublement chaˆın´ee,

par le triple(info;next;previous). Dans uneliste circulaire, on atail:next=headet/ouhead:previous= tail.

2.3 Liste cha

ˆın´ee comme structure recursive

La liste (simplement) cha

ˆın´ee est une structure r´ecursive. Une liste chaˆın´ee est construite par l"application

des r `egles suivantes. hlistei !null(liste vide) hlistei !hnoeudi;hlistei(liste commence parhnoeudi)

Dans d"autres mots, une liste cha

ˆın´ee est soit une r´ef´erence null, soit une paire d"un noeud (sa tˆete) et d"une

liste.

2.4 Implantation avec classe imbriqu

´ee

En Java, on peut implanter une liste cha

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

La liste est sp

´ecifi´ee par la tˆete de la liste (de typeNode).public class LinkedList private static class Node private Object info; private Node next; // prochain element private Node(Object info) // creation d'un nouveau noeud sans successeur this.info=info; this.next=null; private Node head=null; // t^ete de la liste; liste vide au debut public boolean isEmpty(){ return head==null;} // si liste vide 2

2.5 Insertion et suppressionsupprimer

AFGFtêteXAFGFXAFGF1234

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

Node N = new Node(e);

N.next=head;

head = N; private void insertAfter(Node P, Object e) { // insertion apres P

Node N = new Node(e);

N.next = P.next;

P.next = N;

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

´ef´erence.public void deleteFirst()

{ // suppression de la t^ete if (head==null) throw new NoSuchElementException(); head = head.next; private void deleteAfter(Node P) { // suppression apres P if (P.next==null) throw new NoSuchElementException();

P.next=P.next.next;

2.6 Parcours

Le parcours se fait par une boucle ou par r

´ecursion.private Node Kth(int pos) // iteration { // trouve l'element en position pos

Node N = head;

while (N != null && pos>0)

N = N.next;

pos--; return N; }private Node Kth(int pos){ return Kth(head, pos);} private Node Kth(Node N, int pos) // recurrence { // trouve l'element en position pos apres noeud N if (pos==0 || N==null) return N; else return Kth(N.next, pos-1); 3 (en)

Recherche s´equentielle.On peut utiliser une liste chaˆın´ee pour implanter beaucoup de types diff´erents.

Par exemple, pour implanter le TA dictionnaire, on peut utiliser des noeuds avec champs(key;info;next).SEARCH(x)//recherche d"un´el´ement avec cl´exsur une liste non-tri´ee

S1N head//(parcours doit commencer`a la tˆete)

S2whileN6=null//(fin de la liste d´enot´ee parnull) S3ifN:key=xthen returnN:info/(recherche fructueuse)

S4N N:next

S5returnnull//(recherche infructueuse)Th

´eor`eme 2.1.Pour un dictionnaire implant´e par une liste chaˆın´ee, la recherche infructueuse prend un temps lin´eaire

(dans le nombre d"

´el´ements).

Curseurs.Pour pouvoir manipuler la liste lors du parcours, il est n´ecessaire de maintenir une r´ef´erence au

noeud pr

´ec´edent. Le code suivant maintient les entr´ees dans le dictionnaire selon l"ordre de cl´es.ADD(k;x)//ajout d"un paire(k;x)dans une liste tri´ee selon les cl´es

I1N head//(parcours doit commencer`a la tˆete)

I2P null(Pstocke le noeud pr´ec´edent)

I3whileN6=nulletN:key< kdo//(parcours de la liste)

I4P N;N N:next

I5ifP=nulltheninsertFirsthk;xi

I6elseinsertAfterP;hk;xi2.7 Sentinelles

On peut utiliser une sentinelle pour d

´enoter la tˆete et/ou la queue.(en)

´efinition 2.3.Unesentinelleest un´el´ement"factice»dans une structure de donn´ees.private Node HEAD_SENTINEL = new Node(null); // on ne stocke aucune info ici

private head = HEAD_SENTINEL; // ne changera jamais public void deleteFirst() { // suppression a la t^ete deleteAfter(head); public void insertFirst(Object e) { // insertion a la t^ete insertAfter(head, e); public boolean isEmpty(){ return head.next==null;} // si liste vide

Avantage : code plus clair, ex

´ecution un peu plus rapide (mais pas en asymptotique) D ´esavantage : un noeud de plus!nlistes de longueur totale`n´ecessitentn+`noeuds au lieu de` 4quotesdbs_dbs3.pdfusesText_6

[PDF] 2 Listes - IFT2015

IFT2015Miklos Cs}uros 14 septembre 2016

2 Listes

2.1 Types

En Java :

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

Notions.

En Java.

2.2 Liste cha

ˆın´ee

Des structures sp

La structure appell

2.3 Liste cha

ˆın´ee comme structure recursive

La liste (simplement) cha

Dans d"autres mots, une liste cha

2.4 Implantation avec classe imbriqu

´ee

En Java, on peut implanter une liste cha

La liste est sp

2.5 Insertion et suppressionsupprimer

AFGFtêteXAFGFXAFGF1234

Node N = new Node(e);

N.next=head;

Node N = new Node(e);

N.next = P.next;

P.next = N;

´ef´erence.public void deleteFirst()

P.next=P.next.next;

2.6 Parcours

Le parcours se fait par une boucle ou par r

Node N = head;

N = N.next;

S1N head//(parcours doit commencer`a la tˆete)

S4N N:next

S5returnnull//(recherche infructueuse)Th

´el´ements).

I1N head//(parcours doit commencer`a la tˆete)

I2P null(Pstocke le noeud pr´ec´edent)

I4P N;N N:next

I5ifP=nulltheninsertFirsthk;xi

I6elseinsertAfterP;hk;xi2.7 Sentinelles

On peut utiliser une sentinelle pour d

´enoter la tˆete et/ou la queue.(en)

Avantage : code plus clair, ex