1

Structuri de Date în Java (IV)

● Vectori în Java: excepţii, clonare● Colecţii: adăugare, ştergere, numărare, fuzionare,

clonare● Liste înlănţuite: creare, modificare noduri,

ştergere, duplicare● Liste dublu înlănţuite● Comparaţie de performanţe între liste şi vectori

2

Vectori Java● clase colecţii – stochează obiecte de acelaşi fel● un vector – secvenţă cu un anumit număr de componente

7 22 19 56

[0] [1] [2] [3]

int[] scores;// scores este tot o// variabilă referinţă!// ce valoare are scores?// se alocă un array cu 4// componente întregiscores = new int [4];scores.length; // 4

scores

[0] [1] [2] [3]

3

Excepţii folosite de vectori

● NullPointerException – variabilă vector nealocată (null)● ArrayIndexOutOfBounds – de exemplu acces la scores[-1]

int[] scores;int[] exams;scores = new int [4];System.out.println (scores.length);scores[0] = 7;scores[1] = 22;scores[2] = 19;scores[3] = 56;exams = scores;

scores

7 22 19 56

[0] [1] [2] [3]exams

4

Clonarea vectorilor

● Realizează o copie perfectă fără a afecta originalul● Toate obiectele Java au această metodă clone()● Metoda clone() întoarce întotdeauna o referinţă la Object

int[] scores;int[] exams;scores = new int [4];scores[0] = 7;scores[1] = 22;scores[2] = 19;scores[3] = 56;exams = (int[]) scores.clone ();

// necesită conversie explicită!

scores

7 22 19 56

[0] [1] [2] [3]

exams

7 22 19 56

[0] [1] [2] [3]

5

Teste cu vectori

// test 1: care este cel mai mic respectiv cel mai mare index permis ?int[] b = new int[42];

// test 2: ce se afişează?int[] a, b;a = new int [10];a[5] = 1;b = a;a[5] = 42;System.out.println (b[5]);

// test 3: idemint[] a, b;a = new int [10];a[5] = 2;b = (int[]) a.clone ();a[5] = 42;System.out.println (b[5]);

6

Implementarea unei colecţii

● Colecţia de întregi trebuie să permită:● stocarea întregilor într-un vector● adăugarea unui element● ştergerea unui element anume● aflarea numărului total de elemente● determinarea numărului de elemente egale cu

un element dat● fuzionarea cu altă colecţie

7

Definirea clasei

// clasa va implementa interfata Cloneable pentru a suporta duplicareapublic class IntArrayBag implements Cloneable {

// aici stocăm întregiiprivate int[] data;

// câţi întregi sunt în colecţie (spaţiul disponibil e păstrat în ... ?)private int manyIems;

// metodele publice pe care vom expune pe slide-urile următoare// ...

}

8

Constructorii

public IntArrayBag (int initialCapacity) {if (initialCapacity < 0)

throw new IllegalArgumentException (“initial capacity < 0”);manyItems = 0;data = new int [initialCapacity];

}

public IntArrayBag (void) { // constructorii au grijă să punămanyItems = 0; // ceva valid în variabileledata = new int [6]; // membre

}

9

ensureCapacitypublic void ensureCapacity (int minumumCapacity) {

int biggerArray [];if (data.length < minimumCapacity) {

biggerArray = new int [minimumCapacity];System.arraycopy (data, 0, biggerArray, 0, manyItems);data = biggerArray;

}

2 7 9 3

[0] [1] [2] [3] [4] [5]

manyItems 4

data

biggerArray 2 7 9 3

[0] [1] [2] [3] [4] [5] [6] [7]

10

Adăugarea

public void add (int element){

if (manyItems == data.length){

// dublează capacitatea şi adaugă un element// dacă manyItems * 2 + 1 > Integer.MAX_VALUE, va apare// o depăşire aritmetică şi operaţia eşueazăensureCapacity (manyItems * 2 + 1);

}

data[manyItems] = element;manyItems ++;

}

// de exemplux.add (7);

3 5 9 8

[0] [1] [2] [3]

7

[4] [5]

data

manyItems 45

11

Ştergerea

public boolean remove (int target) {// caută locaţia elementului în array; dacă nu este găsit, întoarce manyItemsindex = 0;while (index <= manyItems && target != data[index] )

index ++;

if (index != manyItems) {// s-a găsit elementul data[index]manyItems --;data[index] = data[manyItems];return true;

}// nu s-a găsit un element targetreturn false;

}3 5 9 8

[0] [1] [2] [3]

7

[4] [5]

data

manyItems 5

7

4

12

Numărarea duplicatelor

public int countOccurences (int target) {int answer;int index;

answer = 0;for (index = 0 ; index < manyItems ; index ++)

if (target == data[index])answer ++;

return answer;}

13

Fuzionarea cu altă colecţiepublic void addAll (IntArrayBag vec) {

// dacă vec este null, se aruncă o excepţie// de tip NullPointerExceptionensureCapacity (manyItems + vec.manyItems);

System.arraycopy (vec.data, 0, data, manyItems, vec.manyItems);

manyItems += vec.manyItems;}

de unde unde câte elemente

14

Un alt mod de fuzionare

public static IntArrayBag add (IntArrayBag b1, IntArrayBag b2){

// dacă b1 sau b2 sunt null, se aruncă o excepţieint t = b1.getCapacity () + b2.getCapacity ();IntArrayBag answer = new IntArrayBag (t);answer.manyItems = b1.manyItems + b2.manyItems;

System.arraycopy (b1.data, 0, answer.data, 0, b1.manyItems);System.arraycopy ( // destinaţie, sursă, număr

b2.data, 0, answer.data, b1.manyItems, b2.manyItems);

return answer;}

15

Clonarea

public Object clone () {IntArrayBag answer;

try { // clonăm obiectul bit cu bitanswer = (IntArrayBag) super.clone ();

} catch (CloneNotSupportedException e) {throw new RuntimeException (“forgot to implement Cloneable”);

}

// în noul obiect avem aceeaşi referinţă; trebuie să clonăm şi array-ul!// dacă nu o facem, vom avea array-ul comun în cele două obiecteanswer.data = (int []) data.clone ();

return answer;}

16

Efecte colaterale ale clonării

2 7 9 3

[0] [1] [2] [3] [4] [5]

manyItems 4

2 7 9 3

[0] [1] [2] [3] [4] [5]

manyItems 4

answer.data

data

data

● obiectul iniţial

● după clonare

answer.manyItems 4

`

17

Teste cu IntArrayBag// test 1: cum va arăta colecţia?IntArrayBag bag = new IntArrayBag (10);bag.add (1);bag.add (2);bag.add (3);bag.remove (1);

// test 2// ce se întâmplă dacă, adăugînd elemente,// depăşim cele 10 locaţii prealocate ?

// test 3// cum se scrie folosind System.arraycopy copierea// a 10 elemente de la începutul array-ului x în// array-ul y, începînd de pe poziţia a 5-a ?

18

Liste înlănţuite● Folosită la stocarea ordonată a elementelor● Fiecare element este conectat de elementul următor printr-o legătură (link)● Lista se poate parcurge doar mergînd din element în element● Fiecare nod este alcătuit dintr-o pereche (<valoare>, <legătura spre elementul următor>)

12 -414 10 •

19

Clasa IntNode

● Abstractizează lucrul cu noduri ale liste● Oferă suport pentru:

● crearea nodurilor● modificarea valorii unui nod● adăugarea sau ştergerea unui nod din listă● numărarea nodurilor din listă● căutarea unui nod după valoare● duplicarea listelor

20

Clasa IntNode

public class IntNode {private int data; // valoareprivate IntNode link; // legatura spre nodul următor

// ...}

// lista se păstrează prin memorarea referinţelor către// primul element, denumit head şi ultimul, denumit tailIntNode head;IntNode tail;

12 -414 10 •

head tail

referinţa null

21

Constructorul clasei

// se inţializează variabilele membrepublic IntNode (int val, IntNode lk) {

data = val;link = lk;

}

// de exemplu, aşa ar putea arăta crearea primului nod al listeiIntNode head = new IntNode (42, null);

42 •head

22

Metode acces şi modificare a stării

public int getData () {return data;

}

public IntNode getLink () {return link;

}

public void setData (int val) {data = val;

}

public void setLink (IntNode lk) {link = lk;

}

23

Adăugarea la începutul listei

head = new IntNode (5, head);

● Funcţionează şi dacă iniţial se porneşte cu lista vidă (head == null)

12 -414 10 •

head 5

24

Stergerea primului nodhead = head.getLink ();

● referinţa către (fostul) primul nod se nu se mai păstrează nicăieri● sistemul recunoaşte acest lucru şi va recupera spaţiul (garbage collector)

12 -414 10 •

head

25

Adăugarea unui nod dar nu la început

public void addNodeAfter (int val) {link = new IntNode (val, link);

}

12 -414 10 •

head

nod curent

3

26

Ştergerea unui nod care nu este la început

public void removeNodeAfter() {link = link.link;

} // ce se întâmplă dacă// link este null?

12 -414 10 •

head nod curent

27

Determinarea lungimii listei

public static int listLength (IntNode head) {IntNode cursor;int answer;

answer = 0;for (cursor = head ; cursor != null ; cursor = cursor.link )

answer ++;

return answer;}

28

Căutarea în listă a unui element de o valoare anume

public static IntNode listSearch (IntNode head, int target) {IntNode cursor;

for (cursor = head ; cursor != null ; cursor = cursor.link)if (target == cursor.data)

return cursor;

return null;}

29

Căutarea în listă a unui nod de pe o poziţie dată

public static IntNode listPosition (IntNode head, int position) {IntNode cursor;int i;if (position <= 0)

return null;

cursor = head;for (i = 1 ; i < position && cursor != null ; i ++)

cursor = cursor.link;

return cursor;}

30

Copierea unei liste

public static IntNode listCopy (IntNode source) {IntNode copyHead, copyTail;

// crearea primului nodcopyHead = new IntNode (source.data, null);copyTail = copyHead;

// copierea restului listeiwhile (source.link != null) {

source = source.link;copyTail.addNodeAfter (source.data);copyTail = copyTail.link;

} // se poate utiliza clonarea// pentru duplicarea listei?

return copyHead;}

31

Liste dublu înlănţuite

public class DoubleLinkedList {private int data;private DoubleLinkedNode back;private DoubleLinkedNode next;// ...

}

12 -4 10 •

head tail

•

32

Comparaţie a performanţelor

● dacă elementele sunt accesate la întâmplare, array-ul este mai rapid

● dacă elementele sunt accesate unul după altul, 'la rând', este mai avantajoasă o listă înlănţuită, mai ales pentru inserări la urmă

● redimensionarea este ineficientă pentru array; la o listă, se adaugă un element nou la coadă

● pentru deplasarea în ambele direcţii, folosim o listă dublu-înlănţuită